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 %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 %
赞 (0)

相关推荐

  • C指针原理教程之编译原理-小型计算器实现

    1.打开cygwin,进入home目录,home目录在WINDOWS系统的cygwin安装目录映射为home目录. 2.首先,在home目录中新建文件夹,在文件夹中放置如下内容的test1.l /*统计字数*/ %{ int chars=0; int words=0; int lines=0; %} %% [a-zA-Z]+ {words++;chars+=strlen(yytext);} \n {chars++;lines++;} . {chars++;} %% main(int argc,c

  • C指针原理教程之C指针基础

    tcctok.h定义了C语言的词法分析的基本元素,主要定义了关键字. / keywords /      DEF(TOK_INT, "int")      DEF(TOK_VOID, "void")      DEF(TOK_CHAR, "char")      DEF(TOK_IF, "if")      DEF(TOK_ELSE, "else")      DEF(TOK_WHILE, "wh

  • C指针原理教程之C内嵌汇编

    内联汇编的重要性体现在它能够灵活操作,而且可以使其输出通过 C 变量显示出来.因为它具有这种能力,所以 "asm" 可以用作汇编指令和包含它的 C 程序之间的接口.简单得说,内联汇编,就是可以让程序员在C语言中直接嵌入汇编代码,并与汇编代码交互C程序中的C表达式,享受汇编的高运行效率. 内联汇编的格式是直接在C代码中插入以下格式: asm( .... .... ) 其中的"..."为汇编代码,比如下面例子中,在 result=a*b和printf("%d\

  • C指针原理教程之Ncurses介绍

    1.安装Ncurses Ncurses是一个能提供功能键定义(快捷键),屏幕绘制以及基于文本终端的图形互动功能的动态库. Ncurses是一个能提供基于文本终端窗口功能的动态库. Ncurses可以: · 只要您喜欢,您可以使用整个屏幕 · 创建和管理一个窗口 · 使用8种不同的彩色 · 为您的程序提供鼠标支持 · 使用键盘上的功能键 Ubuntu下 mysea@mysea-desktop:~$ sudo apt-get install libncurses5-dbg libncurses5-d

  • C指针原理教程之垃圾回收-内存泄露

    一.内存泄露 1.正常的链表操作 下面程序建立一个10元素的链表,输出它们的节点,每个节点是一个员工的工号和年龄.最后删除每个节点,释放列表. dp@dp:~/memorytest % cat 1.c #include <stdlib.h> #include <stdio.h> //code:myhaspl@myhaspl.com //author:myhaspl //date:2014-01-10 typedef struct listnode mynode; struct li

  • C指针原理教程之AT&T汇编

    汇编在LINUX系统下的意义远远大于WINDOWS系统,LINUX内核部分代码就是汇编编写的.然后,绝大多数 Linux 程序员以前只接触过DOS/Windows 下的汇编语言,这些汇编代码都是 Intel 风格的.但在 Unix 和 Linux 系统中,更多采用的还是 AT&T 格式,两者在语法格式上有着很大的不同,因此应对AT&T汇编应有一个基本的了解和熟悉. 我们在LINUX下用C编写一段最简单的helloworld程序,命令为hello.c #include <stdio.h

  • C指针原理教程之C快速入门

    一.C简介 1.C语言简介 C语言是一门语法 精简的语言,它的关键字仅有32个,C语言以main函数为主函数,程序编译运行后后,执行的就是main函数的内容,因此,纵观很多C语言程序,形成了一道有趣的风景线:头文件和许多c代码文件以main函数为中心和起始点构造,在main函数中调用了这些文件中编写的代码,引用头文件.C语言程序实质就是在程序中调用 C标准库提供的函数.其它C库提供的函数.操作系统提供的API接口.自己定义的函数,同时应用适当的数据结构和算法来完成工作. C语言虽然精简,但却很强

  • C指针原理教程之语法树及其实现

    下面完成一个简单的计算器通过语法树进行计算,首先定义一个语法树的结构,然后编写flex文件,解析数字或符号,对于 符号返回本身,对于数字,返回NUMBER,并对yylval的d进行赋值,yylval指向一个联合类型,接着,在语法分析器中完成语法树的节点的增加,分别对应数字和符号有不同的增加方式,最后有一个单独的C代码处理计算,以及语法树相关计算的函数.对结果的计算的方式是对语法树进行递归. 词法分析器为: dp@dp:~/flexbison % cat myast.l %option noyyw

  • python语言开发垃圾回收机制原理教程

    python语言开发垃圾回收机制原理教程

    目录 一.什么是垃圾回收机制 二.为什么要有垃圾回收机制 三.垃圾回收机制的原理 1.引用计数 直接引用 间接引用 2.栈区 / 堆区 3.总结 四.标记清除 1.循环引用问题(也叫交叉引用) 2.循环引用导致的结果 3.解决方法 : 清除-标记 五.分代回收 1.效率问题 2.解决方法 : 分代回收 分代 回收 总结 一.什么是垃圾回收机制 垃圾回收机制(简称GC), 解释器自带的一种机制 它是一种动态存储管理技术,自动释放不再被程序引用的对象所占用的内存空间 二.为什么要有垃圾回收机制 程序

  • go reflect要不要传指针原理详解

    目录 正文 什么时候传递指针? 1. 通过传递指针修改变量的值 传值无法修改变量本身 传指针可以修改变量 2. 通过传递指针修改结构体的字段 3. 结构体:获取指针接收值方法 4. 变量本身包含指向数据的指针 通过值反射对象修改 chan.map 和 slice slice 反射对象扩容的影响 slice 容量够的话是不是就可以正常追加元素了? map 也不能通过值反射对象来修改其元素. chan 没有追加 结构体字段包含指针的情况 5. interface 类型处理 interface 底层类

  • C语言入门之指针用法教程

    本文针对C语言初学者详细讲述了指针的用法,并配以实例进行说明.具体分析如下: 对于C语言初学者来说,需要明白指针是啥?重点就在一个"指"上.指啥?指的地址.啥地址?内存的地址. 上面说明就是指针的本质了. 这里再详细解释下.数据存起来是要存在内存里面的,就是在内存里圈出一块地,在这块地里放想放的东西.变量关心的是这块地里放的东西,并不关心它在内存的哪里圈的地:而指针则关心这块地在内存的哪个地方,并不关心这块地多大,里面存了什么东西. 指针怎么用呢?下面就是基本用法: int a, b,

  • 简明的C++函数指针学习教程

    定义 每一个函数都占用一段内存单元,它们有一个起始地址,指向函数入口地址的指针称为函数指针. 语法 数据类型 (*指针变量名)(参数表): int (*myFunc)(double b, int c); 说明 函数指针的定义形式中的数据类型是指函数的返回值的类型. 区分下面两个语句: int (*p)(int a, int b);//p是一个指向函数的指针变量,所指函数的返回值类型为整型 int *p(int a, int b);//p是函数名,此函数的返回值类型为整型指针 指向函数的指针变量不

  • Go语言快速入门指针Map使用示例教程

    目录 1. 指针 1.1 指针地址和指针类型 1.2 指针取值 1.3 空指针 1.4 new 的使用 1.5 new与make的区别 2. Map 2.1 什么是Map key,value存储 hash冲突 hash冲突的常见解决方法 开放定址(线性探测)和拉链的优缺点 2.2 Map 定义 2.3 map基本使用 2.4 map的遍历 2.5 map判断某个键是否存在 2.6 map使用delete()函数删除键值对 1. 指针 区别于C/C++中的指针,Go语言中的指针不能进行偏移和运算,

  • 一文理解Android系统中强指针的实现

    强指针和弱指针基础 android中的智能指针包括:轻量级指针.强指针.弱指针. 强指针:它主要是通过强引用计数来进行维护对象的生命周期. 弱指针:它主要是通过弱引用计数来进行维护所指向对象的生命周期. 如果在一个类中使用了强指针或者弱指针的技术,那么这个类就必须从RefBase这个类进行做继承,因为强指针和弱指针是通过RefBase这个类来提供实现的引用计数器. 强指针和弱指针关系相对于轻量级指针来说更加亲密,因此他们一般是相互配合使用的. 强指针原理分析 以下针对源码的分析都是来源于andr

  • 深入分析golang多值返回以及闭包的实现

    一.前言 golang有很多新颖的特性,不知道大家的使用的时候,有没想过,这些特性是如何实现的?当然你可能会说,不了解这些特性好像也不影响自己使用golang,你说的也有道理,但是,多了解底层的实现原理,对于在使用golang时的眼界是完全不一样的,就类似于看过http的实现之后,再来使用http框架,和未看过http框架时的眼界是不一样的,当然,你如果是一名it爱好者,求知欲自然会引导你去学习. 二.这篇文章主要就分析两点:      1.golang多值返回的实现;      2.golan

随机推荐