Re: Help needed on LALR(1) ambiguity

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

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