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 %cn",*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("= %gn",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:%cn",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 %cn",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指针原理教程之语法树及其实现分享！全部内容且更多的C语言教程关注<计算机技术网(www.ctvol.com)!!>