Comment aborder la rédaction d'un interprète à partir de zéro

Certains disent que « tout se résume à des uns et des zéros », mais comprenons-nous vraiment comment nos programmes sont traduits en ces bits ?

Les compilateurs et les interpréteurs prennent tous deux une chaîne brute représentant un programme, l'analysent et lui donnent un sens. Bien que les interpréteurs soient les plus simples des deux, écrire même un interpréteur très simple (qui ne fait que l'addition et la multiplication) sera instructif. Nous nous concentrerons sur ce que les compilateurs et les interpréteurs ont en commun : la lexification et l'analyse de l'entrée.

Les choses à faire et à ne pas faire pour écrire votre propre interprète

Les lecteurs peuvent se demander quel est le problème avec une regex ? Les expressions régulières sont puissantes, mais les grammaires du code source ne sont pas assez simples pour être analysées par elles. Les langages spécifiques au domaine (DSL) ne le sont pas non plus, et un client peut avoir besoin d'un DSL personnalisé pour les expressions d'autorisation, par exemple. Mais même sans appliquer directement cette compétence, écrire un interpréteur permet d'apprécier beaucoup plus facilement l'effort derrière de nombreux langages de programmation, formats de fichiers et DSL.

Écrire correctement des analyseurs à la main peut être difficile avec tous les cas extrêmes impliqués. C'est pourquoi il existe des outils populaires, comme ANTLR, qui peuvent générer des analyseurs pour de nombreux langages de programmation populaires. Il existe également des bibliothèques appelées combinateurs d'analyseurs , qui permettent aux développeurs d'écrire des analyseurs directement dans leurs langages de programmation préférés. Les exemples incluent FastParse pour Scala et Parsec pour Python.

Nous recommandons aux lecteurs, dans un contexte professionnel, d'utiliser de tels outils et bibliothèques pour éviter de réinventer la roue. Néanmoins, comprendre les défis et les possibilités d'écrire un interpréteur à partir de zéro aidera les développeurs à tirer parti de ces solutions plus efficacement.

Présentation des composants de l'interpréteur

Un interprète est un programme complexe, il comporte donc plusieurs étapes :

1. Un lexer est la partie d'un interpréteur qui transforme une séquence de caractères (texte brut) en une séquence de jetons.
2. Un analyseur , à son tour, prend une séquence de jetons et produit un arbre de syntaxe abstraite (AST) d'un langage. Les règles selon lesquelles un analyseur fonctionne sont généralement spécifiées par une grammaire formelle.
3. Un interpréteur est un programme qui interprète l'AST de la source d'un programme à la volée (sans le compiler au préalable).

Nous ne construirons pas d'interpréteur intégré spécifique ici. Au lieu de cela, nous allons explorer chacune de ces parties et leurs problèmes communs avec des exemples séparés. Au final, le code utilisateur ressemblera à ceci :

 val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res")

Après les trois étapes, nous nous attendons à ce que ce code calcule une valeur finale et imprime Result is: 19 . Ce tutoriel utilise Scala car c'est :

• Très concis, ajustant beaucoup de code sur un seul écran.
• Orienté expression, sans besoin de variables non initialisées/nulles.
• Tapez en toute sécurité, avec une puissante bibliothèque de collections, des énumérations et des classes de cas.

