Cách xây dựng ngôn ngữ WebAssembly để thú vị và lợi nhuận: Phân tích cú pháp

bên trong bài cuối cùng trong loạt bài này về cách xây dựng ngôn ngữ lập trình WebAssembly, chúng tôi đã xây dựng một lexer. Trong bài đăng này, chúng tôi sẽ đề cập đến giai đoạn tiếp theo của trình biên dịch, phân tích cú pháp. Phân tích cú pháp là một phần của trình biên dịch của chúng tôi lấy dòng mã thông báo được tạo bởi lexer và chuyển đổi nó thành cây cú pháp trừu tượng (AST).

AST là một cấu trúc dữ liệu dạng cây tổ chức các mã thông báo thành một hệ thống phân cấp hợp lý để có thể dễ dàng dịch sang mã máy hơn. Rất may, bởi vì wispy là một ngôn ngữ biểu thức S, mã của chúng tôi về cơ bản đã là một AST. Lấy dòng mã thông báo sau:

 “(“, “add”, “3”, “(“, “sub”, “2”, “1”, “)”, “)”

Mỗi tập hợp các dấu ngoặc đơn đại diện cho một cây con, trong đó mã thông báo đầu tiên là nút toán tử và các mã thông báo sau là toán hạng của nó. Nếu chúng ta gặp phải một dấu ngoặc mở khác trước khi tập hợp hiện tại bị đóng, chúng ta biết nó đại diện cho một toán hạng mà bản thân nó là một cây con. Dòng mã thông báo ở trên sẽ được tổ chức thành một cây giống như sau:

Nếu bạn quan tâm đến việc viết trình phân tích cú pháp cho cú pháp giống C phức tạp hơn, hãy xem phần trước của tôi Xây dựng một ngôn ngữ lập trình loạt.

Thông tin thêm về AST

Như chúng ta đã làm với lexer, chúng ta sẽ bắt đầu bằng cách xác định các loại của chúng ta. Những loại này sẽ xác định cấu trúc của AST của chúng tôi. Mỗi loại đại diện cho một “Nút”, vòng tròn từ sơ đồ của chúng tôi trong phần giới thiệu. Đây là các nút cơ bản. Chúng tôi sẽ đánh bóng chúng, vì chúng không khác nhiều so với các mã thông báo mà chúng tôi đã xác định trong lexer:

 // src/types/ast.mts export type IntNode = { type: "int"; value: number; }; export type FloatNode = { type: "float"; value: number; }; export type IdentifierNode = { type: "identifier"; identifier: string; }; export type TypedIdentifierNode = { type: "typed-identifier"; // Note that here, we break down the identifier into its components identifier: string; typeIdentifier: string; };

Một khái niệm mới đối với AST là BlockNode . BlockNode là một biểu thức được tạo thành từ một nhóm các nút khác.

Ví dụ: (add 1 2) là một khối gồm ba nút:

1. Một mã định danh đánh giá một chức năng, hãy add .
2. Int chỉ đơn giản là đánh giá số 1 .
3. Int chỉ đơn giản là đánh giá số 2 .

Việc khối được đánh giá như thế nào là tùy thuộc vào trình biên dịch. Chúng tôi sẽ nói về điều đó trong bài tiếp theo.

Đây là định nghĩa:

 // src/types/ast.mts export type BlockNode = { type: "block"; expressions: AstNode[]; };

Cuối cùng, chúng tôi xác định AstNode . Giống như loại Token thông báo từ lexer, AstNode là một liên hợp phân biệt có thể là một trong bất kỳ nút nào khác mà chúng tôi đã xác định trước đây:

 export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode;

Bạn có thể nhận thấy rằng BlockNode có một mảng các AstNode , Vì AstNode có thể là một BlockNode , nên các BlockNode có thể chứa các BlockNodes con. Nói cách khác, BlockNode là một kiểu đệ quy. Khả năng biểu diễn đệ quy những đứa trẻ có thể có con là nền tảng của AST của chúng tôi. Đó là nơi cây trong AST được phép hình thành.

Tại thời điểm này, src/types/ast.mts đã hoàn thành và trông giống như tập tin này .

Bây giờ xuất các loại từ src/types/index.mts như chúng ta đã làm với các loại mã thông báo:

 // src/types/index.mts export * from "./token.mjs"; export * from "./ast.mjs";

Xây dựng AST

Bây giờ chúng ta đã xác định AST, đã đến lúc xây dựng một AST.

Tạo một tệp src/parser.mts mới và thêm tất cả các mục nhập mà chúng tôi sẽ sử dụng:

 // src/parser.mts import { Token, IdentifierNode, TypedIdentifierNode, IdentifierToken, TypedIdentifierToken, FloatToken, FloatNode, IntToken, IntNode, AstNode, BlockNode, } from "./types/index.mjs";

