Помощь в конфликтах Shift / Reduce - Попытка моделировать (X A) * (X B) * - PullRequest
Новая
       59

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

0 голосов
/ 04 июня 2009

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

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

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

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

declare variable;

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

KW_Declare
KW_Variable
Separator

Анализ грамматики говорит, что существует конфликт Shift / Reduce, состояние 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 Separator - это все токены со значениями "Declare", "Naemsapce", "variable", ";".

Ответы [ 2 ]

3 голосов
/ 04 июня 2009

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

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

Вы также можете ввести контекст в свои действия: вместо того, чтобы определять PrologHeaderList и PrologBodyList , определять PrologRuleList и иметь действия, вызывающие ошибку, если появляется заголовок после тела. Ужасно, но иногда вам приходится это делать: то, что кажется простым в грамматике, может быть непростым в сгенерированном парсере.

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

0 голосов
/ 04 июня 2009

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

...