Re: Parsing techniques

>Where do hand-coded, recursive decent parsers fall into the mix? I
>haven't read too much about them, but it seems that error recovery
>would be terribly difficult. I am looking for the Wirth book on this
>subject of which I have heard good reviews.


It seems to me hand coded recursive descent parsers are provably
smaller and faster than table driven parsers because the computer
program implementing the parser is as a powerful as a turing maching
while table driven parsers are limited to the computing power of a
push down automata (PDA). PDAs are provably weaker in space and time
than turing machines.


The advantage of parser generators, in my view, is to quickly get a
lexical analyzer and parser working if one has a grammar sitting
around.


/Steve


[There's no particular relationship between the relative theoretical
power of two algorithms and the size or speed of two implementations.
For example, if you compare an open coded RD parser on a RISC machine
with large instructions versus a table-driven parser that used a
compact table representation, the table-driver parser would probably
be smaller. Which runs faster depends on everything from the number
of instructions to cache misses to page faults. Earley's algorithm is
one of the most powerful parsing schemes, and it can even handle very
ambiguous grammars, but the implementations of it that I've used have
all been impressively slow. -John]


--

Return to the comp.compilers page.
Search the comp.compilers archives again.