前一版本的计算器并没有充分利用抽象语法树的优点，在这一版中我们将支持变量命名和赋值，比较表达式，if/then/else/和do/while的流程控制，内置和用户自定义的函数等等功能。
Flex词法分析规则
新建fb_3_2.l文件，添加如下代码
%option noyywrap nodefault yylineno
%{
#include "fb_3_2.h"
#include "fb_3_2.tab.h"
%}
/*浮点数指数部分*/
EXP ([Ee][-+]?[0-9]+)
%%
"+" |
"-" |
"*" |
"/" |
"=" |
"|" |
"," |
";" |
"(" |
")" { return yytext[0]; }
">" { yylval.fn = 1; return CMP; }
"<" { yylval.fn = 2; return CMP; }
"<>" { yylval.fn = 3; return CMP; }
"==" { yylval.fn = 4; return CMP; }
">=" { yylval.fn = 5; return CMP; }
"<=" { yylval.fn = 6; return CMP; }
"if" { return IF; }
"then" { return THEN; }
"else" { return ELSE; }
"while" { return WHILE; }
"do" { return DO; }
"let" { return LET; }
"sqrt" { yylval.fn = B_sqrt; return FUNC; }
"exp" { yylval.fn = B_exp; return FUNC; }
"log" { yylval.fn = B_log; return FUNC; }
"print" { yylval.fn = B_print; return FUNC; }
[a-zA-Z][a-zA-Z0-9]* { yylval.s = lookup(yytext); return NAME; }
[0-9]+"."[0-9]*{EXP}? |
"."?[0-9]+{EXP}? { yylval.d = atof(yytext);return NUMBER; }
"//".*
[ \t ] {/*忽略空白字符*/}
\\\n { printf("c> "); } /**忽略续行符*/
\n { return EOL;}
. {yyerror("Mystery character %c\n",*yytext);}
%%
Bison语法分析规则
新建fb_3_2.y语法分析规则文件，代码如下
%{
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include "fb_3_2.h"
%}
/*
第一部分使用%union来生命语法分析器中符号值的类型
一旦联合类型被定义，我们需要告诉bison每种语法符号使用的值类型，这通过放置在尖括号<>中的联合类型的响应成员名字来确定。
新的声明 %type把值<a>赋给exp, factor, term，当我们创建ast时会用到他们
如果你不使用记号或者非终结符的值，你并不需要为他们声明类型。
当声明中存在%union时，如果你试图使用一个没有被赋予类型的符号值，bison将会报错。
*/
%union {
struct ast *a;
double d;
struct symbol *s; /*指定符号*/
struct symlist *sl;
int fn; /*指定函数*/
}
/**正如符号（symbol）值可以指向抽象语法树的指针或者一个具体的数值那样，符号值也可以指向符号表中特定用户符号user symbol,符号列表，比较子类型和函数记号的指针
这儿有一个新记号 FUNC表示内置函数，它的值确定了具体的某个函数，另外还有6个保留字，从IF到LET。记号CMP是6中比较操作符之一，它的值确定了具体的操作符。
优先级声明列表从新的CMP和=操作符开始
*/
%token <d> NUMBER
%token <s> NAME
%token <fn> FUNC
%token EOL
%token IF THEN ELSE WHILE DO LET
/*优先级声明*/
%nonassoc <fn> CMP
%right '='
%left '+' '-'
%left '*' '/'
%nonassoc '|' UMINUS
%type <a> exp stmt list explist
%type <sl> symlist
/**%start 声明定义了顶层规则，所以我们不需要把这条规则放到语法分析器的开始部分*/
%start calclist
%%
/**语法区分了语句stmt和表达式exp。语句是一个控制流(if/then/else或者while/do）或者是一个表达式。
if和while语句具有一连串语句，这里面的语句都用分号结尾。每当规则匹配一条语句时，它调用相应的函数来创建合适的抽象语法树节点
*/
/*stmt和list是计算器语句的语法*/
stmt: IF exp THEN list { $$ = newflow('I', $2, $4, NULL); }
| IF exp THEN list ELSE list { printf("if exp then list else list\n");$$ = newflow('I', $2, $4, $6); }
| WHILE exp DO list { $$ = newflow('W', $2, $4, NULL); }
| exp { printf("stmt:exp:\n"); $$ = $1; }
;
/**
list的定义是右递归的，也就是说是stmt;list 而不是list stmt ;这对于语言识别没有任何差异，但是我们因此会更容易构造一个从头到尾而不是相反方向的语句链表。
每当stmt; list规则被归约时，它创建一个链接来把语句添加到当前链表的头部。如果规则是list stmt ; 语句需要被添加到链表的尾部，这就要求我们使用一个更复杂的循环链表或者反转整个链表
使用右递归而不是左递归的缺点是它把所有需要被归约的语句都放在语法分析器的堆栈里，直到链表的尾部才进行归约，而左递归在分析输入时每次遇到语句都会like将其添加到链表中。
左递归可以避免堆栈溢出并且容易调试
*/
list: /*空*/ { $$ = NULL;}
| stmt ';' list { if ($3 == NULL) {
printf("stmp;list:$3==NULL\n");
$$ = $1;
}
else {
printf("stmp;list:$3!=NULL\n");
$$ = newast('L', $1, $3);
}
}
;
/*计算器表达式的语法*/
exp: exp CMP exp { printf("exp CMP exp\n");$$ = newcmp($2, $1, $3);}
| exp '+' exp { $$ = newast('+', $1, $3);}
| exp '-' exp { $$ = newast('-', $1, $3);}
| exp '*' exp { $$ = newast('*', $1, $3);}
| exp '/' exp { $$ = newast('/', $1, $3);}
| '|' exp { $$ = newast('|', $2, NULL);}
|'(' exp ')' { $$ = $2;}
| '-' exp %prec UMINUS { $$ = newast('M', $2, NULL);}
| NUMBER { printf("number:%f\n",$1);$$ = newnum($1); }
| NAME { printf("exp|NAME:%s\n", $1->name);$$ = newref($1); }
| NAME '=' exp { printf("NAME = exp:%s\n", $1->name);$$ = newasgn($1, $3); }
| FUNC '(' explist ')' { $$ = newfunc($1, $3); }
| NAME '(' explist ')' { printf("newcall NAME=%s\n",$1->name);$$ = newcall($1, $3); }
;
explist: exp { printf("exp\n"); $$ = $1; }
| exp ',' explist { printf("exp,explist\n"); $$ = newast('L', $1, $3); }
;
/**规则explist定义了一个表达式列表，它创建这些表达式的抽象语法树来作为函数调用所需要的实际参数
规则symlist定义了一个符号列表，它创建了这些符号的链表用于函数定义时所需要的虚拟参数。他们都是右递归的，以方便基于期望的顺序创建链表*/
symlist: NAME { printf("symlist|name:%s\n", $1->name);$$ = newsymlist($1, NULL); }
| NAME ',' symlist { printf("symlist|name,symlist:%s\n", $1->name);$$ = newsymlist($1, $3);}
;
/**
计算器的顶层规则
像前面那样，顶层规则计算每条语句的抽象语法树，打印结果，然后释放抽象语法树。
当前，保存函数定义只是便于后续使用
*/
calclist: /*空*/
| calclist stmt EOL {
printf("= %4.4g\n>", eval($2));
treefree($2);
}
| calclist LET NAME '(' symlist ')' '=' list EOL {
dodef($3, $5, $8);
printf("Defined %s\n>", $3->name);
}
| calclist error EOL { yyerrok; printf("> "); }
;
/**
我们至少有可能在错误发生时把语法分析器恢复到可以继续工作的状态。在这里，特殊的伪记号error确定了错误恢复点。
当bison语法分析器遇到一个错误时，它开始从语法分析器堆栈里放弃各种语法符号，直到它到达一个记号error为有效的点；
接着它开始忽略后续输入记号，直到它找到一个在当前状态可以被移进的记号，然后从这一点开始继续分析。
为了避免大段误导性的错误信息，语法分析器通常在第一个错误产生后就抑制后续的分析错误消息，直到它能够成功的在一行里移进三个记号。
动作中的宏yyerrok告诉语法分析器恢复已经完成，这样后续的错误消息可以顺利产生。
*/
%%
void
yyerror(char *s, ...)
{
va_list ap;
va_start(ap, s);
fprintf(stderr, "%d: error: ", yylineno);
vfprintf(stderr, s, ap);
fprintf(stderr, "\n");
}
int
main(int argc, char **argv)
{
printf("> ");
return yyparse();
}
自定义函数实现
新建fb_3_2.funcs.c文件用来实现自定义函数，代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <math.h>
#include "fb_3_2.h"
/**符号表*/
/*哈希一个符号*/
static unsigned
symhash(char *sym)
{
unsigned int hash = 0;
unsigned c;
while (c = *sym++) {
hash = hash * 9 ^ c;
}
return hash;
}
struct symbol *
lookup(char *sym)
{
struct symbol *sp = &symtab[symhash(sym) % NHASH];
int scount = NHASH; /**需要查看的个数*/
printf("symbol find:%s\n", sym);
while (--scount >= 0) {
if (sp->name && ! strcmp(sp->name, sym)) {
return sp;
}
if (!sp->name) {/**新条目*/
sp->name = strdup(sym);
sp->value = 0;
sp->func = NULL;
sp->syms = NULL;
return sp;
}
if (++sp >= symtab + NHASH) {/**尝试下一个条目*/
sp = symtab;
}
}
yyerror("symbol table overflow\n");
abort();/**尝试完所有的条目，符号表已满*/
}
struct ast *
newast(int nodetype, struct ast *l, struct ast *r)
{
struct ast *a = malloc(sizeof(struct ast));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = nodetype;
a->l = l;
a->r = r;
return a;
}
struct ast *
newnum(double d)
{
struct numval *a = malloc(sizeof(struct numval));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = 'K';
a->number = d;
return (struct ast *)a;
}
struct ast *
newcmp(int cmptype, struct ast *l, struct ast *r)
{
struct ast *a = malloc(sizeof(struct ast));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = '0' + cmptype;
a->l = l;
a->r = r;
return a;
}
struct ast *
newfunc(int functype, struct ast *l)
{
struct fncall *a = malloc(sizeof(struct fncall));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = 'F';
a->l = l;
a->functype = functype;
return (struct ast*)a;
}
struct ast *
newcall(struct symbol *s, struct ast *l)
{
struct ufncall *a = malloc(sizeof(struct ufncall));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = 'C';
a->l = l;
a->s = s;
return (struct ast*)a;
}
struct ast *
newref(struct symbol *s)
{
struct symref *a = malloc(sizeof(struct symref));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = 'N';
a->s = s;
return (struct ast*)a;
}
struct ast *
newasgn(struct symbol *s, struct ast *v)
{
struct symasgn *a = malloc(sizeof(struct symasgn));
if (!a) {
printf("out of space");
exit(0);
}
a->nodetype = '=';
a->s = s;
a->v = v;
return (struct ast*)a;
}
struct ast *
newflow(int nodetype, struct ast *cond, struct ast *tl, struct ast *el)
{
struct flow *a = malloc(sizeof(struct flow));
if (!a) {
printf("out of space");
exit(0);
}
printf("begin newflow\n");
a->nodetype = nodetype;
a->cond = cond;
a->tl = tl;
a->el = el;
printf("end newflow\n");
return (struct ast*)a;
}
struct symlist *
newsymlist(struct symbol *sym, struct symlist *next)
{
struct symlist *a = malloc(sizeof(struct symlist));
if (!a) {
printf("out of space");
exit(0);
}
a->sym = sym;
a->next = next;
return a;
}
void
treefree(struct ast *a)
{
switch(a->nodetype) {
/**两颗子树*/
case '+':
case '-':
case '*':
case '/':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case 'L':
treefree(a->r);
/*一颗子树*/
case '|':
case 'M':
case 'C':
case 'F':
treefree(a->l);
/*没有子树*/
case 'K':
case 'N':
break;
case '=':
free( ((struct symasgn *)a)->v);
break;
case 'I':
case 'W':
free(((struct flow*)a)->cond);
if (((struct flow*)a)->tl) {
treefree(((struct flow*)a)->tl);
}
if (((struct flow*)a)->el) {
treefree(((struct flow*)a)->el);
}
break;
default: printf("internal error: bad node %c\n", a->nodetype);
}
free(a); /**总是释放节点自身*/
}
/**释放符号列表*/
void
symlistfree(struct symlist *sl)
{
struct symlist *nsl;
while (sl) {
nsl = sl->next;
free(sl);
sl = nsl;
}
}
/**计算器的核心是eval，它计算语法分析器中构造的抽象语法树。
* 基于C语言的准则，比较表达式根据比较是否成功来返回1或者0.
* 我们采用相似的深度优先的树遍历算法来计算表达式的值。
* 抽象语法树使if/then/else的实现变得直接：计算条件表达式的抽象语法树来决定选择哪个分支，然后计算选择路径上的抽象语法树。
* 对于do/while循环来说，eval中的一个循环会不断的计算条件表达式，然后执行语句体的抽象语法树，直到条件表达式的抽象语法树不再为真。
*
* 当变量被赋值语句修改后，任何使用这个变量的抽象语法树都会基于新值进行计算。
*/
static double callbuiltin(struct fncall *);
static double calluser(struct ufncall *);
double
eval(struct ast *a)
{
double v;
if (!a) {
yyerror("internal error, null eval");
return 0.0;
}
printf("nodetype:%c\n", a->nodetype);
switch(a->nodetype) {
case 'K': /*常量*/
v = ((struct numval *)a)->number;
break;
case 'N': /*名字引用*/
v = ((struct symref*)a)->s->value;
break;
case '=': /*名字引用*/
v = ((struct symasgn*)a)->s->value = eval(((struct symasgn*)a)->v);
break;
/**表达式*/
case '+':
v = eval(a->l) + eval(a->r);
break;
case '-':
v = eval(a->l) - eval(a->r);
break;
case '*':
v = eval(a->l) * eval(a->r);
break;
case '/':
v = eval(a->l) / eval(a->r);
break;
case '|':
v = fabs(eval(a->l));
break;
case 'M':
v = -eval(a->l);
break;
/**比较*/
case '1':
v = (eval(a->l) > eval(a->r)) ? 1 : 0;
break;
case '2':
v = (eval(a->l) < eval(a->r)) ? 1 : 0;
break;
case '3':
v = (eval(a->l) != eval(a->r)) ? 1 : 0;
break;
case '4':
v = (eval(a->l) == eval(a->r)) ? 1 : 0;
break;
case '5':
v = (eval(a->l) >= eval(a->r)) ? 1 : 0;
break;
case '6':
v = (eval(a->l) <= eval(a->r)) ? 1 : 0;
break;
/**控制流*/
/**语法中允许空表达式，所以需要检查这种可能性*/
/**if/then/else*/
case 'I':
if (eval(((struct flow*)a)->cond) != 0) {/**检查条件*/
if (((struct flow*)a)->tl) {/**条件成立分支*/
v = eval(((struct flow*)a)->tl);
} else {
v = 0.0; /*默认值*/
}
} else { /**条件不成立分支*/
if (((struct flow*)a)->el) {
v = eval(((struct flow*)a)->el);
} else {
v = 0.0; /*默认值*/
}
}
break;
/**while/do*/
case 'W':
v = 0.0; /*默认值*/
if (((struct flow*)a)->tl) {
while (eval(((struct flow*)a)->cond) != 0) { /**计算条件*/
v = eval(((struct flow *)a)->tl); /*执行目标语句体*/
}
}
break; /**最后一条语句的值就是while/do的值*/
/**语句列表*/
case 'L':
eval(a->l);
v = eval(a->r);
break;
case 'F':
v = callbuiltin((struct fncall*)a);
break;
case 'C':
printf("356->calluser\n");
v = calluser((struct ufncall*)a);
break;
default: printf("internal error: bad node %c\n", a->nodetype);
}
return v;
}
/**执行计算器中的函数*/
/*计算器中最特别的部分是处理函数。
* 内置函数的实现很简单：他们确定具体的函数，然后调用相应的代码来执行这个函数
*/
static double
callbuiltin(struct fncall *f)
{
enum bifs functype = f->functype;
double v = eval(f->l);
switch (functype) {
case B_sqrt:
return sqrt(v);
case B_exp:
return exp(v);
case B_log:
return log(v);
case B_print:
printf("= %4.4g\n", v);
return v;
default:
yyerror("Unknown built-in function %d", functype);
return 0.0;
}
}
/**用户自定义函数*/
/**函数定义包含函数名，虚拟参数列表，代表函数体的抽象语法树
* 当函数被定义时，参数列表和抽象语法树将被简单地保存到符号表中函数名对应的条目中，同时替换了任何可能的旧版本。
*
*/
void
dodef(struct symbol *name, struct symlist *syms, struct ast *func)
{
printf("begin dodef\n");
if (name->syms) {
symlistfree(name->syms);
}
if (name->func) {
treefree(name->func);
}
name->syms = syms;
name->func = func;
printf("end dodef\n");
}
/**
* 比如你定义一个函数来计算两个参数中的最大值
* lex max（x,y) = if x >= y then x; else y;;
* max(4+5, 6+7)
*
* 这个函数有两个虚拟参数，x和y，当函数被调用时，求值程序将如下执行：
* 1. 计算实际参数值，这个例子中就是4+5, 6+7
* 2. 保存虚拟参数的当前值，然后把实际参数值赋值给它们
* 3. 执行函数体，在涉及到虚拟参数的地方都使用实际参数值
* 4. 将虚拟参数恢复原值
* 5. 返回函数体表达式的值
* */
static double
calluser(struct ufncall *f)
{
struct symbol *fn = f->s; /*函数名*/
struct symlist *sl; /*虚拟参数*/
struct ast *args = f->l; /*实际参数*/
double *oldval, *newval; /*保存的参数值*/
double v;
int nargs;
int i;
if (!fn->func) {
yyerror("call to undefined function:", fn->name);
return 0;
}
printf("call to function:%s\n", fn->name);
/**计算参数个数*/
sl = fn->syms;
for (nargs = 0; sl; sl = sl->next) {
nargs++;
}
printf("function args:%d\n", nargs);
/**为保存参数值做准备*/
oldval = (double *)malloc(nargs * sizeof(double));
newval = (double *)malloc(nargs * sizeof(double));
if (!oldval || !newval) {
yyerror("out of space in %s", fn->name);
return 0.0;
}
/*计算参数值**/
for (i = 0; i < nargs; i++) {
if (!args) {
yyerror("too few args in call to %s", fn->name);
free(oldval);
free(newval);
return 0.0;
}
if (args->nodetype == 'L') {/*是否是节点列表*/
newval[i] = eval(args->l);
args = args->r;
} else { /*是否是列表末尾*/
newval[i] = eval(args);
args = NULL;
}
}
/*保存虚拟参数的旧值，赋予新值*/
sl = fn->syms;
for (i = 0; i < nargs; i++) {
struct symbol *s = sl->sym;
oldval[i] = s->value;
s->value = newval[i];
sl = sl->next;
}
free(newval);
/**计算函数*/
v = eval(fn->func);
/*恢复虚拟参数的值*/
sl = fn->syms;
for (i = 0; i < nargs; i++) {
struct symbol *s = sl->sym;
s->value = oldval[i];
sl = sl->next;
}
free(oldval);
return v;
}
Makefile文件编写
定义Makefile文件来指定编译规则
fb_3_2: fb_3_2.l fb_3_2.y fb_3_2.h
bison -d fb_3_2.y
flex -o fb_3_2.lex.c fb_3_2.l
gcc -o $@ fb_3_2.tab.c fb_3_2.lex.c fb_3_2.funcs.c -lm -g
clean:
rm -rf fb_3_2.lex.c fb_3_2 fb_3_2.tab.c fb_3_2.tab.h core.*
编译测试
% make
bison -d fb_3_2.y
flex -o fb_3_2.lex.c fb_3_2.l
gcc -o fb_3_2 fb_3_2.tab.c fb_3_2.lex.c fb_3_2.funcs.c -lm -g
fb_3_2.funcs.c:20:14: warning: using the result of an assignment as a condition without parentheses [-Wparentheses]
while (c = *sym++) {
~~^~~~~~~~
fb_3_2.funcs.c:20:14: note: place parentheses around the assignment to silence this warning
while (c = *sym++) {
^
( )
fb_3_2.funcs.c:20:14: note: use '==' to turn this assignment into an equality comparison
while (c = *sym++) {
^
==
1 warning generated.
% ./fb_3_2
> let max(x,y) = if x > y then x; else y;;
symbol find:max
symbol find:x
symbol find:y
symlist|name:y
symlist|name,symlist:x
symbol find:x
exp|NAME:x
symbol find:y
exp|NAME:y
exp CMP exp
symbol find:x
exp|NAME:x
stmt:exp:
stmp;list:$3==NULL
symbol find:y
exp|NAME:y
stmt:exp:
stmp;list:$3==NULL
if exp then list else list
begin newflow
end newflow
stmp;list:$3==NULL
begin dodef
end dodef
Defined max
>max(15,3)
symbol find:max
number:15.000000
number:3.000000
exp
exp,explist
newcall NAME=max
stmt:exp:
nodetype:C
356->calluser
call to function:max
function args:2
nodetype:K
nodetype:K
nodetype:I
nodetype:1
nodetype:N
nodetype:N
nodetype:N
= 15
测试说明
针对上述函数定义 > let max(x,y) = if x > y then x; else y;; 编译器工作流程如下：
移进 let -> token是LET
移进 max -> 先去符号表查找，没有的话新建。token是NAME 此时 是 ``LET NAME``
移进 (
移进 x，
移进 y，即 ``LET NAME(NAME,NAME``发生归约，首先y符合``symlist:NAME`` 归约为 LET NAME(NAME,symlist)，接着符合``symlist| NAME ',' symlist`` 归约为 ``LET NAME(symlist``
移进 ), 即: LET NAME(symlist)
移进 =, 即: LET NAME(symlist) =
移进 if, token是IF 即: LET NAME(symlist) = IF
移进 x，符合 ``exp | NAME`` 发生动作newref 归约为 LET NAME(symlist) = IF exp
移进 >，token是CMP,即 LET NAME(symlist) = IF exp CMP
移进 y, 符合 ``exp | NAME ``发生动作newref ，即 LET NAME(symlist) = IF exp CMP exp，符合``exp|exp CMP exp``归约为 LET NAME(symlist) = IF exp
移进 then, 即 LET NAME(symlist) = IF exp THEN
移进 x, 符合``exp|NAME``归约为exp，又符合``stmt|exp``归约为stmt 即 LET NAME(symlist) = IF exp THEN stmt
移进 ;, 符合``list|stmp ';' list`` 归约为LET NAME(symlist) = IF exp THEN list
移进 else，token是ELSE，即 LET NAME(symlist) = IF exp THEN list ELSE
移进 y, 符合``exp|NAME``归约为exp，又符合``stmt|exp``归约为stmt 即 LET NAME(symlist) = IF exp THEN list ELSE stmt
移进 ;, 符合``list|stmt ';' list`` 归约为LET NAME(symlist) = IF exp THEN list ELSE list，符合 ``stmt|IF exp THEN list ELSE list``,归约为 LET NAME(symlist) = stmt
移进 ;, 符合 ``list|stmt ';' list`` 归约为 LET NAME(symlist) = list，符合``calclist|calclist LET NAME(symlist) = list ，执行动作dodef
此时在符号表中，max的struct symbol结构体中已经有了其虚拟参数和函数体。其中函数体的cond是一个ast。
有兴趣的同学，可去我的github下载全部代码。
网友评论