C指针原理教程之语法树及其实现
下面完成一个简单的计算器通过语法树进行计算，首先定义一个语法树的结构，然后编写flex文件，解析数字或符号，对于符号返回本身，对于数字，返回NUMBER，并对yylval的d进行赋值，yylval指向一个联合类型，接着，在语法分析器中完成语法树的节点的增加，分别对应数字和符号有不同的增加方式，最后有一个单独的C代码处理计算，以及语法树相关计算的函数。对结果的计算的方式是对语法树进行递归。
词法分析器为：
dp@dp:~/flexbison%catmyast.l
%optionnoyywrapnodefaultyylineno
%{
#include"myast.h"
#include"myast.tab.h"
charbuffer[20];
%}
EXP([Ee][-+]?[0-9]+)
%%
"+"|"-"|"*"|"/"|"("|")"|"|"{
returnyytext[0];
}
[0-9]+"."[0-9]*{EXP}?|"."?[0-9]+{EXP}?{
yylval.d=atof(yytext);
returnNUMBER;
}
\n{returnEOL;}
"//".*
[\t]{}
"Q"{exit(0);}
.{sprintf(buffer,"invalidcharacter%c\n",*yytext);yyerror(buffer);}
%%
语法分析器为：
dp@dp:~/flexbison%catmyast.y
%{
#include
#include
#include"myast.h"
%}
%union{
structmyast*mya;
doubled;
}
%tokenNUMBER
%tokenEOL
%typeexpfactorterm
%%
calclist:|calclistexpEOL{
printf("=%g\n",eval($2));
treefree($2);
printf("$");
}
|calclistEOL{printf("$");}
;
exp:factor|exp'+'factor{$$=newast('+',$1,$3);}
|exp'-'factor{$$=newast('-',$1,$3);}
;
factor:term
|factor'*'term{$$=newast('*',$1,$3);}
|factor'/'term{$$=newast('/',$1,$3);}
;
term:NUMBER{$$=newnum($1);}
|'|'term{$$=newast('|',$2,NULL);}
|'('exp')'{$$=$2;}
|'-'term{$$=newast('M',$2,NULL);}
;
%%
然后头文件为：
dp@dp:~/flexbison%catmyast.h
externintyylineno;
voidyyerror(char*s);
structast{
intnodetype;
structast*l;
structast*r;
};
structnumval{
intnodetype;
doublenumber;
};
structast*newast(intnodetype,structast*l,structast*r);
structast*newnum(doubled);
doubleeval(structast*);
voidtreefree(structast*);
C代码文件的内容为：
dp@dp:~/flexbison%catmyastfunc.c #include#include #include #include"myast.h" structast*newast(intnodetype,structast*l,structast*r) { structast*a=malloc(sizeof(structast)); if(!a){ yyerror("outofspace"); exit(0); } a->nodetype=nodetype; a->l=l; a->r=r; returna; } structast*newnum(doubled) { structnumval*a=malloc(sizeof(structnumval)); if(!a) { yyerror("outofspace"); exit(0); } a->nodetype='D'; a->number=d; return(structast*)a; } doubleeval(structast*a){ doublev; switch(a->nodetype){ case'D':v=((structnumval*)a)->number;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=eval(a->l);v=v<0?v:-v;break; case'M':v=-eval(a->l);break; defaut:printf("badnode:%c\n",a->nodetype); } returnv; } voidtreefree(structast*a) { switch(a->nodetype){ case'+': case'-': case'*': case'/': treefree(a->r); case'|': case'M': treefree(a->l); case'D': free(a); break; default:printf("freebadnode%c\n",a->nodetype); } } voidyyerror(char*s){ fprintf(stderr,"line%derror!:%s",yylineno,s); } intmain() { printf("$"); returnyyparse(); }
Makefile文件为:
dp@dp:~/flexbison%catmakefile myjs:myast.lmyast.ymyast.h bison-dmyast.y flex-omyast.lex.cmyast.l cc-o$@myast.tab.cmyast.lex.cmyastfunc.c dp@dp:~/flexbison%
运行效果如下
dp@dp:~/flexbison%./myjs $12+99 =111 $11*(9-3)+6/3 =68 $Q dp@dp:~/flexbison%