本文共 3136 字，大约阅读时间需要 10 分钟。
转自：
2009-05-07 15:121.概念yacc使用巴克斯范式(BNF)定义语法，能处理上下文无关文法(context-free)。出现在每个产生式左边(left-hand side：lhs)的符号是非终端符号，出现在产生式右边(right-hand side：rhs)的符号有非终端符号和终端符号，但终端符号只出现在右端。
在规约过程中可能会有冲突。Yacc对此有一些缺省的处理方法，那就是使用第一个匹配的规则。
2.Yacc文件格式Yacc文件分为三部分：... definitions ...%%... rules ...%%... subroutines ...
3.定义部分第一部分包括标志(token)定义和C代码(用“%{”和“%}”括起来)。
如在定义部分定义标志：
%token INTEGER当运行yacc后，会产生头文件，里面包含该标志的预定义，如：#ifndef YYSTYPE#define YYSTYPE int#endif#define INTEGER 258extern 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 ‘*’ ‘/’上面定义的乘法和除法比加法和减法有更高的优先级。
Yacc内部维持着两个栈：符号栈(parse stack)和值栈(value stack)，这两个栈始终是同步的。
改变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的优先级高于其他操作符，所以该操作的优先级也高于其他操作符计算。
4.规则部分规则部分很象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;}int main(void){ yyparse(); return 0;}其中，$1表示右边的第一个标记的值，$2表示右边的第二个标记的值，依次类推。$$表示规约后的值。
5.第三部分该部分是函数部分。当yacc解析出错时，会调用函数yyerror()，用户可自定义函数的实现。main函数是调用yacc解析入口函数yyparse()。 6.递归的处理递归处理有左递归和右递归。左递归形式：
list:item| list ',' item ;右递归形式：
list: item| item ',' list使用右递归时，所有的项都压入堆栈里，才开始规约；而使用左递归的话，同一时刻不会有超过三个项在堆栈里。
所以，使用左递归有很大的优势。
7.If-Else的冲突当有两个IF一个ELSE时，该ELSE和哪个IF匹配是一个问题。有两中匹配方法：与第一个匹配和与第二匹配。现代程序语言都让ELSE与最近的IF匹配，这也是yacc的缺省行为。虽然yacc行为正确，但为避免警告，可以给IF-ELSE语句比IF语句更高的优先级：
%nonassoc IFX%nonassoc ELSEstmt: IF expr stmt %prec IFX| IF expr stmt ELSE stmt
8.出错处理当yacc解析出错时，缺省的行为是调用函数yyerror()，然后从yylex返回一个值。一个更友好的方法是忽略一段错误输入流，继续开始扫描。实现方法如下：
stmt:';'| expr ';'| PRINT expr ';'| VARIABLE '=' expr ';
| WHILE '(' expr ')' stmt| IF '(' expr ')' stmt %prec IFX| IF '(' expr ')' stmt ELSE stmt| '{' stmt_list '}'| error ';'| error '}';这里的error标志表示，当yacc发现错误时，它调用yyerror()，之后是输入流往前到‘；’或‘}’，然后继续扫描。
9.Yacc源程序的风格建议按照如下风格来写：终端符名全部用大写字母，非终端符全部用小写字母； 把语法规则和语义动作放在不同的行； 把左部相同的规则写在一起，左部只写一次，而后面所有规则都写在竖线“|”之后； 把分号“；”放在规则最后，独占一行； 用制表符来对齐规则和动作。
转载地址：http://sdemb.baihongyu.com/