Re: LL vs LR, strengths and weaknesses

ressler@cs.cornell.edu (Gene Ressler) writes:
[How C's 16 precedence levels induce massive stack growth when you
  hit expressions with lots of parentheses]
>(For starters, I believe this is why at least some RD parsers have
>embedded operator precedence parsers to do arithmetic.)


In fact, I once modified a RD parser to use operator precedence ideas
to reduce recursion in the face of parentheses. It was really bad with
cfront output, where there seem to be more paren's than white space.


It turned out that the OP version was much more concise than the pure
RD version, which had 16 versions of "expr : expr op expr" to manage
the precedence. The key thing to note is that all you get from
precedence is the resolution of a shift-reduce conflict. So, code
a RD parser that uses precedence to resolve the conflict, rather than
simple lookahead:




Expr expr(Token op0) {
        Expr e1 = primary();
        while (shift_prec[nextToken] > reduce_prec[op0]) {
Token op1 = nextToken;
match(op1);
Expr e2 = expr(op1);
e1 = GenOp(op1, e1, e2);
        }
        return e1;
}




As I recall, there were a few hacks needed. For example, ?: takes
three operands. This was a few years ago, so it is getting fuzzy.


Bob
--

Return to the comp.compilers page.
Search the comp.compilers archives again.