Dans le  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  (AST).   Dernier commentaire   arbre de syntaxe abstraite  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   un AST. Prenez le flux de jetons suivant : déjà   “(“, “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  série.   Construire un langage de programmation  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   . Un   est une expression composée d'un groupe d'autres nœuds. BlockNode BlockNode  Par exemple,   est un bloc de trois nœuds : (add 1 2)  Un identifiant qui évalue une fonction,   . add  Un Int qui évalue simplement le nombre   . 1  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   . Comme le type   du lexer,   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 : AstNode Token AstNode   export type AstNode = IntNode | FloatNode | IdentifierNode | TypedIdentifierNode | BlockNode;  Vous avez peut-être remarqué que   a un tableau de   s, puisque     un   ,   s peut contenir des   enfants. En d'autres termes,   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. BlockNode AstNode AstNode peut être BlockNode BlockNode BlockNodes BlockNode  À ce stade,   est terminé et devrait ressembler à  . src/types/ast.mts   ce fichier  Exportez maintenant les types depuis   comme nous l'avons fait avec les types de jetons : src/types/index.mts   // 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   et ajoutez toutes les importations que nous utiliserons : src/parser.mts   // 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   qui agit comme la racine de notre arbre. 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, }; };  Ensuite, nous définissons la fonction   .   convertit un tableau plat de jetons en un arbre de jetons. consumeTokenTree consumeTokenTree  É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", ")", ")"];    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 : consumeTokenTree ()   ["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   qui prend l'arbre en entrée et renvoie un   : parseBlock 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é,   mappe chaque élément de l'arborescence avec une fonction   qui n'a pas encore été écrite.   prend un   ou un   et le transforme en son type   correspondant. parseBlock parseExpression parseExpression TokenTree NonBracketToken AstNode  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   . Cette fonction est assez soignée et démontre l'une des fonctionnalités les plus puissantes de TypeScript,  . En termes simples,   teste l'expression et réduit le type à un   spécifique. Cela permet à TypeScript d'être certain que nous transmettons les jetons corrects à leurs fonctions d'analyseur correspondantes sur toute la ligne. isTokenType   gardes de type personnalisé isTokenType TokenType  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,   . Cela signifie essentiellement que T doit être l'une des valeurs possibles du champ   . Typescript est assez intelligent pour savoir que cela signifie que T doit être l'un des   . <T extends Token["type"]> Token.type "int" | "float" | "identifier" | "typed-identifier" | "bracket  Le prochain morceau de code intéressant est l'   . Ce prédicat indique à TypeScript que si la valeur de retour de   est true, alors   doit être le   dont le type correspond à la chaîne passée comme paramètre de   . item is Extract<Token, { type: T }> isTokenType item Token type  En pratique, cela signifie que si nous devions passer un   inconnu à   , dactylographié pourra correctement réduire la valeur à un jeton plus spécifique, comme   . Token isTokenType 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   . N'oubliez pas qu'un identifiant typé prend la forme   . L'analyser est aussi simple que de diviser la chaîne par les deux-points. La première valeur du tableau retourné est l'   , la seconde est le   . Voici la définition : 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], }; };   Voici le fichier terminé  C'est tout le code requis pour un analyseur fonctionnel. Avant de poursuivre, mettons à jour le fichier principal   pour afficher la sortie de l'analyseur : 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));  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.    aujourd'hui pour voir comment Courier fonctionne pour rendre les notifications de produits agréables ! Demandez une démo dès

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

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

About Author

COMMENTAIRES

ÉTIQUETTES

CET ARTICLE A ÉTÉ PARU DANS

Related Stories

Vous voulez gagner un concours d’écriture HackerNoon ? Voici ce que recommandent les gagnants du concours #crypto-api

Des forums aux flux : comment les algorithmes des réseaux sociaux façonnent l'interaction numérique

Créer des produits cryptographiques centrés sur l'utilisateur : l'importance des retours clients

Le modèle Bitcoin UTXO, alimentant un écosystème unique

Vous voulez gagner un concours d’écriture HackerNoon ? Voici ce que recommandent les gagnants du concours #crypto-api

Des forums aux flux : comment les algorithmes des réseaux sociaux façonnent l'interaction numérique

Créer des produits cryptographiques centrés sur l'utilisateur : l'importance des retours clients

Le modèle Bitcoin UTXO, alimentant un écosystème unique

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps