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

Question

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

Когда у вас есть такие вещи:

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

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

Answer 4

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

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

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