bisonc++中的索引运算符优先级（bison，bison++）

Question

我正在设计我自己的编译成 Brainf*ck 代码的玩具语言，遇到了索引运算符的运算符优先级问题。解析器由 Bisonc++ 生成，它的语法文件与其表兄弟 bison 和 bison++ 使用的语法基本相同。

由于 BF 中寻址内存的怪癖，我必须以不同方式处理数组元素上的操作，这就是我为它们生成特定规则的原因（我故意省略了规则的主体）。相关语法（无效）如下：

%right '=' 
// a bunch of other operators
%left '+' '-'
// more operators
%left indexing

expression:
    variable
|
    array_element
|
    expression '+' expression
|
    // a bunch more rules
;

array_subscript:
    '[' expression ']' 
;

array_element:
    expression array_subscript %prec indexing
;

现在，我的印象是通过将 indexing 优先级分配给 array_element 规则，解析器将直接匹配它左侧的最小表达式。但是，请考虑以下代码：

10 + arr[0]
// is parsed as
(10 + arr)[0]

我不明白为什么会这样。当代码更改为 10 + (arr[0]) 时，解析器会执行预期的操作，我认为这证明这与运算符优先级有关。我尝试过的许多事情之一是使用未使用的符号作为索引运算符。例如：

// bottom-most operator in the precedence definition (replacing 'indexing'):
%left '@'

array_element:
    expression '@' array_subscript
;

// Code:
10 + arr@[0] // is now parsed properly

出于某种原因，这解决了问题。我做错了什么吗？我是否误解了运算符优先级在 bison 等人中的工作方式？

提前致谢！

编辑

我已将我的开发分支推送到 github，其中包含一个文件夹，其中包含一个包含 Makefile 和测试文件的最小工作示例。要使用不同的语法规范（文件：grammar）重建解析器，您可以运行 make regenerate，但这需要 bisonc++ 和 flexc++（可从 Debian 获得回购）。要仅使用当前（有故障的）解析器构建项目，运行 make.

https://github.com/jorenheit/brainfix/tree/better_indexing/arraybug

Answer 1

优先声明

array_element:
    expression array_subscript %prec indexing

和pseudo-token indexing的优先顺序对索引表达式

的消歧完全没有影响

10 + arr[0]

如您所说，在这种情况下优先解决的歧义介于

(10 + arr)[0]       and        10 + (arr[0])

并且在解析器已经看到10 + arr并需要决定它是否是(10 + arr)的那一刻被解析。也就是说，它的选项是：

减少使用生产expression: expression '+' expression，或
Shift 前瞻标记，在此示例中为 [。如果它选择移位，那么 expression: expression '+' expression 将在稍后减少，第二个操作数更长，因为所有减少都恰好在生产减少的最后执行，在下一个标记移位之前。

因此正在考虑的优先顺序是在 production expression '+' expression 和先行标记 [ 之间。优先级比较始终采用这种形式：将可能减少的优先级与可能移动的前瞻标记的优先级进行比较。

优先级总是被描述为两个标记之间的比较，这有点令人困惑，可能是因为这是运算符优先级解析中使用的实际算法，这是一种不同的解析算法。在 shift-reduce 解析中，优先级比较总是在移位和归约之间。为了保持它在两个记号之间的错觉，Bison 和几乎所有的 Yacc 衍生物一样，使用归约的优先级基于 last 可见终端的优先顺序的约定right-hand 一侧。（BisonC++ 是个例外。）

通常在需要优先解析的作品中通常只有一个可见终端，所以Yacc/Bison选择最后一个这一事实并不明显，但偶尔会有例外，例如so-called C中的“三元运算符”。产生式expression: expression '?' expression ':' expression的优先级基于:令牌；相关的前瞻标记将是 ?，因此 a?s1:b?s2:s3 的解析基于 ? 与 : 的比较；这两个标记都需要处于相同的优先级。为了避免这种混淆，并允许优先级用于没有可见标记的产生式，例如 expression: expression array_subscript，Yacc 衍生品通常允许您通过为产生式指定替代标记来覆盖默认值，使用 %prec声明。

如果 BisonC++ 是您环境的一部分，这一点尤为重要，因为与几乎所有其他 Yacc 衍生产品不同，BisonC++ 在 right-hand 边。总的来说，在具有多个终止符号的规则中始终使用 %prec 声明可能是个好主意。

无论如何，重要的是要记住 %prec 所做的只是用终结符标识产生式的优先级。它对任何先行标记或任何其他产品的优先级没有影响。如果两个规则具有相同的优先级，您可以（并且可能应该）使用相同的 %prec 声明。

简而言之，expression array_subscript 的优先级与 10 + arr[0] 的解析无关，因为此时在解析中减少生产不是一个选项。（事实上，它永远不会相关，因为 array_subscript 实际上是一个后缀运算符，因此不会产生歧义。优先级解析仅在语法中存在歧义时发生。）

我不知道为什么BisonC++选择减少加法。最初，我认为这是因为您将 [ 置于之前 + 的某个优先级，但显然并非如此。对于 Bison 或 Yacc，如果 [ 不在任何优先级别，那么它就没有声明的优先级，并且不会使用优先级比较来解决歧义。如果是这种情况，(1) 将引发 shift-reduce 冲突警告，并且 (2) 解析器将选择 shift 操作。这就是使用 Bison 测试时此语法所发生的情况。但 BisonC++ 显然使用默认优先级，在某些情况下..

根据 BisonC++ 生成的“详细”输出，使用优先级解决了冲突。我没有找到有关 Bisonc++ 使用的优先级解析算法的任何文档，也没有发现它与 Bison/Yacc 使用的算法不同的任何注释（并且，就其价值而言，Posix 要求） .但这并不意味着文档不存在，而且我不愿意在不验证原始意图的情况下将其称为错误。所以我只会说这很不寻常。

在任何情况下，您都可以通过为 [ 添加优先级来强制 bisonc++ 按您希望的方式解决冲突（如上所述，这是您感兴趣的前瞻标记） .把它放在之后 + 的优先级（和所有其他中缀和前缀运算符，我认为它们存在于完整语法中）：

%left '+'
%left '['

（经过测试，在与源依赖性进行了相当大的斗争之后，使用 BisonC++ 6.04.04。）

bisonc++中的索引运算符优先级（bison，bison++）

Index operator precedence in bisonc++ (bison, bison++)

c++

linux

parsing

bison

bisonc++