Re: ambiguity of grammar and LR(k)

"Hans Kamp" <hanskamp@introweb.nl>
29 Oct 1999 02:29:41 -0400

          From comp.compilers

Related articles
ambiguity of grammar and LR(k) linlist@fudan.edu (Linlist Leo) (1999-10-27)
Re: ambiguity of grammar and LR(k) hanskamp@introweb.nl (Hans Kamp) (1999-10-28)
Re: ambiguity of grammar and LR(k) hanskamp@introweb.nl (Hans Kamp) (1999-10-29)
Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-29)
Re: ambiguity of grammar and LR(k) henning@makholm.net (Henning Makholm) (1999-10-29)
Re: ambiguity of grammar and LR(k) mtimmerm@microstar.nospam-remove.com (Matt Timmermans) (1999-10-29)
Re: ambiguity of grammar and LR(k) nhartzell@macalester.edu (Nathan Hartzell) (1999-10-29)
Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-31)
Re: ambiguity of grammar and LR(k) Xavier.Nicollin@imag.fr (Xavier Nicollin) (1999-10-31)
[5 later articles]
| List of all articles for this month |

From: "Hans Kamp" <hanskamp@introweb.nl>
Newsgroups: comp.theory,comp.compilers
Date: 29 Oct 1999 02:29:41 -0400
Organization: IntroWeb Newsserver
Distribution: inet
References: 99-10-130 99-10-137
Keywords: parse, LR(1)

> > 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


Post a followup to this message

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