Est-il possible d'utiliser l'analyseur de descente récursif pour vérifier la grammaire ET construire l'arbre d'analyse en même temps?

Question

Est-il possible de générer une arborescence d'analyse en même temps que j'utilise un analyseur de descente récursif pour vérifier si les données correspondent à la grammaire?

Si oui, quelle approche utiliserais-je pour construire un arbre en descendant récursivement?

Merci, Boda Cydo.

Note: Je suis novice en analyse syntaxique. (J'ai déjà posé plusieurs questions sur SO, et je m'améliore avec ça.)

Answer 1

Oui, c'est possible. Comment le faire dépendra de l'implémentation que vous voulez. Voici un exemple qui pourrait fonctionner pour vous:

D'abord, définir votre noeud:

class ParseTreeNode { 
    private final String name; 
    private final List<ParseTreeNode> children = /* new */; 
    public ParseTreeNode(String name) { 
    this.name = name; 
    } 
    public void addChild(ParseTreeNode child) { 
    children.add(child); 
} 

Ensuite, vous aurez besoin d'intégrer cela dans vos fonctions de descente récursive:

class RDParser { 
    ParseTreeNode parse(Input input) { 
    ParseTreeNode root = createParseTreeNodeNamed("Root") 
    switch (input.nextToken()) { 
     case OPT1: 
     root.addChild(createParseTreeNodeNamed("Opt1")); 
     break; 
     case OPT2: 
     while (/*someCondition*/) { 
      root.addChild(createParseTreeNodeNamed("Opt2-sibling" + /* i */)); 
     } 
     case SUBTREE: 
     ParseTreeNode subtree = createParseTreeNodeNamed("Subtree"); 
     root.addChild(subtree); 
     parseSubtree(subtree, input); 
     break; 
     default: 
     error("Input %s was not in the expected first/follow sets", input.nextToken()); 
    } 
    } 
    void parseSubtree(ParseTreeNode node, Input input) { 
    node.addChild(createParseTreeNodeNamed("subtree-child")); 
    /* ... */ 
    } 

    /* and other functions do similarly */ 
    ParseTreeNode createParseTreeNodeNamed(String name) { 
    return new ParseTreeNode(name); 
    } 
} 

Comme vous descendez dans votre arbre d'analyse, vous voudrez probablement envoyer le nouveau nœud "root", afin que les enfants puissent y être ajoutés. En variante, parseSubtree pourrait créer et renvoyer un nœud, qui serait ensuite ajouté au nœud racine.

Vous pouvez créer l'arborescence d'analyse ou un simple arbre abstrait en utilisant le processus ci-dessus. Puisque la fonction d'analyse renvoie le nœud racine, qui référencera tous les nœuds enfants, vous aurez un accès complet à l'arborescence d'analyse après l'analyse. Que vous utilisiez un arbre d'analyse hétérogène ou homogène, vous aurez besoin d'un moyen de stocker suffisamment d'informations pour le rendre utile.