lex/yacc系列：yacc简介

yacc（Yet Another Compiler Compiler），用类似BNF的格式从规则列表中生成语法分析程序的程序。

对于某些应用，我们完成简单的词法分析就足够了；而另一些应用需要识别特殊的标记序列并执行适当的动作。传统上，对这样的一套动作描述称为语法。lex将输入流分解成块（标记），然后yacc取得这些块并将它们按照一定的逻辑组合在一起。

语法

yacc的输入语法是BNF（Backus-Naur Form，巴克斯-诺尔范式）的简化版本。BNF是表示语法的一种方法，常用于指定程序设计语言的正式语法。下面是用于构建示例计算器的语法形式：

statement → NAME = expression
expression → NUMBER + NUMBER
 ¦  NUMBER - NUMBER

竖线“¦”表示或者，意味着多种可能性，例如，表达式可以是加法或者减法。箭头左侧的符号，即规则的左边，通常缩写为LHS（lef-hand side），右侧的符号是规则的右边，通常缩写为RHS（right-hand side）。出现在输入流中、被词法分析程序返回的符号是终结符或标记；而规则左侧出现的是非终结符。终结符与非终结符必须是不同的，标记出现在规则左侧是错误的。

通常用树状结构来表示所分析的句子。每个语法都包括起始符号，这些起始符号必须位于语法分析树的根部。在这个语法中，statement是起始符号。

递归规则

规则可以直接或间接地引用本身，这一特性使分析任意长的输入序列成为可能。扩展上面的语法来处理更长的算术表达式：

expression → NUMBER
 ¦  expression + NUMBER
 ¦  expression - NUMBER

yacc对分析递归规则非常有效，几乎可以在使用的每个语法中都看到递归规则。

移进/归约分析

yacc语法分析程序的工作原理是寻找可以匹配目前为止所看到的标记的规则。yacc处理语法分析程序时创建了一组状态，每个状态表示一个或多个被部分地分析的规则中的一个可能的位置。语法分析程序读取标记时，每次当它读到一个标记，而该标记不能完成任何规则，就把该标记压入内部堆栈，并且切换到对应于这个刚读入的标记的新的状态。这个动作称为移进（shift）。当它发现了组成某条规则右侧的全部符号时，它就把这些右侧符号弹出堆栈，而将相对应的左侧符号压入堆栈，并且切换到反映堆栈中新符号的新的状态。这个动作称为归约（reduction），因为它通常减少堆栈中项目的数量。（但也并不总是如此，因为可能有右侧为空的规则。）每当yacc归约一条规则，它就执行与之相关的用户代码。

下面的示例以上面介绍的分析过程分析输入“res = 8 + 12”。刚开始，将标记一次一个压入堆栈：

res
res =
res = 8
res = 8 +
res = 8 + 12

这里可以归约规则“expression → NUMBER + NUMBER”，所以8、+、12被弹出堆栈，代之以expression：

res = expression

现在可以归约规则“NAME = expression”，所以res、=和expression被弹出，代之以statement。这时候，输入完成，堆栈也被归约到起始符号，按照语法，这个输入是有效的。

yacc不能分析什么

• 歧义语法，同样的输入符合多个规则
• 没有歧义，但需要向前看多于一个标记才能决定是否匹配一条规则的语法。例如：
  phrase → cart_animal AND CART
 ¦  work_animal AND PLOW
cart_animal → HORSE GOAT
work_animal → HORSE OX

  对于如“HORSE AND CART”的输入，yacc不能决定HORSE是cart_animal还是work_animal，直到它看到CART，但是yacc不能看那么远。如果把上面的第一条规则改为如下形式：

  phrase → cart_animal CART
 ¦  work_animal PLOW

  yacc就不会遇到麻烦，它会提前看下一个标记来决定，如果HORSE后跟PLOW，就是work_animal，如果后跟CART，则为cart_animal。

yacc语法分析程序

yacc语法分析程序的结构与lex结构类似（lex结构模仿了yacc的结构）。第一部分（定义段）处理yacc生成的语法分析程序的控制信息，并且一般建立语法分析程序运行的执行环境。第二部分包含语法分析程序的规则。第三部分是被逐字拷贝到生成的C程序中的C代码。

下面以简单的计算器示例来了解语法分析程序的结构。

定义段

定义段包含语法中使用的标记的描述、分析程序的堆栈中使用的值的类型，以及其他的一些东西。它还可以包含由%(和%)扩住的C代码，这些代码将被逐字拷贝到生成的C程序中。下面通过声明两个符号标记来开始示例语法分析程序。

%token NAME NUMBER

单个的引用字符可以不经声明直接作为标记使用，所以不需要声明“=”、“+”或“-”。

规则段

语法部分是由一列语法规则组成，其格式与前面使用的规则的格式大致相同。因为ASCII键盘没有“→”键，所以在规则的左侧和右侧使用冒号“:”，而且在每个规则的结尾有一个分号“;”：

