Parser recursive descent issues

Question

I have two questions on how to write a recursive descent parser:

First, when do you have a non-terminal that can match one of several different non-terminals? How do you check which path is correct?

Secondly, how do you build AST? Using YACC, I can simply write a piece of code to execute for each instance of the nonterminal and have special variables that refer to the "values" of the rules. How do you do this in a recursive descent parser?

Answer 1

• You will try them in order, and then step back from the failure. Or you prove that your language is in LL (k) and is looking at more than k characters in front.
• For each successful rule analysis, you create an object from the result of the sub steering.

eg.

class ASTNode { public: virtual int eval() = 0; virtual ~ASTNode() = 0; }; // construct this when parsing an integer literal class Value : ASTNode { int v; public: Value(int v_) : v(v_) {} virtual int eval() { return v; } virtual ~Value() {} }; // construct this when parsing "x+y" class Addition : ASTNode { ASTNode *left, *right; public: Addition(ASTNode *l, ASTNode *r) : left(l), right(r) {} virtual int eval() { return l->eval() + r->eval(); } virtual ~Addition() { delete left; delete right; } }; 

Answer 2

Or leasson on how to give yourself a punch in one easy leasson.

First, when do you have a non-terminal that can match one of several different non-terminals? How do you check which path is correct?

You need to look in the stream and make a decision. Its hard to roll back to RDC.

A simpler solution is to develop your grammar, so it does not need to look ahead (hard).

Secondly, how do you build an AST?

The return value of the function call is a tree for everything that has been parsed by the call. You transfer all the subheadings to another dynamically allocated object and return this.