ML-Yacc shift/reduce

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
[email protected]
https://lists.sourceforge.net/lists/listinfo/smlnj-list