12 Oct 2001 00:19:22 -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: | "Will" <willverine@hotpop.com> |

Newsgroups: | comp.compilers |

Date: | 12 Oct 2001 00:19:22 -0400 |

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

Keywords: | parse, LL(1), LR(1) |

Posted-Date: | 12 Oct 2001 00:19:22 EDT |

I was told that LR(1) parsers are much more powerful than the LL(1)

parsers because they recognize more grammars. Please note, I am just

compare LL(1) to LR(1) and not LL(k), LR(k), LALR, or any other

variant.

I can see that LR(1) parsers are probably more powerful because to

create the parsing table, a stack is used. For LL(1) you just look at

the next input and do a trial and error approach (of course you can

left-factor, and most certainly you have to remove left-recursions

otherwise you'll go into an infinite loop - all this may result in

less backtracking although it's not guaranteed). Aside from the more

complex data structures and algorithms used by the LR(1), I don't

really see any grammars that a LR(1) parser can parse that a LL(1)

cannot. Can anyone give me a grammar that is in LR(1) but not in

LL(1)?

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)?

P.S. - Where can I find a complete FAQ on basic compiler theory? The

only FAQ I found is this: http://www.faqs.org/faqs/compilers/, and it

does not have any discussion on theory.

Thank you,

Will

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.