Re: Why LL(1) Parsers do not support left recursion?

Etienne Gagnon <egagnon@sablevm.org>
22 Jul 2006 21:30:23 -0400

          From comp.compilers

Related articles
[6 earlier articles]
Re: Why LL(1) Parsers do not support left recursion? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-19)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-21)
Re: Why LL(1) Parsers do not support left recursion? luvisi@andru.sonoma.edu (Andru Luvisi) (2006-07-21)
Re: Why LL(1) Parsers do not support left recursion? cfc@shell01.TheWorld.com (Chris F Clark) (2006-07-21)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-22)
Re: Why LL(1) Parsers do not support left recursion? max@gustavus.edu (Max Hailperin) (2006-07-22)
Re: Why LL(1) Parsers do not support left recursion? egagnon@sablevm.org (Etienne Gagnon) (2006-07-22)
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-07-23)
Re: Why LL(1) Parsers do not support left recursion? max@gustavus.edu (Max Hailperin) (2006-07-23)
Re: Why LL(1) Parsers do not support left recursion? cbarron413@adelphia.net (Carl Barron) (2006-07-24)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-25)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-25)
Re: Why LL(1) Parsers do not support left recursion? mailbox@dmitry-kazakov.de (Dmitry A. Kazakov) (2006-07-25)
[18 later articles]
| List of all articles for this month |

From: Etienne Gagnon <egagnon@sablevm.org>
Newsgroups: comp.compilers
Date: 22 Jul 2006 21:30:23 -0400
Organization: Compilers Central
References: 06-07-024 06-07-027 06-07-035 06-07-046 06-07-050 06-07-055 06-07-059
Keywords: parse, LR(1)
Posted-Date: 22 Jul 2006 21:30:22 EDT

Hans-Peter Diettrich wrote:
> Let me summarize my points (John, you may drop my long answer ;-)
>
> 1. LL parsers cannot handle left recursion, whereas LR parsers cannot
> handle right recursion.


I'm not sure I understand clearly... What do you mean by "LR parsers
cannot handle right recursion"?


There is no LALR(1) conflict in the following "right recursive" grammar
(SableCC-like syntax):


  rht_rec_rule =
      {one} some token |
      {many} some token rht_rec_rule;




As far as I remember, LR parsers can deal with both left and right
recusrsive grammars. Maybe you meant something else?


Etienne


--
Etienne M. Gagnon, Ph.D. http://www.info2.uqam.ca/~egagnon/
SableVM: http://www.sablevm.org/
SableCC: http://www.sablecc.org/
Tokens
  some = ; // dummy
  tokens = ; // dummy


Productions


  rht_rec_rule =
      {one} some tokens |
      {many} some tokens rht_rec_rule;


Post a followup to this message

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