En el  de esta serie sobre cómo construir un lenguaje de programación WebAssembly, construimos un lexer. En esta publicación, cubriremos la siguiente fase de nuestro compilador, el análisis. El análisis es la parte de nuestro compilador que toma el flujo de token generado por el lexer y lo convierte en un  (AST).   ultima publicación   árbol de sintaxis abstracta  Un AST es una estructura de datos en forma de árbol que organiza los tokens en una jerarquía lógica que se puede traducir más fácilmente a código de máquina. Afortunadamente, debido a que wispy es un lenguaje de expresión S, nuestro código   es esencialmente un AST. Tome la siguiente secuencia de tokens: ya   “(“, “add”, “3”, “(“, “sub”, “2”, “1”, “)”, “)”  Cada conjunto de paréntesis representa un subárbol, donde el primer token es el nodo operador y los siguientes tokens son sus operandos. Si nos encontramos con otro paréntesis de apertura antes de que se cierre el conjunto actual, sabemos que representa un operando que en sí mismo es un subárbol. El flujo de tokens anterior se organizaría en un árbol que se parece a esto:  Si está interesado en escribir un analizador para una sintaxis similar a C más compleja, consulte mi anterior  serie.   Construyendo un lenguaje de programación  Más sobre AST  Como hicimos con el lexer, comenzaremos definiendo nuestros tipos. Estos tipos definirán la estructura de nuestro AST. Cada tipo representa un "Nodo", el círculo de nuestro diagrama en la introducción. Estos son los nodos básicos. Los pasaremos por alto, ya que no son muy diferentes de los tokens que definimos en el 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; };  Un nuevo concepto para el AST es el   . Un   es una expresión formada por un grupo de otros nodos. BlockNode BlockNode  Por ejemplo,   es un bloque de tres nodos: (add 1 2)  Un identificador que se evalúa como una función,   . add  Un Int que simplemente se evalúa como el número   . 1  Un Int que simplemente se evalúa como el número   . 2  La forma en que se evalúa el bloque depende del compilador. Llegaremos a eso en la próxima publicación.  Aquí está la definición:   // src/types/ast.mts export type BlockNode = { type: "block"; expressions: AstNode[]; };  Finalmente, definimos el   . Al igual que el tipo   del lexer,   es una unión discriminada que puede ser uno de cualquier otro nodo que definimos previamente: AstNode Token AstNode   export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode;  Es posible que haya notado que   tiene una matriz de   s. Dado que     un   ,   s puede contener   secundarios. En otras palabras,   es un tipo recursivo. Esta capacidad de representar niños recursivamente que pueden tener niños es la base de nuestro AST. Es donde se permite que se forme el árbol en AST. BlockNode AstNode AstNode puede ser BlockNode BlockNode BlockNodes BlockNode  En este punto,   está terminado y debería verse como  . src/types/ast.mts   Este archivo  Ahora exporte los tipos de   como hicimos con los tipos de token: src/types/index.mts   // src/types/index.mts export * from "./token.mjs"; export * from "./ast.mjs";  Construyendo el AST  Ahora que hemos definido el AST, es hora de construir uno.  Cree un nuevo archivo   y agregue todas las importaciones que usaremos: src/parser.mts   // src/parser.mts import { Token, IdentifierNode, TypedIdentifierNode, IdentifierToken, TypedIdentifierToken, FloatToken, FloatNode, IntToken, IntNode, AstNode, BlockNode, } from "./types/index.mjs";  Ahora podemos definir nuestra función de análisis de nivel superior. La función parse toma los tokens generados por el lexer y devuelve un   que actúa como la raíz de nuestro árbol. 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, }; };  A continuación, definimos la función   .   convierte una matriz plana de tokens en un árbol de tokens. consumeTokenTree consumeTokenTree  Dada esta tenue expresión:   (add (sub 3 1) (sub 5 2))  El lexer producirá esta matriz de tokens:   // Note: I've simplified the Token format to just be strings to keep things short ["(", "add", "(", "sub", "3", "1", ")", "(", "sub", "5", "2", ")", ")"];    tomará esa matriz plana y la convertirá en un árbol. Esto es tan simple como colocar cada ficha entre un conjunto de fichas de paréntesis   en una matriz. Entonces, nuestra matriz de tokens de arriba se convierte en este árbol de tokens: consumeTokenTree ()   ["add", [, "sub", "3", "1"], ["sub", "5", "2"]];  Aquí está la definición 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"; };  Ahora que tenemos un árbol de fichas, debemos convertirlo en un bloque. Para hacerlo, creamos una función   que toma el árbol como entrada y devuelve un   : parseBlock BlockNode   1const parseBlock = (block?: TokenTree): BlockNode => { return { type: "block", // This is where the recursive magic happens expressions: block.map(parseExpression), }; };  Como habrás notado,   mapea cada elemento del árbol con una función   aún por escribir.   toma un   o un   y lo transforma en su tipo de   correspondiente. parseBlock parseExpression parseExpression TokenTree NonBracketToken AstNode  Aquí está la definición:   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)}`); };  Definamos la función   . Esta función es bastante ordenada y demuestra una de las características más poderosas de TypeScript,  . En pocas palabras,   prueba la expresión y reduce el tipo a un   específico. Esto permite que TypeScript esté seguro de que estamos pasando los tokens correctos a sus funciones de analizador correspondientes en la línea. isTokenType   protectores de tipo personalizado isTokenType TokenType  Aquí está la definición:   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); };  Están sucediendo muchas cosas allí, así que analicemos. Primero, tenemos una definición genérica,   . Básicamente, esto significa que T debe ser uno de los valores posibles del campo   . Typescript es lo suficientemente inteligente como para saber que significa que T debe ser uno de   . <T extends Token["type"]> Token.type "int" | "float" | "identifier" | "typed-identifier" | "bracket  El siguiente fragmento de código interesante es el   . Este predicado le dice a TypeScript que si el valor de retorno de   es verdadero, el   debe ser el   cuyo tipo coincida con la cadena pasada como parámetro de   . item is Extract<Token, { type: T }> isTokenType item Token type  En la práctica, eso significa que si tuviéramos que pasar un   desconocido a   , TypeScript podrá reducir correctamente el valor a un token más específico, como   . Token isTokenType IntToken  Ahora que tenemos definido nuestro protector de tipos personalizado, podemos definir los analizadores de tokens reales. Los primeros tres son simples; esencialmente solo devuelven una copia o una copia ligeramente modificada del token:   const parseFloatToken = (float: FloatToken): FloatNode => ({ ...float }); const parseIntToken = (int: IntToken): IntNode => ({ ...int }); const parseIdentifier = (identifier: IdentifierToken): IdentifierNode => { return { type: "identifier", identifier: identifier.value, }; };  El analizador final es   . Recuerde que un identificador escrito toma la forma   . Analizarlo es tan simple como dividir la cadena por los dos puntos. El primer valor de la matriz devuelta es el   , el segundo es el   . Aquí está la definición: 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], }; };   Aquí está el archivo terminado  Ese es todo el código requerido para un analizador de trabajo. Antes de continuar, actualicemos el archivo principal   para ver la salida del analizador: 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));  Construir y ejecutar el proyecto:   npx tsc wispy example.wispy  Si todo va bien, la salida debería verse como  .   este  Con eso, el analizador está terminado. Ahora podemos convertir el flujo de tokens del lexer en un AST. En la próxima publicación, podemos entrar en las partes jugosas: generar y ejecutar código legible por máquina.  ¡   hoy para ver cómo funciona Courier para hacer que las notificaciones de productos sean agradables! Solicite una demostración

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

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Cómo construir un lenguaje WebAssembly para divertirse y obtener ganancias: análisis

Cómo construir un lenguaje WebAssembly para divertirse y obtener ganancias: análisis

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Telegram: el puente de Crypto Island hacia el continente

Una guía del arquitecto para crear una arquitectura de referencia para un lago de datos de IA/ML

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Telegram: el puente de Crypto Island hacia el continente

Una guía del arquitecto para crear una arquitectura de referencia para un lago de datos de IA/ML

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps