在没有%prec或%left的Bison中设置优先级和关联性

Question

如果不使用%prec或%left，如何在Bison中设置优先级和关联性？有没有一种方法可以在不需要的地方写语法？

Answer 1

如果不想使用%prec、%left和%right，则必须使用多个非终结符来建立优先级。

例如，考虑以下语法：

%token NUMBER
%left '+'
%left '*'
%right '^'
%%
expression
: NUMBER
| expression '+' expression
| expression '*' expression
| expression '^' expression
| '(' expression ')'
;
%%

让我们看看它是如何与表达式1 + 2 * 3匹配的。如果我们从上面的语法中删除优先级指令，那么语法可以通过两种方式匹配这个表达式。有一种方法：

expression(+)
|
+-- expression(NUMBER 1)
|
+-- expression(*)
|
+-- expression(NUMBER 2)
|
+-- expression(NUMBER 3)

这是另一种方式：

expression(*)
|
+-- expression(+)
|       |
|       +-- expression(NUMBER 1)
|       |
|       +-- expression(NUMBER 2)
|
+-- expression(NUMBER 3)

我们想写一个只能像第一种方式匹配的语法，其中*比+绑定得更紧密。我们必须创建新的非终结符，并将expression非终结符的生成拆分为新的非终止符，如下所示：

%token NUMBER
%%
primaryExpression
: NUMBER
| '(' expression ')'
;
exponentiationExpression
: primaryExpression
// Right-recursion makes this right-associative.
| primaryExpression '^' exponentiationExpression
;
multiplicationExpression
: exponentiationExpression
// Left recursion makes this left-associative.
| multiplicationExpression '*' exponentiationExpression
;
additionExpression
: multiplicationExpression
| additionExpression '+' multiplicationExpression
;
expression
: additionExpression
;

让我们看看这个语法是如何匹配表达式1 + 2 * 3的。它只能这样匹配：

expression
|
+-- additionExpression
|
+-- additionExpression
|       |
|       +-- multiplicationExpression
|               |
|               +-- exponentiationExpression
|                   |
|                   +-- primaryExpression(NUMBER 1)
|
+-- multiplicationExpression
|
+-- multiplicationExpression
|       |
|       +-- exponentiationExpression
|               |
|               +-- primaryExpression(NUMBER 2)
|
+-- exponentiationExpression
|
+-- primaryExpression(NUMBER 3)

尽管现在解析树中有更多级别，但它符合所需的绑定优先级。

如果你想用这种方式编写语法，请记住，LALR解析器在处理右递归时通常比处理左递归时使用更多的内存。因此，通常将exponentiationExpression中使用的右递归重写为左递归，并修复代码中的关联性。

Answer 2

是--您可以为不同级别的优先级使用单独的规则，并通过左递归与右递归控制关联性。例如，要获得优先级低于*和/的+和-，一个左关联，另一个右¹，可以执行以下操作：

number: literal | variable;
mul_expr: number
| mul_expr MUL_OP number
;
add_expr: mul_expr
| mul_expr ADD_OP add_expr
;

是的，这真的是类似yacc的伪代码；我相信yacc、byacc、Bison等都会拒绝它。

---

¹是的，这些通常都是左联想的，但我这样做只是为了演示如果你想的话，如何使某些东西具有右联想。