Bâtiment d'analyse des arbres avec analyse de changement de vitesse

Question

J'essaie d'analyser sur mon temps libre et je voulais mettre en œuvre un analyseur de changement de vitesse pour une grammaire très simple. J'ai lu de nombreux articles en ligne mais je suis toujours confondu sur la façon de créer des arbres d'analyse. Voici un exemple de ce que je veux faire:

---

grammaire:

Expr -> Expr TKN_Op Expr 
Expr -> TKN_Num

Voici un exemple d'entrée:

1 + 1 + 1 + 1

que, après la jocalisation, devient:

TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num

---

Je comprends que:

1. changeant signifie pousser le premier jeton d'entrée sur la pile et le retirer de l'entrée
2. Réduire signifie substituer un ou plusieurs éléments sur la pile avec un élément de grammaire

Donc, essentiellement, cela devrait arriver:

Step 1:
    Stack:
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Stack is empty. Shift.

Step 2:
    Stack: TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.

Step 3:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 4:
    Stack: Expr TKN_Op 
    Input: TKN_Num TKN_Op TKN_Num TKN_Op TKN_Num
    What: Cannot reduce. Shift.

Step 5:
    Stack: Expr TKN_Op TKN_Num
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: TKN_Num can be reduced to Expr. Reduce.
    // What should I check for reduction? 
    // Should I try to reduce incrementally using 
    // only the top of the stack first, 
    // then adding more stack elements if I couldn't
    // reduce the top alone?

Step 6:
    Stack: Expr TKN_Op Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: Expr TKN_Op Expr can be reduced to Expr. Reduce.

Step 7:
    Stack: Expr
    Input: TKN_Op TKN_Num TKN_Op TKN_Num
    What: ...
    // And so on...

En dehors des "Que réduire?" doute, je n'ai aucune idée de construire correctement un arbre d'analyse. L'arbre devrait probablement ressembler à ceci:

1    +    o
          |
     1    +    o
               |
          1    +    1

Devrais-je créer un nouveau nœud sur la réduction?

Et quand devrais-je ajouter des enfants au nouveau nœud Créer / lorsque dois-je créer un nouveau nœud racine?

Answer 1

La chose simple et évidente à faire est de créer un nœud d'arbre sur chaque réduction et d'ajouter les nœuds d'arbre des éléments de grammaire réduits à ce nœud d'arbres.

Ceci est facilement géré avec une pile de nœuds qui fonctionne en parallèle à la pile "Token Shift" que l'analyseur brut utilise. Pour chaque réduction pour une règle de longueur n, la pile de jeton de décalage est raccourcie par N, et le jeton non mortminal est poussé sur la pile de décalage. Dans le même temps, raccourcissez la pile de nœud en retirant les nœuds TOP N, créez un nœud pour le non-déterminant, connecté aux nœuds N retirés en tant qu'enfants et appuyez sur ce nœud sur la pile de nœuds.

Cette stratégie fonctionne même avec des règles qui ont la main droite de zéro à droite: créer un nœud d'arbre et attacher le jeu d'enfants vide à celui-ci (par exemple, créer un nœud de feuille).

Si vous pensez à un "décalage" sur un nœud de terminal comme une réduction (des caractères formant la borne) sur le nœud Terminal, le nœud Terminal se déplace correctement. Créez un nœud pour le terminal et poussez-le sur la pile.

Si vous le faites, vous obtenez une "syntaxe en béton / analyse d'analyse" qui correspond à la grammaire isomorphique. (Nous faisons cela pour un outil commercial que j'offre). Il y a beaucoup de gens qui n'aiment pas ces arbres en béton, car ils contiennent des nœuds pour les mots-clés, etc., qui n'ajoute pas vraiment beaucoup de valeur. Vrai, mais de tels arbres sont extrêmement faciles à construire, et suprêmement faciles à comprendre parce que la grammaire est la structure des arbres. Lorsque vous avez 2500 règles (comme nous le faisons pour un analyseur complet de Cobol), cela compte. Ceci est également pratique car tout le mécanisme peut être construit complètement dans l'infrastructure d'analyse. L'ingénieur de la grammaire écrit simplement des règles, l'analyseur tourne, le tourisme, un arbre. Il est également facile de changer la grammaire: changez simplement, voilà, vous obtenez toujours des arbres.

Cependant, si vous ne voulez pas d'arborescence concrete, vous voulez un "arborescence de syntaxe abstraite", puis ce que vous avez à faire est de laisser le contrôle de la grammaire de la réduction des nœuds génère des nœuds; Ajout généralement une certaine pièce jointe de procédure (code) à chaque règle de grammaire à exécuter sur une étape de réduction. Ensuite, si une telle attachement procédurale produit un nœud, il est conservé sur une pile de nœuds. Toute pièce jointe procédurale qui produit un nœud doit fixer des nœuds produites par les éléments de la main droite. Si c'est ce que c'est ce que YACC / BISISON / ... La plupart des moteurs d'analyseurs réduits de changement de vitesse font. Allez en savoir plus sur YACC ou BISON et examinez une grammaire. Ce système vous donne beaucoup de contrôle, au prix d'insister sur le fait que vous prenez ce contrôle. (Pour ce que nous faisons, nous ne voulons pas que ce nouvel effort d'ingénierie dans la construction d'une grammaire).

Dans le cas de la production de CST, il est extrêmement simple d'éliminer les nœuds "inutiles" des arbres; Nous faisons cela dans notre outil. Le résultat est beaucoup comme une AST, sans effort manuel pour écrire toutes ces pièces jointes procédurales.

Answer 2

La raison de votre problème est que vous avez un conflit de quart / réduit dans votre grammaire:

expr: expr OP expr
    | number

Vous pouvez résoudre ce problème de 2 façons:

expr: expr OP number
    | number

pour les opérateurs associatifs gauche, ou

expr: number OP expr
    | number

Pour les bons associatifs. Cela devrait également déterminer la forme de votre arbre.

La réduction est généralement effectuée lorsqu'une clause est détectée complète. Dans le bon boîtier associatif, vous commencerez dans un état 1 qui s'attend à ce qui s'attend à un nombre, la pousse à la pile de valeurs et passe à l'état 2. Dans l'état 2, si le jeton n'est pas un op, vous pouvez réduire un nombre à une expr. . Sinon, appuyez sur l'opérateur et passez à l'état 1. Une fois l'état 1 terminé, vous pouvez réduire le nombre, l'opérateur et l'expression à une autre expression. Remarque, vous avez besoin d'un mécanisme pour "retour" après une réduction. L'analyseur global commencerait alors à l'état 0, par exemple, qui va immédiatement à l'état 1 et accepte après la réduction.

Notez que les outils tels que YACC ou BISON font ce genre de choses beaucoup plus facilement car ils apportent toutes les machines de bas niveau et les piles.