C指针教程中，如何构建语法树并实现其功能？

本文共计1025个文字，预计阅读时间需要5分钟。

下面完成了一个简单的计算器，通过语法树进行计算，定义了一个语法树的结构，并编写了flex文件来解析数字或符号，对符号返回自身，对数字返回NUMBER，并对yylval的d进行赋值。

c#include #include

typedef struct Node { int type; int d; struct Node *left; struct Node *right;} Node;

Node* createNode(int type, int d) { Node *node=(Node*)malloc(sizeof(Node)); node->type=type; node->d=d; node->left=NULL; node->right=NULL; return node;}

Node* parseExpression();

int main() { Node *root=parseExpression(); printf(Result: %d\n, root->d); free(root); return 0;}

Node* parseExpression() { Node *node=parseTerm(); while (yylval.d=='+') { node=createNode('+', node->d + yylval.d); node->right=parseTerm(); yylval.d='+'; } return node;}

Node* parseTerm() { Node *node=parseFactor(); while (yylval.d=='-') { node=createNode('-', node->d + yylval.d); node->right=parseFactor(); yylval.d='-'; } return node;}

Node* parseFactor() { if (yylval.d=='+') { yylex(); return parseFactor(); } if (yylval.d=='-') { yylex(); Node *node=createNode('-', 0); node->left=parseFactor(); return node; } if (yylval.d >='0' && yylval.d <='9') { Node *node=createNode(NUMBER, yylval.d - '0'); yylex(); return node; } printf(Invalid input.\n); exit(1);}

int main() { while (1) { printf(Enter an expression: ); yylex(); if (yylval.d==EOF) { break; } Node *root=parseExpression(); printf(Result: %d\n, root->d); free(root); } return 0;}

flex%{#include calc.tab.h%}%%[ \t]+ ;[+]+ { return '+'; }[-]+ { return '-'; }[0-9]+ { yylval.d=atoi(yytext); return NUMBER; }. { printf(Invalid input: %s\n, yytext); exit(1); }%%

int main() { yylex(); while (yyin !=NULL) { switch (yylex()) { case EOF: break; default: printf(Unexpected token: %d\n, yylval.d); break; } } return 0;}

下面完成一个简单的计算器通过语法树进行计算，首先定义一个语法树的结构，然后编写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 %