Comment construire un arbre de syntaxe abstraite

Question

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

Si vous êtes donné une grammaire et d'un arbre d'analyse, comment voulez-vous construire l'AST?

Comment faites-vous si vous êtes donné une grammaire et une expression?

Answer 1

Bien, tout d'abord, la grammaire est utilisée pour construire un arbre d'analyse à partir d'une expression.

Donc, si vous avez déjà un arbre d'analyse, vous n'avez pas besoin de la grammaire.

En fonction de la quantité de travail de votre analyseur n', l'arbre résultant qui est formé à partir de l'analyse d'une expression peut-être déjà un arbre de syntaxe abstraite. Ou il pourrait être un simple arbre d'analyse qui nécessite une deuxième phase de construction de l'ast.

Pour construire l'arbre d'analyse à partir d'une grammaire et d'une expression, il faut d'abord convertir votre grammaire dans le code du travail.

En règle générale, vous répartir le travail dans un générateur de jetons qui divise le flux d'entrée représentant l'expression dans une liste de jetons, et un analyseur qui prend la liste de jetons et construit un arbre d'analyse\ast à partir d'elle.

Donc l'expression "1 + 2*(3+4)" peut être divisé 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 réelle valeur de texte. Le deuxième représente le type de jeton.

Ces jetons sont introduits dans l'analyseur, qui est construit à partir de votre grammaire et reconnaît les jetons et construit l'arbre d'analyse.

Alors, comment écrit-on l'lexicale tokenizer et le réel de l'analyseur? Vous pourriez rouler à la main.

Ou, plus communément, l'utilisation d'un analyseur générateur de coco ou antlr ou de la lex\yacc. Ces outils prennent une description de votre grammaire et de générer le code pour un tokenzier et de l'analyseur.

Des générateurs de Code pour la plupart des langues populaires et certains impopulaire aussi bien.

Comment vous construisez votre analyseur dépend fortement de ce que la langue que vous utilisez.

Comment vous écrire un analyseur en Haskell est entièrement différent de la façon dont vous le feriez dans, disons, C.

Voici un tutoriel qui vous montre comment construire votre propre descente récursive de l'analyseur. Ses une ancienne, mais toujours bon: nous allons construire un compilateur

Coco est un analyseur générateur de diverses langues. C'est également livré avec une documentation sur la façon de commencer: Coco

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