索引操作符在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等人的优先操作方式？

提前感谢！

编辑

我已经将dev分支推到github，github包含一个包含一个Makefile和测试文件的最小工作示例的文件夹。要用不同的语法规范(file：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

并且伪标记indexing的优先级对索引表达式的消歧没有任何影响。

10 + arr[0]

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

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

当解析器看到10 + arr并需要决定它是否是(10 + arr)时，它就被解决了。换言之，它的备选方案是：

• Reduce使用生产expression: expression '+' expression，or
• Shift为前瞻性令牌，在本例中为[。如果它选择移位，那么expression: expression '+' expression将在稍后减少，并有更长的第二个操作数，因为在下一个令牌移动之前，所有的缩减都精确地在生产结束时执行。

因此，正在考虑的优先级排序在生产expression '+' expression和查找令牌[之间。优先级比较总是这种形式:可能的缩减的优先级与可能被移动的查找令牌的优先级进行比较。

优先级总是被描述为两个令牌之间的比较，这可能是因为这是运算符优先分析中使用的实际算法，这是一种不同的解析算法。在shift -约简语法分析中，优先比较总是在shift和减缩之间进行。为了保持在两个令牌之间的错觉，Bison和几乎所有的Yacc衍生产品一样，使用的惯例是，简化的优先级是基于右边最后一个可见终端的优先级排序。(BisonC++是个例外。)

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

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

无论如何，重要的是要记住，%prec所做的所有工作都是用终端符号标识产品的优先级。它对任何前瞻性令牌或任何其他产品的优先级没有影响。如果两个规则具有相同的优先级，您可以(而且可能应该)使用相同的%prec声明。

简而言之，expression array_subscript的优先级与10 + arr[0]的解析无关，因为在解析过程中，减少生产并不是一种选择。(实际上，它将永远不相关，因为array_subscript实际上是一个后缀操作符，因此并不含糊。只有在语法中存在歧义时，才会出现优先解决。)

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

根据BisonC++生成的“详细”输出，使用优先级解决冲突。我没有找到Bisonc++使用的优先级解析算法的任何文档，也没有注意到它将与Bison/Yacc使用的算法不同(以及它的价值，它是Posix所要求的)。但这并不意味着文档不存在，我不愿意在不验证原始意图的情况下将其称为bug。所以我只想说这很不寻常。

在任何情况下，您都可以通过为bisonc++添加一个优先级级别(如上所述，这是您感兴趣的前瞻性令牌)，强制[以您希望的方式解决冲突。将其放在+的优先级之后(以及所有其他infix和前缀操作符，我认为它们都存在于完整的语法中)：

%left '+'
%left '['

(在与源依赖进行了相当大的斗争之后，使用了BisonC++ 6.04.04进行了测试。)