William D Clinger <cesuraSPAM@verizon.net> wrote:
+---------------
| William Bland asked:
| > 2) is this what people mean when they say "recursive descent parser"?
|
| A recursive descent parser is an LL(1) parser that's implemented
| along the lines you gave. A parser that's implemented along those
| lines but isn't LL(1) is not a recursive descent parser. It might
| be recursive descent with backup, or even worse, but it isn't a
| recursive descent parser.
+---------------
To expand a little (though rather informally and not very precisely)
on what Will said, an LL(1) grammar is one in which the next production
(non-terminal) to be reduced can be determined just from looking at the
next terminal symbol encountered in the input stream. This means that
it works very much better if you have a separate lexical analyzer in
front of it so that the LL(1) parser is looking at "tokens", not raw
characters.
That said, recursive descent parsers work *very* well on "keyword"-
style grammars, such as are used in classical Algol-like control
structures (IF/THEN/ELSE/FI, etc.), but not so well for things like
complex arithmetic expressions.
Fortunately, when building small ad-hoc parsers (such as the one you
[Bland] seem to be working on), there is a very useful hybrid parsing
technique which I first encountered in the BLISS-10 compiler [also
see Wulf, et al, "The Design of an Optimizing Compiler", on BLISS-11],
and have used with great success myself in several small projects:
Combine a recursive descent parser for control structures (and other
"large" features) with a simple-operator-precedence parser for arithmetic
expressions. The way you hook these together is to make the LL(1)
"keywords" be "operators" with a *very* high precedence (higher than
any normal arithmetic operator), so that when you encounter one of
them you always try to reduce it first. Since the recursive descent
routines call the simple-operator-precedence parser to parse any
subexpressions, the two styles nicely weave back & forth between
themselves.
-Rob
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607