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

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

0 голосов
/ 29 мая 2018

У меня есть следующая грамматика 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, но безрезультатно.Учитывая, что бизоны разрешают конфликт по своему усмотрению (например, изменяет, а не уменьшает), это не так уж и плохо, но мне интересно, как мы можем избавиться от конфликта, не меняя принятого языка.

1 Ответ

0 голосов
/ 29 мая 2018

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

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

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

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

%%

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

NoHungry
  : "true"
  | "false"

Выдержка из -v output: 

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 не предоставляет автоматического инструмента для выполнения этих вычислений, хотя обычно вы можете извлечь список из shift-lowerотчеты о конфликтах.(Может даже быть, что "if" является частью набора, в этом случае ассоциативность будет иметь значение.)

...