1

我正在编写一个应该识别以下单词的语法（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
4

1 回答 1

1

简单的解决方案是在附加到生产 1 的语义操作中检查括号列表的有效性。然后您只需摆脱PARAM，并ARG改用它。

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

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

为了避免冲突，我们在不进行某些缩减的情况下构建 AST，然后在必要时对其进行修复。特别是，我们可能需要将 an 转换L为 anE或将 a转换PARAM为 an ARG，这涉及将 idents 列表转换为 args 列表，这反过来又涉及对 each执行identto的归约。Nident

（在下文中，我参考了我编写的实际代码，它使用终端是全大写的正常约定，而非终端是小写。习惯很难改掉。对不起。）

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

如果我们实际上是在解析一个参数列表，我们可能会开始将它解析为一个标识符列表，但我们最终会找到一些迫使我们识别它的东西。要么我们点击 a NUM，在这种情况下，我们需要追溯地将所有IDs 减少为values，或者我们将在没有看到 a 的情况下到达语句的末尾=，在这种情况下，我们需要将 s 重新lvalue用作调用表达式。

所以结果如下。为了尽可能清楚，我将语义动作包括在内。实际功能不包括在内，但我相信它们的行为或多或少从它们的名称中显而易见。请注意，在两个操作中存在显式转换：一个将 a 转换param_list为 an arg_list（当NUM遇到 a 时），另一个将 an 转换lvalue为 an 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，而不仅仅是IDor NUM。这仍然可以与上述模型一起使用。我们需要定义expr_not_ID（即 anexpr不仅仅是 an ID），我们将NUM在上面的产生式中使用它来代替。然后我们可以将 as 定义expr为expr_not_ID | ID, 用于两个产生式 for stmt（并且可能在语法中的其他地方）。

于 2015-12-11T07:19:18.103 回答