Reduce/reduce 冲突

Question

我正在编写一个语法 (YACC - "LALR") 应该识别以下单词，例如：

ident(ident,...,ident) = ident(num,ident,num,...,num) 
ident(ident,...,ident) = num
ident = num
ident = ident(num,ident,num,...,num) 
ident(ident,num,...,num)
num
ident

然后我写了下面的语法：

(1) L : ident ( PARAM ) = E
(2) L : E

(3) E : ident ( ARG )
(4) E : N

(5) N : num
(6) N : ident

(7) ARG : ARG , E
(8) ARG : E

(9) PARAM : PARAM , ident
(10)PARAM : ident

所以，我的问题是规则 (6) 和 (10) 之间的 reduce/reduce 冲突。有没有人知道如何解决这个问题？

之前，我问了以下问题，认为这是对我的真实问题的简化......但事实并非如此。

郑重声明，我之前的问题是关于识别这些词的语法：

a
b
b,b
b,b,b
[...]
b,b,b,[...],b # infinite list of b

所以，我写了下面的语法：

L : E
  | F

E : a
  | b

F : F , b
  | b

但是，从逻辑上讲，我有一个 reduce/reduce 规则冲突：

F : b

和

E : b

这道题的正确语法是：

E : a
E : F
F : F,b
F : b

Answer 1

简单的解决方案是在产生式 1 附带的语义操作中检查括号列表的有效性。然后你只需删除 PARAM，并使用 ARG 代替。

另一个简单的解决方案是让 bison 生成 GLR 解析器而不是 LALR 解析器。由于语法是明确的，这将工作正常。它会稍微慢一些，但在大多数情况下你不会注意到。

但是，可以修改语法，使其能够准确识别所需的语言。有一个问题：在看到以下标记之前，我们无法判断 ident(ident) 是 E 还是 L 的开头。此外，我们无法判断（在大多数情况下）括号列表中的 ident 是否是 L 的一部分，或者是否应该将其简化为 N 因为它是一部分E.

为了避免冲突，我们在构建AST时没有进行一定的缩减，然后在需要的时候修复它。特别是，我们可能需要将 L 转换为 E 或将 PARAM 转换为 ARG，这涉及将 idents 列表转换为 args 列表，这反过来涉及对每个 ident.

执行 ident 到 N 的减少

(以下参考我实际写的代码，使用常规约定终端全大写，非终端小写，习惯难改。抱歉。)

所以我们要做的是将逗号分隔列表的产生式分成两个 不相交 集。一个是 name_list，这是一个简单的标识符列表 (IDs)，它可能会变成参数列表或参数列表。另一种产生式是 arg_list，其中至少包含一个数字 (NUM)。这无疑是一个参数列表。

如果我们真的在解析一个参数列表，我们可能会开始将它解析为一个标识符列表，但我们最终会发现一些东西迫使我们认清它是什么。要么我们会命中 NUM，在这种情况下我们需要将所有 ID 追溯减少为 value，否则我们将在没有看到语句的情况下到达语句的末尾=，在这种情况下，我们需要将 lvalue 重新用作调用表达式。

结果如下。为了尽可能清楚，我包括了语义动作。不包括实际功能，但我相信它们的行为或多或少从它们的名称中可以看出。请注意，在两个操作中存在显式转换：一个是将 param_list 转换为 arg_list（当遇到 NUM 时），另一个是将 lvalue 到 expr。另外，我实际上并没有插入 value: ID | NUM 产生式，因为在这种情况下，将缩减作为语义操作的一部分会更直接。请参阅语法后的注释。

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

param_list
    : ID                    { $$ = push_name(0, ); }
    | param_list ',' ID     { $$ = push_name(, ); }
arg_list
    : NUM                   { $$ = push_val(0, make_ival()); }
    | arg_list ',' ID       { $$ = push_val(, make_sval()); }
    | arg_list ',' NUM      { $$ = push_val(, make_ival()); }
    | param_list ',' NUM    { $$ = push_val(names_to_vals(),
                                            make_ival()); }
lvalue
    : ID '(' param_list ')' { $$ = make_proto(, reverse_names()); }
expr: ID '(' arg_list ')'   { $$ = make_call(, reverse_vals()); }
    | lvalue                { $$ = proto_to_call(); }
    | NUM                   { $$ = make_ival(); }
    | ID                    { $$ = make_sval(); }
stmt: lvalue '=' expr       { $$ = make_assign(, ); }
    | 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 的两个产生式（并且可能在语法的其他地方）。

Reduce/reduce 冲突

Reduce/reduce conflict

grammar

yacc

reduce-reduce-conflict