lex/yacc系列：yacc进阶（三）

下面我们使用符号表——一种用来跟踪使用中的名字的结构，来增加使用长变量名的能力。每次语法分析程序读取输入中的名字，它都在符号表中查找这个名字，并且得到一个对应于符号表条目的指针。因为符号表要求词法分析程序和语法分析程序之间共享数据结构，所以我们创建一个头文件calc4.h：

#define NSYMS 20 /* 允许的符号个数 */

struct symtab {
  char *name;
  double value;
} symtab[NSYMS];

struct symtab *symlook();

在这个实现中，符号表是一个结构数组（也可以使用其他类型的数据结构，例如链表），每个结构包含变量的名字和它的值。还声明了一个函数symlook()，它以文本字符串形式的名字为参数，返回对应的符号表条目的指针，如果不存在，就添加。

语法分析程序只需要少许修改，以使用符号表：

%{
#include "calc4.h"
#include

int nsym = 0;
%}

%union {
  double dval;
  struct symtab *symp;
}

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

%type <dval> expression

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

statement : NAME '=' expression { $1->value = $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 { $$ = $1->value; }
 ;

%%
struct symtab *
symlook(char *s)
{
 int i;

 for (i = 0; i < nsym; ++i) {
  if (!strcmp(symtab[i].name, s))
   return &symtab[i];
 }

 if (nsym < NSYMS) {
  symtab[nsym].name = strdup(s);
  ++nsym;
  return &symtab[nsym-1];
 }

 yyerror("Too many symbols");
 exit(1);
}

NAME标记的值是指向符号表的指针，%union和NAME的%token声明适当地有所改变，而且给变量赋值和读取变量的动作现在将标记值作为指针来使用，读写符号表条目的value字段。函数symlook()被定义在用户子例程部分，它顺序地搜索符号表来寻找与作为参数传入的名字对应的条目，并返回其指针；如果没有找到，就把它保存在符号表中。顺序搜索对于这个简单示例是合适的，但对于大尺寸的符号表来说太慢了，需要使用散列表或者其他的快速搜索方法。

词法分析程序也需要稍加修改以适应符号表。识别变量名的规则匹配“[A-Za-z][A-Za-z0-9]*”，任何以字母开头的包含
字母和数字的字符串被认为是变量名。它的动作调用symlook()得到指向符号表条目的指针，并将它存储在标记的值yylval.symp中。

%{
#include "y.tab.h"
#include "calc4.h"
#include
%}

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

[ \t] ;

[A-Za-z][A-Za-z0-9]* {
  yylval.symp = symlook(yytext);
  return NAME;
 }

"$"   { return 0; }

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

%%

因为字符串动态分配，所以对于变量名的长度没有限制。下面是运行实例：

% calc4
foo = 12
foo /5
= 2.4
thisisanextremelylongvariablenamewhichnobodywouldwanttotype = 42
3 * thisisanextremelylongvariablenamewhichnobodywouldwanttotype
= 126
thisisanextremelylongvariablenamewhichnobodywouldwanttotype / foo
= 3.5
$