语法中的SR冲突-如何解决？(Lemon/yacc)

Question

我在Lemon中组合了一个语法(类似于YACC)，但它产生了S/R冲突。我不习惯LALR解析，不知道问题是什么，也不知道如何解决它。语法是：

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

Lemon的输出是：

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

你可以在“国家36”中找到冲突(我剔除了超额产出)。我相信这应该可以通过优先级规则来解决，但我不知道如何解决。

Answer 1

冲突来自于规则

statement ::= assign_expr argument_expr_list. [UN]

在我看来这是完全没有必要的。从这个产品派生的任何statement也可以派生自

statement: expr.

所以语法是模糊的：

a = b (unary_expr assign_op assign_expr)就是assign_expr的一个例子。另一个例子是a = sin(0.5)。因为我们也有statement ::= expr (和expr ::= assign_expr)，所以可以通过两种方式将a = sin(0.5)解析为statement：作为assign_expr代码，直接简化为expr，或者作为后跟<assign_expr>d16a = sin(0.5) >的assign_expr代码。在我看来，第二种情况从来都没有用过，应该从语法中删除这个结果。但也许您在脑海中有一些特定的语义。

您的语法中充满了优先级声明，这些声明可能不会造成任何伤害，但我怀疑这些优先级声明是否有任何效果。报告的特定移位/归约冲突不能通过任何优先级声明来解决，因为可能的归约是一个没有声明优先级的单位规则。(unary_expr ::= postfix_expr.)给它一个任意的优先级可能会解决冲突，但在我看来，它不太可能以一种有用的方式解决它；无论您如何解决它，其他一些规则将变得不可用，这是一个不好的迹象。