SR конфликт в граматика - как да го разрешим? (лимон/як)

Събрах граматика в 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“ (избрах излишния изход). Вярвам, че трябва да бъде разрешено с правилата за приоритет, но не мога да разбера как.


parsing yacc bison lalr lemon
person Evgeniy Yakovich    schedule 03.01.2020    source източник

Отговори (1)


arrow_upward
2
arrow_downward

Конфликтът идва от правилото

statement ::= assign_expr argument_expr_list. [UN]

което ми се струва напълно ненужно. Всеки statement, получен от това производство, също може да бъде извлечен от

statement: expr.

Така че граматиката е двусмислена:

Пример за assign_expr би бил a = b (unary_expr assign_op assign_expr). Друг пример би бил a = sin(0.5). Тъй като имаме също statement ::= expr (и expr ::= assign_expr), a = sin(0.5) може да бъде анализирано като statement по два начина: като assign_expr a = sin(0.5), намалено директно до expr, или като assign_expr a = sin, последвано от argument_expr_list. Струва ми се, че вторият случай никога не е полезен и че продукцията трябва просто да бъде изтрита от граматиката. Но може би имате предвид някаква конкретна семантика.

Вашата граматика е пълна с декларации за приоритет, които вероятно не причиняват никаква вреда, но се съмнявам дали някоя от тези декларации за приоритет има някакъв ефект. Със сигурност е така, че конкретният конфликт на преместване/намаляване, за който се докладва, не може да бъде разрешен чрез никоя от декларациите за приоритет, тъй като възможното намаляване е правило за единица, което няма деклариран приоритет. (unary_expr ::= postfix_expr.) Даването на произволен приоритет може да разреши конфликта, но ми се струва малко вероятно, че ще го разреши по полезен начин; както и да го разрешите, някое друго правило ще стане неизползваемо, което е лош знак.

person rici    schedule 03.01.2020