Recursive descent parser questions

Question

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

The first is what when you have a nonterminal that can match one of a few different nonterminals? How do you check which way is correct?

Second, how do you build an AST? Using YACC, I can just write a piece of code to execute for every instance of a nonterminal and it has special variables which refer to the "values" of the rules. How do you do a similar thing in a recursive descent parser?

Answer 1

Or a leasson in how to give yourself a stroke in one easy leasson.

The first is what when you have a nonterminal that can match one of a few different nonterminals? How do you check which way is correct?

You need to look ahead in the stream and make a decision. Its hard to do backtracking on a RDC.

An easier solution is to design your grammar so that it does not need to look ahead (hard).

Second, how do you build an AST?

The return value from the function call is the tree for everything that was parsed by the call. You wrap all the sub calls into another dynamically allocated object and return that.

Answer 2

1. You try them in order, then backtrack on failure. Or you prove that your language is in LL(k) and look at most k symbols ahead.
2. For each successful parse of a rule, you construct an object from the result of subrules.

E.g.,

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