の中に WebAssembly プログラミング言語の作成方法に関するこのシリーズの 1 回目で、レクサーを作成しました。この投稿では、コンパイラの次のフェーズである解析について説明します。構文解析は、レクサーによって生成されたトークン ストリームを受け取り、それを （AST）。 最後の投稿 抽象構文木 AST は、機械コードに簡単に変換できる論理階層にトークンを編成するツリー状のデータ構造です。ありがたいことに、wispy は S 式言語であるため、コードは基本的に AST です。次のトークンのストリームを取得します。 既に “(“, “add”, “3”, “(“, “sub”, “2”, “1”, “)”, “)” 括弧の各セットはサブツリーを表し、最初のトークンは演算子ノードで、次のトークンはそのオペランドです。現在のセットが閉じられる前に別の開き括弧に遭遇した場合、それ自体がサブツリーであるオペランドを表していることがわかります。上記のトークンのストリームは、次のようなツリーに編成されます。 より複雑な C ライクな構文のパーサーを作成することに興味がある場合は、以前の記事を参照してください。 シリーズ。 プログラミング言語の構築 ASTについての詳細 レクサーで行ったように、型を定義することから始めます。これらの型は、AST の構造を定義します。各タイプは、イントロの図の円である「ノード」を表します。基本的なノードは次のとおりです。 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; }; AST の新しい概念は です。 は、他のノードのグループで構成される式です。 BlockNode BlockNode たとえば、 は 3 つのノードのブロックです。 (add 1 2) 関数 に評価される識別子。 add 単に数値 に評価される Int 。 1 単純に数値 に評価される Int 。 2 ブロック自体がどのように評価されるかは、コンパイラ次第です。それについては、次の投稿で説明します。 定義は次のとおりです。 // src/types/ast.mts export type BlockNode = { type: "block"; expressions: AstNode[]; }; 最後に、 を定義します。 lexer の タイプと同様に、 は、以前に定義した他のノードの 1 つである判別共用体です。 AstNode Token AstNode export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode; には の配列があることに気付いたかもしれません。 AstNode は に あるため、 には子 を ことができます。つまり、 は再帰型です。子を持つことができる子を再帰的に表現するこの機能は、AST の基盤です。 AST のツリーが形成できる場所です。 BlockNode AstNode AstNode なる可能性が BlockNode BlockNode BlockNodes BlockNode この時点で は完成しており、次のようになります。 . src/types/ast.mts このファイル トークン型で行ったように、 から型をエクスポートします。 src/types/index.mts // src/types/index.mts export * from "./token.mjs"; export * from "./ast.mjs"; AST の構築 AST を定義したので、今度は AST を作成します。 新しい ファイルを作成し、使用するすべてのインポートを追加します。 src/parser.mts // src/parser.mts import { Token, IdentifierNode, TypedIdentifierNode, IdentifierToken, TypedIdentifierToken, FloatToken, FloatNode, IntToken, IntNode, AstNode, BlockNode, } from "./types/index.mjs"; これで、最上位の解析関数を定義できます。 parse 関数は、レクサーによって生成されたトークンを受け取り、ツリーのルートとして機能する を返します。 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, }; }; 次に、 関数を定義します。 は、トークンのフラットな配列をトークンのツリーに変換します。 consumeTokenTree consumeTokenTree このかすかな表現を考えると： (add (sub 3 1) (sub 5 2)) lexer は、次のトークンの配列を生成します。 // Note: I've simplified the Token format to just be strings to keep things short ["(", "add", "(", "sub", "3", "1", ")", "(", "sub", "5", "2", ")", ")"]; はそのフラットな配列を取り、それをツリーに変換します。これは、一連のブラケット トークン の間にあるすべてのトークンを配列に入れるのと同じくらい簡単です。したがって、上記のトークン配列は次のトークン ツリーになります。 consumeTokenTree () ["add", [, "sub", "3", "1"], ["sub", "5", "2"]]; の実際の定義は次のとおりです。 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"; }; トークン ツリーができたので、それをブロックに変換する必要があります。そのために、ツリーを入力として取り、 を 関数を作成します。 BlockNode parseBlock 1const parseBlock = (block?: TokenTree): BlockNode => { return { type: "block", // This is where the recursive magic happens expressions: block.map(parseExpression), }; }; お気づきかもしれませんが、 はツリーの各項目をまだ作成されていない 関数にマップします。 は、 または のいずれかを受け取り、それを対応する タイプに変換します。 parseBlock parseExpression parseExpression TokenTree NonBracketToken AstNode 定義は次のとおりです。 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)}`); }; 関数を定義しましょう。この関数はかなりきれいで、TypeScript の最も強力な機能の 1 つを示しています。 .簡単に言えば、 は式をテストし、型を特定の に絞り込みます。これにより、TypeScript は、対応するパーサー関数に正しいトークンを渡していることを確認できます。 isTokenType カスタムタイプガード isTokenType TokenType 定義は次のとおりです。 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); }; そこではたくさんのことが起こっているので、それを見ていきましょう。まず、一般的な定義 あります。これは基本的に、T が フィールドの可能な値の 1 つでなければならないことを示しています。 Typescript は、T が . <T extends Token["type"]> Token.type "int" | "float" | "identifier" | "typed-identifier" | "bracket 次に興味深いコードは、戻り値の型の述語 であることです。この述語は TypeScript に、 の戻り値が true の場合、 は パラメーターとして渡された文字列と型が一致する でなければならないことを伝えます。 item is Extract<Token, { type: T }> isTokenType item type Token 実際には、未知の を に渡した場合、typescript は値をより具体的なトークン ( など) に正しく絞り込むことができることを意味します。 Token isTokenType IntToken カスタム型ガードを定義したので、実際のトークン パーサーを定義できます。最初の 3 つは単純です。基本的に、トークンのコピーまたはわずかに変更されたコピーを返すだけです。 const parseFloatToken = (float: FloatToken): FloatNode => ({ ...float }); const parseIntToken = (int: IntToken): IntNode => ({ ...int }); const parseIdentifier = (identifier: IdentifierToken): IdentifierNode => { return { type: "identifier", identifier: identifier.value, }; }; 最後のパーサーは です。型付き識別子は の形式を取ることに注意してください。それを解析することは、文字列をコロンで分割するのと同じくらい簡単です。返される配列の最初の値は で、2 番目の値は です。定義は次のとおりです。 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], }; }; 完成したファイルはこちら 動作するパーサーに必要なコードはこれだけです。先に進む前に、メインの ファイルを更新して、パーサーの出力を表示しましょう。 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)); プロジェクトをビルドして実行します。 npx tsc wispy example.wispy すべてがうまくいけば、出力は次のようになります . これ 以上で、パーサーは終了です。これで、レクサーからのトークンのストリームを AST に変換できます。次の投稿では、機械可読コードの生成と実行という興味深い部分について説明します。 今すぐ Courier がどのように製品通知を楽しくするかを確認してください。 デモをリクエストして、

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

このオーディオは、ストーリーの元の言語で制作されています。

長すぎる; 読むには

楽しみと利益のために WebAssembly 言語を構築する方法: 構文解析

楽しみと利益のために WebAssembly 言語を構築する方法: 構文解析

長すぎる; 読むには

Company Mentioned

@courier

関連ストーリー