Сдвиг уменьшить конфликт

Question

У меня проблемы с пониманием сдвига / уменьшения конфликта для грамматики, которая, как я знаю, не имеет двусмысленности. Этот случай относится к типу if else, но это не проблема 'dangling else', поскольку у меня есть обязательные предложения END, разделяющие блоки кода.

Вот грамматика для gppg (это компилятор, похожий на бизон, и это не было эхом):

%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.

Я был бы признателен за элегантные решения, мне удалось сделать это, уничтожив правила / * empty * / и продублировав все, что требовало пустого списка, но в большой грамматике, над которой я работаю, это просто заканчивается как «синдром спаргетти грамматики».

Вот несколько ссылок:

http://nitsan.org/~maratb/cs164/bison.html

http://compilers.iecc.com/comparch/article/98-01-079

GPPG, парсер, который я использую

Руководство для зубров

Answer 1

Ваше исправленное правило ELSEIF не имеет маркеров для условия - к нему должны быть добавлены '(' и ')'.

Более серьезно, теперь у вас есть правило для

elsebody : else
         | elseifs else
         ;

и

elseifs : /* Nothing */
        | elseifs ...something... 
        ;

«Ничего» не нужно; об этом косвенно заботится «другое» без «elseifs».

Я был бы очень склонен использовать правила '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
    ;

Я не запускал это через генератор синтаксического анализатора, но я нахожу это относительно простым для понимания.

Answer 2

Я думаю, что проблема в предложении elseifs.

elseifs : elseifs '#' ELSEIF statements else
        | '#' ELSEIF statements else
        ;

Я думаю, что первая версия не требуется, так как предложение else в любом случае ссылается на elseifs:

else : '#' END
     | '#' ELSE statements '#' END
     | elseifs
     ;

Что произойдет, если вы измените elseifs?:

elseifs : '#' ELSEIF statements else
        ;

Answer 3

Ответ от Джонатана выше, кажется, будет лучшим, но так как он не работает для вас, у меня есть несколько предложений, которые вы можете попробовать, которые помогут вам в отладке ошибки.

Во-первых, рассматривали ли вы вопрос о том, чтобы сделать хеш / острый символ частью самих токенов (т. Е. #END, #IF и т. Д.)? Так что они могут быть уничтожены лексером, а это значит, что их не нужно включать в анализатор.

Во-вторых, я призываю вас переписать правила, не дублируя потоки токенов. (Часть принципа «Не повторяйся сам».) Таким образом, правило «# # инструкции ELSEIF else» должно существовать только в одном месте в этом файле (а не в двух, как указано выше).

Наконец, я предлагаю вам рассмотреть приоритет и ассоциативность токенов IF / ELSEIF / ELSE. Я знаю, что у вас должна быть возможность написать парсер, который не требует этого, но в этом случае это может быть то, что вам нужно.

Answer 4

ОК - здесь грамматика (не минимальная) для блоков if. Я выкопал его из некоторого кода, который у меня есть (называемый adhoc, основанный на hoc из «Среды программирования UNIX» Кернигана и Плаугера). Эта контурная грамматика компилируется с 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).

Я не потратил время на выяснение того, почему это компилирует без конфликтов, а то, что я описал ранее, нет. Надеюсь, это поможет.

Answer 5

elsebody : elseifs else
         | elseifs
         ;

elseifs : /* empty */
        | elseifs '#' ELSEIF statements
        ;

else : '#' ELSE statements '#' END
     ;

Я думаю, что это должно оставить рекурсию и всегда заканчиваться.

Answer 6

Я все еще переключаюсь, и в моем исходном вопросе были некоторые ошибки, так как последовательность 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 ИНФОРМАЦИЯ . Но я ищу решение с левой рекурсией в предложении elseifs .