是否可以使用Recursive Descent Parser来验证语法并同时构建解析树？

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可以创建并返回一个节点,然后将该节点添加到根节点.

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

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