Bây giờ chúng ta có thể xác định hàm phân tích cú pháp cấp cao nhất của mình. Hàm phân tích cú pháp nhận các mã thông báo được tạo bởi lexer và trả về một BlockNode hoạt động như gốc cây của chúng ta.

 // src/parser.mts export const parse = (tokens: Token[]): BlockNode => { const blocks: BlockNode[] = []; // This loop is run as long as there are tokens to consume while (tokens.length) { // consumeTokenTree converts an array of tokens into a tree of tokens, more on that later. const tree = consumeTokenTree(tokens); // parseBlock turns our new tree of tokens into an actual BlockNode, recursively. More on that later as well. blocks.push(parseBlock(tree)); } // Finally we return the top level BlockNode return { type: "block", expressions: blocks, }; };

Tiếp theo, chúng ta xác định hàm consumeTokenTree . consumeTokenTree chuyển đổi một mảng phẳng các mã thông báo, thành một cây mã thông báo.

Với biểu thức phức tạp này:

 (add (sub 3 1) (sub 5 2))

Lexer sẽ tạo ra một loạt các mã thông báo:

 // Note: I've simplified the Token format to just be strings to keep things short ["(", "add", "(", "sub", "3", "1", ")", "(", "sub", "5", "2", ")", ")"];

consumeTokenTree sẽ lấy mảng phẳng đó và biến nó thành một cái cây. Điều này đơn giản như việc đặt mọi mã thông báo vào giữa một tập hợp các mã thông báo trong ngoặc vuông () vào một mảng. Vì vậy, mảng mã thông báo của chúng tôi từ phía trên trở thành cây mã thông báo này:

 ["add", [, "sub", "3", "1"], ["sub", "5", "2"]];

Đây là định nghĩa thực tế của consumeTokenTree :

 // src/parser.mts // This is token besides for the bracket tokens export type NonBracketToken = Exclude<Token, "parenthesis" | "square-bracket">; // The token tree is made of NonBracketTokens and other TokenTrees export type TokenTree = (NonBracketToken | TokenTree)[]; const consumeTokenTree = (tokens: Token[]): TokenTree => { const tree: TokenTree = []; // Ensures the first token is a left bracket and then discards it, defined below this function. consumeLeftBracket(tokens); while (tokens.length) { // Preview the next token const token = tokens[0]; // Check to see if the next token is a left bracket. if (token.type === "bracket" && getBracketDirection(token) === "left") { // If it is, we just ran into a sub-TokenTree. So we can simply call this function within // itself. Gotta love recursion. tree.push(consumeTokenTree(tokens)); continue; } // Check to see if the next token is a right bracket if (token.type === "bracket" && getBracketDirection(token) === "right") { // If it is, we just found the end of the tree on our current level tree.shift(); // Discard the right bracket break; // Break the loop } // If the token isn't a bracket, it can simply be added to the tree on this level tree.push(token); // Consume / discard the token from the main tokens array tokens.shift(); } // Return the tree. Don't forget to check out the helper functions below! return tree; }; const consumeLeftBracket = (tokens: Token[]) => { const bracketDirection = getBracketDirection(tokens[0]); if (bracketDirection !== "left") { throw new Error("Expected left bracket"); } return tokens.shift(); }; const getBracketDirection = (token: Token): "left" | "right" => { if (token.type !== "bracket") { throw new Error(`Expected bracket, got ${token.type}`); } // If we match a left bracket return left if (/[\(\[]/.test(token.value)) return "left"; // Otherwise return right return "right"; };

