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)文章
本文主要介紹C語言 以字符形式讀寫文件,這里整理了讀寫文件的一些資料并附示例代碼，供大家學(xué)習(xí)參考，有需要的小伙伴可以參考下2016-08-08
C++?17?引入了std::optional，表示一個可能有值的對象，這篇文章主要來和大家聊聊std::optional的使用，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下2023-06-06
常成員函數(shù)可以訪問常對象中的數(shù)據(jù)成員，但仍然不允許修改常對象中數(shù)據(jù)成員的值。有時在編程時有要求，一定要修改常對象成員中的某個數(shù)據(jù)成員的值（例如類中有一個用于計數(shù)的變量count，其值應(yīng)當(dāng)不能變化）2013-10-10
C語言中feof函數(shù)和ferror函數(shù)示例詳解
在C語言中feof函數(shù)用于檢查文件流的結(jié)束標(biāo)志,判斷文件在讀取時是否已經(jīng)到達了文件的末尾,這篇文章主要給大家介紹了關(guān)于C語言中feof函數(shù)和ferror函數(shù)的相關(guān)資料,需要的朋友可以參考下2024-09-09
本篇文章是對如何尋找數(shù)組中的第二大數(shù)進行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
HDOJ 1443 約瑟夫環(huán)的最新應(yīng)用分析詳解
本篇文章是對HDOJ 1443 約瑟夫環(huán)的最新應(yīng)用進行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
大家好，本篇文章主要講的是C語言中浮點數(shù)的精度丟失問題解決，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
C語言 詳細(xì)分析結(jié)構(gòu)體的內(nèi)存對齊
C 數(shù)組允許定義可存儲相同類型數(shù)據(jù)項的變量，結(jié)構(gòu)是 C 編程中另一種用戶自定義的可用的數(shù)據(jù)類型，它允許你存儲不同類型的數(shù)據(jù)項，本篇讓我們來了解C 的結(jié)構(gòu)體內(nèi)存對齊2022-03-03
模板是C++最重要的設(shè)計。這篇文章講的是函數(shù)模板,只是簡單介紹模板的一些功能,關(guān)于模板的更多的內(nèi)容會在類模板中詳細(xì)介紹。文章還著重介紹了重載解析過程2022-08-08
數(shù)組是一組有序的數(shù)據(jù)的集合，數(shù)組中元素類型相同，由數(shù)組名和下標(biāo)唯一地確定，數(shù)組中數(shù)據(jù)不僅數(shù)據(jù)類型相同，而且在計算機內(nèi)存里連續(xù)存放，地址編號最低的存儲單元存放數(shù)組的起始元素，地址編號最高的存儲單元存放數(shù)組的最后一個元素2022-04-04