Решение уменьшить / уменьшить конфликты

У нас есть грамматика CFG, и мы строим таблицу разбора LR(1). Мы видим, что в одной ячейке таблицы синтаксического анализа есть конфликт "уменьшить - уменьшить". Можно ли решить этот конфликт, используя больше входных символов прогнозирования на каждом шаге? Я спрашиваю об этом, потому что думаю, что, увеличивая символы предпросмотра, мы можем (не всегда) разрешать только сдвиг - уменьшать конфликты. Я имею в виду, что дополнительные взгляды в конфликте с уменьшением и уменьшением не помогают нам. Я прав?

Источник

2 ответа

Решение

Можно было бы решить конфликт уменьшить / уменьшить с помощью большего количества перспектив. Это также может быть возможно решить путем рефакторинга.

Это действительно зависит от характера конфликта. Там нет общей процедуры.

Пример конфликта уменьшения / уменьшения, который может быть решен с помощью дополнительного просмотра:

A → something
B → A
C → A
D → B u v
D → C u w

Здесь последние два производства D однозначны, но решение о сокращении A в B или C не может быть сделано, когда u виден. Это сделал бы еще один символ предвкушения, потому что второй следующий символ определяет сокращение.

Рефакторинг решение:

Au → A u
Bu → Au
Cu → Au
D  → Bu v
D  → Cu w

Отложив выбор B/C на один токен, нам удалось устранить конфликт уменьшения / уменьшения. Обратите внимание, что это решение будет работать, даже если u не один токен; это может, например, нетерминал. Таким образом, эта модель может работать в тех случаях, когда простого увеличения прогнозирования недостаточно.

Источник

В общем, любой конфликт может быть разрешен дополнительным прогнозом. В крайнем случае вам нужно прочитать файл до конца. Нет существенной разницы между сдвигом / уменьшением и уменьшением / уменьшением конфликтов. Их разрешение отчасти похоже.

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

Пожалуйста, посмотрите: http://cdsan.com/LinkPool/Data/2915/Conflicts-In-The-LR-Grammars.pdf

Если у вас есть вопросы, пожалуйста, дайте мне знать.

Источник
Другие вопросы по тегам