Yacc介绍与使用

•什么是YACC？

yacc(Yet Another Compiler Compiler)，是Unix/Linux上一个用来生成编译器的编译器（编译器代码生成器）.

使用巴克斯范式(BNF)定义语法，能处理上下文无关文法(context-free)。出现在每个产生式左边(left-hand side：lhs)的符号是非终端符号，出现在产生式右边(right-hand side：rhs)的符号有非终端符号和终端符号，但终端符号只出现在右端。

yacc是开发编译器的一个有用的工具,采用LR（1）（实际上是LALR(1)）语法分析方法。

LR(k)分析方法是1965年Knuth提出的，括号中的k（k >=0）表示向右查看输入串符号的个数。LR分析法正视给出一种能根据当前分析栈中的符号串和向右顺序查看输入串的k个符号就可唯一确定分析器的动作是移进还是规约和用哪个产生式规约。

这种方法具有分析速度快，能准确，即使地指出出错的位置，它的主要缺点是对于一个使用语言文法的分析器的构造工作量相当大，k愈大构造愈复杂，实现比较困难。

一个LR分析器有3个部分组成：

•总控程序，也可以称为驱动程序。

对所有的LR分析器总控程序都是相同的。

•分析表或分析函数。

不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作(ACTION)表和状态转换(GOTO)表两个部分，它们都可用二维数组表示。

•分析栈，包括文法符号栈和相应的状态栈。

它们均是先进后出栈。 分析器的动作由栈顶状态和当前输入符号所决定(LR(0)分析器不需要向前查看输入符号)。

LR分析器工作过程如下 :

其中SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表内容按关系GOTO[Si，X] = Sj确定，该关系式是指当栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。X为终结符或非终结符。 ACTION[Si，a]规定了栈顶状态为Si是遇到输入符号a应执行的动作。

动作

动作有4种可能：

移进：

当Sj= GOTO[Si，a]成立，则把Sj移入到状态栈，把a移入到文法符号栈。其中i，j表示状态号。

规约：

当在栈顶形成句柄为β时，则用β归约为相应的非终结符A，即当文法中有 A-->β的产生式，而β的长度为r（即|β| = r）,则从状态栈和文法符号栈中自栈顶向下去掉r个符号，即栈指针SP减去r。并把A移入文法符号栈内，再把满足Sj= GOTO[Si，A]的状态移进状态栈，其中Si为修改指针后的栈顶状态。

接受acc:

当规约到文法符号栈只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是‘#’，则为分析成功。

报错：

当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子。

YACC文件格式

yacc文件分为三部分：

... definitions ...（%{}%）

%%
... rules ...
%%

... subroutines ...

定义部分

第一部分包括标志（token）定义和C代码（用“%{”和“%}”括起来）。

如在定义部分定义标志：
%token INTEGER

当运行yacc后，会产生头文件，里面包含该标志的预定义，如：
#ifndef YYSTYPE
#define YYSTYPE int
#endif
#define INTEGER 258
extern YYSTYPE yylval;

lex使用该头文件中的标志定义。Yacc调用lex的yylex()来获得标志（token），与标志对应的值由lex放在变量yylval中。yylval的类型由YYSTYPE决定，YYSTYPE缺省类型是int。如：
[0-9]+ {
yylval = atoi(yytext);
return INTEGER;
}

标志0-255被保留作为字符值，一般产生的token标志从258开始。如：
[-+] return *yytext; /* return operator */
返回加号或减号。注意要把减号放在前面，避免被认作是范围符号。

对于操作符，可以定义%left和%right：%left表示左相关（left-associative），%right表示右相关（right-associative）。可以定义多组%left或%right，在后面定义的组有更高的优先级。如：
%left ‘+’ ‘-‘
%left ‘*’ ‘/’
上面定义的乘法和除法比加法和减法有更高的优先级。

改变YYSTYPE的类型。如这样定义TTSTYPE：
%union

{
int iValue; /* integer value */
char sIndex; /* symbol table index */
nodeType *nPtr; /* node pointer */
};

则生成的头文件中的内容是：
typedef union

{
int iValue; /* integer value */
char sIndex; /* symbol table index */
nodeType *nPtr; /* node pointer */
} YYSTYPE;
extern YYSTYPE yylval;

可以把标志（token）绑定到YYSTYPE的某个域。如：
%token <iValue> INTEGER
%type <nPtr> expr
把expr绑定到nPtr，把INTEGER绑定到iValue。yacc处理时会做转换。如：
expr: INTEGER { $$ = con($1); }
转换结果为：
yylval.nPtr = con(yyvsp[0].iValue);
其中yyvsp[0]是值栈（value stack）当前的头部。

定义一元减号符有更高的优先级的方法：
%left GE LE EQ NE '>' '<'
%left '+' '-'
%left '*'
%nonassoc UMINUS
%nonassoc的含义是没有结合性。它一般与%prec结合使用表示该操作有同样的优先级。如：
expr: '-' expr %prec UMINUS { $$ = node(UMINUS, 1, $2); }
表示该操作的优先级与UMINUS相同，在上面的定义中，UMINUS的优先级高于其他操作符，所以该操作的优先级也高于其他操作符计算。

规则部分

规则部分很象BNF语法。

规则中目标或非终端符放在左边，后跟一个冒号（：），然后是产生式的右边，之后是对应的动作（用{}包含）。如：
%token INTEGER
%%
program: program expr '\n' { printf("%d\n", $2); }

