Bison 下标表达式意外错误

Question

语法如下：

program: /*empty*/ | stmt program;
stmt: var_decl | assignment;
var_decl: type ID '=' expr ';';
assignment: expr '=' expr ';';
type: ID | ID '[' NUMBER ']';
expr: ID | NUMBER | subscript_expr;
subscript_expr: expr '[' expr ']';

我希望以下内容有效：

array[5] = 0;

这只是一个 assignment，左侧有一个 subscript_expr。然而，生成的解析器给出了该语句的错误：

syntax error, unexpected '=', expecting ID

生成解析器还会警告存在 1 个 shift/reduce 冲突。删除 subscript_expr 使其消失。

为什么会发生这种情况，我怎样才能将 array[5] = 0; 解析为 assignment 和 subscript_expr？

我正在使用 Bison 2.3。

Answer 1

添加 %glr-parser 解决了这个问题。

Answer 2

以下两个陈述在您的语言中均有效：

x [ 3 ] = 42;

x [ 3 ] y = 42;

第一个是数组变量x的一个元素的赋值，而第二个是声明和数组变量 y 的初始化，其元素为 type x.

但是从解析器的角度来看，x和y都只是ID；它无法知道 x 在第一种情况下是变量，在第二种情况下是类型。它所能做的就是注意到这两个语句分别匹配产生式 assignment 和 var_decl。

不幸的是，在看到 ] 之后的标记之前，它无法执行此操作。如果该标记是 ID，则语句必须是 var_decl；否则，它是一个 assignment（当然假设该语句是有效的）。

但是为了将语句解析为赋值，解析器必须能够生成

expr '=' expr

在本例中是 expr: subsciprt_expr 的结果，而 expr: subsciprt_expr 又是 subscript_expr: expr[expr]`。

所以第一个语句的归约集如下：（注意：我没有写移位；相反，我通过在每个归约的末尾放置一个 • 来标记解析的进度。要进入下一步，只需移动 • 直到到达手柄的末端。）

ID • [ NUMBER ] = NUMBER ;             expr: ID
expr [ NUMBER • ] = NUMBER ;           expr: NUMBER
expr [ expr ] • = NUMBER ;             subscript_expr: expr '[' expr ']'
subscript_expr • = NUMBER ;            expr: subscript_expr
expr = NUMBER • ;                      expr: NUMBER
expr = expr ; •                        assignment: expr '=' expr ';'
assignment

第二条语句必须解析如下：

ID [ NUMBER ] • ID = NUMBER ;          type: ID '[' NUMBER ']'
type ID = NUMBER • ;                   expr: NUMBER
type ID = expr ; •                     var_decl: type ID '=' expr ';'
var_decl

这是一个 shift/reduce 冲突，因为必须在第一个 ID 之后立即做出关键决定。在第一条语句中，我们需要将标识符缩减为 expr。在第二个语句中，我们必须继续移位，直到我们准备好减少一个 type.

当然，如果我们可以词法区分类型IDs和变量名，这个问题就不会存在了IDs，但这可能是不可能的（或者，如果可能，它可能是不可取的，因为它需要从解析器到词法分析器的反馈）。

正如所写，shift/reduce 预测可以通过固定前瞻进行，因为 ID 之后的第四个标记将确定可能性。这使语法成为 LALR(4)，但这并没有多大帮助，因为 bison 只实现了 LALR(1) 解析器。在任何情况下，不太简化的语法都可能不会是 fixed-lookahead，例如，如果数组大小允许使用常量表达式，或者数组可以具有多个维度。

即便如此，语法也没有歧义，所以可以用GLR解析器来解析。 Bison 确实实现了 GLR 解析器；只需插入

%glr-parser

进入序幕。（仍然会产生 shift/reduce 警告，但解析器会正确识别这两种语句。）

值得注意的是，C 没有这个特殊的解析问题，因为它将数组大小放在声明的变量名称之后。我不认为这样做是为了避免解析问题（虽然谁知道？），而是因为人们认为按照变量的使用方式编写声明更为自然。因此，我们写 int a[3] 和 char *p，因为在程序中我们将使用 a[i] 和 *p.

取消引用

可以为这种语法写一个 LALR(1) 文法，但有点烦人。关键是要延迟语法 ID [ NUMBER ] 的缩减，直到我们确定它将是哪个产品的开始。这意味着我们需要包括产生式 expr: ID '[' NUMBER ']'。这将导致更多的 shift/reduce 警告（因为它使语法不明确），但由于野牛总是喜欢移位，它应该产生一个正确的解析器。

Bison 下标表达式意外错误

Bison subscript expression unexpected error

syntax

grammar

parsing

bison

shift-reduce-conflict