Как должны быть определены бинарные операторы в зубрах?

Question

Я пишу синтаксический анализатор в C с бизоном, и, хотя он, кажется, работает правильно при любых обстоятельствах, которые я до сих пор пытался, я получаю кучу предупреждений сдвига / уменьшения на моих бинарных операторах (и одно на моем унарном операторе NOT, как Что ж).

binary_op :
      PLUS { }
      | MINUS { }
      | TIMES { }
      | SLASH { }
      | POWER { }
      | AND { }
      | OR { }
      | LE { }
      | LT { }
      | GE { }
      | GT { }
      | EQ { }
      | NE { }
      | MOD { }
    ;

unary_op :
    NOT { }
    ;

expr :
    ...
    | unary_op expr { }
    | expr binary_op expr { }

Когда я запускаю свой.y файл через bison --verbose, я вижу:

state 51
   11 set_existence: expr . IN set
   12              | expr . NOT IN set
   34 expr: expr . binary_op expr
   34     | expr binary_op expr .

   ...
   NOT    shift, and go to state 26
   AND    shift, and go to state 27
   OR     shift, and go to state 28
   ....
   NOT     [reduce using rule 34 (expr)]
   AND     [reduce using rule 34 (expr)]
   OR      [reduce using rule 34 (expr)]

Я не вижу каких-либо проблем с синтаксическим анализом бинарных операторов, но, похоже, я все равно должен решить проблемы сдвига / уменьшения. Я не могу понять, где конфликт - произведения set_existence кажутся совершенно не связанными. Мое лучшее предположение (выстрел в темноте) состоит в том, что это может иметь какое-то отношение к тому факту, что EQ используется в качестве бинарного оператора (сравнение равенства), а также присваивание (например, "foo = bar = baz;" установит foo в true/false в зависимости от того, равны ли bar и baz). Если я изменю свое сравнение на равенство == ("foo = bar==baz;"), мой синтаксический анализатор будет работать так, как ожидалось, но при этом все равно будут иметь такие же конфликты сдвиг / уменьшение

РЕДАКТИРОВАТЬ: У меня есть определенная ассоциативность:

%left OR
%left AND
%left NOT
%left LT LE GT GE NE EQ
%left PLUS MINUS
%left TIMES MOD SLASH
%left POWER

Answer 1

Есть несколько способов избежать этого. Во-первых, использовать %left, %right а также %nonassoc Команды для указания уровня приоритета (см. руководство).

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

expr ::= term | expr + term
term ::= factor | term * factor
factor ::= number | ( expr )

Это устраняет неоднозначный анализ на уровне грамматики.