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

"SLK Parsers" <parsersinc@earthlink.net>
3 Aug 2006 11:04:31 -0400

          From comp.compilers

Related articles
[28 earlier articles]
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-07-29)
Re: Why LL(1) Parsers do not support left recursion? ajo@andrew.cmu.edu (Arthur J. O'Dwyer) (2006-07-29)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-07-29)
Re: Why LL(1) Parsers do not support left recursion? parsersinc@earthlink.net (SLK Parsers) (2006-07-31)
Re: Why LL(1) Parsers do not support left recursion? wyrmwif@tsoft.org (SM Ryan) (2006-08-01)
Re: Why LL(1) Parsers do not support left recursion? DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-08-03)
Re: Why LL(1) Parsers do not support left recursion? parsersinc@earthlink.net (SLK Parsers) (2006-08-03)
Re: Why LL(1) Parsers do not support left recursion? parsersinc@earthlink.net (SLK Parsers) (2006-08-04)
| List of all articles for this month |

From: "SLK Parsers" <parsersinc@earthlink.net>
Newsgroups: comp.compilers
Date: 3 Aug 2006 11:04:31 -0400
Organization: Parsers Inc.
References: 06-07-115
Keywords: parse

>How would I guess which one is that?


The technique is called "controlled ambiguity" in the Dragon book. You can
read about it there. I leave the LL solution as an exercise for the
interested reader, as if there are any.


Hint 1: We want to associate the ELSE with the closest IF, so use the
production that consumes the ELSE sooner.


Hint 2: There are only 2 possibilities, try them both and see which one
works.


The grammar solution is quite clever. If it were not so redundant, and
solved a problem that actually exists, it would be useful.


Forget about yacc for a minute. Assume you were creating the parse table by
hand. When you got to the shift-reduce conflict, you would say "Oh, I
remember this one from my first year compiler course. I will use the shift
as the entry in the parse table". This is what yacc does automatically.


The SLK parser generator: http://home.earthlink.net/~slkpg/


Post a followup to this message

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