Сдвиг уменьшить конфликт
Вопрос
У меня возникла проблема с пониманием конфликта сдвига/сокращения для грамматики, которая, как я знаю, не имеет двусмысленности.Случай относится к типу if else, но это не проблема «висячего else», поскольку у меня есть обязательные предложения END, разделяющие блоки кода.
Вот грамматика gppg (это компилятор типа Bison...и это было не эхо):
%output=program.cs
%start program
%token FOR
%token END
%token THINGS
%token WHILE
%token SET
%token IF
%token ELSEIF
%token ELSE
%%
program : statements
;
statements : /*empty */
| statements stmt
;
stmt : flow
| THINGS
;
flow : '#' IF '(' ')' statements else
;
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Вот результат конфликта:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 10: else -> elseifs
Shift "'#'": State-22 -> State-23
Items for From-state State 22
10 else: elseifs .
-lookahead: '#', THINGS, EOF
11 elseifs: elseifs . '#' ELSEIF statements else
Items for Next-state State 23
11 elseifs: elseifs '#' . ELSEIF statements else
// End conflict information for parser
Я уже все переключил и знаю, как это решить, но это решение предполагает отказ от левой рекурсии на «elseif» в пользу правой рекурсии.
Я просмотрел всю скудную документацию по этой проблеме, которую нашел в Интернете (в конце я публикую несколько ссылок), но до сих пор не нашел элегантного решения.Я знаю об ANTLR и не хочу сейчас об этом думать.Пожалуйста, ограничьте свое решение парсерами Yacc/Bison.
Я был бы признателен за элегантные решения, мне удалось это сделать, исключив правила /* пустые */ и продублировав все, что нуждалось в пустом списке, но в более крупной грамматике, над которой я работаю, это просто заканчивается как «синдром грамматики спаргетти».
Вот несколько ссылок:
http://nitsan.org/~maratb/cs164/bison.html
http://compilers.iecc.com/comparch/article/98-01-079
Решение
В вашем пересмотренном правиле ELSEIF нет маркеров для условия — номинально к нему должны быть добавлены символы «(» и «)».
А если серьезно, теперь у вас есть правило для
elsebody : else
| elseifs else
;
и
elseifs : /* Nothing */
| elseifs ...something...
;
«Ничто» не нужно;о нем неявно заботится «другой» без «остальных».
Я был бы очень склонен использовать правила «opt_elseifs», «opt_else» и «end»:
flow : '#' IF '(' ')' statements opt_elseifs opt_else end
;
opt_elseifs : /* Nothing */
| opt_elseifs '#' ELSIF '(' ')' statements
;
opt_else : /* Nothing */
| '#' ELSE statements
;
end : '#' END
;
Я не запускал это через генератор синтаксического анализатора, но мне кажется, что это относительно легко понять.
Другие советы
Я думаю, что проблема в предложении elseifs.
elseifs : elseifs '#' ELSEIF statements else
| '#' ELSEIF statements else
;
Я думаю, что первая версия не требуется, так как предложение else в любом случае ссылается на elseifs:
else : '#' END
| '#' ELSE statements '#' END
| elseifs
;
Что произойдет, если вы измените elseifs?
elseifs : '#' ELSEIF statements else
;
Ответ от Джонатана выше, кажется, будет лучшим, но так как он не работает для вас, у меня есть несколько предложений, которые вы можете попробовать, которые помогут вам в отладке ошибки.
Во-первых, рассматривали ли вы вопрос о том, чтобы сделать хеш / острый символ частью самих токенов (т. е. #END, #IF и т. д.)? Таким образом, они могут быть уничтожены лексером, что означает, что их не нужно включать в анализатор.
Во-вторых, я призываю вас переписать правила, не дублируя потоки токенов. (Часть принципа «Не повторяй себя».) Итак, правило " '#' Операторы ELSEIF else " должен существовать только в одном месте в этом файле (а не в двух, как у вас выше). Р>
Наконец, я предлагаю вам рассмотреть приоритетность и ассоциативность токенов IF / ELSEIF / ELSE. Я знаю, что у вас должна быть возможность написать парсер, который не требует этого, но это может быть то, что вам нужно в этом случае.
Я все еще переключаюсь, и в моем исходном вопросе были некоторые ошибки, так как последовательность elseifs содержала else в конце, что было неверно. Вот еще один взгляд на этот вопрос, на этот раз я получаю два конфликта сдвига / уменьшения:
flow : '#' IF '(' ')' statements elsebody
;
elsebody : else
| elseifs else
;
else : '#' ELSE statements '#' END
| '#' END
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
Конфликты сейчас:
// Parser Conflict Information for grammar file "program.y"
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 12: elseifs -> /* empty */
Shift "'#'": State-10 -> State-13
Items for From-state State 10
7 flow: '#' IF '(' ')' statements . elsebody
4 statements: statements . stmt
Items for Next-state State 13
10 else: '#' . ELSE statements '#' END
11 else: '#' . END
7 flow: '#' . IF '(' ')' statements elsebody
Shift/Reduce conflict on symbol "'#'", parser will shift
Reduce 13: elseifs -> elseifs, '#', ELSEIF, statements
Shift "'#'": State-24 -> State-6
Items for From-state State 24
13 elseifs: elseifs '#' ELSEIF statements .
-lookahead: '#'
4 statements: statements . stmt
Items for Next-state State 6
7 flow: '#' . IF '(' ')' statements elsebody
// End conflict information for parser
Пустые правила только ухудшают gppg, я боюсь. Но они кажутся настолько естественными в использовании, что я продолжаю пробовать их.
Я уже знаю, что правильная рекурсия решает проблему, как сказал 1800 INFORMATION . Но я ищу решение с левой рекурсией в предложении elseifs .
elsebody : elseifs else
| elseifs
;
elseifs : /* empty */
| elseifs '#' ELSEIF statements
;
else : '#' ELSE statements '#' END
;
Я думаю, что это должно оставить рекурсию и всегда заканчиваться.
Хорошо - здесь есть грамматика (не минимальная) для блоков if. Я выкопал его из некоторого кода, который у меня есть (называемый adhoc, основанный на hoc из Kernighan & Plauger's " The UNIX Programming Environment "). Эта контурная грамматика компилируется с Yacc без конфликтов.
%token NUMBER IF ELSE
%token ELIF END
%token THEN
%start program
%%
program
: stmtlist
;
stmtlist
: /* Nothing */
| stmtlist stmt
;
stmt
: ifstmt
;
ifstmt
: ifcond endif
| ifcond else begin
| ifcond eliflist begin
;
ifcond
: ifstart cond then stmtlist
;
ifstart
: IF
;
cond
: '(' expr ')'
;
then
: /* Nothing */
| THEN
;
endif
: END IF begin
;
else
: ELSE stmtlist END IF
;
eliflist
: elifblock
| elifcond eliflist begin /* RIGHT RECURSION */
;
elifblock
: elifcond else begin
| elifcond endif
;
elifcond
: elif cond then stmtlist end
;
elif
: ELIF
;
begin
: /* Nothing */
;
end
: /* Nothing */
;
expr
: NUMBER
;
%%
Я использовал 'NUMBER' в качестве фиктивного элемента вместо THINGS, и я использовал ELIF вместо ELSEIF. Это включает в себя ТОГДА, но это не обязательно. Операции 'begin' и 'end' использовались для захвата счетчика программы в сгенерированной программе - и поэтому должны быть удалены из него, не затрагивая его.
Была причина, по которой я думал, что мне нужно использовать правую рекурсию вместо обычной левой рекурсии - но я думаю, что это связано со стратегией генерации кода, которую я использовал, а не с чем-либо еще. Вопросительный знак в комментарии был в оригинале; Я помню, что не был счастлив с этим. Программа в целом работает - это проект, который находился на заднем плане в течение последнего десятилетия или около того (хммм ... Я проделал некоторую работу в конце 2004 года и в начале 2005 года; до этого это был 1992 год). и 1993).
Я не потратил время на выяснение того, почему это компилирует без конфликтов, а то, что я описал ранее, нет. Надеюсь, это поможет.