Re: ambiguity of grammar and LR(k)

> > It is well-known the following grammar is ambiguous so that it is
> > not LR(k) for any k.
> > S -> iEtSeS | iEtS | a
> > ('a' is not important, maybe just some assigning statement)
> >
> > But it can be written in an umambiguous way. I devised the following
> > grammar(maybe incorrect).
> > S -> M | U
> > M -> iEtMeM | a
> > U -> iEtS
> >
> > I guess it LR(1). Any correction will be welcomed.


> [ Kernighan and Pike propose ]
> stmt : if cond stmt end
> | if cond stmt end ELSE stmt end ;
>
> if : IF ;
>
> cond : '(' expr ')' ;
>
> end : ;


Now I have tested it. It seems to be still ambiguous... Yacc and bison
give a shift/reduce conflict. When you take the syntax of Visual
Basic:


statement : IF expression THEN statementlist opt_else END IF;


statementlist : statementlist '\n' statement
                                        | statementlist ':' statement
                                        | statement
                                        ;


opt_else :
                                | ELSE statementlist
                                ;


Then there is no shift/reduce conflict. If you code:


        If a < 5 Then
                b = 5
        Else
                If c < 3 Then
                        d = 2
                Else
                        d = 4
                End If
        End If


then there is no chance of misinterpretation or miscompilation.


(VB seems not to be case sensitive)
--
Hans Kamp

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