0

我正在设计自己的玩具语言，该语言可以编译成 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 等人中运算符优先级的工作方式？

提前致谢！

编辑

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

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

4

1 回答 1

2

优先声明

array_element:
    expression array_subscript %prec indexing

并且伪标记的优先顺序对indexing索引表达式的消歧绝对没有影响

10 + arr[0]

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

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

10 + arr并且在解析器看到并需要决定它是否是的那一刻就解决了(10 + arr)。换句话说，它的选项是：

  • 减少使用生产expression: expression '+' expression，或
  • 移动前瞻标记，在本例中为[. 如果它选择移位，则expression: expression '+' expression稍后将被归约，第二个操作数更长，因为所有归约都是在被归约的生产结束时精确执行的，在下一个令牌被移位之前。

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

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

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

如果 BisonC++ 是您环境的一部分，这一点尤其重要，因为与几乎所有其他 Yacc 衍生产品不同，BisonC++ 使用右侧的第一个非终结符。总体而言，%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 进行了测试。）

于 2022-02-07T01:49:00.533 回答