Plus précisément, le code ici est écrit dans la syntaxe des accolades facultatives Scala3 (une syntaxe de type Python, basée sur l'indentation). Mais aucune des approches n'est spécifique à Scala, et Scala est similaire à de nombreux autres langages : les lecteurs trouveront simple de convertir ces exemples de code dans d'autres langages. À défaut, les exemples peuvent être exécutés en ligne à l'aide de Scastie.

Enfin, les sections Lexer, Parser et Interpreter ont différents exemples de grammaires . Comme le montre le référentiel GitHub correspondant, les dépendances dans les exemples ultérieurs changent légèrement pour implémenter ces grammaires, mais les concepts généraux restent les mêmes.

Composante interpréteur 1 : Rédaction d'un lexer

Disons que nous voulons lex cette chaîne : "123 + 45 true * false1" . Il contient différents types de jetons :

• Littéraux entiers
• Opérateur A +
• Un opérateur *
• Un true littéral
• Un identifiant, false1

Les espaces entre les jetons seront ignorés dans cet exemple.

A ce stade, les expressions n'ont pas besoin d'avoir un sens ; le lexer convertit simplement la chaîne d'entrée en une liste de jetons. (Le travail de "donner un sens aux jetons" est laissé à l'analyseur.)

Nous allons utiliser ce code pour représenter un jeton :

 case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOF

Chaque jeton a un type, une représentation textuelle et une position dans l'entrée d'origine. Le poste peut aider les utilisateurs finaux du lexer avec le débogage.

Le jeton EOF est un jeton spécial qui marque la fin de l'entrée. Il n'existe pas dans le texte source ; nous l'utilisons uniquement pour simplifier l'étape de l'analyseur.

Ce sera la sortie de notre lexer :

 Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )

Examinons la mise en œuvre :

 class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toList

Nous commençons avec une liste vide de jetons, puis nous parcourons la chaîne et ajoutons des jetons au fur et à mesure.

Nous utilisons le caractère d' anticipation pour décider du type du jeton suivant . Notez que le caractère d'anticipation n'est pas toujours le caractère le plus en avant examiné. Sur la base de l'anticipation, nous savons à quoi ressemble le jeton et utilisons currentPos pour analyser tous les caractères attendus dans le jeton actuel, puis ajoutons le jeton à la liste :

Si l'anticipation est un espace blanc, nous l'ignorons. Les jetons à une seule lettre sont triviaux; nous les ajoutons et incrémentons l'index. Pour les entiers, il suffit de s'occuper de l'indice.

Nous arrivons maintenant à quelque chose d'un peu compliqué : les identificateurs contre les littéraux. La règle est que nous prenons la correspondance la plus longue possible et vérifions s'il s'agit d'un littéral ; si ce n'est pas le cas, c'est un identifiant.

Faites attention lorsque vous manipulez des opérateurs comme < et <= . Là, vous devez regarder devant vous un caractère de plus et voir s'il s'agit de = avant de conclure qu'il s'agit d'un opérateur <= . Sinon, c'est juste un < .

Avec cela, notre lexer a produit une liste de jetons.

Composant 2 de l'interpréteur : écriture d'un analyseur

Nous devons donner une certaine structure à nos jetons - nous ne pouvons pas faire grand-chose avec une liste seule. Par exemple, nous devons savoir :

Quelles expressions sont imbriquées ? Quels opérateurs sont appliqués dans quel ordre ? Quelles règles de portée s'appliquent, le cas échéant ?

Une arborescence prend en charge l'imbrication et l'ordonnancement. Mais d'abord, nous devons définir quelques règles pour construire des arbres. Nous aimerions que notre analyseur soit sans ambiguïté, c'est-à-dire qu'il renvoie toujours la même structure pour une entrée donnée.

Notez que l'analyseur suivant n'utilise pas l'exemple d'analyseur lexical précédent . Celui-ci sert à additionner des nombres, donc sa grammaire n'a que deux jetons, '+' et NUM :

 expr -> expr '+' expr expr -> NUM

Un équivalent, utilisant un caractère pipe ( | ) comme symbole "ou" comme dans les expressions régulières, est :

 expr -> expr '+' expr | NUM

Dans tous les cas, nous avons deux règles : une qui dit que nous pouvons additionner deux expr s et une autre qui dit que expr peut être un jeton NUM , ce qui ici signifiera un entier non négatif.

