Разрешить конфликт в грамматике бизонов с помощью разделенных пробелами списков выражений + if/then/else

Question

У меня есть следующая грамматика yacc/bison/happy:

%token 
  if              TokenIf
  then            TokenThen
  else            TokenElse
  true            TokenTrue
  false           TokenFalse

%left APP
%right IF

%%

Hungry
  : NoHungry
  | Hungry NoHungry %prec APP
  | if Hungry then Hungry else Hungry %prec IF

NoHungry
  : true
  | false

bison -v говорит мне, что в следующей ситуации есть два конфликта:

State 12

    2 Hungry: Hungry . NoHungry
    3       | if Hungry then Hungry else Hungry .

    true   shift, and go to state 2
    false  shift, and go to state 3

    true      [reduce using rule 3 (Hungry)]
    false     [reduce using rule 3 (Hungry)]
    $default  reduce using rule 3 (Hungry)

    NoHungry  go to state 8

Я попытался разрешить конфликт путем явного объявления приоритета с помощью %prec, но безрезультатно. Учитывая, что бизоны разрешают конфликт по своему усмотрению (например, изменяет, а не уменьшает), это не так уж плохо, но мне интересно, как мы можем избавиться от конфликта, не меняя принятого языка.

Answer 1

Как видно из отчета о зубрах, конфликты с терминалами true а также false, которые не перечислены в предшествующих отношениях. Следовательно, правила приоритета не применяются к этим конфликтам.

Напомним, что отношение приоритета определяется между производством и терминалом. Он не связан ни с двумя терминалами, ни с двумя производственными процессами (и поэтому не может быть использован для разрешения конфликтов уменьшения-уменьшения). Сравнение между приоритетом производства, которое может быть уменьшено, и терминалом прогнозирования определяет, произойдет ли уменьшение или сдвиг. Для удобства обозначения продукция представлена ​​именем терминала, обычно единственного терминала в продукции; это соответствует общему варианту использования, но иногда сбивает с толку. В частности, %prec Декларация служит только для того, чтобы дать правилу имя для использования в декларациях предшествования, и, вероятно, лучше подумать об этом, а не как о "явной" декларации.

Короче говоря, конфликт в упрощенной грамматике в вашем вопросе может быть разрешен путем явного добавления соответствующих терминалов в отношения предшествования:

%precedence "if"
%precedence "true" "false"

%%

Hungry
  : NoHungry
  | Hungry NoHungry
  | "if" Hungry "then" Hungry "else" Hungry %prec "if"

NoHungry
  : "true"
  | "false"

Выдержка из -v выход:

State 12

    2 Hungry: Hungry . NoHungry
    3       | "if" Hungry "then" Hungry "else" Hungry .

    "true"   shift, and go to state 2
    "false"  shift, and go to state 3

    $default  reduce using rule 3 (Hungry)

    NoHungry  go to state 8

Используя -r solved вместо -vВы можете увидеть разрешение более четко:

    Conflict between rule 3 and token "true" resolved as shift ("if" < "true").
    Conflict between rule 3 and token "false" resolved as shift ("if" < "false").

Я мог бы использовать "else" как имя для if производство, которое было бы по умолчанию без %prec декларация, но "if" кажется более интуитивным

%precedence объявление (доступно в последних версиях бизонов) не подразумевает левую или правую ассоциативность; в этом случае ассоциативность не применяется, потому что нет случая, когда конфликт включает производство и терминал равного приоритета. Если Happy не реализует это, либо %left или же %right может быть использовано по той же причине (ассоциативность не имеет значения), но я думаю, %precedence лучше документирует ситуацию.

Поскольку это, несомненно, сокращенный пример, стоит отметить, что более полная грамматика потребует некоторого грамматического анализа. В частности, список терминалов с приоритетом больше "if" придется включить все терминалы в FIRST(NoHungry)и bison не предоставляет автоматического инструмента для выполнения этих вычислений, хотя обычно вы можете извлечь список из отчетов о конфликтах с уменьшением смещения. (Это может быть даже "if" является частью набора, в этом случае ассоциативность будет иметь значение.)