ML-Yacc shift/reduce

[borisd]

Hi,

While implementing an ML-Yacc parser for the MiniJava language from the book "Modern Compiler Implementation in Java", I encountered a couple of shift/reduce conflicts.

Below is the grammar for MiniJava taken from the book:

----------------------------------------------------------------------
   Program = MainClass ClassDecl*
 MainClass = class id { public static void main ( String [] id )
               { Statement }}
 ClassDecl = class id { VarDecl* MethodDecl* }
           = class id extends id { VarDecl* MethodDecl* }
   VarDecl = Type id ;
MethodDecl = public Type id ( FormalList )
               { VarDecl* Statement* return Exp ;}
FormalList = Type id FormalRest*
FormalRest =, Type id
      Type = int []
           = boolean
           = int
           = id
 Statement = { Statement* }
           = if ( Exp ) Statement else Statement
           = while ( Exp ) Statement
           = System.out.println ( Exp ) ;
           = id = Exp ;
           = id [ Exp ]= Exp ;
       Exp = Exp op Exp
           = Exp [ Exp ]
           = Exp . length
           = Exp . id ( ExpList )
           = INTEGER LITERAL
           = true
           = false
           = id
           = this
           = new int [ Exp ]
           = new id ()
           = ! Exp
           = ( Exp )
   ExpList = Exp ExpRest*
           =
  ExpRest  =  ,Exp
----------------------------------------------------------------------


The conflicts I encountered are the following (from the ML-Yacc .desc file):

----------------------------------------------------------------------
error:  state 17: shift/reduce conflict (shift Id, reduce by rule 7)

state 17:

    vardeclseq : vardecl . vardeclseq

    Id    shift 22
    INT    shift 21
    BOOLEAN    shift 20
    STRING    shift 19

    vardeclseq    goto 25
    vardecl    goto 17
    typ    goto 16

    .    reduce by rule 7

----------------------------------------------------------------------
error:  state 49: shift/reduce conflict (shift Id, reduce by rule 7)

state 49:

    methoddecl : PUBLIC typ Id LPAR formallist RPAR LCURL . vardeclseq stmseq RETURN exp SEMI RCURL

    Id    shift 22
    INT    shift 21
    BOOLEAN    shift 20
    STRING    shift 19

    vardeclseq    goto 58
    vardecl    goto 17
    typ    goto 16

    .    reduce by rule 7
----------------------------------------------------------------------

My grammar definition has the following rule for vardeclseq:

vardeclseq : (* empty *) ([]) | vardecl vardeclseq (vardecl :: vardeclseq)
vardecl    : typ Id SEMI (Ast.VarDecl(typ, Id))

Interestingly, a slight change to the above rule eliminates the conflicts, but I end up with my variable declarations in reverse order:

vardeclseq : (* empty *) ([]) | vardeclseq vardecl (vardecl :: vardeclseq)

I don't understand why this change eliminates the conflicts, since nothing in the grammar definition has been changed other than the order in which I build the list. And also, if this is the way to deal with these conflicts, how can I get the variable declarations in the right order?

Do you guys have good references on how to handle conflicts in LR parsers? The best I've come across so far is  http://www.sable.mcgill.ca/listarchives/sablecc-list/msg00238.html but I'm still at a loss how to handle this problem.

Thanks in advance for any suggestions you may have.


------------------------------------------------------------------------------
Create and Deploy Rich Internet Apps outside the browser with Adobe(R)AIR(TM)
software. With Adobe AIR, Ajax developers can use existing skills and code to
build responsive, highly engaging applications that combine the power of local
resources and data with the reach of the web. Download the Adobe AIR SDK and
Ajax docs to start building applications today-http://p.sf.net/sfu/adobe-com
_______________________________________________
Smlnj-list mailing list
Smlnj-list@...
https://lists.sourceforge.net/lists/listinfo/smlnj-list

[Jon Riehl]

On Tue, Feb 3, 2009 at 1:00 AM, Boris D <borisd@...> wrote:
...