Les règles sont généralement spécifiées avec une grammaire formelle . Une grammaire formelle consiste en : Les règles elles-mêmes, comme indiqué ci-dessus Une règle de départ (la première règle spécifiée, par convention) Deux types de symboles pour définir les règles avec : Terminaux : les « lettres » (et autres caractères) de notre langue— les symboles irréductibles qui composent les jetons Les non-terminaux : les constructions intermédiaires utilisées pour l'analyse (c'est-à-dire les symboles qui peuvent être remplacés)

Seul un non-terminal peut se trouver sur le côté gauche d'une règle ; le côté droit peut avoir à la fois des terminaux et des non-terminaux. Dans l'exemple ci-dessus, les terminaux sont '+' et NUM , et le seul non terminal est expr . Pour un exemple plus large, dans le langage Java, nous avons des terminaux comme 'true' , '+' , Identifier et '[' , et des non-terminaux comme BlockStatements , ClassBody et MethodOrFieldDecl .

Il existe de nombreuses façons d'implémenter cet analyseur. Ici, nous utiliserons une technique d'analyse par « descente récursive ». C'est le type le plus courant car c'est le plus simple à comprendre et à mettre en œuvre.

Un analyseur de descente récursive utilise une fonction pour chaque non-terminal de la grammaire. Il part de la règle de départ et descend à partir de là (d'où «descente»), en déterminant quelle règle appliquer dans chaque fonction. La partie « récursive » est vitale car on peut imbriquer des non-terminaux de manière récursive ! Les expressions régulières ne peuvent pas faire cela : elles ne peuvent même pas gérer les parenthèses équilibrées. Nous avons donc besoin d'un outil plus puissant.

Un analyseur pour la première règle ressemblerait à ceci (code complet):

 def expr() = expr() eat('+') expr()

La fonction eat() vérifie si l'anticipation correspond au jeton attendu, puis déplace l'index d'anticipation. Malheureusement, cela ne fonctionnera pas encore car nous devons résoudre certains problèmes de grammaire.

Ambiguïté de la grammaire

Le premier problème est l'ambiguïté de notre grammaire, qui peut ne pas être apparente à première vue :

 expr -> expr '+' expr | NUM

Étant donné l'entrée 1 + 2 + 3 , notre analyseur pourrait choisir de calculer soit l' expr gauche soit l' expr droit en premier dans l'AST résultant :

C'est pourquoi nous devons introduire une certaine asymétrie :

 expr -> expr '+' NUM | NUM

L'ensemble des expressions que nous pouvons représenter avec cette grammaire n'a pas changé depuis sa première version. Seulement maintenant c'est sans ambiguïté : L'analyseur va toujours à gauche. Juste ce dont nous avions besoin!

Cela rend notre + opération laissée associative , mais cela deviendra apparent lorsque nous arriverons à la section Interpreter.

Règles récursives à gauche

Malheureusement, le correctif ci-dessus ne résout pas notre autre problème, la récursivité à gauche :

 def expr() = expr() eat('+') eat(NUM)

Nous avons ici une récursivité infinie . Si nous devions entrer dans cette fonction, nous aurions éventuellement une erreur de débordement de pile. Mais la théorie de l'analyse syntaxique peut aider !

Supposons que nous ayons une grammaire comme celle-ci, où alpha pourrait être n'importe quelle séquence de terminaux et de non-terminaux :

 A -> A alpha | B

On peut réécrire cette grammaire comme suit :

 A -> BA' A' -> alpha A' | epsilon

Ici, epsilon est une chaîne vide - rien, pas de jeton.

Prenons la révision actuelle de notre grammaire :

 expr -> expr '+' NUM | NUM

En suivant la méthode de réécriture des règles d'analyse détaillée ci-dessus, avec alpha étant nos jetons '+' NUM , notre grammaire devient :

 expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilon

Maintenant, la grammaire est correcte et nous pouvons l'analyser avec un analyseur de descente récursive. Voyons à quoi ressemblerait un tel analyseur pour cette dernière itération de notre grammaire :

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head

Ici, nous utilisons le jeton EOF pour simplifier notre analyseur. Nous sommes toujours sûrs qu'il y a au moins un jeton dans notre liste, nous n'avons donc pas besoin de gérer un cas particulier de liste vide.

De plus, si nous passons à un lexer en continu, nous n'aurions pas de liste en mémoire mais un itérateur, nous avons donc besoin d'un marqueur pour savoir quand nous arrivons à la fin de l'entrée. Lorsque nous arrivons à la fin, le jeton EOF devrait être le dernier jeton restant.

En parcourant le code, nous pouvons voir qu'une expression peut être juste un nombre. S'il ne reste plus rien, le jeton suivant ne serait pas un Plus , donc nous arrêterions l'analyse. Le dernier jeton serait EOF et nous aurions fini.

Si la chaîne d'entrée a plus de jetons, ceux-ci devraient ressembler à + 123 . C'est là que la récursivité sur exprOpt() entre en jeu !

Génération d'un AST

Maintenant que nous avons réussi à analyser notre expression, il est difficile de faire quoi que ce soit avec elle telle quelle. Nous pourrions mettre des rappels dans notre analyseur, mais ce serait très lourd et illisible. Au lieu de cela, nous renverrons un AST, un arbre représentant l'expression d'entrée :

 case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case Epsilon

Cela ressemble à nos règles, utilisant des classes de données simples.

Notre analyseur renvoie maintenant une structure de données utile :

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon

Pour eat() , error() et d'autres détails d'implémentation, veuillez consulter le référentiel GitHub qui l'accompagne.

Règles de simplification

Notre non terminal ExprOpt peut encore être amélioré :

 '+' NUM exprOpt | epsilon

Il est difficile de reconnaître le modèle qu'il représente dans notre grammaire simplement en le regardant. Il s'avère que nous pouvons remplacer cette récursivité par une construction plus simple :

 ('+' NUM)*

Cette construction signifie simplement '+' NUM se produit zéro fois ou plus.

Maintenant, notre grammaire complète ressemble à ceci :

 expr -> NUM exprOpt* exprOpt -> '+' NUM

Et notre AST est plus joli :

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int)

L'analyseur résultant est de la même longueur mais plus simple à comprendre et à utiliser. Nous avons éliminé Epsilon , qui est maintenant implicite en commençant par une structure vide.

Nous n'avions même pas besoin de la classe ExprOpt ici. Nous aurions pu simplement mettre case class Expr(num: Int, exprOpts: Seq[Int]) , ou au format grammaire, NUM ('+' NUM)* . Alors pourquoi pas nous ?

Considérez que si nous avions plusieurs opérateurs possibles, comme - ou * , alors nous aurions une grammaire comme celle-ci :

 expr -> NUM exprOpt* exprOpt -> [+-*] NUM

Dans ce cas, l'AST a alors besoin d' ExprOpt pour s'adapter au type d'opérateur :

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int)

Notez que la syntaxe [+-*] dans la grammaire signifie la même chose que dans les expressions régulières : "l'un de ces trois caractères". Nous verrons cela en action bientôt.

Interprète Composante 3 : Rédaction d'un interprète

Notre interpréteur utilisera notre lexer et notre analyseur pour obtenir l'AST de notre expression d'entrée, puis évaluera cet AST comme nous le souhaitons. Dans ce cas, nous avons affaire à des nombres, et nous voulons évaluer leur somme.

Dans l'implémentation de notre exemple d'interpréteur, nous utiliserons cette grammaire simple :

 expr -> NUM exprOpt* exprOpt -> [+-] NUM

Et cet AST :

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)

(Nous avons expliqué comment implémenter un lexer et un analyseur pour des grammaires similaires, mais tous les lecteurs bloqués peuvent parcourir les implémentations du lexer et de l'analyseur pour cette grammaire exacte dans le référentiel.)

Nous allons maintenant voir comment écrire un interpréteur pour la grammaire ci-dessus :

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp

Si nous analysons notre entrée dans un AST sans rencontrer d'erreur, nous sommes sûrs que nous aurons toujours au moins un NUM . Ensuite, nous prenons les nombres optionnels et les ajoutons (ou soustrayons-les) à notre résultat.

La note du début concernant l'associativité à gauche de + est maintenant claire : nous partons du nombre le plus à gauche et en ajoutons d'autres, de gauche à droite. Cela peut sembler sans importance pour l'addition, mais considérez la soustraction : L'expression 5 - 2 - 1 est évaluée comme (5 - 2) - 1 = 3 - 1 = 2 et non comme 5 - (2 - 1) = 5 - 1 = 4 !

Mais si nous voulons aller au-delà de l'interprétation des opérateurs plus et moins, il y a une autre règle à définir.

Priorité

Nous savons comment analyser une expression simple comme 1 + 2 + 3 , mais quand il s'agit de 2 + 3 * 4 + 5 , nous avons un petit problème.

La plupart des gens s'accordent sur la convention selon laquelle la multiplication a une priorité plus élevée que l'addition. Mais l'analyseur ne le sait pas. Nous ne pouvons pas simplement l'évaluer comme ((2 + 3) * 4) + 5 . Au lieu de cela, nous voulons (2 + (3 * 4)) + 5 .

Cela signifie que nous devons d' abord évaluer la multiplication . La multiplication doit être plus éloignée de la racine de l'AST pour forcer son évaluation avant l'addition. Pour cela, nous devons introduire encore une autre couche d'indirection.

Corriger une grammaire naïve du début à la fin

Il s'agit de notre grammaire originale, récursive à gauche, qui n'a pas de règles de priorité :

 expr -> expr '+' expr | expr '*' expr | NUM

Premièrement, nous lui donnons des règles de priorité et levons son ambiguïté :

 expr -> expr '+' term | term term -> term '*' NUM | NUM

Ensuite, il obtient des règles non récursives à gauche :

 expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUM

Le résultat est un AST magnifiquement expressif :

 case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)

Cela nous laisse avec une implémentation concise de l'interpréteur :

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmp

Comme auparavant, les idées du lexer et de la grammaire requis ont été couvertes plus tôt, mais les lecteurs peuvent les trouver dans le référentiel si nécessaire.

Prochaines étapes dans la rédaction d'interprètes

Nous n'avons pas couvert cela, mais la gestion et le signalement des erreurs sont des fonctionnalités cruciales de tout analyseur. En tant que développeurs, nous savons à quel point il peut être frustrant lorsqu'un compilateur produit des erreurs confuses ou trompeuses. C'est un domaine qui a de nombreux problèmes intéressants à résoudre, comme donner des messages d'erreur corrects et précis, ne pas dissuader l'utilisateur avec plus de messages que nécessaire, et récupérer gracieusement des erreurs. C'est aux développeurs qui écrivent un interpréteur ou un compilateur d'assurer à leurs futurs utilisateurs une meilleure expérience.

En parcourant nos exemples de lexers, d'analyseurs et d'interpréteurs, nous n'avons fait qu'effleurer la surface des théories derrière les compilateurs et les interpréteurs, qui couvrent des sujets tels que :

• Portées et tables de symboles
• Types statiques
• Optimisation au moment de la compilation
• Analyseurs de programmes statiques et linters
• Formatage du code et jolie impression
• Langages spécifiques à un domaine

Pour aller plus loin, je vous recommande ces ressources :

• Modèles d'implémentation de langage par Terence Parr
• Un livre en ligne gratuit, Crafting Interpreters , par Bob Nystrom
• Introduction aux grammaires et à l'analyse par Paul Klint
• Écrire de bons messages d'erreur du compilateur par Caleb Meredith
• Les notes du cours "Program Translation and Compiling" de l'East Carolina University