Comment construire un arbre de syntaxe abstrait

J’ai une idée générale de ce qu’est un AST, mais je veux savoir comment en construire un.

Si on vous donne une grammaire et un arbre d’parsing, comment construisez-vous l’AST?

Comment faites-vous si vous recevez une grammaire et une expression?

Eh bien, tout d’abord, la grammaire est utilisée pour construire un arbre d’parsing à partir d’une expression. Donc, si vous avez déjà un arbre d’parsing, vous n’avez pas besoin de la grammaire.

Selon la quantité de travail de votre parsingur, l’arborescence obtenue à partir de l’parsing d’une expression peut déjà être un arbre de syntaxe abstrait. Ou il pourrait s’agir d’un simple arbre d’parsing qui nécessite une seconde passe pour construire l’ast.

Pour construire l’arbre d’parsing à partir d’une grammaire et d’une expression, vous devez d’abord convertir votre grammaire en code de travail. En règle générale, vous divisez le travail en un tokenizer qui divise le stream d’entrée représentant l’expression en une liste de jetons, et un parsingur qui prend la liste des jetons et en construit un arbre d’parsing.

Donc, l’expression 1 + 2*(3+4) pourrait être divisée en une liste de jetons comme ceci:

 1 - int + - add_operator 2 - int * - mul_operator ( - lparen 3 - int + - add_operator 4 - int ) - rparen 

La première colonne est la valeur réelle du texte. La seconde représente le type de jeton. Ces jetons sont introduits dans l’parsingur, qui est construit à partir de votre grammaire et reconnaît les jetons et construit l’arbre d’parsing.

Alors, comment on écrit le tokenizer lexical et le parseur réel? Vous pourriez rouler à la main. Ou, plus communément, utilisez un générateur d’parsingur syntaxique comme Coco ou Antlr ou Lex / Yacc. Ces outils prennent une description de votre grammaire et génèrent le code pour un tokenzier et un parsingur syntaxique. (Les générateurs de code existent pour la plupart des langages populaires et certains impopulaires.)

Comment vous construisez votre parsingur dépend fortement de la langue que vous utilisez. Comment vous pourriez écrire un parsingur dans Haskell est complètement différent de la façon dont vous le feriez dans, disons, C.

  • Voici un tutoriel qui vous montre comment construire votre propre parsingur de descente récursif .

  • Coco est un générateur d’parsingurs syntaxiques pour différentes langues, accompagné d’une documentation sur la manière de commencer.

  • Si Python est votre truc, alors pyparsing peut-être pour vous.

Je vais répondre à cela d’un sharepoint vue général, sans essayer de parler de lexers et de parseurs.

Un arbre d’parsing contient des symboles non-terminaux qui font partie d’une grammaire sans contexte, et montre la chaîne de productions pour obtenir une chaîne composée de symboles terminaux, de manière récursive ou non. Donc, quand vous avez l’arbre d’parsing, vous n’avez pas besoin de la grammaire – vous pouvez dériver la grammaire de l’arbre d’parsing.

Un AST ne contient aucun symbole non terminal. Il ne contient que des symboles.

Exemple:

  E | E + T | | TM * M | | | M ab | a 

Quelle est une version très rapide de l’affichage d’ a+a*b . Notez que la manière dont l’arbre syntaxique abstrait est interprété dépend de la priorité de l’arborescence, du type de parcours que vous effectuez (dans l’ordre, en pré-commande, en post-ordre). Cependant, en général, l’AST pour cet arbre d’parsing peut ressembler à ceci:

  + | | a * | | ab