%%
statement : NAME '=' expression
 ¦  expression
 ;

expression : NUMBER '+' NUMBER
 ¦  NUMBER '-' NUMBER
 ;

这里，分析程序增加了一条规则：statement可以是纯表达式，也可以是一个赋值。如果用户输入一个纯表达式，就打印它的结果。

第一条规则的左侧符号通常是起始符号，但可以在定义段使用%start声明覆盖它。

符号的值以及动作

yacc语法分析程序中的每个符号都有一个值，这个值给出了该符号的特定实例的额外信息：如果符号表示一个数字，它的值就是某个数字；如果符号表示一个引用字符串，它的值就可能是一个指向该字符串拷贝的指针；如果符号表示程序中的一个变量，它的值就是指向这个变量的符号表项的指针。有些标记没有有用的值，例如，表示闭括号的标记，因为所有的闭括号都是一样的。

在示例语法分析程序中，NUMBER的值是一个数值，expression的值是表达式的值，NAME的值是一个符号表指针。

在实际的语法分析程序中，不同符号的值可能使用不同的数据类型，例如，对于数字符号使用int和double，对于字符串使用char *，对于复杂符号使用结构指针。如果使用了多种数据类型，就必须在语法分析程序中列出所有的数据类型，yacc创建了一个包含所有数据类型的名为YYSTYPE的C联合（union）类型定义。

在示例程序中，唯一感兴趣的是输入的数字和表达式的数值。默认情况下，yacc将所有数值的类型定义为int，示例程序将使用这个默认定义。

每当语法分析程序归约一个规则时，它就执行与该规则相关的C代码，即规则的动作。规则动作被包含在大括号中，出现的位置在规则结尾之后，分号（;）或竖线（¦）之前。动作代码可以通过$1、$2……引用规则右侧符号的值，也可以通过$$设置规则左侧的值。在示例程序中，符号expression的值是它所代表的表达式的值。下面添加一些代码来打印和计算表达式：

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

expression : expression '+' NUMBER { $$ = $1 + $3; }
 ¦  expression '-' NUMBER { $$ = $1 - $3; }
 ¦  NUMBER { $$ = $1; }
 ;

构建表达式的规则计算相应的值，识别表达式的规则打印结果。在构建表达式的规则中，第一个和第二个数值分别对应于$1和$3，$2则是操作符的值，我们对它不感兴趣；该规则中的最后一个动作不是绝对必要的，因为当yacc每次归约后，在运行任何显式的动作代码之前，都会执行默认动作，将$1的值赋予$$。

词法分析程序

为了测试示例的语法分析程序，我们还需要一个词法分析程序来提供标记。语法分析程序是较高级的例程，当它需要从输入流中获取一个标记，它就调用词法分析程序yylex()。词法分析程序一发现语法分析程序感兴趣的标记，它就返回语法分析程序，并将标记代码作为值返回。yacc将语法分析程序中的标记的名称定义在C预处理文件y.tab.h中，从而词法分析程序可以使用它们。

下面是为示例语法分析程序提供标记的简单词法分析程序：

%{
#include "y.tab.h"
extern int yylval;
%}

%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
[ \t]  ; /* 忽略空白 */
\n     { return 0; }
.      { return yytext[0]; }
%%

上面的词法分析程序将数字串转换为数字，忽略空白，当遇到换行时返回输入结束标记（数字0），通知语法分析程序没有更多的东西需要读取。最后一条规则是非常常用的截流器（catch-all），即将所有其他未处理的字符作为单个字符返回给语法分析程序。字符标记通常是标点符号，如大括号、分号以及单字操作符。如果语法分析程序接收到不认识的标记，它就产生语法错误，因此这条规则可以让你很容易地处理所有的单字操作符，而让yacc的错误检查捕获和“抱怨”无效的输入。

当词法分析程序将一个标记返回给语法分析程序时，如果该标记有相关的值，词法分析程序在返回前必须将值储存在yylval中。在上面的示例中，yylval被显式声明。在更复杂的语法分析程序中，yacc在y.tab.h中将yylval声明为一个联合（union）。

编译运行示例语法分析程序

将上面的语法分析程序代码保存在文件calc1.y中，词法分析程序代码在calc1.l中。yyac将产生y.tab.h和C语言语法分析程序y.tab.c。lex创建lex.yy.c，C语言词法分析程序。你需要用lex和yacc库将它们编译在一起。这些库中包含所有支持例程的可用的默认版本，包括一个main()，它调用语法分析程序yyparse()，然后退出。

% yacc -d calc1.y
% lex calc1.l
% cc -o calc1 y.tab.c lex.yy.c -ly -ll
% calc1
99+12
= 111
% calc1
2 + 3-14+33
= 24
% calc1
100 + -50
syntax error