bên trong  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  (AST).   bài cuối cùng   cây cú pháp trừu tượng  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  loạt.   Xây dựng một ngôn ngữ lập trình  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à   .   là một biểu thức được tạo thành từ một nhóm các nút khác. BlockNode BlockNode  Ví dụ:   là một khối gồm ba nút: (add 1 2)  Một mã định danh đánh giá một chức năng, hãy   . add  Int chỉ đơn giản là đánh giá số   . 1  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   . Giống như loại   thông báo từ lexer,   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: AstNode Token AstNode   export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode;  Bạn có thể nhận thấy rằng   có một mảng các   , Vì     một   , nên các   có thể chứa các   con. Nói cách khác,   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. BlockNode AstNode AstNode có thể là BlockNode BlockNode BlockNodes BlockNode  Tại thời điểm này,   đã hoàn thành và trông giống như  . src/types/ast.mts   tập tin này  Bây giờ xuất các loại từ   như chúng ta đã làm với các loại mã thông báo: src/types/index.mts   // 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   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   // 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   hoạt động như gốc cây của chúng ta. BlockNode   // 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   .   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. consumeTokenTree consumeTokenTree  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", ")", ")"];    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: consumeTokenTree ()   ["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   lấy cây làm đầu vào và trả về   : parseBlock 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,   ánh xạ từng mục của cây với một hàm   chưa được viết.   nhận   hoặc   và chuyển nó thành loại   tương ứng. parseBlock parseExpression parseExpression TokenTree NonBracketToken AstNode  Đâ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   . 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,  . Nói một cách đơn giản,   kiểm tra biểu thức và thu hẹp loại thành một   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. isTokenType   bảo vệ loại tùy chỉnh isTokenType TokenType  Đâ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,   . 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   . Typecript đủ thông minh để biết điều đó có nghĩa là T phải là một trong   . <T extends Token["type"]> Token.type "int" | "float" | "identifier" | "typed-identifier" | "bracket  Đoạn mã thú vị tiếp theo là   . Vị từ này cho TypeScript biết rằng nếu giá trị trả về của   là true, thì   phải là   thông báo có kiểu khớp với chuỗi được truyền dưới dạng tham số   . item is Extract<Token, { type: T }> isTokenType item Token type  Trong thực tế, điều đó có nghĩa là nếu chúng ta chuyển một   thông báo không xác định cho   , 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ư   . Token isTokenType 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à   . Hãy nhớ rằng một số nhận dạng đã nhập sẽ lấy từ   . 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à   , giá trị thứ hai là   . Đây là định nghĩa: parseTypedIdentifier identifier:type identifier type   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   chính để xem đầu ra của trình phân tích cú pháp: src/index.mts   // 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.    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ị! Yêu cầu bản demo

Lexer

Orchestrate Unlimited Notifications From 1 API | Sign-up today!

Courier simplifies triggering and sending notifications from your app with one API and drag and drop UI.


2021 - HackerNoon Contributor of the Year - SOFTWARE-ARCHITECTURE

2022 - HackerNoon Contributor of the Year - Business Strategy

2022 - HackerNoon Contributor of the Year - Digital Transformation

2022 - HackerNoon Contributor of the Year - Graphql

2022 - HackerNoon Contributor of the Year - Rest Api

2022 - HackerNoon Contributor of the Year - Software Architecture

2022 - Tech Ceo of the Year

2021 - HackerNoon Contributor of the Year - APP-DEVELOPMENT

Nominated for 2022 - HackerNoon Contributor of the Year - Rest Api

Nominated for 2022 - Tech Ceo of the Year

Nominated for 2022 - HackerNoon Contributor of the Year - Digital Transformation

Nominated for 2022 - HackerNoon Contributor of the Year - Graphql

Nominated for 2022 - HackerNoon Contributor of the Year - Business Strategy

Nominated for 2022 - HackerNoon Contributor of the Year - Software Architecture

Nghe bài viết này bằng Tiếng Anh, đọc bởi robot thông minh của HackerNoon

dài quá đọc không nổi

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

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

About Author

BÌNH LUẬN

chuyên mục

BÀI VIẾT NÀY CŨNG CÓ MẶT TẠI

Related Stories

581 Stories To Learn About Non Fiction

189 Stories To Learn About Reading Books

147 Stories To Learn About Reading Books Online

85 Stories To Learn About Travel

581 Stories To Learn About Non Fiction

189 Stories To Learn About Reading Books

147 Stories To Learn About Reading Books Online

85 Stories To Learn About Travel

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps