4

为了我的个人娱乐，我一直在研究一种类似 C 的语法。但是，我一直在遇到 shift/reduce 冲突，我很确定它们可以得到解决。

现在我expressions看起来像这样，以简化的形式，剥离了动作：

%left '+' '-'

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

但是，这会导致移位/减少冲突：解析器不确定如何处理括号。据我-v所知，尚不清楚 like 表达式是否expr '+' expr '('应该减少或expr '+' expr移动expr括号。

显然，我希望括号移动。foo % bar(4)不应该最终成为(foo % bar)(4). 但是，我没有成功使用该%prec指令来表示这个意思。在规则之后添加%left FUNCALLand%prec FUNCALL不会产生任何变化。

我知道 Bison 的 LALR 解析器在遇到 shift/reduce 时的默认路径是 shift，我可以用它%expect来解决问题。但是，每个表达式都会产生一个冲突，我是否需要更改该列表，我还需要更改%expect声明，这对我来说似乎是一个相当丑陋的解决方案。此外，我相信你们中的一个聪明的孩子有解决这个问题的办法。

我的目标是有一个类似于上面的规则，Bison 会知道，每当它遇到'('from 函数调用规则时，它都会移动括号，而不会发生移位/减少冲突。作为记录，我对%prec指令的使用如下，所以如果我做错了，你可以纠正我。它确实存在移位/减少冲突。

%left '+' '-'
%left FUNCALL

%%

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

%%
4

1 回答 1

4

您需要添加%left '('优先规则（或者%nonassoc '('可能更好）。

在 yacc/bison 中，优先级解决移位/减少冲突的方式是将要减少的规则的优先级与要移位的令牌的优先级进行比较。在您的示例中，冲突是减少expr: expr '+' expr和移动 a之间的冲突'('，因此要解决它，您需要优先级'('（并且您希望它高于来自 的规则'+'）

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

于 2010-01-15T00:44:52.513 回答