Yacc使用

rookie 2012-09-12

展开全文

1.概念

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 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;
返回加号或减号。注意要把减号放在前面，避免被认作是范围符号。

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

Yacc内部维持着两个栈：符号栈（parse stack）和值栈（value stack），这两个栈始终是同步的。

改变YYSTYPE的类型。如这样定义TTSTYPE：
%union {
int iValue;
char sIndex;
nodeType *nPtr;
};
则生成的头文件中的内容是：
typedef union {
int iValue;
char sIndex;
nodeType *nPtr;
} YYSTYPE;
extern YYSTYPE yylval;

可以把标志（token）绑定到YYSTYPE的某个域。如：
%token INTEGER
%type 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;
}