是否可以使用递归下降解析器来验证语法并同时构建解析树? [英] Is it possible to use Recursive Descent Parser to both verify the grammar AND build the parse tree at the same time?

问题描述

在使用递归下降解析器检查数据是否与语法匹配的同时，是否可以生成解析树?

Is it possible to generate a parse tree at the same time as I use recursive descent parser to check if the data matches grammar?

如果是这样，当我递归下降时，我将使用哪种方法来构建树?

If so, what approach would I use to build a tree as I recursively descent?

感谢Boda Cydo.

Thanks, Boda Cydo.

注意:我是解析新手. (已经在SO上提出了几个问题，而我对此情况有所改善.)

Note: I am new to parsing. (Asked several questions on SO already, and I am getting better with it.)

推荐答案

是的，有可能.如何执行将取决于您想要的实现.这是一个可能适合您的示例:

Yes, it's possible. How to do so will depend on the implementation you want. Here's a sample that might work for you:

首先，定义您的节点:

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

下一步，您需要将其集成到递归下降函数中:

Next, you'll need to integrate that into your recursive descent functions:

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

As you descend down your parse tree, you'll probably want to send whatever the new "root" node is, so that children can be added to it. Alternatively, parseSubtree could create and return a node, which would then be added to the root node.

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

You could build either the parse tree or a simple abstract tree using the above process. Since the parse function returns the root node, which will reference any and all children nodes, you'll have full access to the parse tree after parsing.

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

Whether you use a heterogeneous or homogeneous parse tree, you'll need a way to store sufficient information to make it useful.

这篇关于是否可以使用递归下降解析器来验证语法并同时构建解析树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！