No  desta série sobre como construir uma linguagem de programação WebAssembly, construímos um lexer. Nesta postagem, abordaremos a próxima fase do nosso compilador, a análise. A análise é a parte do nosso compilador que pega o fluxo de token gerado pelo lexer e o converte em um  (AST).   última postagem   árvore de sintaxe abstrata  Um AST é uma estrutura de dados semelhante a uma árvore que organiza os tokens em uma hierarquia lógica que pode ser mais facilmente traduzida em código de máquina. Felizmente, como wispy é uma linguagem de expressão S, nosso código   é essencialmente um AST. Pegue o seguinte fluxo de tokens: já   “(“, “add”, “3”, “(“, “sub”, “2”, “1”, “)”, “)”  Cada conjunto de parênteses representa uma subárvore, onde o primeiro token é o nó do operador e os tokens seguintes são seus operandos. Se encontrarmos outro parêntese de abertura antes que o conjunto atual seja fechado, sabemos que ele representa um operando que é uma subárvore. O fluxo de tokens acima seria organizado em uma árvore semelhante a esta:  Se você estiver interessado em escrever um analisador para uma sintaxe mais complexa semelhante a C, consulte meu  Series.   Construindo uma linguagem de programação  Mais sobre AST  Assim como fizemos com o lexer, começaremos definindo nossos tipos. Esses tipos definirão a estrutura do nosso AST. Cada tipo representa um “Nó”, o círculo do nosso diagrama na introdução. Aqui estão os nós básicos. Vamos passar por cima deles, pois não são muito diferentes dos tokens que definimos no 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; };  Um novo conceito para o AST é o   . Um   é uma expressão composta por um grupo de outros nós. BlockNode BlockNode  Por exemplo,   é um bloco de três nós: (add 1 2)  Um identificador que é avaliado como uma função,   . add  Um Int que simplesmente resulta no número   . 1  Um Int que simplesmente resulta no número   . 2  Como o próprio bloco é avaliado depende do compilador. Nós vamos chegar a isso no próximo post.  Aqui está a definição:   // src/types/ast.mts export type BlockNode = { type: "block"; expressions: AstNode[]; };  Finalmente, definimos o   . Como o tipo   do lexer,   é uma união discriminada que pode ser um de qualquer outro nó que definimos anteriormente: AstNode Token AstNode   export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode;  Você deve ter notado que   tem um array de   s, já que     um   ,   s pode conter   filhos . Em outras palavras,   é um tipo recursivo. Essa capacidade de representar recursivamente filhos que podem ter filhos é a base do nosso AST. É onde a árvore no AST pode se formar. BlockNode AstNode AstNode pode ser BlockNode BlockNode BlockNodes BlockNode  Neste ponto,   está concluído e deve se parecer com  . src/types/ast.mts   este ficheiro  Agora exporte os tipos de   como fizemos com os tipos de token: src/types/index.mts   // src/types/index.mts export * from "./token.mjs"; export * from "./ast.mjs";  Construindo o AST  Agora que definimos o AST, é hora de criar um.  Crie um novo arquivo   e adicione todas as importações que usaremos: src/parser.mts   // src/parser.mts import { Token, IdentifierNode, TypedIdentifierNode, IdentifierToken, TypedIdentifierToken, FloatToken, FloatNode, IntToken, IntNode, AstNode, BlockNode, } from "./types/index.mjs";  Agora podemos definir nossa função de análise de nível superior. A função parse pega os tokens gerados pelo lexer e retorna um   que atua como a raiz da nossa árvore. 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, }; };  Em seguida, definimos a função   .   converte uma matriz plana de tokens em uma árvore de tokens. consumeTokenTree consumeTokenTree  Dada esta expressão tênue:   (add (sub 3 1) (sub 5 2))  O lexer produzirá este array de tokens:   // Note: I've simplified the Token format to just be strings to keep things short ["(", "add", "(", "sub", "3", "1", ")", "(", "sub", "5", "2", ")", ")"];    essa matriz plana e a transformará em uma árvore. Isso é tão simples quanto colocar cada token entre um conjunto de tokens de colchetes   em uma matriz. Portanto, nossa matriz de tokens acima se torna esta árvore de tokens: consumeTokenTree ()   ["add", [, "sub", "3", "1"], ["sub", "5", "2"]];  Aqui está a definição real de   : 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"; };  Agora que temos uma árvore de tokens, precisamos transformá-la em um bloco. Para fazer isso, criamos uma função   que recebe a árvore como entrada e retorna um   : parseBlock BlockNode   1const parseBlock = (block?: TokenTree): BlockNode => { return { type: "block", // This is where the recursive magic happens expressions: block.map(parseExpression), }; };  Como você deve ter notado,   mapeia cada item da árvore com uma função   ainda a ser escrita.   pega um   ou um   e o transforma em seu tipo   correspondente. parseBlock parseExpression parseExpression TokenTree NonBracketToken AstNode  Aqui está a definição:   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)}`); };  Vamos definir a função   . Esta função é bem legal e demonstra um dos recursos mais poderosos do TypeScript,  . Simplificando,   testa a expressão e restringe o tipo a um   específico. Isso permite que o TypeScript tenha certeza de que estamos passando os tokens corretos para suas funções de analisador correspondentes na linha. isTokenType   protetores de tipo personalizado isTokenType TokenType  Aqui está a definição:   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); };  Há muita coisa acontecendo lá, então vamos dar uma olhada. Primeiro, temos uma definição genérica,   . Isso significa essencialmente que T deve ser um dos valores possíveis do campo   . Typescript é inteligente o suficiente para saber que significa T deve ser um dos   . <T extends Token["type"]> Token.type "int" | "float" | "identifier" | "typed-identifier" | "bracket  A próxima parte interessante do código é que o   . Esse predicado informa ao TypeScript que, se o valor de retorno de   for true,   deverá ser o   cujo tipo corresponde à cadeia de caracteres passada como o parâmetro   . item is Extract<Token, { type: T }> isTokenType item Token type  Na prática, isso significa que, se passarmos um   desconhecido para   , o typescript poderá restringir corretamente o valor a um token mais específico, como   . Token isTokenType IntToken  Agora que temos nosso protetor de tipo personalizado definido, podemos definir os analisadores de token reais. Os três primeiros são simples; eles basicamente retornam uma cópia ou uma cópia ligeiramente modificada do token:   const parseFloatToken = (float: FloatToken): FloatNode => ({ ...float }); const parseIntToken = (int: IntToken): IntNode => ({ ...int }); const parseIdentifier = (identifier: IdentifierToken): IdentifierNode => { return { type: "identifier", identifier: identifier.value, }; };  O analisador final é o   . Lembre-se de que um identificador digitado assume o formato   . A análise é tão simples quanto dividir a string pelos dois pontos. O primeiro valor da matriz retornada é o   , o segundo é o   . Aqui está a definição: 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], }; };   Aqui está o arquivo finalizado  Esse é todo o código necessário para um analisador funcional. Antes de prosseguirmos, vamos atualizar o arquivo   principal para visualizar a saída do analisador: 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));  Construa e execute o projeto:   npx tsc wispy example.wispy  Se tudo correr bem, a saída deve se parecer com  .   isto  Com isso, o analisador está finalizado. Agora podemos converter o fluxo de tokens do lexer em um AST. No próximo post, podemos entrar nos detalhes importantes: gerar e executar código legível por máquina.    hoje para ver como o Courier funciona para tornar as notificações de produtos deliciosas! Solicite uma demonstração

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

Como construir uma linguagem WebAssembly para diversão e lucro: análise

About Author

COMENTARIOS

Rótulos

ESTE ARTIGO FOI APRESENTADO EM

Related Stories

Telegram: a ponte da Crypto Island para o continente

Valhalla de Floki se junta como patrocinador associado da viagem da Índia ao Sri Lanka

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Como melhorar seu fluxo de trabalho em 10 vezes: 17 aplicativos essenciais

Telegram: a ponte da Crypto Island para o continente

Valhalla de Floki se junta como patrocinador associado da viagem da Índia ao Sri Lanka

Quer ganhar um concurso de redação do HackerNoon? Aqui está o que os vencedores do concurso #crypto-api recomendam

Como melhorar seu fluxo de trabalho em 10 vezes: 17 aplicativos essenciais

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps