C指针原理教程之语法树及其实现

下面完成一个简单的计算器通过语法树进行计算，首先定义一个语法树的结构，然后编写flex文件，解析数字或符号，对于 符号返回本身，对于数字，返回NUMBER，并对yylval的d进行赋值，yylval指向一个联合类型，接着，在语法分析器中完成语法树的节点的增加，分别对应数字和符号有不同的增加方式，最后有一个单独的C代码处理计算，以及语法树相关计算的函数。对结果的计算的方式是对语法树进行递归。

词法分析器为：

 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 <stdio.h> #include <stdlib.h> #include "myast.h" %} %union{ struct myast *mya; double d; } %token <d> NUMBER %token EOL %type <mya> 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 <stdio.h> #include <stdlib.h> #include <stdarg.h> #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指针原理教程之Ncurses介绍
• C指针原理教程之垃圾回收-内存泄露
• C指针原理教程之C指针基础
• C指针原理教程之编译原理-小型计算器实现
• C指针原理教程之C内嵌汇编
• C指针原理教程之AT&T汇编
• C指针原理教程之C快速入门