Как решить этот конфликт сокращения/сокращения в Bison?

Question

Вот выдержка из [имя файла] .output состояние 94

32 expr: expr . opt_at_type '.' TYPEID '(' opt_expr_list ')' 
    39  | expr . '+' expr 
    40  | expr . '-' expr 
    41  | expr . '*' expr 
    42  | expr . '/' expr 
    42  | expr '/' expr . 
    44  | expr . '<' expr 
    45  | expr . LE expr 
    46  | expr . '=' expr 

    '@' shift, and go to state 73 

    '.'  reduce using rule 23 (opt_at_type) 
    '.'  [reduce using rule 42 (expr)] 
    $default reduce using rule 42 (expr) 

    opt_at_type go to state 74 

opt_at_type определяется как:

opt_at_type: 
      { $$ = idtable.add_string("SELF_TYPE"); } 
      |  '@' TYPEID 
      { $$ = $2; } 
      ; 

и вы можете просветить меня, почему это происходит?

Answer 1

Проблемы вы бежите в том, что уровни Yacc очередности принимаются только в для разрешения конфликтов смены/сокращения, а не сокращения/сокращения. В этом случае правило opt_at_type может соответствовать пустой строке (это необязательно), что приводит к конфликту уменьшения/уменьшения.

Чтобы исправить это, вам нужно unfactor правила, чтобы избавиться от производства эпсилона:

expr: expr '.' TYPEID '(' opt_expr_list ')' 
    | expr '@' TYPEID '.' TYPEID '(' opt_expr_list ')' 
    | expr '+' expr 
     : 

Без производства эпсилона, он не нуждается в раннем уменьшить, поэтому конфликт становится сдвигом/уменьшить конфликт, который может быть разрешен с помощью приоритета yacc.

Answer 2

Когда Bison видит следующее:

expr '/' expr '.' 

Он не знает, если это соответствует:

1) expr opt_at_type '.' 

ИЛИ

2) expr '/' expr opt_at_type '.' 

Для 1) было бы уменьшить expr '/' expr к expr первый и для 2) это уменьшит/* Пусто */до opt_at_type первых.

Итак, мы обнаружили двусмысленность, чтобы решить эту проблему, вы должны определить, какой синтаксис вы хотите. Одним из решений было бы сделать первый выраж правила отдельного правила так, чтобы оно не могло быть использовано в других выражениях, как так:

typeexpr: expr opt_at_type '.' TYPEID '(' opt_expr_list ')'