Re: LL(1) vs. LR(1)

"Will" <willverine@hotpop.com> writes:


> Another curiosity is the efficiency of LL(1) and LR(1) algorithms. Due
> to backtracking, LL(1) may end up being exhaustive in that it may
> backtrack to the point that it reaches the last production in which it
> will try to apply. This exhaustive search means LL(1) is bounded by an
> exponential (am I correct?). However, the LR(1) algorithms for
> producing the parsing table also seems to be exponential; when you
> find the "closure" and "goto" of LR(1) items, you look at each item
> and in turn each of these items may require you to do "closure" and
> "goto" again. Because of this fan-out, it seems LR(1) algorithm for
> creating parsing table (btw: I'm talking about the algorithm presented
> in the new dragon book) is also bounded exponentially (am I
> correct?). So it seems LR(1) requires the same computational power as
> LL(1)?
>


It may in fact be that the LR(1) and LL(1) algorithms are exponential
(I haven't done a full analysis and my hunch says no), but in practice
(LA)LR(1) is much, much faster on any practical programming language
grammar.


If you think about it, the LR(1) "closure" and "goto" operations would
need a very silly grammar in order to be very slow. In order for it
to be bad, each rule would have to look a bit like this:


A -> A A' ...
    -> B B' ...
    -> C C' ...


for many different nonterminals in the grammar. I have serious doubts
that grammars of this nature show up that much in practical usage.


Just for kicks, implement an LL(1) parser for C in Elisp and see how
slow it is (I have - it's bad). You could easily imagine an LR parser
being much quicker.


--
Geoff(rey) Wozniak, Limited Duties Instructor
University of Western Ontario
Computer Science (Graduate) Department
London, Ontario, Canada
http://woz.killdash9.org/


GPG Key: http://woz.killdash9.org/misc/woz.gpg

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