如何正确地将优先规则应用于 Bison 的表达式？

Question

这里是野牛新手。

我正在尝试为我的玩具计算器添加一项功能，即可以省略任何变量前的乘法运算符 *，以便它可以解析如下内容：3x * 2y .

我已经将程序缩减为一个非常简单的解析器，它只支持乘法（显式和省略），其中数字由字符 n 表示，变量由字符 [= 表示16=].

这是一个输入示例，类似于上面的示例，应该被接受：

nv * nv

更复杂的示例也应该有效（请忽略空格）：

nvv * n * nvvv

这里是代码文件calc.y:

%start  expression
%left '*'

%%
expression: 
    'n'
|   'v'
|   expression 'v' %prec '*'
|   expression '*' expression
;
%%

"Compiled" 与：

bison calc.y

我收到以下警告：

calc.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]

根据我对此的有限理解，%prec '*' 东西似乎什么也没做。我如何告诉 Bison 按照它们出现的顺序匹配任一规则？谢谢！

Answer 1

你几乎可以肯定最好不要使用优先级来消除这种结构的歧义。它可以工作，但它比替代方案更笨拙且更难理解（至少，在我看来是这样。）这里有几个 SO 答案，探索用明确的表达式优先顺序编写语法，包括 "invisible"运算符：How can I have an “implicit multiplication” rule with Bison? and .

yacc/bison 优先算法在 bison manual and more briefly in a number of SO answers, several of which quote the following paragraph (originally from 中描述。）

Recall that a precedence relation is defined between a production and a terminal. It does not relate two terminals nor two productions (and so cannot be used to resolve reduce-reduce conflicts). The comparison between precedence of the production which could be reduced and the lookahead terminal determines whether a reduce or a shift will occur. For notational convenience, productions are represented by the name of a terminal, usually the only terminal in the production; this corresponds to a common use case but it is sometimes confusing. In particular, the %prec declaration only serves to give a rule a name for use in precedence declarations, and it is probably better to think about it in that way rather than as an "explicit" declaration.

所以你的优先声明没有做任何事情来解决

中的歧义

expression 'v' %prec '*'

因为相关的先行标记是 'v'，并且在优先级 table.

中没有任何已声明的顺序

此外，您可能真的不希望相邻乘法具有与显式乘法相同的优先级，因为 2*3v 似乎不是 (2*3)v（这是 2*3*v 被解析的as)，而是 2*(3v)。不是每个人都会同意这一点——这也是相邻乘法有问题的部分原因——有些人会说 2/3v 意味着 (2/3)*v。我们可以同意在这一点上有所不同，但需要注意这一点。

无论如何，如果你真的想用优先关系来做到这一点，你需要在你的优先顺序中包含所有可能位于 expression 开头的标记。（它们应该都在列表末尾的单一优先级中。）

在 this answer 的末尾有一个关于作为运算符的邻接的 SO 答案列表；其中一些包括优先顺序作为解决方案的示例。在您的情况下，您有两种选择，具体取决于您认为显式和隐式乘法应该如何交互：

%left '*'
%left 'v' /* And any other token which could start an expression */

或

%left '*' 'v' /* Again, add other tokens which could start an expression */

由于在这两种情况下，'v'都处于优先顺序，因此无需修改expression 'v'产生式的默认优先级；默认优先级（v，因为这是产品中的最后一个终端）将正常工作：

expression: 'n' | expression 'v' | expression '*' expression

但是，如果有一天您决定 2(3+v) 是一个有效的隐式乘法，那么您需要将其更改为：

expression: 'n' | '(' expression ')' | expression '*' expression
          | expression expression %prec 'v'

现在需要 %prec 声明，因为 expression expression 没有默认优先级。

您可以将它添加到优先顺序中，在这种情况下您可以从产生式中删除 %prec 声明：

Answer 2

如果我正确理解@rici 的回答，使用优先级来解决这个问题不是一个好主意，因为我们必须为 'expression' 之后的标记设置优先级，在这种情况下只是 'v'，但可能有很多（我们必须为所有这些设置）。

另一种方法是限制可以出现在 'v' 之前的东西，这样一开始就没有歧义，就像这样（注意 'v' 之前的东西不能包含显式乘法）：

%start  expression
%left '*'

%%
term:
    'n'
|   'v'
|   term 'v'
;

expression: 
    term
|   expression '*' expression
;
%%

如何正确地将优先规则应用于 Bison 的表达式？

How to correctly apply precedence rules to an expression with Bison?

bison