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

Question

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

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

arg_list 
    : ID 
    | arg_list ID 
    ; 

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

fnbody 
    : '{' '}' 
    ; 

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

Answer 1

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

Второго варианта заключается в добавлении предпросмотра в лексере - в этом случае, прежде чем возвращать ')' маркер, посмотрите, если следующая лексема является '{' и либо вернуть специальный тег, который говорит вам, это является 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 
      ;