Re: Help needed on LALR(1) ambiguity

philip.k.chow@gmail.com writes:
[...]
> Expr : ID ;
> Expr : ALL ID ;
> Expr : ALL Decl BAR Expr ;
>
> Names : ID COLON ;
> Names : ID COMMA Names ;
>
> Decl : Names Expr COMMA Decl ;
> Decl : Names Expr ;
>
> Forcing the shift-reduce decision one-way-or-the-other doesn't work,
> since sometimes it really should shift, and sometimes it should
> reduce. I've also tried several standard techniques of grammar
> refactoring, but I haven't succeeded.
[...]


I'm afraid that it's not simply a matter of having the right
technology to decide when to shift or when to reduce. Your grammar is
ambiguous. For instance, the following sentence can be parsed in two
ways (the parenthesized sub-sentences being generated by Expr):


    Sentence: all i : all i , i : all i , i : all i | i | i


    Parse 1: all i : ( all i , i : ( all i ) , i : ( all i ) | i ) | i


    Parse 2: all i : ( all i ) , i : ( all i , i : ( all i ) | i ) | i


Most of the following sentences have multiple parses:


    all i : ( all i , i : )^m all i ( | i )^n


If I'm not mistaken, such a sentence is part of the language when:


    1 <= n <= m+1


and it has multiple parses when:


    2 <= n <= m.


If the meaning of the expressions depends on the parse trees that you
build (and normally it should), then you cannot rely on parsing using
your grammar to give a definite meaning to the expressions.


Danny

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