# Re: Help needed on LALR(1) ambiguity

## Chris Dodd <cdodd@acm.org>Mon, 17 Nov 2008 00:25:38 -0600

From comp.compilers

Related articles
Help needed on LALR(1) ambiguity philip.k.chow@gmail.com (2008-11-14)
Re: Help needed on LALR(1) ambiguity cdodd@acm.org (Chris Dodd) (2008-11-17)
Re: Help needed on LALR(1) ambiguity armelasselin@hotmail.com (Armel) (2008-11-17)
Re: Help needed on LALR(1) ambiguity svenolof.nystrom-nospam@bredband.net (Sven-Olof Nystrom) (2008-11-18)
Re: Help needed on LALR(1) ambiguity philip.k.chow@gmail.com (2008-11-18)
Re: Help needed on LALR(1) ambiguity Danny.Dube@ift.ulaval.ca (2008-12-01)
| List of all articles for this month |

 From: Chris Dodd Newsgroups: comp.compilers Date: Mon, 17 Nov 2008 00:25:38 -0600 Organization: Compilers Central References: 08-11-055 Keywords: parse, theory Posted-Date: 17 Nov 2008 08:25:16 EST

philip.k.chow@gmail.com wrote in news:08-11-055@comp.compilers:
(grammar deleted)
> Here is a tricky sentence that demonstrates why it's hard:
>
> all a: all b, c: all d | x
>
> This has only one legal parse (parentheses added for clarification):
>
> all (a:all b), (c:all d) | x

To understand precisely why this is so hard, consider what happens if you
add a |-suffix to the end:

all a: all b, c: all d | x | y

now the parse looks completely different:

all (a: all (b, c : all d) | x) | y

So the problem is that you need to be able to look ahead to the end of the
input to see how many |-suffixes there are in order to figure out how to
parse the beginning of the expression. This makes it pretty much impossible
to parse without unbounded lookahead, or backtracking, or something else.

Chris Dodd
cdodd@acm.org

Post a followup to this message