TechQA.

SR conflict in a grammar - how to resolve it? (Lemon/yacc)

140 views Asked by At

I have put together a grammar in Lemon (which is similar to YACC) but it is producing an S/R conflict. I am not used to LALR parsing and don't understand what the problem is, nor how to resolve it. The grammar is:

%right EQUALS.
%right RIGHT_ASSIGN LEFT_ASSIGN MOD_ASSIGN DIV_ASSIGN MUL_ASSIGN.

%right QUESTION COLON.

%left EQ_OP.
%left NE_OP LE_OP GE_OP LCARET RCARET.

%left PLUS MINUS.
%left STAR PERCENT FSLASH.
%right UNA.

%left DOT PTR_OP.
%left UN.

%left LBRACKET LSBRACKET RBRACKET RSBRACKET.

%right DOTACCESS.

file ::= statement_list EOF.

statement_break ::= EOL.

statement_list ::= statement statement_break.
statement_list ::= statement_list statement statement_break.

statement ::= expr.
statement ::= assign_expr argument_expr_list. [UN]

primary_expr
    ::= IDENTIFIER.
primary_expr
    ::= CONSTANT.
primary_expr
    ::= STRING_LITERAL.
primary_expr
    ::= LBRACKET expr RBRACKET.

postfix_expr
    ::= primary_expr.
postfix_expr
    ::= postfix_expr LSBRACKET expr RSBRACKET. [UN]
postfix_expr
    ::= postfix_expr LBRACKET RBRACKET. [UN]
postfix_expr
    ::= postfix_expr LBRACKET argument_expr_list RBRACKET. [UN]
postfix_expr
    ::= postfix_expr DOT IDENTIFIER. [DOTACCESS]
postfix_expr
    ::= postfix_expr PTR_OP IDENTIFIER. [DOTACCESS]
postfix_expr
    ::= postfix_expr INC_OP. 
postfix_expr
    ::= postfix_expr DEC_OP. 

argument_expr_list
    ::= assign_expr.
argument_expr_list
    ::= argument_expr_list COMMA assign_expr.

unary_expr
    ::= postfix_expr.
unary_expr
    ::= unary_operator cast_expr. [UNA]
unary_expr
    ::= SIZEOF unary_expr. [UN]
unary_expr
    ::= SIZEOF LBRACKET type_name RBRACKET. [UN]

unary_operator
    ::= EXCLAMATION.

cast_expr
    ::= unary_expr.
cast_expr
    ::= LBRACKET type_name RBRACKET cast_expr. [UNA]

mul_expr
    ::= cast_expr.
mul_expr
    ::= mul_expr STAR cast_expr.
mul_expr
    ::= mul_expr FSLASH cast_expr.
mul_expr
    ::= mul_expr PERCENT cast_expr.

add_expr
    ::= mul_expr.
add_expr
    ::= add_expr PLUS mul_expr.
add_expr
    ::= add_expr MINUS mul_expr.

shift_expr
    ::= add_expr.
shift_expr
    ::= shift_expr LEFT_OP add_expr.
shift_expr
    ::= shift_expr RIGHT_OP add_expr.

rel_expr
    ::= shift_expr.
rel_expr
    ::= rel_expr LCARET shift_expr.
rel_expr
    ::= rel_expr RCARET shift_expr.
rel_expr
    ::= rel_expr LE_OP shift_expr.
rel_expr
    ::= rel_expr GE_OP shift_expr.

eq_expr
    ::= rel_expr.
eq_expr
    ::= eq_expr EQ_OP rel_expr.
eq_expr
    ::= eq_expr NE_OP rel_expr.

and_expr
    ::= eq_expr.
and_expr
    ::= and_expr AND eq_expr.

excl_or_expr
    ::= and_expr.
excl_or_expr
    ::= excl_or_expr HAT and_expr.


incl_or_expr
    ::= excl_or_expr.
incl_or_expr
    ::= incl_or_expr BAR excl_or_expr.

log_and_expr
    ::= incl_or_expr.
log_and_expr
    ::= log_and_expr AND_OP incl_or_expr.

log_or_expr
    ::= log_and_expr.
log_or_expr
    ::= log_or_expr OR_OP log_and_expr.

cond_expr
    ::= log_or_expr.
cond_expr
    ::= log_or_expr QUESTION expr COLON cond_expr.

assign_expr
    ::= cond_expr.
assign_expr
    ::= unary_expr assign_op assign_expr.

assign_op
    ::= EQUALS. [EQUALS]
assign_op
    ::= MUL_ASSIGN. [EQUALS]
assign_op
    ::= DIV_ASSIGN. [EQUALS]
assign_op
    ::= MOD_ASSIGN. [EQUALS]
assign_op
    ::= ADD_ASSIGN. [EQUALS]
assign_op
    ::= SUB_ASSIGN. [EQUALS]
assign_op
    ::= LEFT_ASSIGN. [EQUALS]
assign_op
    ::= RIGHT_ASSIGN. [EQUALS]
assign_op
    ::= AND_ASSIGN. [EQUALS]
assign_op
    ::= XOR_ASSIGN. [EQUALS]
