Как я могу разрешить конфликт reduce reduce:

Следующая (упрощенная) грамматика бизона производит конфликт reduce reduce: 

expr
    :    '(' expr ')'
    |    ID
    |    fn
    ;

arg_list
    :    ID
    |    arg_list ID
    ;

fn
    :    '(' ')' fnbody
    |    '(' arg_list ')' fnbody
    ;

fnbody
    :    '{' '}'
    ;

Я вижу проблему-только с одним маркером lookahead невозможно сказать, является ли (an_id '(' expr ')' или fn. Но как мне ее разрешить?

1 2
yacc bison

1 ответ:

Ну, самый простой ответ-просто использовать больше lookahead в синтаксическом анализаторе - либо использовать что-то вроде btyacc, либо использовать опцию bison %glr-parser.

Второй вариант-добавить lookahead в лексере - в этом случае, прежде чем возвращать маркер ')', Посмотрите, является ли следующий маркер '{' и либо верните специальный тег, который говорит вам, что это arg_list, который вы собираетесь закончить, а не заключенное в скобки выражение, либо просто верните два в виде одного маркера и измените свою грамматику так, как вы хотите. подходящий.

Третий выбор-это факторизация грамматики. Это не всегда легко и может увеличить размер грамматики. Основная идея состоит в том, чтобы идентифицировать конфликтующие правила и объединить их в единое правило, которое может быть исправлено синтаксическим анализатором и отложить выбор относительно того, что является окончательной конструкцией, пока вы не увидите достаточно.

В этом примере вы добавляете новое правило для конфликтующего случая: 

expr_or_fnhead:  '(' ID ')'  ;

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

fn :  '(' ')' fnbody               /* 0 arg function */
   |  expr_or_fnhead fnbody        /* 1 arg function */
   |  '(' ID arg_list ')' fnbody   /* 2+ arg function */
   ;

Правило expr более сложное: 

expr       : ID
           | non_ID_expr
           ;
non_ID_expr: '(' non_ID_expr ')'
           | expr_or_fnhead
           | fn
           ;
2