bison的运算符优先级一例

看到phyeas同学在试写JavaScript语法，顺便参一腿 =v=
本文里的代码放在附件里了，有需要的拿。

关于语法中左递归/右递归与规则的左结合/右结合的关系，我觉得就照着简单的表达式语法把推导过程画出来，找找感觉就能行。要注意的是推导结束后，把每步推导过程画成树（也就是解析树或者叫语法树），离根越远的节点在就越先被求值，也就是“优先级高”的表现了。写这帖的时候懒得画例子了……有必要再补充。

自顶向下的解析方法，如递归下降式或者LL式，一般无法支持左递归的语法，无聊是直接左递归还是间接左递归。这是因为它总是从推导规则中的第一个符号开始推，如果第一个符号就是自己或者间接回回到自己，那么解析过程就无法前进，就无限递归而出错了。（近年来有人提出过一些改进方案使自顶向下解析可以支持左递归，这帖里就不讨论了。有兴趣的同学可以阅读这篇论文：Packrat parsers can support left recursion）。

传统上，为了解决无法左递归的问题，可以改写语法规则，通过引入一个ε转换来把左递归变为右递归。但是这样得到的语法树的结合性就不对了，要得到正确的语法树需要做额外的工作来把树的形状转换回来。

LR系的解析方式则既支持左递归也支持右递归，写起语法来就轻松很多。结合性直接靠语法的递归位置就可以表达。

结合性有两个经典的应用场景，一是表达式的解析，二是if-else问题的解决。这帖主要着眼于前者。
表达式的形式比较固定，但传统上运算符有不同优先级，写语法的时候为了照顾优先级可以选择把相似的结构重复写在多个规则里，让这些规则的层次表达优先级的差别。但规则多了，状态图也就变复杂了。
通过显式指定运算符的优先级，语法中结构相似的规则可以写在同一条规则里，既简化了语法，对应的解析器的效率也更高。

GNU Bison是主要采用LALR(1)的解析器生成器。它支持显式指定规则的优先级以及结合性。
那么优先级能否跨规则而存在呢？先看个例子：
calc1.y

%{
#include <stdio.h>
#include <ctype.h>
#include <math.h>
%}

%union {
    double dval;
}

%token <dval> NUMBER
%token POW

%left '+' '-'
%left '*' '/'
%nonassoc UMINUS
%right POW

%type <dval> expr

%%

line
    : expr '\n'             { printf("%lf\n", $1); }
    ;

expr
    : NUMBER                { $$ = $1; }
    | expr '+' expr         { $$ = $1 + $3; }
    | expr '-' expr         { $$ = $1 - $3; }
    | expr '*' expr         { $$ = $1 * $3; }
    | expr '/' expr         {
        if (0 == $3) yyerror("divided by zero");
        else $$ = $1 / $3;
    }
    | '-' expr %prec UMINUS { $$ = -$2; }
    | expr POW expr         { $$ = pow($1, $3); }
    | '(' expr ')'          { $$ = $2; }
    ;

%%

int main() {
    return yyparse();
}

int yyerror(char* s) {
    fprintf(stderr, "%s\n", s);
    return 1;
}

int end = 0;

int yylex() {
    if (end) return 0;
    int c;
    
    /* skip space */
    while (' ' == (c = getchar())) { }
    
    if (isdigit(c)) {
        ungetc(c, stdin);
        scanf("%lf", &yylval);
        return NUMBER;
    }
    
    if ('*' == c) {
        c = getchar();
        if ('*' == c) {
            return POW;
        } else {
            ungetc(c, stdin);
            return '*';
        }
    }
    
    if ('\n' == c) {
        end = 1;
    }
    
    return c;
}

这是个简单的计算器，支持加、减、乘、除、负、幂等运算，并且可以通过括号改变表达式的结合性。注意到，所有表示“表达式”的规则都在同一个大规则expr里，它们的结合性和优先级则在语法文件的头部声明。

如果把expr改为下面的样子呢？
calc2.y

expr
    : NUMBER          { $$ = $1; }
    | expr binop expr {
        switch ($2) {
        case '+': $$ = $1 + $3; break;
        case '-': $$ = $1 - $3; break;
        case '*': $$ = $1 * $3; break;
        case '/': $$ = $1 / $3; break;
        case POW: $$ = pow($1, $3); break;
        }
    }
    | '-' expr        { $$ = -$2; }
    | '(' expr ')'    { $$ = $2; }
    ;

binop
    : '+'| '-' | '*' | '/' | POW
    ;

bison会抱怨说出现了5个递进/规约冲突。用bison -v calc2.y命令，查看calc2.output，可以看到冲突出现在状态17：

state 17

    3 expr: expr . binop expr
    3     | expr binop expr .

    POW  shift, and go to state 9
    '+'  shift, and go to state 10
    '-'  shift, and go to state 11
    '*'  shift, and go to state 12
    '/'  shift, and go to state 13

    POW       [reduce using rule 3 (expr)]
    '+'       [reduce using rule 3 (expr)]
    '-'       [reduce using rule 3 (expr)]
    '*'       [reduce using rule 3 (expr)]
    '/'       [reduce using rule 3 (expr)]
    $default  reduce using rule 3 (expr)

    binop  go to state 15

在这个状态时，下一个字符假如是+，那么既可以递进并转到状态10，也可以规约，于是就冲突了。

问题的关键就在于，这个“优先级”到底是干嘛用的。以calc1.y为例，如果没有指定运算符优先级，匹配到这样一个状态：

expr '+' expr .

（“.”表示当前匹配的位置）
假如下一个符号是*，那么到底应该选择递进，变为：

expr '+' expr '*' .

还是规约，变为：

expr .

呢？
有了优先级，bison就可以比较递进与规约的选择间涉及的优先级；看到*的优先级比+高，于是选择递进。

而在calc2.y中，加减乘除幂这几个带优先级的运算符堆在了binop规则中。匹配该规则其实不需要优先级，单靠lookahead就足够了；在遇到加减乘数幂这几个运算符时，bison肯定会选择规约为binop；规约后，binop本身就不带有任何优先级信息了。而在expr规则中，需要优先级去区分递进或规约的expr binop expr子规则却得不到任何优先级信息，于是递进/规约冲突又冒出来了。

phyeas的问题：

phyeas 写道

另外，想问下如果我在声明处定义如下：
%left PLUS
然后在规则处：
expression:
    expression op expression
;
op:
    PLUS
;

这样的华expression是否会应用上面定义的优先级？

答案是：不会。

进一步阅读：
首推自然是bison的手册。
这个帖子也可以读读，也是用表达式计算器为例子来讲解的。现在好困，不想码那么多字，既然有现成的解释我也就不用码了 =v=

评论

1 楼 phyeas 2009-09-19  

谢谢，明白了