assign_op
    ::= OR_ASSIGN. [EQUALS]

expr
    ::= assign_expr.
expr
    ::= expr COMMA assign_expr.

type_name
    ::= TYPE.

and the output from Lemon is:

State 4:
          primary_expr ::= * IDENTIFIER
          primary_expr ::= * CONSTANT
          primary_expr ::= * STRING_LITERAL
          primary_expr ::= * LBRACKET expr RBRACKET
          postfix_expr ::= * primary_expr
          postfix_expr ::= * postfix_expr LSBRACKET expr RSBRACKET
          postfix_expr ::= * postfix_expr LBRACKET RBRACKET
          postfix_expr ::= postfix_expr LBRACKET * RBRACKET
          postfix_expr ::= * postfix_expr LBRACKET argument_expr_list RBRACKET
          postfix_expr ::= postfix_expr LBRACKET * argument_expr_list RBRACKET
          postfix_expr ::= * postfix_expr DOT IDENTIFIER
          postfix_expr ::= * postfix_expr PTR_OP IDENTIFIER
          postfix_expr ::= * postfix_expr INC_OP
          postfix_expr ::= * postfix_expr DEC_OP
          argument_expr_list ::= * assign_expr
          argument_expr_list ::= * argument_expr_list COMMA assign_expr
          unary_expr ::= * postfix_expr
          unary_expr ::= * unary_operator cast_expr
          unary_expr ::= * SIZEOF unary_expr
          unary_expr ::= * SIZEOF LBRACKET type_name RBRACKET
          unary_operator ::= * EXCLAMATION
          cast_expr ::= * unary_expr
          cast_expr ::= * LBRACKET type_name RBRACKET cast_expr
          mul_expr ::= * cast_expr
          mul_expr ::= * mul_expr STAR cast_expr
          mul_expr ::= * mul_expr FSLASH cast_expr
          mul_expr ::= * mul_expr PERCENT cast_expr
          add_expr ::= * mul_expr
          add_expr ::= * add_expr PLUS mul_expr
          add_expr ::= * add_expr MINUS mul_expr
          shift_expr ::= * add_expr
          shift_expr ::= * shift_expr LEFT_OP add_expr
          shift_expr ::= * shift_expr RIGHT_OP add_expr
          rel_expr ::= * shift_expr
          rel_expr ::= * rel_expr LCARET shift_expr
          rel_expr ::= * rel_expr RCARET shift_expr
          rel_expr ::= * rel_expr LE_OP shift_expr
          rel_expr ::= * rel_expr GE_OP shift_expr
          eq_expr ::= * rel_expr
          eq_expr ::= * eq_expr EQ_OP rel_expr
          eq_expr ::= * eq_expr NE_OP rel_expr
          and_expr ::= * eq_expr
          and_expr ::= * and_expr AND eq_expr
          excl_or_expr ::= * and_expr
          excl_or_expr ::= * excl_or_expr HAT and_expr
          incl_or_expr ::= * excl_or_expr
          incl_or_expr ::= * incl_or_expr BAR excl_or_expr
          log_and_expr ::= * incl_or_expr
          log_and_expr ::= * log_and_expr AND_OP incl_or_expr
          log_or_expr ::= * log_and_expr
          log_or_expr ::= * log_or_expr OR_OP log_and_expr
          cond_expr ::= * log_or_expr
          cond_expr ::= * log_or_expr QUESTION expr COLON cond_expr
          assign_expr ::= * cond_expr
          assign_expr ::= * unary_expr assign_op assign_expr

                      LBRACKET shift        2      
                      RBRACKET shift-reduce 12     postfix_expr ::= postfix_expr LBRACKET RBRACKET
                    IDENTIFIER shift-reduce 6      primary_expr ::= IDENTIFIER
                      CONSTANT shift-reduce 7      primary_expr ::= CONSTANT
                STRING_LITERAL shift-reduce 8      primary_expr ::= STRING_LITERAL
                        SIZEOF shift        32     
                   EXCLAMATION shift-reduce 24     unary_operator ::= EXCLAMATION
                   assign_expr shift        43       /* because assign_expr==argument_expr_list */
            argument_expr_list shift        43     
                  primary_expr shift        36       /* because primary_expr==postfix_expr */
                  postfix_expr shift        36     
                    unary_expr shift        33     
                unary_operator shift        31     
                     cast_expr shift        42       /* because cast_expr==mul_expr */
                      mul_expr shift        42     
                      add_expr shift        55     
                    shift_expr shift        54     
                      rel_expr shift        39     
                       eq_expr shift        47     
                      and_expr shift        69     
                  excl_or_expr shift        68     
                  incl_or_expr shift        66     
                  log_and_expr shift        64     
                   log_or_expr shift        45     
                     cond_expr shift        43       /* because cond_expr==assign_expr */  

