lex/yacc系列：yacc进阶（一）

下面尝试将简单的计算器扩展，处理带乘法、除法、负号和括号的表达式：

expression : expression '+' expression { $$ = $1 + $3; }
 ¦ expression '-' expression { $$ = $1 - $3; }
 ¦ expression '*' expression { $$ = $1 * $3; }
 ¦ expression '/' expression
     { if ($3 == 0)
         yyerror("divide by zero");
       else
         $$ = $1 / $3;
     }
 ¦ '-' expression { $$ = -$2; }
 ¦ '(' expression ')' { $$ = $2; }
 ¦ NUMBER { $$ = $1; }
 ;

除法动作检查被零除的情况，调用yyerror()（标准的yacc错误处理例程）报告错误。

上面的语法存在问题：它有歧义。例如，输入2+3*4，可以意味着(2+3)*4，也可以是2+(3*4)，对于输入3-4-5-6，可以是3-(4-(5-6)))，也可以是(3-4)-(5-6)，或者其他很多种可能性。

如果你编译上面那样的语法，yacc将告知存在多个移进/归约冲突，表明它无法决定到底是先将标记压入堆栈，还是先归约规则。

例如，当分析“2+3*4”时，语法分析程序要经过这些步骤（这里将expression简写为E）：

2     移进 NUMBER
E     归约 E → NUMBER
E+    移进 +
E+3   移进 NUMBER
E+E   归约 E → NUMBER

这时，语法分析程序查看“*”，它可以或者利用规则：

expression : expression '+' expression

将“2+3”归约为expression，或者移进“*”，期望稍后能归约：

expression : expression '*' expression

问题是我们没能告诉yacc操作符的优先级和组合规则。优先级控制表达式中哪个操作符要先执行。数学和编程惯例规定乘法和除法优先于加法和减法，所以a+b*c的意思是a+(b*c)，d/e-f的意思是(d/e)-f。在所有的表达式语法中，操作符都被归组到由低到高不同的优先级中。级别的数目取决于语言。C语言因为有太多的优先级而出名，一共有15个级别。

组合规则（associativity）控制同一优先级上的操作符组合顺序。操作符可以从左至右组合，例如在C语言中，a-b-c意味着(a-b)-c；或者从右至左，例如a=b=c的意思是a=(b=c)。在某些情况下，操作符根本不能组合，例如在Fortran语言中，A.LE.B.LE.C是无效的。

有两种方式可以指定语法中的优先级和组合规则：隐式地和显示地。所谓隐式地指定，是指使用单独的非终结符号为每个优先级重新编写语法。假设使用常用的优先级和从左至右的组合规则，重新编写的表达式规则如下：

expression : expression '+' mulexp
 ¦ expression '-' mulexp
 ¦ mulexp
 ;

mulexp : mulexp '*' primary
 ¦ mulexp '/' primary
 ¦ primay
 ;

primary : '(' expression ')'
 ¦ '-' primary
 ¦ NUMBER
 ;

yacc还允许显式地指定优先级。可以在定义部分添加：

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

每一行定义了一个优先级：“+”和“-”从左至右组合，处于最低的优先级；“*”和“/”从左至右组合，处于较高的优先级；UMINUS是一个代表一元负号的伪标记，没有组合规则，处于最高的优先级。（从右至左组合规则使用%right定义。）

yacc指定规则右侧最右边标记的优先级作为该规则的优先级。当yacc遇到歧义语法引起的移进/归约冲突时，它就参考优先级表，并且如果冲突所涉及的所有规则都包含一个出现在优先级声明中的标记时，它使用优先级来解决冲突。

在前面的语法中，所有的冲突都发生在形如expression OPERATOR expression的规则中，所以为四个操作符设置优先级将解决所有的冲突。在这个语法分析程序中，使用优先级与利用额外规则的隐式方式相比，需要归约的规则比较少，所以程序略小而且速度稍快。

下面是完整的yacc语法文件：

%token NAME NUMBER
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

%%
statement : NAME '=' expression
 ¦ expression { printf("= %d\n", $1); }
 ;

expression : expression '+' expression { $$ = $1 + $3; }
 ¦ expression '-' expression { $$ = $1 - $3; }
 ¦ expression '*' expression { $$ = $1 * $3; }
 ¦ expression '/' expression
      { if ($3 == 0)
          yyerror("divide by zero");
        else
          $$ = $1 / $3;
      }
 ¦ '-' expression %prec UMINUS { $$ = -$2; }
 ¦ '(' expression ')' { $$ = $2; }
 ¦ NUMBER { $$ = $1; }
 ;

负号规则包括“%prec UMINUS”，这条规则包括的唯一操作符是“-”，这个操作符具有很低的优先级，但是我们希望一元负号具有比乘法更高的优先级，%prec告知yacc这条规则使用UMINUS的优先级。