Is it possible to use a recursive descent parser to check the grammar and assemble the parse tree at the same time?

Question

Is it possible to generate a parsing tree at the same time using a recursive descent analyzer to check if the data matches the grammar?

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

Thanks, Boda Sido.

Note. I am new to parsing. (Asked a few questions about SO already, and I'm improving with it.)

Answer 1

Yes it is possible. How to do this will depend on the desired implementation. Here's a sample that might work for you:

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

Then you will need to integrate this 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 the parsing tree, you will probably want to send any new “root” node so that children can be added to it. Alternatively, parseSubtree can create and return a node, which will then be added to the root directory of the node.

You can create either a parsing tree or just an abstract tree using the process described above. Since the parse function returns the root directory of the node, which will refer to any and all child nodes, you will get full access to the parsing tree after parsing.

If you are using a heterogeneous or homogeneous parse tree, you will need a way to store enough information to make it useful.