如何消除由有限前瞻引起的 shift/reduce 错误？

Question

在我的语法中，通常可以只使用 declaration，它看起来像：

int x, y, z = 23;
int i = 1;
int j;

在 for 中，我想使用一组不同类型的逗号分隔声明，例如

for (int i = 0, double d = 2.0; i < 0; i++) { ... }

使用 yacc，有限的前瞻会产生问题。这是朴素的语法：

variables_decl
    : type_expression IDENT
    | variables_decl ',' IDENT
    ;

declaration
    : variables_decl
    | variables_decl '=' initializer
    ;

declaration_list
    : declaration
    | declaration_list ',' declaration
    ;

这会导致“,”出现 shift/reduce 错误:

state 149

  100 variables_decl: variables_decl . ',' IDENT
  101 declaration: variables_decl .
  102            | variables_decl . '=' initializer

    ','  shift, and go to state 261
    '='  shift, and go to state 262

    ','       [reduce using rule 101 (declaration)]
    $default  reduce using rule 101 (declaration)

我想解决这个问题，让它真正起作用：

for (double x, y, int i, j = 0, long l = 1; i < 0; i++) { ... }

但我不太清楚该怎么做。

Answer 1

一般来说，您可以通过避免强制解析器在绝对必要之前做出决定来避免这种类型的 shift/reduce 冲突。

可以理解你为什么要这样构造语法；直觉上，声明列表是一个声明列表，其中每个声明都是一个类型和该类型的变量列表。问题是这个定义使得无法知道逗号是属于内部列表还是外部列表。

此外，一个额外的先行标记可能还不够，因为下面的 IDENT 可能是类型名或要声明的变量的名称，假设 type-expression 是通常的 C 语法，可以以对应于类型名称的标识符。

但这不是查看声明列表语法的唯一方法。相反，您可以将其视为单个声明的列表，每个声明都以可选类型开始（列表中的第一个除外，它必须具有显式类型），使用省略的类型与前一个变量的类型。这导致以下无冲突语法：

declaration_list: explicit_decl
                | declaration_list ',' declaration
declaration     : explicit_decl
                | implicit_decl
explicit_decl   : type_expression implicit_decl
implicit_decl   : IDENT opt_init
opt_init        : %empty | '=' expr

这没有捕捉到 C 声明的语法，因为并非所有 C 声明都具有 type_expression IDENT 的形式。被定义的 IDENT 可以埋在声明中，例如 int a[4] 或 int f(int i)；幸运的是，这些形式在 for 循环中的使用有限。

另一方面，与您的语法不同，它确实允许初始化所有声明的变量，因此

int a = 1, b = 0, double x = -1.0, y = 0.0

应该可以。

另一个注意事项：C for 子句中的第一项可以为空、声明（可能以列表的形式）或表达式。在最后一种情况下，顶级 , 是一个运算符，而不是列表指示器。

简而言之，以上片段可能是也可能不是您实际语法上下文中的解决方案。但它在一个简单的测试框架中是无冲突的，其中类型化声明始终采用 typename identifier.

形式

如何消除由有限前瞻引起的 shift/reduce 错误？

How does one remove shift/reduce errors caused by limited lookahead?

yacc