2

我有以下 Bison 语法片段：

二进制操作：二进制操作
                    {
                        ...
                    }
                    | '|' %prec BINARY_OP
                    {
                        ...
                    }
;

non_keyword_expr: non_keyword_expr binary_op non_keyword_expr %prec BINARY_SEND_PREC %dprec 2
                    {
                        ...
                    }
;

|在我的语法中有重载的含义，所以我不能只从词法分析器中将它作为标记 BINARY_OP 返回。根据上下文，它可能是不同的标记。

如果我使用它作为我的输入：

4 OR 5 OR 6

我可以成功解析它（或被词法分析器识别为 BINARY_OP 令牌）。

但是，如果我的输入是这样的：

4 | 5 | 6

我得到一个模棱两可的语法错误。（|不被识别为左联想）

如何让binary_op在non_keyword_expr中保持左关联？%prec关于binary_op的第二条规则的声明似乎没有效果。

编辑：这是一个 GLR 解析器

4

2 回答 2

1

简单的回答：你不能。优先级（和关联性）仅适用于产生式（左侧）和终端（右侧）。它们不适用于非终端。

这不是一个武断的决定。这是野牛处理移位/减少冲突的方式所固有的。在每个解析步骤中，前瞻标记（终端）最终都必须被移动，但有可能在终端移动之前存在可以减少的产生式。如果不立即执行缩减，则永远不会执行。LR(1) 语法允许解析器根据当前的解析堆栈和前瞻标记来决定是否应该执行缩减或是否应该立即移动前瞻标记。如果这两个动作都是可能的，则称该文法存在移位/归约冲突，严格来说它不是 LR(1)。

优先级和关联性规则用于解决移位/减少冲突。产生式可能具有隐含或显式优先级：显式优先级由%prec宣言; 否则使用生产中最后一个终端的优先级。在发生移位/减少冲突的情况下，将可以减少的生产的优先级与可以移位的先行终端的优先级进行比较，并且具有较大优先级的优先级获胜。而已。优先级不会保留或继承。事实上，说比较优先级是不准确的，因为在解析期间不会发生这种情况。解析器有一个动作或转换表，它定义了在特定堆栈配置（“状态”）和前瞻令牌的情况下要做什么，并且优先级信息在解析器生成时用于填写动作表中的条目否则会模棱两可。

在您的生产中

binary_op: '|' %prec BINARY_OP

%prec声明是无用的，因为binary_op必须立即减少；它不能参与移位/减少冲突。shift/reduce 冲突伴随着non_keyword_expression生产而来，它标有（不同的）%prec声明，这就是将用于该生产的声明。

for 的产生non_keyword_expression式没有终结符，因此也没有隐含的优先级。这通常不是您想要的，并且使用以下产品：

binary_op: '|' | "OR" ;

与使用优先级解决解析冲突并不真正兼容。

注 1：如果您要求 GLR 解析器，这并不完全正确。GLR 解析器可以同时执行移位和归约，因为它（有效地）同时维护多个解析器状态。最终，除了其中一种状态之外，所有状态都必须被消除；否则，解析是不明确的。GLR 解析器使用优先级（和%prec声明）的方式与非 GLR 解析器完全相同；被优先级消除的解析器动作确实被消除了，并且不会导致并行状态。但是，GLR 解析器也可以处理归约/归约冲突，其中有两种可能的归约（可能是同一个非终结符）。这些冲突可以使用%dprec（“动态优先级”）声明来解决。

于 2014-05-16T20:23:09.717 回答
1

在解决 s/r 冲突时，Bison 的规则优先级通过将规则的优先级与要转移的所有冲突标记的优先级进行比较来工作。所以它将 BINARY_SEND_PREC 与 '|' 的优先级进行比较 和“或”。对于“或”，它选择减少。获得“|”的减少 以及令牌'|' 本身就需要%left '|'。让他们一起工作'|' 和“或”需要相同的优先级。

如果您可以指定终端“OR”和“|”等的关联性并将它们的优先级设置为相同，则可以解决此类问题。通过一些更改，中缀计算器示例可以解析如下输入：

2 加 -3 乘以 4 ^ 2 + 3

-43

主要变化如下所示：

%token PLUS
%token TAKE
%left '-' '+' PLUS TAKE

... 

add:      '+' | PLUS;
exp:      NUM                           { $$ = $1;         }
        | exp add exp        %prec '+'  { $$ = $1 + $3;    }

非终端的优先级将是野牛恕我直言的有用扩展。当非终结符的前缀可以移动时（并且只有当它可以优先为非终结符移动时 - 可能有其他正当理由转移）。事实上，我在尝试实现haskell风格的函数应用程序语法后发现了这个问题，即

 x y z -> ((x y) z)

但是因为单个终端在这里也是有效的，所以将 x/y/z 减少到非终端是有效的。Therfore bison 将到达non-term_x non-term_y | z（|是堆栈/前瞻边界）并且不知道是减少non-term_x_y还是移动 z。（幸运的是，类似的技巧在这里有效）

我在野牛源中挖了一下，但我看不到一种简单的方法来允许非终端上的 %prec 。当 s/r 冲突被解决时，只有归约规则是已知的，并且冲突的令牌要移位，比较它们的优先级。您需要在这里了解所有有效的转换原因，并且有一些方法可以访问冲突的转换规则，所以也许..您需要将可转换标记分成与它们最终减少的规则相对应的组，然后比较规则' 的优先级。某天我会看的东西...

于 2014-08-23T11:21:08.337 回答