一，Yacc文法介绍

在《Lex和Yacc——Lex学习》中我们已经了解了Lex，今天再来了解以下Yacc。看度娘是如何解释Yacc的：

yacc(Yet Another Compiler Compiler)，是一个经典的生成语法分析器的工具。yacc生成的编译器主要是用C语言写成的语法解析器（Parser），需要与词法解析器Lex一起使用，再把两部份产生出来的C程序一并编译。
简单来说，Lex是词法分析器，Yacc是语法分析器，二者结合就和以生成一个编译器。当然Lex和Yacc也都是可以单独使用的。

相比于Lex，Yacc稍微复杂一些。Yacc的文法采用BNF（Backus-Naur Form）的变量规则描述。BNF文法最初由John Backus和Peter Naur发明，并且用于描述Algol60语言。BNF能够用于表达上下文无关的语言。现代程序语言大多数结构能够用BNF来描述。我们今天用一个加减乘除的计算器的例子来学习Yacc。

比如：1+2/3+4*6-3

BNF文法：

  • E = num        规约a      0
  • E = E / E       规约b      1
  • E = E * E       规约c       1
  • E = E + E       规约d      2
  • E = E - E        规约e      2

上面第一列是E表达式；第二列是规约名字，方便后面描述；第三列是优先级，数字越小优先级越高。

这里像E表达式这样出现在左边的结构叫做非终端符（nonterminal），像num这样的标识符叫做终端符，终端符只出现在右边。

终端符号：代表一类在语法结构上等效的标记。终端符号有三种类型：

  • 命名标记：由%token标识符来定义。按照惯例，他们都是大写。lexer返回命名标记。
  • 字符标记：字符常量的写法与C相同。例如，--就是一个字符标记。
  • 字符串标记：写法与C的字符串常量相同。例如，“<<”就是一个字符串标记。
    非终端符号：是一组非终端符号和终端符号组成的符号。按照惯例，它们都是小写。
    我们将“1+2/3+4*6-3”逐个字符移进堆栈，如下所示：

.1+2/3+4*6-3

  1. 1.+2/3+4*6-3 移进
  2. E.+2/3+4*6-3 规约a
  3. E+.2/3+4*6-3 移进
  4. E+2./3+4*6-3 移进
  5. E+E./3+4*6-3 规约a
  6. E+E/.3+4*6-3 移进
  7. E+E/3.+4*6-3 移进
  8. E+E/E.+4*6-3 规约a
  9. E+E/E+.4*6-3 移进
  10. E+E/E+4.*6-3 移进
  11. E+E/E+E.*6-3 规约a
  12. E+E/E+E*.6-3 移进
  13. E+E/E+E*6.-3 移进
  14. E+E/E+E*E.-3 规约a
  15. E+E/E+E*E-.3 移进
  16. E+E/E+E*E-3. 移进
  17. E+E/E+E*E-E. 规约a
  18. E+E+E*E-E. 规约b
  19. E+E+E-E. 规约c
  20. E+E-E. 规约d
  21. E-E. 规约d
  22. E. 规约e

我们在实际运算操作中是把一个表达式逐步简化成一个非终端符。称之为“自底向上”或者“移进归约”分析法。

点左面的结构在堆栈中，而点右边的是剩余的输入信息。我们以把标记移入堆栈开始。当堆栈顶部和右式要求的记号匹配时，我们就用左式取代所匹配的标记。概念上，匹配右式的标记被弹出堆栈，而左式被压入堆栈。我们把所匹配的标记认为是一个句柄，而我们所做的就是把句柄左式归约。这个过程一直持续到把所有输入都压入堆栈中，而最终堆栈中只剩下最初的非终端符。

在第1步中我们把1压入堆栈中。第2步对应规则a，把1转换成E。然后继续压入和归约，直到第5步。此时堆栈中剩下E+E，按照规则E，可以进行E=E+E的合并，然后输入信息并没有结束，这就产生了“移进-归约”冲突（shift-reduce conflict）。在yacc中产生这种冲突时，会继续移进。在第17步，E+E/E，即可以采用规则d，也可以采用E/E规则b，如果使用E=E+E归约，显然从算法角度是错误的，这就有了运算符优先级的概念。这种情况称为“归约-归约”冲突（reduce-reduce conflict）。此时yacc会采用第一条规则，即E=E/E。

二，Yacc语法介绍

我们用一个使用Lex和Yacc实现的简单的加减乘除计算器的例子来讲解Yacc语法。先列出代码：

lex文件：cal.l

%{

#include<stdio.h>

void yyerror(char *); 

#include "cal.tab.h"

%}

