野牛下标表达式意外错误

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 个移位/减少冲突。删除subscript_expr会使它消失。

为什么会发生这种情况，如何让它将array[5] = 0;解析为具有subscript_expr的assignment？

我正在使用野牛 2.3。

Answer 1

以下两个语句在您的语言中都有效：

x [ 3 ] = 42;
x [ 3 ] y = 42;

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

，其元素的类型为x

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

不幸的是，在看到]后面的令牌之前，它无法执行此操作。如果该令牌是ID，则该语句必须是var_decl;否则，它是一个assignment(当然，假设该语句有效)。

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

expr '=' 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

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

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

如前所述，可以通过固定的展望进行移位/减少预测，因为ID后面的第四个标记将确定可能性。这使得语法成为 LALR(4)，但这并没有多大帮助，因为 bison 只实现了 LALR(1) 解析器。在任何情况下，不太简化的语法很可能不会是固定的，例如，如果数组大小允许常量表达式，或者数组可以有多个维度。

即便如此，语法也不是模棱两可的，因此可以使用 GLR 解析器来解析它。Bison确实实现了GLR解析器;只需要插入

%glr-parser

进入序幕。(仍会生成移位/减少警告，但解析器将正确识别这两种语句。

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

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

Answer 2

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