> My grammar definition has the following rule for vardeclseq:
>
> vardeclseq : (* empty *) ([]) | vardecl vardeclseq (vardecl :: vardeclseq)
> vardecl    : typ Id SEMI (Ast.VarDecl(typ, Id))
>
> Interestingly, a slight change to the above rule eliminates the conflicts,
> but I end up with my variable declarations in reverse order:
>
> vardeclseq : (* empty *) ([]) | vardeclseq vardecl (vardecl :: vardeclseq)
>
> I don't understand why this change eliminates the conflicts, since nothing
> in the grammar definition has been changed other than the order in which I
> build the list. And also, if this is the way to deal with these conflicts,
> how can I get the variable declarations in the right order?

This is one of the "gotchas" with LL and LR parsers.  Your original
grammar was right recursive (the left-hand non-terminal also appears
on the right hand of the right-hand side), which a LR parser generator
is going to have problems with.  The transformed rule is left
recursive, which a LL parser generator would have trouble with (but
not the LR parser generator).  When I have to deal with this, I
usually have the action code cons the reversed list, but then reverse
it back in productions that use the recursive non-terminal.

> Do you guys have good references on how to handle conflicts in LR parsers?
> The best I've come across so far is
> http://www.sable.mcgill.ca/listarchives/sablecc-list/msg00238.html but I'm
> still at a loss how to handle this problem.

IIRC, the O'Reilly Yacc book attempts to discuss this somewhat.  I
also seem to recall the "Dragon book" (Aho, Sethi, Ullman) discussing
syntax transformations like right and left factoring.  I recommend
both books for reference.  You might also mine Usenet archives of
comp.compilers, since this is a frequently asked question there.

Hope this helps,
-Jon

------------------------------------------------------------------------------
Create and Deploy Rich Internet Apps outside the browser with Adobe(R)AIR(TM)
software. With Adobe AIR, Ajax developers can use existing skills and code to
build responsive, highly engaging applications that combine the power of local
resources and data with the reach of the web. Download the Adobe AIR SDK and
Ajax docs to start building applications today-http://p.sf.net/sfu/adobe-com
_______________________________________________
Smlnj-list mailing list
Smlnj-list@...
https://lists.sourceforge.net/lists/listinfo/smlnj-list

[borisd]

Jon Riehl wrote:

> On Tue, Feb 3, 2009 at 1:00 AM, Boris D <borisd@...> wrote:
> ...
>  
>> My grammar definition has the following rule for vardeclseq:
>>
>> vardeclseq : (* empty *) ([]) | vardecl vardeclseq (vardecl :: vardeclseq)
>> vardecl    : typ Id SEMI (Ast.VarDecl(typ, Id))
>>
>> Interestingly, a slight change to the above rule eliminates the conflicts,
>> but I end up with my variable declarations in reverse order:
>>
>> vardeclseq : (* empty *) ([]) | vardeclseq vardecl (vardecl :: vardeclseq)
>>
>> I don't understand why this change eliminates the conflicts, since nothing
>> in the grammar definition has been changed other than the order in which I
>> build the list. And also, if this is the way to deal with these conflicts,
>> how can I get the variable declarations in the right order?
>>    
>
> This is one of the "gotchas" with LL and LR parsers.  Your original
> grammar was right recursive (the left-hand non-terminal also appears
> on the right hand of the right-hand side), which a LR parser generator
> is going to have problems with.  The transformed rule is left
> recursive, which a LL parser generator would have trouble with (but
> not the LR parser generator).  When I have to deal with this, I
> usually have the action code cons the reversed list, but then reverse
> it back in productions that use the recursive non-terminal.
>
>  

That was very helpful. Thanks a lot, Jon.

------------------------------------------------------------------------------
Create and Deploy Rich Internet Apps outside the browser with Adobe(R)AIR(TM)
software. With Adobe AIR, Ajax developers can use existing skills and code to
build responsive, highly engaging applications that combine the power of local
resources and data with the reach of the web. Download the Adobe AIR SDK and
Ajax docs to start building applications today-http://p.sf.net/sfu/adobe-com
_______________________________________________
Smlnj-list mailing list
Smlnj-list@...
https://lists.sourceforge.net/lists/listinfo/smlnj-list