Когда двусмысленная грамматика или производственное правило в порядке?(бизон переключает / уменьшает предупреждения)

Question

Безусловно, существует множество документов и руководств по устранению ошибок shift / reduce.Документы bison предполагают, что правильное решение, как правило, состоит в том, чтобы просто % ожидать их и иметь с этим дело.

Когда у тебя случаются подобные вещи:

S: S 'b' S | 't'

Вы можете легко разрешить их следующим образом:

S: S 'b' T | T
T: 't'

Мой вопрос заключается в следующем:Лучше ли оставить грамматику немного двусмысленной и %ожидать проблем сдвига / уменьшения или лучше попытаться скорректировать грамматику, чтобы избежать их?Я подозреваю, что существует баланс, и он основан на потребностях автора, но я действительно не знаю.

Answer 1

Когда я читаю это, ваш вопрос звучит так: "Когда двусмысленная грамматика или производственное правило в порядке?"

Сначала рассмотрим язык, который вы описываете.Каковы были бы последствия допущения неоднозначного производственного правила в язык.

Ваш пример описывает язык, который может включать в себя выражение типа: t b t b t b t

Выражение, разрешенное, как в вашем втором примере, будет следующим (((( t ) b t) b t ) b t ) но в двусмысленной грамматике это также может стать ( t b ( t b ( t b ( t)))) или даже ( t b t ) b ( t b t ).Который мог бы быть действительным, может зависеть от языка.Если в b оператор моделирует вычитание, это действительно не должно быть двусмысленным, но если бы это было сложение, все могло бы быть в порядке.Это действительно зависит от языка.

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

Answer 2

Вы можете управлять разрешением конфликтов с помощью приоритета оператора.Объявлять 'b' как оператор с левой или правой ассоциацией, и вы рассмотрели, по крайней мере, этот случай.

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

Answer 3

В моем курсе по компиляции в прошлом семестре мы использовали bison и создали компилятор для подмножества pascal.

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

Это анализ затрат и выгод, когда все становится по-настоящему сложным, но, ИМХО, сначала следует подумать об исправлении этого, а затем на самом деле выяснить, в чем будет заключаться работа (и если эта работа что-то еще сломает или усложнит что-то еще), и перейти оттуда.Никогда не выдавайте их за банальность.

Answer 4

Когда мне нужно доказать, что грамматика однозначна, я обычно записываю ее сначала как Синтаксический анализ Грамматики выражения, а затем преобразуйте его вручную в любой грамматический тип, который я использую для нужд проекта.Однако, по моему опыту, потребность в таком уровне доказательства встречается очень редко, поскольку большинство конфликтов сдвига / уменьшения, с которыми я сталкивался, были довольно тривиальными, чтобы показать правильность (в порядке вашего примера).