Re: Parsing techniques (Steve Meyer)
15 Dec 1996 16:02:06 -0500

          From comp.compilers

Related articles
[7 earlier articles]
Re: Parsing techniques (1996-12-01)
Re: Parsing techniques (1996-12-03)
Re: Parsing techniques (Ron House) (1996-12-07)
Re: Parsing techniques (1996-12-09)
Re: Parsing techniques (Terence Parr) (1996-12-09)
Re: Parsing techniques (Terence Parr) (1996-12-09)
Re: Parsing techniques (1996-12-15)
| List of all articles for this month |

From: (Steve Meyer)
Newsgroups: comp.compilers
Date: 15 Dec 1996 16:02:06 -0500
Organization: CRL Dialup Internet Access
References: 96-11-157 96-12-015
Keywords: parse, LL(1), LALR, C++

>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


[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]


Post a followup to this message

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