2007年12月4日星期二

lex/yacc系列:yacc进阶(二)

下面再扩展计算器的功能,使它能够处理名字为单个字母的变量。先只考虑26个小写字母为变量名,我们将这26个变量储存在数组vbltable中。为了使计算器更有用,我们还进一步扩展,使它能处理多条表达式,每行一条,并且使用浮点数作为数值。

拥有变量和实数数值的计算器语法分析程序calc3.y:

%{
double vbltable[26];
%}

%union {
  double dval;
  int vblno;
}

%token <vblno> NAME
%token <dval> NUMBER
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS

%type <dval> expression

%%
statement_list : statement '\n'
 ¦ statement_list statement '\n'
 ;

statement : NAME '=' expression { vbltable[$1] = $3; }
 ¦ expression { printf("= %g\n", $1); }
 ;

expression : expression '+' expression { $$ = $1 + $3; }
 ¦ expression '-' expression { $$ = $1 - $3; }
 ¦ expression '*' expression { $$ = $1 * $3; }
 ¦ expression '/' expression
    { if ($3 == 0.0)
        yyerror("divide by zero");
      else
        $$ = $1 / $3;
    }
 ¦ '-' expression %prec UMINUS { $$ = -$2; }
 ¦ '(' expression ')' { $$ = $2; }
 ¦ NUMBER
 ¦ NAME { $$ = vbltable[$1]; }
 ;

拥有变量和实数数值的计算器词法分析程序calc3.l:

%{
#include "y.tab.h"
#include <math.h>
extern double vbltable[26];
%}

%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {
    yylval.dval = atof(yytext);
    return NUMBER;
  }

[ \t] ;

[a-z] { yylval.vblno = yytext[0] - 'a'; return NAME; }

"$"   { return 0; }

\n    ¦
.     { return yytext[0]; }

%%

在这个程序中,符号值有多种数据类型:表达式的值是double,变量引用和符号NAME的值是对应于vbltable的从0到25之间的整数。为了定义可能的符号类型,在定义部分加入了%union声明:

%union {
  double dval;
  int vblno;
}

声明中的内容将被逐字拷贝到输出文件y.tab.h中,作为C类型定义YYSTYPE的联合声明的内容:

#define NAME 257
#define NUMBER 258
#define UMINUS 259
typedef union {
  double dval;
  int vblno;
} YYSTYPE;
extern YYSTYPE yylval;

生成的头文件中还声明了变量yylval,并且定义了语法中使用的的符号标记的标记号。

在语法分析程序中的定义部分的符号定义行,由尖括号扩住的联合声明中的字段名指定了符号值的类型。

%token <vblno> NAME
%token <dval> NUMBER

%type <dval> expression

非终结符不需要声明,除非需要通过声明%type指定其类型。也可以在%left%right%nonassoc通过尖括号指定类型。在动作代码中,yacc对于符号值引用将自动添加合适的字段名,例如,如果第三个字符是NUMBER,对$3的引用就等于$3.dval。

在这个扩展的语法分析程序中还加入了一个新的起始符号statement_list,因此它能处理一系列而不仅仅是一条语句,每条语句以换行结尾。还为设置变量的规则增加了一个动作,并在最后添加了一条将NAME转换成expression的新规则,它获取变量的值。

词法分析程序也必须进行一些修改。yylval已经在y.tab.h中声明,所以不需要再次声明。词法分析程序并不能自动识别符号的类型,所以设置yylval时必须显式地添加字段引用。动作代码调用atof()读入数字,然后将值赋给yylval.dval。对于变量,在yylval.vblno中返回变量表中变量的下标。最后,使“\n”成为了一个普通标记,并使用“$”标志输入的结束。

下面是运行实例:

% calc3
2/3
= 0.666667
a = 2/7
a
= 0.285714
z = a+1
z
= 1.28571
a/z
= 0.222222
$

没有评论: