缩小/减少冲突

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）之间的减少/减少冲突。 有没有人有如何解决这个问题的想法？

---

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

为了记录在案，我刚才的问题是在语法识别那些话：

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 

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

F : b 

和

E : b 

这个问题的正确语法是：

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

Answer 1

简单的解决方法是检查组合列表的有效性在连接到生产1.然后你只需摆脱PARAM语义动作，并改用ARG。

另一个简单的解决方案是要求野牛生成GLR解析器而不是LALR解析器。由于语法是明确的，这将工作得很好。它会稍微慢一点，但在大多数情况下你不会注意到。

但是，可以修改语法，使其能够精确识别所需的语言。有一个问题：我们无法确定ident(ident)是E还是L的开始，直到我们看到以下标记为止。此外，我们无法说明（在大多数情况下）括号内列表中的ident是L的一部分，还是因为它是E的一部分而应减少为N。

为了避免冲突，我们建立AST没有一定的减少，然后在必要时修复它。特别地，我们可能需要一个L到E或PARAM转换为ARG，这涉及idents的列表转换成ARGS的列表，这又涉及到每个ident执行ident还原为N。

（在下文中，我指的是实际的代码我写的，它使用端子ALL-CAPS，而非端子是小写。习难改正常约定。对不起。）

所以我们所做的是将用于逗号分隔列表的作品分成两个不相交的集。一个是name_list，它是一个简单的标识符列表（ID s），它可能是一个参数列表或参数列表。另一种产品是arg_list，其中包括至少一个数字（NUM）。这无疑是一个参数列表。

如果我们实际上正在解析一个参数列表，我们可能会开始将它解析为一个标识符列表，但是我们最终会发现一些迫使我们识别它的原因。要么我们点击一​​个NUM，在这种情况下，我们需要追溯减少所有的ID s到value s，否则我们会在没有看到=的情况下到达声明的结尾，在这种情况下，我们需要重新调整作为调用表达式，可以使用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（也可能在语法中的其他位置）的两个作品中。