Comment créer un langage WebAssembly pour le plaisir et le profit : analyse

Dans le Dernier commentaire de cette série sur la façon de construire un langage de programmation WebAssembly, nous avons construit un lexer. Dans cet article, nous aborderons la prochaine phase de notre compilateur, l'analyse. L'analyse est la partie de notre compilateur qui prend le flux de jetons généré par le lexer et le convertit en un arbre de syntaxe abstraite (AST).

Un AST est une structure de données arborescente qui organise les jetons dans une hiérarchie logique qui peut être plus facilement traduite en code machine. Heureusement, comme Wispy est un langage d'expression S, notre code est essentiellement déjà un AST. Prenez le flux de jetons suivant :

 “(“, “add”, “3”, “(“, “sub”, “2”, “1”, “)”, “)”

Chaque ensemble de parenthèses représente un sous-arbre, où le premier jeton est le nœud opérateur et les jetons suivants sont ses opérandes. Si nous rencontrons une autre parenthèse ouvrante avant que l'ensemble courant ne soit fermé, nous savons qu'il représente un opérande qui est lui-même un sous-arbre. Le flux de jetons ci-dessus serait organisé dans un arbre qui ressemble à ceci :

Si vous êtes intéressé par l'écriture d'un analyseur pour une syntaxe de type C plus complexe, consultez mon précédent Construire un langage de programmation série.

En savoir plus sur l'AST

Comme nous l'avons fait avec le lexer, nous allons commencer par définir nos types. Ces types définiront la structure de notre AST. Chaque type représente un "Nœud", le cercle de notre diagramme dans l'intro. Voici les nœuds de base. Nous les passerons sous silence, car ils ne sont pas très différents des jetons que nous avons définis dans le 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 nouveau concept de l'AST est le BlockNode . Un BlockNode est une expression composée d'un groupe d'autres nœuds.

Par exemple, (add 1 2) est un bloc de trois nœuds :

1. Un identifiant qui évalue une fonction, add .
2. Un Int qui évalue simplement le nombre 1 .
3. Un Int qui évalue simplement le nombre 2 .

La façon dont le bloc lui-même est évalué dépend du compilateur. Nous y reviendrons dans le prochain post.

Voici la définition :

 // src/types/ast.mts export type BlockNode = { type: "block"; expressions: AstNode[]; };

Enfin, nous définissons le AstNode . Comme le type Token du lexer, AstNode est une union discriminée qui peut être l'un de n'importe quel autre nœud que nous avons précédemment défini :

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

Vous avez peut-être remarqué que BlockNode a un tableau de AstNode s, puisque AstNode peut être un BlockNode , BlockNode s peut contenir des BlockNodes enfants. En d'autres termes, BlockNode est un type récursif. Cette capacité à représenter récursivement les enfants qui peuvent avoir des enfants est le fondement de notre AST. C'est là que l'arbre dans AST est autorisé à se former.

À ce stade, src/types/ast.mts est terminé et devrait ressembler à ce fichier .

Exportez maintenant les types depuis src/types/index.mts comme nous l'avons fait avec les types de jetons :

 // src/types/index.mts export * from "./token.mjs"; export * from "./ast.mjs";

Construire l'AST

Maintenant que nous avons défini l'AST, il est temps d'en créer un.

Créez un nouveau fichier src/parser.mts et ajoutez toutes les importations que nous utiliserons :

 // src/parser.mts import { Token, IdentifierNode, TypedIdentifierNode, IdentifierToken, TypedIdentifierToken, FloatToken, FloatNode, IntToken, IntNode, AstNode, BlockNode, } from "./types/index.mjs";

Nous pouvons maintenant définir notre fonction d'analyse de niveau supérieur. La fonction d'analyse prend les jetons générés par le lexer et renvoie un BlockNode qui agit comme la racine de notre arbre.

 // 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, }; };

Ensuite, nous définissons la fonction consumeTokenTree . consumeTokenTree convertit un tableau plat de jetons en un arbre de jetons.

Étant donné cette expression vaporeuse:

 (add (sub 3 1) (sub 5 2))

