È possibile utilizzare il parser di discendenza ricorsiva per verificare la grammatica e costruire l'albero di analisi contemporaneamente?

Question

È possibile generare un albero di analisi nello stesso momento in cui utilizzo il parser di discesa ricorsivo per verificare se i dati corrispondono alla grammatica?

In tal caso, quale approccio utilizzerei per costruire un albero mentre ricominciamo a discendere?

Grazie, Boda Cydo.

Nota: sono nuovo nell'analisi. (Ho già fatto diverse domande su SO e sto migliorando.)

Answer 1

Sì, è possibile. Come farlo dipenderà dall'implementazione che desideri. Ecco un esempio che potrebbe funzionare per voi:

In primo luogo, definire il nodo:

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); 
} 

successivo, è necessario integrare che nelle vostre funzioni discesa ricorsiva:

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); 
    } 
} 

Come si scendi lungo il tuo albero di analisi, probabilmente vorrai inviare qualunque sia il nuovo nodo "root", in modo che i bambini possano essere aggiunti ad esso. In alternativa, parseSubtree potrebbe creare e restituire un nodo, che verrà quindi aggiunto al nodo radice.

È possibile creare l'albero di analisi o un albero astratto semplice utilizzando il processo precedente. Poiché la funzione parse restituisce il nodo root, che farà riferimento a qualsiasi e tutti i nodi figli, avrai accesso completo all'albero di analisi dopo l'analisi.

Se si utilizza un albero di analisi eterogeneo o omogeneo, è necessario un modo per memorizzare informazioni sufficienti per renderlo utile.