是否有可能使用递归下降解析器来验证语法并同时构建解析树？

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可以创建并返回节点，然后将其添加到根节点。

您可以使用上述过程来构建分析树或简单的抽象树。由于解析函数返回将引用任何和所有子节点的根节点，因此解析后您将可以完全访问解析树。

无论您使用异构还是同构分析树，您都需要一种方法来存储足够的信息以使其有用。