Почему правило для каждой операции в зубре - PullRequest
Новая
       106

Почему правило для каждой операции в зубре

1 голос
/ 18 апреля 2020

При поиске грамматики бизонов я нашел этот пример грамматики C:

https://www.lysator.liu.se/c/ANSI-C-grammar-y.html

logical_and_expression
    : inclusive_or_expression
    | logical_and_expression AND_OP inclusive_or_expression
    ;
logical_or_expression
    : logical_and_expression
    | logical_or_expression OR_OP logical_and_expression
    ;

Я не понял причину для правила для каждой логической операции. Есть ли преимущество над этой конструкцией ниже? 

binary_expression:
    : object // imagine it can be bool, int, real ...
    | binary_expression AND_OP binary_expression
    | binary_expression OR_OP binary_expression
    ;

1 Ответ

3 голосов
/ 18 апреля 2020

Грамматика, которую вы цитируете, однозначна.

Тот, который вы предлагаете, является неоднозначным, хотя yacc / bison позволяет вам использовать правила приоритета для устранения неоднозначностей.

Есть несколько преимуществ использования грамматики, которая делает явный приоритет операторов:

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

  • Грамматика является автономной. Неоднозначные грамматики могут быть поняты только с добавлением правил приоритета. Это особенно важно для грамматик, используемых в языковых стандартах, но, как правило, влияет на попытки автоматически создавать другие инструменты на основе синтаксиса.

  • Явные грамматики носят более общий характер. Не все операторные ограничения можно легко описать с помощью сравнения чисел c.

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

С другой стороны, правила приоритета имеют некоторые преимущества:

  • Таблица приоритетов компактно описывает приоритет оператора, что полезно для быстрого ознакомления.

  • Полученная грамматика требует меньше единиц продукции, немного увеличив скорость разбора. (Обычно не заметно, но все же ...)

  • Некоторые конфликты намного легче разрешить с помощью деклараций предшествования, хотя понимание того, как конфликт разрешается, может быть неочевидным. (Пример classi c представляет собой неопределенную неопределенность.) Такие случаи не имеют ничего общего с интуитивным пониманием приоритета операторов, поэтому использование правил приоритета является чем-то вроде хака.

Использование грамматических правил не влияет на общий размер грамматики. Как уже упоминалось, правила приоритета позволяют избежать необходимости создания единиц, но каждая единица производства соответствует одной декларации приоритета, поэтому общее количество строк одинаково. Нетерминалов меньше, но нетерминалы стоят недорого; Основное раздражение в yacc / bison - объявление всех типов semanti c, но это легко автоматизировать.

...