LL(1) vs LALR(1) parsers

Odd Arild Olsen <oaolsen@login.eunet.no>
Sat, 4 Nov 1995 21:55:01 GMT

          From comp.compilers

Related articles
LL(1) vs LALR(1) parsers oaolsen@login.eunet.no (Odd Arild Olsen) (1995-11-04)
Re: LL(1) vs LALR(1) parsers krish@cs.purdue.edu (Saileshwar Krishnamurthy) (1995-11-09)
Re: LL(1) vs LALR(1) parsers sc@iaxp01.inf.uni-jena.de (Sebastian Schmidt) (1995-11-10)
Re: LL(1) vs LALR(1) parsers the_tick@access5.digex.net (1995-11-10)
Re: LL(1) vs LALR(1) parsers parrt@lonewolf.parr-research.com (1995-11-14)
Re: LL(1) vs LALR(1) parsers simmons@bnr.ca (steve (s.s.) simmons) (1995-11-15)
Re: LL(1) vs LALR(1) parsers parrt@parr-research.com (Terence John Parr) (1995-11-20)
[21 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: Odd Arild Olsen <oaolsen@login.eunet.no>
Keywords: parse, LALR, LL(1), question
Organization: Compilers Central
Date: Sat, 4 Nov 1995 21:55:01 GMT

Allen I. Holub in section E.12 in his book Compiler design in C, Prentice
Hall, 1990, says that a parser based on a LL(1) grammar will be both
faster and smaller than one based on a LALR(1) grammar (at least using his
tools LLama and occs, occs being equivalent to yacc).

It also seems to me that it is easier to understand the mechanisms and
implement an error handling system in top-down parsers than in bottom up
parsers. Recursive descent parsers can also be written by hand, while that
is not the case for bottom-up parsers (I think).

Why do compiler design text book authors only describe recursive parsers
as a step stone on their way to bottom up parsers? I know that LALR allows
for more complex grammars, but many languages can be described by LL(1)
grammars. If LL(1) can yield faster, smaller and more understandable
parsers with better error handling for many languages, why isn't this
method more elaborated? (Holub, as an example, presents full grammar and
compiler listings for a bottom-up C-compiler, not for top-down).

A LL(1) grammar for C written by Mohd Hanafiah Abdullah can be found on
many ftp-sites (cgram-ll1). So, although the grammar gets rather complex
in LL(1) notation, LL(1) is good enough for at least one useful language.
And the various Small-C compilers were recursive descending. Which common
languages can not be parsed by LL(1) grammars?


Post a followup to this message

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