Duangw

Yacc使用

索引:

  1. 概念
  2. Yacc文件格式
  3. 定义部分
  4. 规则部分
  5. 第三部分
  6. 递归的处理
  7. If-Else的冲突
  8. 出错处理
  9. Yacc源程序的风格

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;  /* 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 ELSE
stmt:  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源程序的风格

建议按照如下风格来写:

  1. 终端符名全部用大写字母,非终端符全部用小写字母;
  2. 把语法规则和语义动作放在不同的行;
  3. 把左部相同的规则写在一起,左部只写一次,而后面所有规则都写在竖线“|”之后;
  4. 把分号“;”放在规则最后,独占一行;
  5. 用制表符来对齐规则和动作。