在野牛，我怎么能保留一个非终端的结合？

我有以下的野牛语法片段：在野牛，我怎么能保留一个非终端的结合？

binary_op:   BINARY_OP 
        { 
         ... 
        } 
        | '|' %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左结合的？关于binary_op的第二条规则的%prec声明似乎没有效果。

编辑：这是一个GLR分析器

来源

2014-05-16 nielsbot

答案很简单：你不能。优先级（和关联性）仅适用于制作（左侧）和终端（右侧）。它们不适用于非终端。

这不是一个任意的决定;这是野牛处理转换/减少冲突的方式所固有的。在每一个解析步骤中，先行令牌（终端）必须最终被移位，但是有可能在终端被移位之前有可能减少产量。如果不立即执行减少，它将不会执行。 LR（1）语法允许解析器基于当前解析堆栈和先行令牌来决定是应该执行缩减还是应当立即移位先行令牌。如果两种行为都是可能的，那么这个语法就被说成有一个转换/减少的冲突，并且严格来说不是LR（1）。

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

在生产

binary_op: '|' %prec BINARY_OP

的%prec声明是没用的，因为binary_op必须立即减少的情况;它不能参与转移/减少冲突。转换/减少冲突来自non_keyword_expression生产，该生产标记有（不同的）%prec声明，并且该声明将用于该生产。

non_keyword_expression的生产没有终端，所以它也没有隐式优先。这通常不是你想要的，以及使用作品的喜欢：

binary_op: '|' | "OR" ;

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

注1：如果您要求使用GLR解析器，这并不完全正确。 GLR解析器可以执行shift和reduce操作，因为它（有效地）同时维护许多解析器状态。最终，除了这些国家之外的所有国家都必须被淘汰。否则，解析是不明确的。 GLR语法分析程序的使用优先级（和%prec声明）与非GLR语法分析程序的使用方式完全相同;优先级消除的解析器动作实际上被消除并且不会导致并行状态。但是，GLR解析器也可以处理减少/减少冲突，其中有两种可能的减少（可能对同一个非终端）。这些冲突可以使用%dprec（“动态优先权”）声明来解决。

来源

2014-05-16 20:23:09 rici

感谢您的答案。你在说'|'吗？在我的语法中不是终端？混淆为什么它可以正常工作“OR”（令牌BINARY_OP）而不是'|' （隐含的令牌'|'）BINARY_OP的关联性似乎成功连接到非终端binary_op ... – nielsbot

@nielsbot：对不起，我不是很清楚。我会编辑我的答案。但有一个问题：你使用GLR解析器吗？（如果是这样，你应该在你的问题中提及它，因为它既不明显也不共同。） – rici

是的，它是GLR。我的意思是补充，但忘了... – nielsbot

如果您可以指定终端'OR'和'|'等的关联性并将它们的优先级设置为相同，那么存在这种问题的解决方法。与一对夫妇改变缀计算器例子可以解析这样的输入：

2 PLUS -3 TIMES 4^2 + 3

-43

的主要变化是这样的：

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

... 

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

非终端的优先权将是对野牛恕我直言的一个有用的扩展。当非终端的前缀可以被移位时，它将允许用户通过有利于减少来解决s/r冲突（并且当它可以被移动到具有优先级的非终端时可以有只有-可能有其他有效的理由转移）。事实上，我发现这个问题，试图实现一个Haskell风格的功能应用的语法即

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

后却因为单独一个终端也是有效这里，减少了X/Y/Z到非终端是有效的。因此野牛会达到non-term_x non-term_y | z（|是堆栈/超前边界）并且不知道是否减少到non-term_x_y或移位z。（类似的技巧幸运地在这里工作）

我在野牛源中挖了一点，但我看不到一个简单的方法来允许在非终端％prec。当s/r conficts被解决时，只有裁减规则是已知的，并且冲突的令牌要移位，其优先级被比较。你需要知道所有有效的移位原因，并且有办法访问冲突的移位规则，所以也许..您需要将可切换令牌分成与最终减少的规则相对应的组，然后比较规则的优先级。 Somethin我会看看有一天...

来源

2014-08-23 11:21:08 user3125280

在野牛，我怎么能保留一个非终端的结合？

回答

相关问题