Bây giờ chúng ta có một cây mã thông báo, chúng ta cần biến nó thành một khối. Để làm như vậy, chúng ta tạo một hàm parseBlock lấy cây làm đầu vào và trả về BlockNode :

 1const parseBlock = (block?: TokenTree): BlockNode => { return { type: "block", // This is where the recursive magic happens expressions: block.map(parseExpression), }; };

Như bạn có thể đã nhận thấy, parseBlock ánh xạ từng mục của cây với một hàm parseExpression chưa được viết. parseExpression nhận TokenTree hoặc NonBracketToken và chuyển nó thành loại AstNode tương ứng.

Đây là định nghĩa:

 const parseExpression = (expression?: TokenTree | NonBracketToken): AstNode => { // If the expression is an Array, we were passed another TokenTree, so we can // pass the expression back to the parseBlock function if (expression instanceof Array) { return parseBlock(expression); } // The mapping here is pretty straight forward. Match the token type and pass the // expression on to a more specific expression parser. if (isTokenType(expression, "identifier")) return parseIdentifier(expression); if (isTokenType(expression, "typed-identifier")) return parseTypedIdentifier(expression); if (isTokenType(expression, "float")) return parseFloatToken(expression); if (isTokenType(expression, "int")) return parseIntToken(expression); throw new Error(`Unrecognized expression ${JSON.stringify(expression)}`); };

Hãy xác định hàm isTokenType . Chức năng này khá gọn gàng và thể hiện một trong những tính năng mạnh mẽ nhất của TypeScript, bảo vệ loại tùy chỉnh . Nói một cách đơn giản, isTokenType kiểm tra biểu thức và thu hẹp loại thành một TokenType cụ thể. Điều này cho phép TypeScript chắc chắn rằng chúng tôi đang chuyển các mã thông báo chính xác đến các chức năng phân tích cú pháp tương ứng của chúng.

Đây là định nghĩa:

 export const isTokenType = <T extends Token["type"]>( item: TokenTree | NonBracketToken | undefined, type: T ): item is Extract<Token, { type: T }> => { return isToken(item) && item.type === type; }; const isToken = (item?: TokenTree | NonBracketToken): item is NonBracketToken => { return !(item instanceof Array); };

Có rất nhiều điều xảy ra ở đó, vì vậy chúng ta hãy đi qua nó. Đầu tiên, chúng ta có một định nghĩa chung, <T extends Token["type"]> . Về cơ bản, điều này nói rằng T phải là một trong những giá trị có thể có của trường Token.type . Typecript đủ thông minh để biết điều đó có nghĩa là T phải là một trong "int" | "float" | "identifier" | "typed-identifier" | "bracket .

Đoạn mã thú vị tiếp theo là item is Extract<Token, { type: T }> . Vị từ này cho TypeScript biết rằng nếu giá trị trả về của isTokenType là true, thì item phải là Token thông báo có kiểu khớp với chuỗi được truyền dưới dạng tham số type .

Trong thực tế, điều đó có nghĩa là nếu chúng ta chuyển một Token thông báo không xác định cho isTokenType , thì typecript sẽ có thể thu hẹp chính xác giá trị thành một mã thông báo cụ thể hơn, như IntToken .

Bây giờ chúng ta đã xác định bộ bảo vệ kiểu tùy chỉnh của mình, chúng ta có thể xác định bộ phân tích cú pháp mã thông báo thực tế. Ba đầu tiên là đơn giản; về cơ bản họ chỉ trả lại một bản sao hoặc bản sao được sửa đổi một chút của mã thông báo:

 const parseFloatToken = (float: FloatToken): FloatNode => ({ ...float }); const parseIntToken = (int: IntToken): IntNode => ({ ...int }); const parseIdentifier = (identifier: IdentifierToken): IdentifierNode => { return { type: "identifier", identifier: identifier.value, }; };

Trình phân tích cú pháp cuối cùng là parseTypedIdentifier . Hãy nhớ rằng một số nhận dạng đã nhập sẽ lấy từ identifier:type . Phân tích cú pháp nó đơn giản như tách chuỗi bằng dấu hai chấm. Giá trị đầu tiên của mảng được trả về là identifier , giá trị thứ hai là type . Đây là định nghĩa:

 const parseTypedIdentifier = (identifier: TypedIdentifierToken): TypedIdentifierNode => { const vals = identifier.value.split(":"); return { type: "typed-identifier", identifier: vals[0], typeIdentifier: vals[1], }; };

Đây là tệp đã hoàn thành

Đó là tất cả mã cần thiết cho một trình phân tích cú pháp hoạt động. Trước khi tiếp tục, hãy cập nhật tệp src/index.mts chính để xem đầu ra của trình phân tích cú pháp:

 // src/index.mts #!/usr/bin/env node import { readFileSync } from "fs"; import { lex } from "./lexer.mjs"; import { parse } from "./parser.mjs"; const file = process.argv[2]; const input = readFileSync(file, "utf8"); const tokens = lex(input); const ast = parse(tokens); console.log(JSON.stringify(tokens, undefined, 2));

Xây dựng và chạy dự án:

 npx tsc wispy example.wispy

Nếu mọi việc suôn sẻ, đầu ra sẽ giống như đây .

Với điều đó, trình phân tích cú pháp đã hoàn thành. Giờ đây, chúng tôi có thể chuyển đổi luồng mã thông báo từ lexer thành AST. Trong bài đăng tiếp theo, chúng ta có thể đi sâu vào những điều thú vị: tạo và chạy mã có thể đọc được bằng máy.

Yêu cầu bản demo ngay hôm nay để xem Courier hoạt động như thế nào để tạo ra các thông báo về sản phẩm một cách thú vị!