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

From: Kevin S. Van Horn (kevin.vanhorn_at_[hidden])
Date: 2002-02-26 12:50:37

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.