%%

[0-9]+      { yylval = atoi(yytext);  return INTEGER; }
[-+*/n] { return *yytext; }
[ t]        { ;  /* 去除空格 */ }
.       { yyerror("invalid characters");  }

%%

int yywrap(void)
{
    return 1;
}

yacc文件：cal.y

%{

#include <stdio.h>
#include <stdlib.h>

int     yylex(void);
void    yyerror(char *);

%}

 /* 上面%{ %}的代码和Lex一样，一般称为定义段。就是一些头文件声明，
  * 宏定义、变量定义声明、函数声明之类的。
  */

%token  INTEGER
%left   '+' '-'
%left   '*' '/'

%%

program:
       program expr 'n'  {printf("%dn", $2); }
       |
       ;

expr:
    INTEGER { $$ = $1; }
    | expr '*' expr { $$ = $1 * $3; }
    | expr '/' expr { $$ = $1 / $3; }
    | expr '+' expr { $$ = $1 + $3; }
    | expr '-' expr { $$ = $1 - $3; }
    ;

%%

void yyerror(char *s)
{
    printf("Error: %s n", s);
}

int main(void)
{
    yyparse();

    return 0;
}

编译运行：

allan@NYC:~/test/lex_yacc/cal$ bison -d cal.y
allan@NYC:~/test/lex_yacc/cal$ lex cal.l 
allan@NYC:~/test/lex_yacc/cal$ gcc -o parser *.c
allan@NYC:~/test/lex_yacc/cal$ ll
total 140
drwxrwxr-x 2 allan allan  4096 6月   4 13:19 ./
drwxrwxr-x 3 allan allan  4096 6月   4 10:25 ../
-rw-rw-r-- 1 allan allan   269 6月   4 10:34 cal.l
-rw-rw-r-- 1 allan allan 43946 6月   4 13:19 cal.tab.c
-rw-rw-r-- 1 allan allan  2048 6月   4 13:19 cal.tab.h
-rw-rw-r-- 1 allan allan   479 6月   4 10:32 cal.y
-rw-rw-r-- 1 allan allan 44740 6月   4 13:19 lex.yy.c
-rwxrwxr-x 1 allan allan 28808 6月   4 13:19 parser*
allan@NYC:~/test/lex_yacc/cal$ ./parser 
1+2*5+10/5
13
11
11
1 + 4 * 5
21
allan@NYC:~/test/lex_yacc/cal$

这里需要说明以下bison（GUN下面的yacc工具）的-d参数(--defines)。当我们将lex和yacc一起使用的时候，我们一般将变量、宏定义等标记名称定义在yacc里面，然后lex里面取引用。我们使用-d的话，yacc工具将编写额外的输出文件，这个文件里面会包含这些宏定义：愈发中定义的标记类型名称，语义的取值类型YYSTYPE，以及一些外部变量声明。比如上面生成的文件叫"cal.tab.h"。然后我们在lex的源文件里面包含这个头文件，就可以在lex里面使用yacc定义的变量，从而将二者配合使用。

用Yacc来创建一个编译器包括四个步骤：

  1. 通过在语法文件上运行Yacc生成一个解析器。

  2. 说明语法：

    • 编写一个.y的语法文件（同时说明C在这里要进行的动作）。
    • 编写一个词法分析器来处理输入并将标记传递给解析器。这个一般使用Lex完成。
    • 编写一个函数，通过调用yyparse()来开始解析。
    • 编写错误处理例程（如yyerror()）。
  3. 编译Yacc生成的代码以及相关的源文件。
  4. 将目标文件链接到适当的可执行解析器库。
    下面我们结合上面的例子来看Yacc的语法规则。Yacc和Lex一样，也包含由“%%”分隔的三个段：定义声明、语法规则、C代码段。

1. 定义段和预定义标记部分

上面%{ %}的代码和Lex一样，一般称为定义段。就是一些头文件声明，宏定义、变量定义声明、函数声明之类的

%}和%%之间的那部分可以看做预定义标记部分。%token INTEGER定义声明了一个标记。党我们编译后，会在cal.tab.c中生成一个解析器，同时会在cal.tab.h产生包含信息：

enum yytokentype
  {
    INTEGER = 258 
  };

其中0-255之间的标记值约定为字符值，是系统保留的后定义的token。cal.tab.h里面其他部分是默认生成的，与token INTEGER无关。

lex文件需要包含这两个头文件，并且使用其中对标记值的定义。为了获得标记，yacc会调用yylex。yylex的返回值类型是整型，可以用于返回标记。而在yylval变量中保存这与返回的标记相对应的值。

