在Bison下移位/减少与类C语法的冲突

问题描述

为了个人娱乐，我一直在研究类似C的语法.但是，我已经遇到了转移/减少冲突，并且我很确定它们可以解决.

I've been working on a C-like grammar for my personal amusement. However, I've been running into shift/reduce conflicts, and I'm quite sure they could be resolved.

现在，我的expressions看起来像这样，以简化的形式包含了一些动作:

Right now my expressions look like this, in a simplified form, stripped of actions:

%left '+' '-'

%%
expr
 : NUMBER
 | IDENTIFIER
 | expr '+' expr
 | expr '-' expr
 /* other operators like '*', '/', etc. */
 | expr '(' expr ')' /* function call */
%%

但是，这导致移位/减少冲突:解析器不确定如何处理括号.从-v告诉我的情况来看，目前尚不清楚像expr '+' expr '('这样的表达式是否应将expr '+' expr简化为expr或移动括号.

However, this results in shift/reduce conflicts: the parser is unsure about how to treat parentheses. From what -v tells me, it is unclear whether an expression like expr '+' expr '(' should reduce expr '+' expr into expr or shift the parenthesis.

很显然，我希望括号被改变. foo % bar(4)不应以(foo % bar)(4)结尾.但是，使用%prec指令表示这种方法并没有成功.在规则后添加%left FUNCALL和%prec FUNCALL不会产生任何变化.

Obviously, I want the parenthesis to be shifted. foo % bar(4) shouldn't end up being (foo % bar)(4). However, I've had no success using the %prec directive to that mean. Adding %left FUNCALL and %prec FUNCALL after the rule yields no change.

我知道Bison的LALR解析器在遇到移位/减少时的默认路径是移位，而我可以使用%expect来解决该问题.但是，每个表达式都会产生一个冲突，我需要更改该列表，还需要更改%expect声明，这对我来说似乎是一个非常丑陋的解决方案.此外，我敢肯定你们中有一个聪明的孩子可以解决这个问题.

I know that the default path Bison's LALR parsers will go when encountering a shift/reduce will be to shift, and that I could just use %expect to work around the problem. However, one conflict is generated for each expression, and would I ever need to change that list, I'll also need to change the %expect declaration, which looks like a rather ugly solution to me. Besides, I'm sure one of you wise kids have a solution to that problem.

我的目标是要有一条与上述规则类似的规则，为此Bison将知道，只要遇到函数调用规则中的'('，它就会移动括号，而不会发生移位/减少冲突.作为记录，我对%prec指令的使用如下，因此，如果我做错了，则可以纠正我.它确实具有移位/减少冲突.

My goal is to have a rule similar to the one above, for which Bison will know that whenever it encounters the '(' from the function call rule, it has shift the parenthesis, without a possible shift/reduce conflict. For the record, my use of the %prec directive is the following, so if I'm just doing it wrong you can correct me. It does have the shift/reduce conflict.

%left '+' '-'
%left FUNCALL

%%

expr
    : NUMBER
    | IDENTIFIER
    | expr '+' expr
    | expr '-' expr
    /* other operators like '*', '/', etc. */
    | expr '(' expr ')' %prec FUNCALL /* function call */

%%

推荐答案

您需要将%left '('添加到优先级规则中(或者%nonassoc '('可能更好).

You need to add %left '(' to your precedence rules (or %nonassoc '(' might be better).

优先级用于解决yacc/野牛中的移位/减少冲突的方式是将要减少的规则的优先级与 token 的优先级进行比较被转移.在您的示例中，冲突在于减小expr: expr '+' expr和移动'('之间，因此要解决此问题，您需要在'('上设置优先级(并且您希望它高于来自'+'的规则) )

The way that precedence works to resolve shift/reduce conflicts in yacc/bison is that it compares the precedence of the rule to be reduced with the precedence of the token to be shifted. In your example, the conflict is between reducing expr: expr '+' expr and shifting a '(', so to resolve it, you need a precedence on '(' (and you want it to be higher than the rule, which comes from '+')

%prec指令仅设置规则的优先级，覆盖其默认优先级，该默认优先级来自其rhs上的第一个标记.它不会以任何方式影响规则中出现的令牌的优先级.

The %prec directive just sets the precedence of a rule, overriding its default precedence which comes from the first token on its rhs. It doesn't affect the precedence of tokens that appear in the rule in any way.

这篇关于在Bison下移位/减少与类C语法的冲突的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！