Is it possible to use Recursive Descent Parser to both verify the grammar AND build the parse tree at the same time?

Question

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?

Thanks, Boda Cydo.

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

Kaleb Pederson Kaleb Pederson · Accepted Answer · 2010-03-10T20:01:54

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

First, define your node:

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

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.

Is it possible to use Recursive Descent Parser to both verify the grammar AND build the parse tree at the same time?

1 Answers