是否有可能使用遞歸下降解析器來驗證語法並同時構建解析樹？

Question

是否有可能在我使用遞歸下降解析器檢查數據是否匹配語法的同時生成解析樹？

如果是這樣，我會用遞歸下降的方式來構建一棵樹嗎？

謝謝，Boda Cydo。

注：我是新來解析。 （被問及幾個關於SO的問題，並且我對它越來越好。）

Answer 1

是的，這是可能的。如何做到這一點取決於你想要的實現。下面是可能會爲你工作的例子：

首先，定義您的節點：

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

接下來，你需要的是融入你的遞歸下降功能：

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

正如你下降你的分析樹，你可能會想發送任何新的「根」節點，以便可以將子節點添加到它。或者，parseSubtree可以創建並返回節點，然後將其添加到根節點。

您可以使用上述過程來構建分析樹或簡單的抽象樹。由於解析函數返回將引用任何和所有子節點的根節點，因此解析後您將可以完全訪問解析樹。

無論您使用異構還是同構分析樹，您都需要一種方法來存儲足夠的信息以使其有用。