Le lexer produira ce tableau de jetons :

 // Note: I've simplified the Token format to just be strings to keep things short ["(", "add", "(", "sub", "3", "1", ")", "(", "sub", "5", "2", ")", ")"];

consumeTokenTree prendra ce tableau plat et le transformera en arbre. C'est aussi simple que de placer chaque jeton entre un ensemble de jetons entre parenthèses () dans un tableau. Ainsi, notre tableau de jetons ci-dessus devient cet arbre de jetons :

 ["add", [, "sub", "3", "1"], ["sub", "5", "2"]];

Voici la définition réelle 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"; };

Maintenant que nous avons un arbre à jetons, nous devons le transformer en bloc. Pour ce faire, nous créons une fonction parseBlock qui prend l'arbre en entrée et renvoie un BlockNode :

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

Comme vous l'avez peut-être remarqué, parseBlock mappe chaque élément de l'arborescence avec une fonction parseExpression qui n'a pas encore été écrite. parseExpression prend un TokenTree ou un NonBracketToken et le transforme en son type AstNode correspondant.

Voici la définition :

 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)}`); };

Définissons la fonction isTokenType . Cette fonction est assez soignée et démontre l'une des fonctionnalités les plus puissantes de TypeScript, gardes de type personnalisé . En termes simples, isTokenType teste l'expression et réduit le type à un TokenType spécifique. Cela permet à TypeScript d'être certain que nous transmettons les jetons corrects à leurs fonctions d'analyseur correspondantes sur toute la ligne.

Voici la définition :

 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); };

Il se passe beaucoup de choses là-bas, alors allons-y. Tout d'abord, nous avons une définition générique, <T extends Token["type"]> . Cela signifie essentiellement que T doit être l'une des valeurs possibles du champ Token.type . Typescript est assez intelligent pour savoir que cela signifie que T doit être l'un des "int" | "float" | "identifier" | "typed-identifier" | "bracket .

Le prochain morceau de code intéressant est l' item is Extract<Token, { type: T }> . Ce prédicat indique à TypeScript que si la valeur de retour de isTokenType est true, alors item doit être le Token dont le type correspond à la chaîne passée comme paramètre de type .

En pratique, cela signifie que si nous devions passer un Token inconnu à isTokenType , dactylographié pourra correctement réduire la valeur à un jeton plus spécifique, comme IntToken .

Maintenant que nous avons défini notre garde de type personnalisé, nous pouvons définir les analyseurs de jetons réels. Les trois premiers sont simples; ils renvoient essentiellement une copie ou une copie légèrement modifiée du jeton :

 const parseFloatToken = (float: FloatToken): FloatNode => ({ ...float }); const parseIntToken = (int: IntToken): IntNode => ({ ...int }); const parseIdentifier = (identifier: IdentifierToken): IdentifierNode => { return { type: "identifier", identifier: identifier.value, }; };

L'analyseur final est le parseTypedIdentifier . N'oubliez pas qu'un identifiant typé prend la forme identifier:type . L'analyser est aussi simple que de diviser la chaîne par les deux-points. La première valeur du tableau retourné est l' identifier , la seconde est le type . Voici la définition :

 const parseTypedIdentifier = (identifier: TypedIdentifierToken): TypedIdentifierNode => { const vals = identifier.value.split(":"); return { type: "typed-identifier", identifier: vals[0], typeIdentifier: vals[1], }; };

Voici le fichier terminé

C'est tout le code requis pour un analyseur fonctionnel. Avant de poursuivre, mettons à jour le fichier principal src/index.mts pour afficher la sortie de l'analyseur :

 // 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));

Générer et exécuter le projet :

 npx tsc wispy example.wispy

Si tout se passe bien, la sortie devrait ressembler à cette .

Avec cela, l'analyseur est terminé. Nous pouvons maintenant convertir le flux de jetons du lexer en un AST. Dans le prochain article, nous pourrons entrer dans les détails juteux : générer et exécuter du code lisible par machine.

Demandez une démo dès aujourd'hui pour voir comment Courier fonctionne pour rendre les notifications de produits agréables !