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

En el ultima publicación 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 árbol de sintaxis abstracta (AST).

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 ya es esencialmente un AST. Tome la siguiente secuencia de tokens:

 “(“, “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 Construyendo un lenguaje de programación serie.

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 BlockNode . Un BlockNode es una expresión formada por un grupo de otros nodos.

Por ejemplo, (add 1 2) es un bloque de tres nodos:

1. Un identificador que se evalúa como una función, add .
2. Un Int que simplemente se evalúa como el número 1 .
3. 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 AstNode . Al igual que el tipo Token del lexer, AstNode es una unión discriminada que puede ser uno de cualquier otro nodo que definimos previamente:

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

Es posible que haya notado que BlockNode tiene una matriz de AstNode s. Dado que AstNode puede ser un BlockNode , BlockNode s puede contener BlockNodes secundarios. En otras palabras, BlockNode 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.

En este punto, src/types/ast.mts está terminado y debería verse como Este archivo .

Ahora exporte los tipos de src/types/index.mts como hicimos con los tipos de token:

 // 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 src/parser.mts y agregue todas las importaciones que usaremos:

 // 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 BlockNode que actúa como la raíz de nuestro árbol.

 // 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 consumeTokenTree . consumeTokenTree convierte una matriz plana de tokens en un árbol de tokens.

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", ")", ")"];

consumeTokenTree 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:

 ["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 parseBlock que toma el árbol como entrada y devuelve un BlockNode :

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

Como habrás notado, parseBlock mapea cada elemento del árbol con una función parseExpression aún por escribir. parseExpression toma un TokenTree o un NonBracketToken y lo transforma en su tipo de AstNode correspondiente.

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 isTokenType . Esta función es bastante ordenada y demuestra una de las características más poderosas de TypeScript, protectores de tipo personalizado . En pocas palabras, isTokenType prueba la expresión y reduce el tipo a un TokenType 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.

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, <T extends Token["type"]> . Básicamente, esto significa que T debe ser uno de los valores posibles del campo Token.type . Typescript es lo suficientemente inteligente como para saber que significa que T debe ser uno de "int" | "float" | "identifier" | "typed-identifier" | "bracket .

El siguiente fragmento de código interesante es el item is Extract<Token, { type: T }> . Este predicado le dice a TypeScript que si el valor de retorno de isTokenType es verdadero, el item debe ser el Token cuyo tipo coincida con la cadena pasada como parámetro de type .

En la práctica, eso significa que si tuviéramos que pasar un Token desconocido a isTokenType , TypeScript podrá reducir correctamente el valor a un token más específico, como 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 parseTypedIdentifier . Recuerde que un identificador escrito toma la forma identifier:type . Analizarlo es tan simple como dividir la cadena por los dos puntos. El primer valor de la matriz devuelta es el identifier , el segundo es el type . Aquí está la definición:

 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 src/index.mts para ver la salida del analizador:

 // 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.

¡ Solicite una demostración hoy para ver cómo funciona Courier para hacer que las notificaciones de productos sean agradables!