C指针原理教程之语法树及其实现
更新时间:2020年4月25日 17:26 点击:2003
下面完成一个简单的计算器通过语法树进行计算,首先定义一个语法树的结构,然后编写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语言数组a和&a的区别讲解
下一篇: C语言实现词法分析器
相关文章
- 本文给大家分享的是如何使用C语言编写一个小型计算器的实例代码,有需要的小伙伴可以参考下...2020-04-25
- 本文给大家分享的是如何使用C语言的指针原来来实现语法树,并给大家提供了详细的实例代码,希望大家能够喜欢...2020-04-25
- 指针是一个特殊的变量,它里面存储的数值被解释成为内存里的一个地址。要搞清一个指针需要搞清指针的四方面的内容:指针的类型、指针所指向的类型、指针的值或者叫指针所指向的内存区、指针本身所占据的内存区。...2020-04-25
- C语言作为大学编程或者计算机专业的一门必修课,把很多初学编程的小伙伴都难住了,感觉无从下手,今天呢,我们来简单介绍下,如何快速入门C语言...2020-04-25
- C语言没有运行时库,无法自动压缩使用中的内存,缩小堆栈所需内存空间。若只申请内存,没有释放,势必造成系统内存不断减少、丢失。长时间的运行,最终导致系统死机。文章阐述了C语言垃圾产生的原因,并从引用计数、标记一清除算法两方面提出如何实现C语言的垃圾回收。...2020-04-25
- 在学习 C 语言内嵌汇编的实验过程中,发现内嵌汇编极容易造成段错误。...2020-04-25
- Ncurses 提供字符终端处理库,包括面板和菜单。为了能够使用ncurses库,您必须在您的源程序中将curses.h包括(include)进来,而且在编译的需要与它连接起来. 在gcc中您可以使用参数-lcurses进行编译....2020-04-25