Re: Yacc, lex, and C++

From: Kevin S. Van Horn (kevin.vanhorn_at_[hidden])
Date: 2002-02-28 14:38:19

Thanks for all of the useful replies.  ANTLR looks especially interesting.  I
hadn't known that there had been significant advances in parsing since I
learned this stuff.  I've downloaded the ANTLR book and am taking a look at
it.

> It's really quite trivial for a handwritten
> recursive descent parser to parse infix expressions with no
> backtracking and single token lookahead:
>
> [...]
>
> Or have I misunderstood you entirely?

There is a problem if you have left associativity and you want to do strict
recursive descent in terms of the production rules of a CFG:

E -> T | E + T | E - T
T -> F | T * F | T / F
F -> variable | literal

The problem here is that when you see "x * 3 + y * 7 / 3 - 6 - x * y", you
don't know where the "E" in "E - T" ends unless you look far ahead.

What you've done is to use EBNF:

E -> T { A T }*
A -> + | -
T -> F { M F }*
M -> * | /
F -> variable | literal

which solves the problem, as long as complete expressions are always followed
by EOF or some token that cannot start an expression.

When I learned parsers we always used bottom-up parsing for infix
expressions, and that's the YACC method too, so I didn't consider this
approach.