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).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk