Produire des expressions à partir de cette grammaire avec la descente récursive

Question

J'ai une grammaire simple. En fait, la grammaire que j'utilise est plus complexe, mais c'est le plus petit sous-ensemble qui illustre ma question.

Expr ::= Value Suffix 
     | "(" Expr ")" Suffix 

Suffix ::= "->" Expr 
     | "<-" Expr 
     | Expr 
     | epsilon 

Value identificateurs de matchs, des chaînes, des nombres, et cetera. La règle Suffix est là pour éliminer la récursivité gauche. Cela correspond à des expressions telles que:

a -> b (c -> (d) (e)) 

C'est un graphique où a va à la fois b et le résultat de (c -> (d) (e)) et c va d et e. J'essaie de produire un arbre de syntaxe abstraite pour ces expressions, mais je rencontre des difficultés car tous les opérateurs peuvent accepter n'importe quel nombre d'opérandes de chaque côté. Je préfère garder la logique de production de l'AST dans les méthodes d'analyse par descente récursives, car cela évite d'avoir à dupliquer la logique d'extraction d'une expression. Ma stratégie actuelle est la suivante:

1. Si un Value apparaît, pousser à la sortie.

2. Si un From ou To apparaît:

   1. sortie un séparateur.

   2. Obtenez le suivant Expr.

   3. Créez un noeud Link.

   4. Faites apparaître le premier ensemble d'opérandes à partir de la sortie dans le Link jusqu'à ce qu'un séparateur apparaisse.

   5. Effacez le séparateur découvert.

   6. Pop le deuxième ensemble d'opérandes dans le Link jusqu'à un séparateur.

   7. Poussez le Link vers la sortie.

Si je lance ce à travers sans obéir les étapes 2.3 – 2.7, je reçois une liste des valeurs et des séparateurs.Pour l'expression citée plus haut, a -> b (c -> (d) (e)), la sortie doit être:

A sep_1 B sep_2 C sep_3 D E 

En appliquant la règle To alors le rendement:

A sep_1 B sep_2 (link from C to {D, E}) 

Et ensuite:

(link from A to {B, (link from C to {D, E})}) 

La chose importante à noter est que sep_2, crucial pour délimiter les opérandes gauche de la deuxième ->, n'apparaît pas, de sorte que l'analyseur estime que l'expression a été écrit:

a -> (b c -> (d) (e)) 

Afin de résoudre avec ma stratégie actuelle, il me faudrait un moyen de produire un séparateur entre les expressions adjacentes, mais seulement si l'expression actuelle est une expression From ou To enfermé dans parenthèses. Si c'est possible, alors je ne le vois pas et la réponse devrait être simple. Cependant, s'il y a une meilleure façon de procéder, n'hésitez pas à me le faire savoir!

Answer 1

Je n'ai pas essayé de l'analyser en détail, mais: « From ou To expression entre parenthèses » commence à sembler beaucoup comme « dépendant du contexte », qui descente récursive ne peut pas gérer directement. Pour éviter la dépendance au contexte, vous aurez probablement besoin d'une production séparée pour un From ou To entre parenthèses contre From ou To sans les parenthèses.

Edit: Bien qu'il soit trop tard pour faire du bien, si ma compréhension de ce que vous voulez faire correspondre est correct, je pense que je l'écris plus comme ceci:

Graph := 
     | List Sep Graph 
     ; 

Sep := "->" 
    | "<-" 
    ; 

List := 
     | Value List 
     ; 

Value := Number 
     | Identifier 
     | String 
     | '(' Graph ')' 
     ; 

Il est difficile de Soyez certain, mais je pense que cela devrait au moins être proche de la correspondance (seulement) les entrées que vous voulez, et devrait rendre raisonnablement facile de générer un AST qui reflète l'entrée correctement.