Откуда происходят конфликты сдвига / уменьшения в этом коде Bison?

Question

Я пытаюсь разобрать этот синтаксис:

34 + 1 − 8, 32 * 87 + 6 / 4, 34 / 8

Я ожидаю, что это так:

(, (- (+ 34 1) 8) (/ (+ (* 32 87) 6) 4) (/ 34 8))

Это код для ЗУБР:

%token NUMBER
%token COMMA
%token OPERATOR
%left OPERATOR
%left COMMA
%%

term: NUMBER | term op term ;
op: OPERATOR | COMMA;
%%

Есть проблема:

test.y: conflicts: 2 shift/reduce

Как я могу это решить?

Answer 1

Чтобы определить, где находятся конфликты, используйте параметр --verbose и посмотрите файл example.output, где ваш входной файл example.y. Вот файл, который я получил от вашего ввода:

State 7 conflicts: 2 shift/reduce

(опущено)

state 7

    2 term: term . op term
    2     | term op term .

    COMMA     shift, and go to state 4
    OPERATOR  shift, and go to state 5

    COMMA     [reduce using rule 2 (term)]
    OPERATOR  [reduce using rule 2 (term)]
    $default  reduce using rule 2 (term)

    op  go to state 6

Answer 2

Проблема в том, что вы определили term:

term: NUMBER | term op term ;

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

Решением может быть определение:

term: NUMBER reminder;
reminder: /* empty */ | op term;

Грамматика после адаптации выглядит следующим образом:

%token NUMBER
%token COMMA
%token OPERATOR
%left OPERATOR
%left COMMA
%%

term: NUMBER reminder;
reminder: /* empty */ | op term;
op: OPERATOR | COMMA;
%%

компилируется без предупреждений с помощью bison (GNU Bison) 2.4.1.

Answer 3

Возможно, вы не указали приоритет операторов, как,

% осталось '+' '-'

% осталось '*' '/'

(в разделе определения)