Уменьшить / уменьшить конфликт

Простое решение состоит в том, чтобы проверить правильность списка в скобках в семантическом действии, связанном с продуктом 1. Тогда вы просто избавитесь от PARAM и вместо него используете ARG.

Другое простое решение — попросить bison создать синтаксический анализатор GLR вместо синтаксического анализатора LALR. Поскольку грамматика однозначна, это будет работать нормально. Это будет немного медленнее, но в большинстве случаев вы этого не заметите.

Однако можно изменить грамматику так, чтобы она точно распознавала нужный язык. Есть одна проблема: мы не можем сказать, является ли ident(ident) E или началом L, пока не увидим следующий токен. Кроме того, мы не можем сказать (в большинстве случаев), является ли ident в списке в скобках частью L или его следует сократить до N, потому что он является частью E.

Во избежание конфликтов мы строим AST без определенных сокращений, а потом исправляем при необходимости. В частности, нам может понадобиться преобразовать L в E или PARAM в ARG, что включает в себя преобразование списка идентификаторов в список аргументов, что, в свою очередь, включает выполнение сокращения ident до N для каждого ident.

(Далее я ссылаюсь на написанный мной код, в котором используется обычное соглашение о том, что терминалы пишутся ЗАГЛАВНЫМИ БУКВАМИ, а нетерминалы — строчными буквами. Привычки умирают с трудом. Извините.)

Итак, что мы делаем, так это делим продукцию для списков, разделенных запятыми, на два непересекающихся множества. Одним из них является name_list, представляющий собой простой список идентификаторов (IDs), который может оказаться списком параметров или списком аргументов. Другая продукция — arg_list, которая включает хотя бы одно число (NUM). Это однозначно список аргументов.

Если мы на самом деле анализируем список аргументов, мы могли бы начать анализировать его как список идентификаторов, но в конечном итоге мы найдем что-то, что заставит нас распознать его таким, какой он есть. Либо мы столкнемся с NUM, и в этом случае нам нужно задним числом уменьшить все IDs до values, либо мы дойдем до конца оператора, не увидев =, и в этом случае нам нужно чтобы переназначить lvalue как выражение вызова.

Итак, получается следующее. Чтобы быть максимально ясным, я включаю семантические действия. Фактические функции не включены, но я надеюсь, что их поведение более или менее очевидно из их названий. Обратите внимание, что существует явное преобразование в двух действиях: одно для преобразования param_list в arg_list (когда встречается NUM), а другое - для преобразования lvalue в expr. Кроме того, я на самом деле не вставлял производство value: ID | NUM, потому что в этом случае было бы проще просто выполнить сокращение как часть семантического действия. См. примечание после грамматики.

prog: /* EMPTY */
    | prog stmt ';'         { print_stmt($2); free_node($2); }

param_list
    : ID                    { $$ = push_name(0, $1); }
    | param_list ',' ID     { $$ = push_name($1, $3); }
arg_list
    : NUM                   { $$ = push_val(0, make_ival($1)); }
    | arg_list ',' ID       { $$ = push_val($1, make_sval($3)); }
    | arg_list ',' NUM      { $$ = push_val($1, make_ival($3)); }
    | param_list ',' NUM    { $$ = push_val(names_to_vals($1),
                                            make_ival($3)); }
lvalue
    : ID '(' param_list ')' { $$ = make_proto($1, reverse_names($3)); }
expr: ID '(' arg_list ')'   { $$ = make_call($1, reverse_vals($3)); }
    | lvalue                { $$ = proto_to_call($1); }
    | NUM                   { $$ = make_ival($1); }
    | ID                    { $$ = make_sval($1); }
stmt: lvalue '=' expr       { $$ = make_assign($1, $3); }
    | expr

И вот пример вывода из приведенного выше:

id1;
[E: id1]
3;
[E: 3]
f(id1);
[CALL: f([E: id1])]
f(3);
[CALL: f([E: 3])]
f(id1,3);
[CALL: f([E: id1], [E: 3])]
f(3,id1);
[CALL: f([E: 3], [E: id1])]
f(id1)=g(id2);
[ASSIGN: [PROTO: f(id1)] = [CALL: g([E: id2])]]
f(id1)=42;
[ASSIGN: [PROTO: f(id1)] = [E: 42]]
f(id1)=g(42);
[ASSIGN: [PROTO: f(id1)] = [CALL: g([E: 42])]]
f(id1)=g;
[ASSIGN: [PROTO: f(id1)] = [E: g]]

В реальной грамматике вполне вероятно, что arg_list на самом деле будет списком expr, а не только ID или NUM. Это все еще может работать с вышеуказанной моделью. Нам нужно определить expr_not_ID (то есть expr, а не просто ID), который мы будем использовать вместо NUM в приведенных выше постановках. Тогда мы можем определить expr как expr_not_ID | ID для использования в двух постановках для stmt (и, возможно, в других местах грамматики).