Блог

Главная - Вопросы по программированию - Разрешить сдвиг / уменьшить конфликт в Bison для элементов, разделенных точками

Разрешить сдвиг / уменьшить конфликт в Bison для элементов, разделенных точками

#c #grammar #bison #yacc

#c #грамматика #bison #yacc

Вопрос:

Я создаю интерпретатор для языка, в котором все является выражениями. Он поддерживает конструкции, которые мы можем называть выражениями, разделенными точками. EXPR . EXPR . EXPR Правило грамматики для выражения:

 expr:
    INTEGER | DOUBLE
    | ... SOME OTHER EXPR'S
    | expressions_dot                 { printf("Dot expression"); }
    ;
expressions_dot:
    DOT expr %prec DOT
    | expressions_dot DOT expr %prec DOT { printf("dot separated expressionn"); }
    ;

До введения этого правила у меня не было конфликтов, но после его появления появляется ровно один конфликт. Все дело в том, что мне нужно парсить слева направо, тогда будет удобно создавать вектор для структуры типа Node*, в которой хранится дерево. expressions_dot имеет наивысший приоритет %left DOT .

Файл y.output журнала показывает, что с этим проблем не будет, но мое чувство перфекциониста не дает мне успокоиться, и я не могу спать.

 state 28

   13 expr: expressions_dot .
   44 expressions_dot: expressions_dot . DOT expr

    DOT  shift, and go to state 55

    DOT       [reduce using rule 13 (expr)]
    $default  reduce using rule 13 (expr)

Возможно ли разрешить этот конфликт без правила справа налево? Или какой-то трюк для использования дополнительного правила?

UPD: главное, я не могу понять, почему Bison хотят уменьшить??

Комментарии:

1. Вы не уверены в ожидаемой грамматике, хотите ли вы EXPR (DOT EXPR)* (список выражений, разделенных ТОЧКОЙ) или мы можем иметь DOT DOT EXPR DOT DOT ( DOT работает «как» круглые скобки, но нет разницы между открытым и закрытым).

2. @Jarod42 первый, expr (DOT expr) *. Позже его следует использовать в 3 правилах: expr expressions_dot, DOT expr expressions_dot, DOT DOT expr expressions_dot. Для разных контекстов. Таким образом, правило expressions_dot используется для создания специального полезного вектора узлов, который будет лучше для дерева программы.

3. Итак, вы уже должны были решить проблему с таким списком для sum, что-то вроде expr_leaf: DOUBLE | INT; expr: expr_leaf dot_expr; dot_expr: empty | DOT expr .

4. @Jarod42 почему? Я так не думаю, потому что dot_expr не может быть пустым в моей грамматике.

5. Здесь my dot_expr — просто помощник, переименуйте его, если хотите. В чем разница между expr и expressions_dot ? 42 . 42 . 42 насколько я понимаю, это и то, и другое. (как 42 и 42 42 42 оба являются допустимой суммой).