CODEWITHSUNDEEP
compiler-constructionsyntaxpascalshift-reduce-conflict
Uros K
Uros K

Reputation: 3384

How to resolve shift reduce conflicts in my grammar?

I'm writing a compiler from (reduced) Pascal into ARM asm. I'm at the second step of the process - after writing lexical analyzer now I'm working on syntax analysis with java cup.

I have written my grammar, but got 5 S/R conflicts, which are all very similar. Example:

   Warning : *** Shift/Reduce conflict found in state #150
between assign_stmt ::= val_expr ASSIGN val_expr (*) 
  and     val_expr ::= val_expr (*) LBRACKET val_expr RBRACKET 
  under symbol LBRACKET
  Resolved in favor of shifting

My grammar for this section:

assign_stmt ::=
 val_expr ASSIGN val_expr;

val_expr ::=
     NIL | BOOL_CONST | INT_CONST | CHAR_CONST | PTR val_expr %prec MEM | ADD val_expr %prec UADD |
     SUB val_expr %prec USUB | NOT val_expr | val_expr PTR %prec VAL | val_expr MUL val_expr |
     val_expr DIV val_expr | val_expr ADD val_expr | val_expr SUB val_expr | val_expr EQU val_expr |
     val_expr NEQ val_expr | val_expr LTH val_expr | val_expr GTH val_expr | val_expr LEQ val_expr |
     val_expr GEQ val_expr | val_expr AND val_expr | val_expr OR val_expr | IDENTIFIER | 
     val_expr LBRACKET val_expr RBRACKET | val_expr DOT IDENTIFIER | IDENTIFIER LPARENTHESIS params_list RPARENTHESIS |
     LBRACKET type_desc RBRACKET | LPARENTHESIS val_expr RPARENTHESIS
    ;

How could I eliminate this conflict?

Thanks.

Upvotes: 2

Views: 4885

Answers (1)

imgx64
imgx64

Reputation: 4152

Your grammar is ambiguous, and both right- and left-recursive. From my (limited) knowledge about parsers, I know this is impossible to parse by most parser generators.

It's ambiguous because val_expr ADD val_expr SUB val_expr can be parsed as:

       ADD
      /   \
val_expr  SUB
         /   \
   val_expr  val_expr

and

        SUB
       /   \
     ADD  val_expr
    /   \
val_expr  val_expr

I've never used Java CUP, but here's how I did a similar thing using another parser generator:

val_expr ::=
    expr1 (SUB | ADD | <add all your operators here>) val_expr
    | expr1 ;

expr1 ::=
    NIL | BOOL_CONST | INT_CONST | CHAR_CONST | <etc> ;

This makes the grammar unambiguous and only right-recursive, which can be handled by all parser generators I know of.

A negative aspect of this grammar is that you don't have any precedence, but Java CUP probably has another way to specify precedence.

Edit: Fixed first grammar rule.

Upvotes: 5

Related Questions