State 20:
          primary_expr ::= * IDENTIFIER
          primary_expr ::= * CONSTANT
          primary_expr ::= * STRING_LITERAL
          primary_expr ::= * LBRACKET expr RBRACKET
          postfix_expr ::= * primary_expr
          postfix_expr ::= * postfix_expr LSBRACKET expr RSBRACKET
          postfix_expr ::= * postfix_expr LBRACKET RBRACKET
          postfix_expr ::= * postfix_expr LBRACKET argument_expr_list RBRACKET
          postfix_expr ::= * postfix_expr DOT IDENTIFIER
          postfix_expr ::= * postfix_expr PTR_OP IDENTIFIER
          postfix_expr ::= * postfix_expr INC_OP
          postfix_expr ::= * postfix_expr DEC_OP
          unary_expr ::= * postfix_expr
          unary_expr ::= * unary_operator cast_expr
          unary_expr ::= * SIZEOF unary_expr
          unary_expr ::= * SIZEOF LBRACKET type_name RBRACKET
          unary_operator ::= * EXCLAMATION
          cast_expr ::= * unary_expr
          cast_expr ::= * LBRACKET type_name RBRACKET cast_expr
          mul_expr ::= * cast_expr
          mul_expr ::= * mul_expr STAR cast_expr
          mul_expr ::= * mul_expr FSLASH cast_expr
          mul_expr ::= * mul_expr PERCENT cast_expr
          add_expr ::= * mul_expr
          add_expr ::= * add_expr PLUS mul_expr
          add_expr ::= * add_expr MINUS mul_expr
          shift_expr ::= * add_expr
          shift_expr ::= * shift_expr LEFT_OP add_expr
          shift_expr ::= * shift_expr RIGHT_OP add_expr
          rel_expr ::= rel_expr LE_OP * shift_expr

                      LBRACKET shift        2      
                    IDENTIFIER shift-reduce 6      primary_expr ::= IDENTIFIER
                      CONSTANT shift-reduce 7      primary_expr ::= CONSTANT
                STRING_LITERAL shift-reduce 8      primary_expr ::= STRING_LITERAL
                        SIZEOF shift        32     
                   EXCLAMATION shift-reduce 24     unary_operator ::= EXCLAMATION
                  primary_expr shift        36       /* because primary_expr==postfix_expr */
                  postfix_expr shift        36     
                    unary_expr shift        42       /* because unary_expr==mul_expr */
                unary_operator shift        31     
                     cast_expr shift        42       /* because cast_expr==mul_expr */
                      mul_expr shift        42     
                      add_expr shift        55     
                    shift_expr shift        49     


State 36:
          postfix_expr ::= postfix_expr * LSBRACKET expr RSBRACKET
          postfix_expr ::= postfix_expr * LBRACKET RBRACKET
          postfix_expr ::= postfix_expr * LBRACKET argument_expr_list RBRACKET
          postfix_expr ::= postfix_expr * DOT IDENTIFIER
          postfix_expr ::= postfix_expr * PTR_OP IDENTIFIER
          postfix_expr ::= postfix_expr * INC_OP
          postfix_expr ::= postfix_expr * DEC_OP
     (20) unary_expr ::= postfix_expr *

                           DOT shift        61     
                        PTR_OP shift        60     
                      LBRACKET shift        4      
                      LBRACKET reduce       20      ** Parsing conflict **
                     LSBRACKET shift        7      
                        INC_OP shift-reduce 16     postfix_expr ::= postfix_expr INC_OP
                        DEC_OP shift-reduce 17     postfix_expr ::= postfix_expr DEC_OP
                     {default} reduce       20     unary_expr ::= postfix_expr

You can find the conflict in the 'State 36' (I culled excess output). I believe it should be resolveable with Precedence rules but I cannot figure out how.

parsing bison yacc lalr lemon
Original Q&A
1

There are 1 answers

0
rici On

The conflict comes from the rule

statement ::= assign_expr argument_expr_list. [UN]

which seems to me to be completely unnecessary. Any statement derived from this production could also derived from

statement: expr.

So the grammar is ambiguous:

An example of an assign_expr would be a = b (unary_expr assign_op assign_expr). Another example would be a = sin(0.5). Since we also have statement ::= expr (and expr ::= assign_expr), a = sin(0.5) could be parsed as statement in two ways: as the assign_expr a = sin(0.5), reduced directly to expr, or as the assign_expr a = sin followed by argument_expr_list. It seems to me that the second case is never useful, and that the production should just be deleted from the grammar. But perhaps you have some specific semantic in mind.

Your grammar is full of precedence declarations which probably don't do any harm, but I doubt whether any of those precedence declarations have any effect whatsoever. It's certainly the case that the particular shift/reduce conflict being reported cannot be resolved by means of any of the precedence declarations, because the possible reduction is a unit rule which has no declared precedence. (unary_expr ::= postfix_expr.) Giving it a an arbitrary precedence might resolve the conflict, but it seems to me unlikely that it will resolve it in a useful way; however you resolve it, some other rule will become unusable, which is a bad sign.

Related Questions in PARSING

Related Questions in BISON

Related Questions in YACC

Related Questions in LALR

Related Questions in LEMON

Popular Questions

Popular Tags

javascript python java c# php android html jquery c++ css ios sql mysql r reactjs node.js arrays c asp.net json

Trending Questions