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

Ответ 1

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

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

elsebody : else
         | elseifs else
         ;

и

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

"Ничто" не требуется; он неявно позаботится о "elsebody" без "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
    ;

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

Ответ 2

Я думаю, что проблема заключается в условии elseifs.

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

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

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

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

elseifs : '#' ELSEIF statements else
        ;

Ответ 3

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

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

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

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

Ответ 4

Я все еще переключаю предмет arround, и у моего первоначального вопроса были некоторые ошибки, так как последовательность 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.

Ответ 5

elsebody : elseifs else
         | elseifs
         ;

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

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

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

Ответ 6

ОК - вот грамматика (не минимальная) для блоков if. Я выкопал его из некоторого кода, который у меня есть (называемый adhoc, основанный на hoc от Kernighan и Plauger "среда программирования 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. Он включает THEN, но это необязательно. Операции "начать" и "конец" были использованы для захвата счетчика программ в сгенерированной программе и, следовательно, должны быть удалены из этого, не затрагивая его.

Была причина, по которой я думал, что мне нужно использовать правильную рекурсию вместо обычной левой рекурсии, но я думаю, что это связано с используемой мной стратегией генерации кода, а не с чем-либо еще. Вопросительный знак в комментарии был в оригинале; Я помню, что не доволен этим. Программа в целом работает - это проект, который был на заднем плане в течение последнего десятилетия или около того (hmmm... Я проделал определенную работу в конце 2004 года и в начале 2005 года, а до этого 1992 года и 1993).

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