C指針原理教程之語(yǔ)法樹及其實(shí)現(xiàn)

來(lái)源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語(yǔ)言|點(diǎn)擊：次

下面完成一個(gè)簡(jiǎn)單的計(jì)算器通過(guò)語(yǔ)法樹進(jìn)行計(jì)算，首先定義一個(gè)語(yǔ)法樹的結(jié)構(gòu)，然后編寫flex文件，解析數(shù)字或符號(hào)，對(duì)于符號(hào)返回本身，對(duì)于數(shù)字，返回NUMBER，并對(duì)yylval的d進(jìn)行賦值，yylval指向一個(gè)聯(lián)合類型，接著，在語(yǔ)法分析器中完成語(yǔ)法樹的節(jié)點(diǎn)的增加，分別對(duì)應(yīng)數(shù)字和符號(hào)有不同的增加方式，最后有一個(gè)單獨(dú)的C代碼處理計(jì)算，以及語(yǔ)法樹相關(guān)計(jì)算的函數(shù)。對(duì)結(jié)果的計(jì)算的方式是對(duì)語(yǔ)法樹進(jìn)行遞歸。

詞法分析器為：

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;}
"http://".*
[ \t] {}
"Q" {exit(0);}
. {sprintf(buffer,"invalid character %c\n",*yytext); yyerror(buffer);} 
%%

語(yǔ)法分析器為：

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代碼文件的內(nèi)容為：

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 %

運(yùn)行效果如下

dp@dp:~/flexbison % ./myjs
$ 12+99
= 111
$11*(9-3)+6/3
= 68
$Q
dp@dp:~/flexbison %

上一篇：C++類中的特殊成員函數(shù)示例詳解

欄目：C語(yǔ)言

下一篇：單鏈表實(shí)現(xiàn)反轉(zhuǎn)的3種方法示例代碼

本文標(biāo)題：C指針原理教程之語(yǔ)法樹及其實(shí)現(xiàn)

本文地址：http://www.jygsgssxh.com/a1/Cyuyan/461.html

更多C語(yǔ)言

雷火电竞-中国电竞赛事及体育赛事平台

C語(yǔ)言

C指針原理教程之語(yǔ)法樹及其實(shí)現(xiàn)

您可能感興趣的文章

閱讀排行

本欄相關(guān)

隨機(jī)閱讀