使用递归下降分析器既能验证语法又能同时构建解析树，这种做法可行吗？

Question

使用递归下降分析器既能验证语法又能同时构建解析树，这种做法可行吗？

parsingrecursive-descentparse-tree

8

在使用递归下降解析器检查数据是否符合语法的同时，生成解析树是否可能？

如果可以，我应该使用什么方法来构建解析树呢？

谢谢，Boda Cydo。

注意：我是新手。（已在SO上提出了几个问题，并且我正在变得更加熟练。）

- bodacydo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kaleb Pederson · Accepted Answer

是的，这是可能的。如何实现取决于您想要的具体实现方式。以下是一个可能适用于您的示例：

首先，定义您的节点：

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

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

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