Ist es möglich, Recursive Descent Parser zu verwenden, um sowohl die Grammatik zu überprüfen als auch gleichzeitig den Parse-Baum zu erstellen?

Question

Ist es möglich, einen Parse-Baum gleichzeitig mit dem rekursiven Descent-Parser zu generieren, um zu überprüfen, ob die Daten mit der Grammatik übereinstimmen?

Wenn ja, welchen Ansatz würde ich verwenden, um einen Baum zu erstellen, wie ich rekursiv absteigend?

Danke, Boda Cydo.

Hinweis: Ich bin neu beim Parsen. (Ich habe schon einige Fragen zu SO gestellt, und es geht mir immer besser.)

Answer 1

Ja, das ist möglich. Wie das geht, hängt von der gewünschten Implementierung ab. Hier ist ein Beispiel, das für Sie arbeiten könnte:

Zunächst definieren Sie Ihre Knoten:

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

Als Nächstes müssen Sie das in Ihre rekursiven Abstiegs-Funktionen integrieren:

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

Wie Sie Wenn Sie den Parserbaum herunterfahren, werden Sie wahrscheinlich den neuen "root" -Knoten senden müssen, damit Kinder hinzugefügt werden können. Alternativ könnte parseSubtree einen Knoten erstellen und zurückgeben, der dann zum Stammknoten hinzugefügt würde.

Sie können entweder den Syntaxbaum oder einen einfachen abstrakten Baum mithilfe des obigen Prozesses erstellen. Da die Syntaxanalysefunktion den Wurzelknoten zurückgibt, der auf alle untergeordneten Knoten verweist, haben Sie nach dem Parsen vollständigen Zugriff auf den Syntaxbaum.

Unabhängig davon, ob Sie einen heterogenen oder homogenen Syntaxbaum verwenden, benötigen Sie eine Möglichkeit, ausreichende Informationen zu speichern, um sie nützlich zu machen.