Re: [boost] Yacc, lex, and C++

From: David Abrahams (david.abrahams_at_[hidden])
Date: 2002-02-26 13:05:47

----- Original Message -----
From: "Kevin S. Van Horn" <kevin.vanhorn_at_[hidden]>

> David Abrahams writes:
>
> > Most good C++ parsers use recursive descent, as I understand it.
>
> I don't think so.  A recursive descent parser has to be nondeterministic
> -- and hence do LOTS of backtracking -- in order to parse expressions
> involving infix operators.  The problem is that, unless every production
> begins with one or more terminal symbols that is distinct from the initial
> symbols of all other rules, a recursive-descent parsers won't know which
> is the right rule to apply at every step, and so will have to try every
> possibility.  This also means that it needs the entire token sequence all
> available at once (forward iterator, not input iterator), as there's no
> telling how far it might have to backtrack.

Guess what? C++ compiler developers know this, and many do it anyway. I know
of several implementations which work that way. In fact, the fastest C++
parser I know of works that way. I think it's partly because you need
arbitrary lookahead for C++ anyway (at least, that's what I think I
overheard a compiler-writer say at a recent committee meeting).

-Dave