13 Oct 2001 23:10:45 -0400

Related articles |
---|

LL(1) vs. LR(1) willverine@hotpop.com (Will) (2001-10-12) |

Re: LL(1) vs. LR(1) gzw@home.com (Geoff Wozniak) (2001-10-13) |

Re: LL(1) vs. LR(1) joachim_d@gmx.de (Joachim Durchholz) (2001-10-13) |

Re: LL(1) vs. LR(1) cfc@world.std.com (Chris F Clark) (2001-10-13) |

From: | Geoff Wozniak <gzw@home.com> |

Newsgroups: | comp.compilers |

Date: | 13 Oct 2001 23:10:45 -0400 |

Organization: | Excite@Home - The Leader in Broadband http://home.com/faster |

References: | 01-10-042 |

Keywords: | parse, theory |

Posted-Date: | 13 Oct 2001 23:10:45 EDT |

"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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.