Помогите с конфликтом Shift/Reduce - Попытка смоделировать (X A)* (X B)*

StackOverflow https://stackoverflow.com/questions/949976

Вопрос

Я пытаюсь смоделировать выражение EBNF 

("declare" "namespace" ";")* ("declare" "variable" ";")*

Я создал грамматику yacc (я использую MPPG), которая, кажется, отражает это, но не соответствует моему тестовому выражению.

Тестовый пример, который я пытаюсь сопоставить, 

declare variable;

Поток токенов от лексера 

KW_Declare
KW_Variable
Separator

Анализ грамматики говорит, что существует «конфликт сдвига/сокращения, состояние 6 на KW_Declare».Я попытался решить эту проблему с помощью «%left PrologHeaderList PrologBodyList», но ни одно из решений не помогло.

Program                     : Prolog;
Prolog                      : PrologHeaderList PrologBodyList;

PrologHeaderList            : /*EMPTY*/
                            | PrologHeaderList PrologHeader;
PrologHeader                : KW_Declare KW_Namespace Separator;

PrologBodyList              : /*EMPTY*/
                            | PrologBodyList PrologBody;
PrologBody                  : KW_Declare KW_Variable Separator;

KW_Declare KW_Namespace Разделитель KW_Variable — это все токены со значениями «declare», «naemsapce», «variable», «;».

Это было полезно?

Решение

Прошло много времени с тех пор, как я использовал что-либо подобное yacc, но вот несколько советов, которые могут помочь, а могут и не помочь.

Кажется, в этой ситуации вам нужен просмотр с двумя токенами.Парсер доходит до последнего ПрологЗаголовок, и он должен решить, является ли следующая конструкция ПрологЗаголовок или ПрологТело, и он не может определить это по файлу KW_Declare.Если в этой ситуации есть директива увеличить просмотр вперед, это, вероятно, решит проблему.

Вы также можете добавить контекст в свои действия:а не определять ПрологЗаголовокСписок и ПрологBodyList, определять Список правил Пролога и чтобы действия вызывали ошибку, если заголовок появляется после тела.Некрасиво, но иногда приходится это делать:то, что кажется простым в грамматике, может оказаться непростым в сгенерированном парсере.

Хакерский подход может заключаться в объединении токенов:скорее, чем KW_Declare и KW_Variable, пусть ваш лексер распознает пространство и использует KW_Declare_Variable.Поскольку оба являются ключевыми словами, вы не столкнетесь с проблемами конфликта пространств имен.

Другие советы

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top