C指针原理教程之语法树及其实现
下面完成一个简单的计算器通过语法树进行计算，首先定义一个语法树的结构，然后编写flex文件，解析数字或符号，对于 符号返回本身，对于数字，返回NUMBER，并对yylval的d进行赋值，yylval指向一个联合类型，接着，在语法分析器中完成语法树的节点的增加，分别对应数字和符号有不同的增加方式，最后有一个单独的C代码处理计算，以及语法树相关计算的函数。对结果的计算的方式是对语法树进行递归。
成都创新互联公司专注为客户提供全方位的互联网综合服务，包含不限于网站制作、成都网站制作、仙游网络推广、小程序制作、仙游网络营销、仙游企业策划、仙游品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；成都创新互联公司为所有大学生创业者提供仙游建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com
词法分析器为：
dp@dp:~/flexbison % cat myast.l
%option noyywrap nodefault yylineno
%{
#include "myast.h"
#include "myast.tab.h"
char buffer[20];
%}
EXP ([Ee][-+]?[0-9]+)
%%
"+"|"-"|"*"|"/"|"("|")"|"|" {
return yytext[0];
}
[0-9]+"."[0-9]*{EXP}?|"."?[0-9]+{EXP}? {
yylval.d=atof(yytext);
return NUMBER;
}
\n {return EOL;}
"//".*
[ \t] {}
"Q" {exit(0);}
. {sprintf(buffer,"invalid character %c\n",*yytext); yyerror(buffer);}
%%
语法分析器为：
dp@dp:~/flexbison % cat myast.y
%{
#include
#include
#include "myast.h"
%}
%union{
struct myast *mya;
double d;
}
%token NUMBER
%token EOL
%type exp factor term
%%
calclist:|calclist exp EOL{
printf("= %g\n",eval($2));
treefree($2);
printf("$");
}
|calclist EOL{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 % cat myast.h
extern int yylineno;
void yyerror(char *s);
struct ast{
int nodetype;
struct ast *l;
struct ast *r;
};
struct numval{
int nodetype;
double number;
};
struct ast *newast(int nodetype,struct ast *l,struct ast *r);
struct ast *newnum(double d);
double eval(struct ast *);
void treefree(struct ast *);
C代码文件的内容为：
dp@dp:~/flexbison % cat myastfunc.c #include#include #include #include "myast.h" struct ast * newast(int nodetype,struct ast *l,struct ast *r) { struct ast *a=malloc(sizeof(struct ast)); if (!a){ yyerror("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) { yyerror("out of space"); exit(0); } a->nodetype='D'; a->number=d; return (struct ast *)a; } double eval(struct ast *a){ double v; switch(a->nodetype){ case 'D':v=((struct numval *)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("bad node:%c\n",a->nodetype); } return v; } void treefree(struct ast*a) { switch(a->nodetype){ case '+': case '-': case '*': case '/': treefree(a->r); case '|': case 'M': treefree(a->l); case 'D': free(a); break; default:printf("free bad node %c\n",a->nodetype); } } void yyerror(char *s){ fprintf(stderr,"line %d error!:%s",yylineno,s); } int main() { printf("$ "); return yyparse(); }
Makefile文件为:
dp@dp:~/flexbison % cat makefile myjs:myast.l myast.y myast.h bison -d myast.y flex -omyast.lex.c myast.l cc -o $@ myast.tab.c myast.lex.c myastfunc.c dp@dp:~/flexbison %
运行效果如下
dp@dp:~/flexbison % ./myjs $ 12+99 = 111 $11*(9-3)+6/3 = 68 $Q dp@dp:~/flexbison %
名称栏目：C指针原理教程之语法树及其实现
文章位置：http://scyanting.com/article/jggsij.html
