compiler-construction - 在没有 %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)

我们想写一个只能像第一种方式那样匹配的语法，其中*比+绑定(bind)得更紧密。我们必须创建新的非终结符并将 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)

虽然现在解析树中有更多级别，但它匹配所需的绑定(bind)优先级。

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