yacc在内部维护这两个堆栈：一个分析栈和一个内容栈。分析站中保存着终端符和非终端符，并且记录了当前解析状态。而内容栈是一个YYSTYPE类型的元素数组，对于分析栈中的每一个元素都保存这一个对应的值。例如，当yylex返回一个INTEGER标记时，把这个标记移入分析栈。同时，相应的yacc值将会被移入内容栈中。分析栈和内容栈的内容总是同步的，因此从栈中找到对应的标记值是很容易的。

比如lex文件中下面的这一段：

[0-9]+        { yylval = atoi(yytext);  return INTEGER; }

这是将整数的值保存在yylval中，同时向yacc返回标记INTEGER。即内容栈存在了整数的值，对应的分析栈就为INTEGER标记了。yylval类型由YYSTYPE决定，由于他的默认类型是整型，所以在这个例子中运行正常。

再看下面的：

%left    '+' '-'
%left    '*' '/'

%left表示左结合，%right表示右结合。最后列出的定义拥有最高的优先权。因此乘法和除法拥有比加法和减法更高的优先权。+-*/所有这四个算术符都是左结合的。运用这个简单的技术，我们可以消除文法的歧义。

关于结合性，各运算符的结合性分为两种，即左结合性(自左至右)和右结合性
(自右至左)。例如算术运算符的结合性是自左至右，即先左后右。如有表达式x-y+z则y
应先与“-”号结合， 执行x-y运算，然后再执行+z的运算。这种自左至右的结合方向
就称为“左结合性”。而自右至左的结合方向称为“右结合性”。 最典型的右结合性运
算符是赋值运算符。如x=y=z,由于“=”的右结合性，应先执行y=z再执行x=(y=z)运算。

2. 规则部分

%%

program:
       program expr 'n'  {printf("%dn", $2); }
       |
       ;

expr:
    INTEGER { $$ = $1; }
    | expr '*' expr { $$ = $1 * $3; }
    | expr '/' expr { $$ = $1 / $3; }
    | expr '+' expr { $$ = $1 + $3; }
    | expr '-' expr { $$ = $1 - $3; }
    ;

%%

要理解这个规则，关键一点就是要理解yacc的递归解析方式。program和expr是规则标记，但是作为一个整体描述表达式。

先看expr，可以由单个INTEGER值组成，也可以由多个INTEGER和运算符组合组成。以表达式“1+4/23-0”为例：1 4 2 3 0都是expr，就是expr+expr/exprexpr-expr，说到底最后还是个expr。递归思想正好与之相反，逆推下去会发现expr这个规则标记能表示所有的数值运算表达式。

再看program，首先program可以为空，也可以用单单的expr加上"n"组成，结合起来看program定义的就是多个表达式组成的文件内容。比如我们创建一个input文件，文件内容及运行结果如下：

allan@NYC:~/test/lex_yacc/cal$ cat input 
1+5/5+4*5
3+9+2*10-9
2/2
3-9
allan@NYC:~/test/lex_yacc/cal$ ./parser < input 
22
23
1
-6
allan@NYC:~/test/lex_yacc/cal$

最后，我们来看lex是如何在程序中运作的。以expr: expr '+' expr { $$ = $1 + $3; }为例：

在分析栈中我们其实用左式替代了右式。在本例中，我们弹出“expr '+' expr”，然后压入“expr”。我们通过弹出三个成员，压入一个成员来缩小堆栈。在我们的代码中可以看到用相对地址访问内容栈中的值。如$1，$2，这样都是yacc预定义可以直接使用的标。“$1”代表右式中的第一个成员，“$2”代表第二个，后面的以此类推。“$$”表示缩小后的堆栈顶部。在上面的动作中，把对应两个表达式的值相加，弹出内容栈中的三个成员，然后把得到的和压入堆栈中。这样，保持分析栈和内容栈中的内容依然同步。

而下面这个定义说明每当一行表达式结束时，打印第二个栈值，即expr的值，完成字符运算。

program:

program expr 'n' { printf("%dn", $2); }

3. C代码部分

该部分是函数部分。当Yacc解析出错时，会调用yyerror()，用户可自定义函数的实现。

main函数调用了yacc解析的入口函数yyparse()（相当于Lex的yylex()）。

本文整理自网络。

Lex和Yacc是编译器方面的一门比较深的学问，对于不做编译器方面研究的人或许没有太深研究的必要，但是我觉得了解一下这种方式对于我们去理解编译器的行为还是非常有好处的。