;
expr: INTEGER { $$ = $1; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
;
%%
int yyerror(char *s)
{
fprintf(stderr, "%s\n", s);
return 0;
}

其中，$1表示右边的第一个标记的值，$2表示右边的第二个标记的值，依次类推。$$表示规约后的值。

第三部分

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

main函数是调用yacc解析入口函数yyparse()。如：

int main(void)
{
yyparse();
return 0;
}

递归的处理

递归处理有左递归和右递归。

左递归形式：
list: item
| list ',' item;

右递归形式：
list: item
| item ',' list

使用右递归时，所有的项都压入堆栈里，才开始规约；而使用左递归的话，同一时刻不会有超过三个项在堆栈里。

If-Else的冲突

当有两个IF一个ELSE时，该ELSE和哪个IF匹配是一个问题。有两种匹配方法：与第一个匹配和与第二匹配。现代程序语言都让ELSE与最近的IF匹配，这也是yacc的缺省行为。

虽然yacc行为正确，但为避免警告，可以给IF-ELSE语句比IF语句更高的优先级：
%nonassoc IFX
%nonassoc ELSE
stmt: IF expr stmt %prec IFX
| IF expr stmt ELSE stmt

出错处理

当yacc解析出错时，缺省的行为是调用函数yyerror()，然后从yylex返回一个值。一个更友好的方法是忽略一段错误输入流，继续开始扫描。这里要涉及到YACC中错误保留字error的应用。

Yacc源程序的风格

建议按照如下风格来写：
（1）终端符名全部用大写字母，非终端符全部用小写字母；
（2）把语法规则和语义动作放在不同的行；
（3）把左部相同的规则写在一起，左部只写一次，而后面所有规则都写在竖线“|”之后；
（4）把分号“；”放在规则最后，独占一行；
（5）用制表符来对齐规则和动作。

语法分析中的错误处理

当进行语法分析时发现输入串有语法错误，最好能在报告出错信息以后继续进行语法分析，以便发现更多的错误。
Yacc处理错误的方法是：当发现语法错误时，yacc丢掉那些导致错误的符号适当调整状态栈。然后从出错处的后一个符号处或跳过若干符号直到遇到用户指定的某个符号时开始继续分析。Yacc内部有一个保留的终结符error，把它写在某个产生式的右部，则Yacc就认为这个地方可能发生错误，当语法分析的确在这里发生错误时，Yacc就用上面介绍的方法处理，如果没有用到 error的产生式，则 Yacc打印出“Syntax error”，就终止语法分析。

下面看两个使用error的简单例子：

1．下面的产生式
stat: error
;
使yacc在分析stat推导出的句型时，遇到语法错误时跳过出错的部分，继续分析（也会打印语法错误信息）

2．下面的产生式
stat: error ';'
;
使yacc碰到语法错时，跳过输入串直到碰到下一个分号才继续开始语法分析。

嵌入式动作

对于语法分析程序中的每一个语法规则，都有相应的C/C++语句来做一些额外的处理，这个额外的处理就是语法动作。不过语法动作和词法动作的不同之处在于，语法动作允许嵌入式的语法动作，而词法动作不行。

尽管yacc的语法分析技术只允许动作在规则的末端，但yacc可以自动模拟嵌入在规则内部的动作。如果在规则内部写入一个动作，yacc就会创造一个右侧为空并且左边是自动生成的名字规则，使得嵌入的动作进高规则的动作里去，用自动成成的名字代替最初的规则内的动作。

例如： 下面的句子是等价的

thing : A {printf("I am A") ;} B

thing : A fakename B;

fakename : {printf("I am A");}

这种方式将A植作为$1, 规则末端的动作可将嵌入式动作的值作为$2,B的值为$3.

Example:

//L文件：
%{
#include"FIRST_TA.H"
#include<stdio.h>
#include<stdlib.h>
%}
%%
a{returnA_STATE;}
b{returnB_STATE;}
c{returnC_STATE;}
not{returnNOT;}
%%

//Y文件：
%{
#include<stdio.h>
#include<stdlib.h>
%}
%tokenA_STATEB_STATEC_STATENOT
%%

program:
A_STATEB_STATE{
intc,d;
c=20;
d=25;
}
c_state_not{
inte,f;
e=30;
f=35;
}
|
A_STATEB_STATE{
inta,b;
a=10;
b=15;
}
c_state_not:C_STATENOT{}
%%

输入文件的字符：a,b,c,f,c,not

//L文件：
%{
#include "FIRST_TA.H"
#include <stdio.h>
#include <stdlib.h>
%}
%%
a	{return A_STATE;}
b	{return B_STATE;}
c 	{return C_STATE;}
not   {return NOT;}
%%

//Y文件：
%{
#include <stdio.h>
#include <stdlib.h>
%}
%token	A_STATE B_STATE C_STATE NOT
%%

program :	
	A_STATE B_STATE {
		int c, d;
		c = 20;
		d = 25;
	}
      c_state_not  {
		    int e,f;
		    e = 30;
		    f = 35;
		}
	|
	A_STATE B_STATE  {
	        int a, b;
	        a = 10;
	        b = 15;
	}
	c_state_not : C_STATE NOT{}
%%

输入文件的字符：a, b, c, f, c, not