C指針原理教程之語法樹及其實現(xiàn)
更新時間：2019年02月07日 11:49:58 投稿：hebedich
本文給大家分享的是如何使用C語言的指針原來來實現(xiàn)語法樹，并給大家提供了詳細(xì)的實例代碼，希望大家能夠喜歡
下面完成一個簡單的計算器通過語法樹進行計算，首先定義一個語法樹的結(jié)構(gòu)，然后編寫flex文件，解析數(shù)字或符號，對于 符號返回本身，對于數(shù)字，返回NUMBER，并對yylval的d進行賦值，yylval指向一個聯(lián)合類型，接著，在語法分析器中完成語法樹的節(jié)點的增加，分別對應(yīng)數(shù)字和符號有不同的增加方式，最后有一個單獨的C代碼處理計算，以及語法樹相關(guān)計算的函數(shù)。對結(jié)果的計算的方式是對語法樹進行遞歸。
詞法分析器為：
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);}
%%
語法分析器為：
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 %
運行效果如下
dp@dp:~/flexbison % ./myjs $ 12+99 = 111 $11*(9-3)+6/3 = 68 $Q dp@dp:~/flexbison %
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了Qt簡單實現(xiàn)密碼器控件，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
C語言詳解鏈?zhǔn)疥犃信c循環(huán)隊列的實現(xiàn)
隊列（Queue）與棧一樣，是一種線性存儲結(jié)構(gòu)，它具有如下特點：隊列中的數(shù)據(jù)元素遵循“先進先出”（First In First Out）的原則，簡稱FIFO結(jié)構(gòu)。在隊尾添加元素，在隊頭刪除元素，本篇來講解鏈?zhǔn)疥犃信c循環(huán)隊列的實現(xiàn)2022-04-04
這篇文章主要介紹了MFC中Radio Button的用法,需要的朋友可以參考下2014-07-07
C++中關(guān)于Crt的內(nèi)存泄漏檢測的分析介紹
本篇文章介紹了，在C++中關(guān)于Crt的內(nèi)存泄漏檢測的分析說明。需要的朋友參考下2013-04-04
在c++Template中很多地方都用到了typename與class這兩個關(guān)鍵字，而且好像可以替換，是不是這兩個關(guān)鍵字完全一樣呢?下面這篇文章主要給大家介紹了關(guān)于c++模板中class與typename的相關(guān)資料，需要的朋友可以參考下。2017-07-07
這篇文章主要介紹了C++?NFS掛載,文中給大家提到了掛載NFS時常用的命令，本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-12-12
下面小編就為大家?guī)硪黄猚++ 快速排序算法【過程圖解】。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
這篇文章主要介紹了c++ 讓程序開機自動啟動的方法,需要的朋友可以參考下2017-09-09
C語言數(shù)據(jù)結(jié)構(gòu)之學(xué)生信息管理系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細(xì)介紹了C語言數(shù)據(jù)結(jié)構(gòu)之學(xué)生信息管理系統(tǒng)課程設(shè)計，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-11-11
這篇文章主要介紹了C語言使用libZPlay錄制聲音并寫到文件的方法,實例分析了C語言操作音頻文件的相關(guān)技巧,需要的朋友可以參考下2015-06-06