




已阅读5页,还剩16页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
。课程设计3 基于Flex/Bison的高级解释器设计及实现3.1 需求分析3.1.1 问题定义1. 使用flex和bison开发了一个具有全部功能的桌面计算器,能够支持变量,过程,循环和条件表达式,使它成为一个虽然短小但是具有现实意义的编译器。2. 重点学习抽象语法树的用法,它具有强大而简单的数据结构来表示分析。3.1.2 功能描述1. 计算器具体需要实现的功能:a) 变量命名;b) 实现赋值功能;c) 实现比较表达式(大于、小于、等于等等)d) 实现if/then/else和do/while的流程控制;e) 用户可以自定义函数;f) 简单的错误恢复机制。2. 编写 Flex/Bison源文件,实现C 语言的语法分析功能,最后上机调试。3. 要求编写一个测试程序:首先自定义两个函数sq和avg,sq函数使用Newton方法来迭代计算平方根;avg函数计算两个数值的平均值。利用定义好的函数进行计算,得到计算结果并显示出来。4.根据习题1的要求,修改fb3-2相关代码;实现实现以下自定义函数,并保存为fb3-3。函数示例:let sq(n)e=1; while (|(t=n/e)-e).001) do e=avg(e,t);let avg(a,b)(a+b)/2;let max(a,b) if(ab) then a; else b; let max3(a,b,c) if(ab) then if(ac) then a; else c; else if(bc) then b; else c; 3.1.3 开发环境及工具介绍1、Window环境下载Visual Studio之后,利用其命令提示窗口进行操作。下载并安装Flex。 2、vs2010的编译器cl.exe。3、flex:词法分析器Flex是用来生成程序的工具,他们所生成的程序能够处理结构化输入,最初的Flex是用来生成编译器的,但是后来他们被证明在其他领域也非常有效。Flex是一个SourceForge项目。其依赖于GNU m4宏处理器。Linux和BSD都应该有m4,对于Windos用户来说,Flex被包含在Cygein Linux模拟环境中。什么是FLEX?它是一个自动化工具,可以按照定义好的规则自动生成一个C函数yylex(),也成为扫描器(Scanner)。这个C函数把文本串作为输入,按照定义好的规则分析文本串中的字符,找到符合规则的一些字符序列后,就执行在规则中定义好的动作(Action)。例如在规则中可以这样定义:如果遇到一个换行字符n,那么就把行计数器的值加一。Flex文件就是一个文本文件,内容包括定义好的一系列词法规则。4、bison:语法分析器GNU bison 是属于 GNU 项目的一个语法分析器生成器。Bison 把一个关于“向前查看 从左到右 最右”(LALR) 上下文无关文法的描述转化成可以分析该文法的 C 或 C+ 程序。它也可以为二义文法生成 “通用的 从左到右 最右” (GLR)语法分析器。Bison是一种通用目的的分析器生成器。它将LALR(1)上下文无关文法的描述转化成分析该文法的C程序。 一旦你精通Bison,你可以用它生成从简单的桌面计算器到复杂的程序设计语言等等许多语言的分析器。 Bison 基本上与 Yacc 兼容,并且在 Yacc 之上进行了改进。它经常和 Flex (一个自动的词法分析器生成器)一起使用。 此软件的源代码是可自由获得的,在 GPL 下发布。3.2 系统概要设计3.2.1 系统体系结构本实验计算器系统是基于抽象语法树的改进的计算器,在fb3-3.h的文件中实现声明部分,在fb3-3.l文件中实现计算器对应的词法分析,在fb3-3.y文件实现计算器的语法语义分析部分,在fb3-3funcs.c文件对应的是相应的计算器的C语言的代码。之后利用Visual Studio命令提示实现计算器的功能。结构图如下: 图3-1 系统体系结构图 计算器系统流程图: 图3-2 系统流程图3.2.2 系统模块划分(1)fb3-3.h文件头声明部分我们要做开始声明部分,在.h 头文件中我们可以用以下语句来定义抽象语法树的struct ast int nodetype;struct ast *l;struct ast *r; 且所有节点都有公共的初始 nodetype。 而删除和释放抽象语法树可以用语句 void treefree(struct ast *)来实现即可。常量使用 numval,符号引用使用 symref 赋值使用 symasgn,它有一个指向被赋值符号的指针和使用抽象语法树表示的值;(2) fb3-3.l文件词法分析部分词法分析器中设计六个比较操作符都返回一个带有字面值以便于区分的 CMP 记号,其中这六个关键字和四个内置函数通过文字模式加以识别,它们放在通用模式之前以 便于在通用模式之前进行匹配; 利用符号表进行词法分析,其中符号表中记录输入中使用的名称以及常用的符号。在这部分需要注意与C语言的交叉使用,对于每一类的词法分析须严格按照正则表达式来实现。(3) fb3-3.y文件语法分析部分语法分析器的设计,其中在语法分析器的最后提供了小部分错误恢复机制,这让我们有可能在错误发生时把语法分析器恢复到可以继续工作的状态;在这一部分我们为每个表达式建立了抽象语法树,以抽象语法树为单位进行计算,并打印出结果,并释放语法树。在这一部分需考虑移进/规约冲突和操作符的优先级,一定要在此代码中区分语句(stmt)和表达式(exp)。(4)fb3-3funcs.c文件C语言代码部分在这一部分的文件中语法分析器及.y文件需要调用其中的函数,创建语法树节点、分配节点进行填充、遍历抽象语法树。最后还要加一个辅助函数,正如flex 与 bison中所讲的一样,例程 treefree 的 扩展版本会递归的遍历一颗抽象语法树并释放这棵树的所有节点。本计算器的核心例 程是 eval,它用来计算分析器中构造的抽象语法树。我们采用深度优先遍历算法来计 算表达式的值; 3.2.3系统的数据流图在系统中,用户在输入要计算的内容后,先进行词法分析和语法分析,之后再判断用户要计算的类型是哪种四则运算,系统运算之后将结果返回给用户,数据流图如下: 图3-3 系统数据流图3.3 详细设计与实现3.3.1 fb3-3.h文件模块的设计与实现在这部分中,主要是对整个系统中的头文件的说明。首先我们要做开始声明部分,在.h头文件中我们可以用以下语句来定义抽象语法树的节点,且所有节点都有公共的初始nodetype。而删除和释放抽象语法树可以用语句voidtreefree (struct ast *) 来实现即可。常量使用numval, 符号引用使用symref赋值使用symasgn, 它有一个指向被赋值符号的指针和使用抽象语法树表示的值;在代码的一开始是说明与词法分析器的接口,其中的变量yylineno来自词法分析器,接下来的部分用于构造抽象语法树,抽象语法树有多个节点组成,每个节点都有一个节点类型。不同的节点可以有不同的域,但是在这个文件中有八种不同类型的指针。之后一部分是对抽象语法树的操作,首先用eval遍历抽象语法树,返回它所代表的表达式的值,之后删除和释放抽象语法树。下一部分是对符号表的声明,其中symbol为变量名,func为函数体,syms为虚拟参数列表。之后建立一个符号列表,并将其作为参数列表。在这个计算器中,每个符号都有一个变量和一个用户自定义函数。value域用来保存符号的值,func域指向用抽象语法树表达的该函数的用户代码,而sym域指向任意多个虚拟参数的链表,这些参数也是符号。函数newsymlist和symlistfree创建和释放符号。下面抽象语法树的声明:struct ast *newast(int nodetype, struct ast *l, struct ast *r);struct ast *newcmp(int cmptype, struct ast *l, struct ast *r);struct ast *newfunc(int functype, struct ast *l);struct ast *newcall(struct symbol *s, struct ast *l);struct ast *newref(struct symbol *s);struct ast *newasgn(struct symbol *s, struct ast *v);struct ast *newnum(double d);struct ast *newflow(int nodetype, struct ast *cond, struct ast *tl, struct ast *tr); 图3-4 声明文件流程图3.3.2 fb3-3.l文件模块的设计与实现词法分析器中设计六个比较操作符都返回一个带有字面值以便于区分的CMP 记号,其中这六个关键字和四个内置函数通过文字模式加以识别,它们放在通用模式之前以便于在通用模式之前进行匹配; 该词法分析器能够 实现基本的词法分析功能如行数、关键字个数、单词个数以及简单注释等的判别。这部分流程图如下所示: 图3-5 词法分析程序流程图3.3.3 fb3-3.y文件模块的设计与实现 这一部分主要是进行语法和语义分析。语法分析器的设计,其中在语法分析器的最后提供了小部分错误恢复机制,这让我们有可能在错误发生时把语法分析器恢复到可以继续工作的状态;在在代码的一开始%union定义了很多种符号值,符号值可以是符号表中特定用户符号、符号列表、比较子类型和函数记号的指针。FUNC表示内置函数,它的值确定了具体的某个函数,另外6个保留字,从IF到Let。记号CMP是6种比较操作符之一,它的值确定了具体的操作符。优先级声明列表从新的CMP和=操作符开始,%start声明定义了顶层规则。接下的部分区分了stmt和exp,语句是一个控制流或者是一个表达式。每当规则匹配到一条语句时,他将调用相应的程序去创建合适的抽象语法树。且list的定义是右递归的。新的CMP规则处理6种比较操作符,它使用CMP的值来判断当前的操作符,还有一条赋值规则来创建赋值节点。这一部分的程序流程图如下图所示:图3-6 语法部分流程图 3.3.4 fb3-3funcs.c模块的设计与实现在这一部分,用C语言进行创建抽象语法树和符号列表的过程,代码中对每一个节点进行分配,然后基于节点类型恰当地填充各个域,利用treefree递归地遍历一棵抽象语法树,同时释放这棵树的所有节点。计算器的核心是函数eval,他计算语法分析器中构造的抽象语法树。最后还要加一个辅助函数,正如flex 与bison中所讲的一样,例程treefree 的扩展版本会递归的遍历一颗抽象语法树并释放这棵树的所有节点。本计算器的核心例程是eval,它用来计算分析器中构造的抽象语法树。我们采用深度优先遍历算法来计算表达式的值;doubleeval(struct ast *a) double v; if(!a) yyerror(internal error, null eval); return 0.0; switch(a-nodetype) /* constant */ case K: v = (struct numval *)a)-number; break; /* name reference */ case N: v = (struct symref *)a)-s-value; break; /* assignment */ case =: v = (struct symasgn *)a)-s-value = eval(struct symasgn *)a)-v); break; /* expressions */图3-7 语法分析树图例如:分析 fred = 14 + 23 - 11 + 7 图3-8 抽象语法树3.4 系统分析与测试3.4.1 测试用例设计(1)简单的计算器,只能进行简单的四则运算,如(1+2)-(2*6)、1+2-3*2/5;C:GnuWin32binfb3-1.tab.exe |-1= 1 |123= 123 (1+2)-(2*6)= -9 1+2-3*2/5= 1.8(2)使用内置函数sqrt(n)、 exp(n) ,log(n)C:GnuWin32binfb3-2.tab.exe sqrt(10)= 3.162 exp(2)= 7.389 log(7.389)= 2(3)定义函数sq(n)、avg(a, b),用于计算平方根C:GnuWin32binfb3-2.tab.exe let sq(n)=e=1; while |(t=n/e)-e).001 do e=avg(e,t);Defined sq let avg(a,b)=(a+b)/2;Defined avg sq(10)= 3.162 sq(10)-sqrt(10)= 0.000178(4)第二次的改进的计算器,可以进行自定义函数的运算,而且语法更加贴近C语言;定义函数sq(n)、avg(a, b),用于计算平方根C:GnuWin32binfb3-2.tab.exe let avg(a,b)(a+b)/2;Defined avg let sq(n)e=1; while (|(t=n/e)-e).001) do e=avg(e,t);Defined sq sq(10);= 3.162 sq(10)-sqrt(10);= 0.000178定义函数max(a,b) ,用于求a,b的最大值C:GnuWin32binfb3-2.tab.exe let max(a,b) if(ab) then a; else b; Defined max max(4,5);= 5 max(1,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025年度房地产代理合同大全:特色小镇项目招商代理
- 2025年金融代签合同委托书专业范本
- 2025年货运司机服务外包合作协议书
- 2025版供应链金融三方担保贷款合同
- 2025版水泥企业节能减排技术改造采购合同
- 2025电梯维保安全协议书-电梯安全维保与绿色出行倡议合同
- 2025版企业补充养老保险应收账款质押贷款协议
- 2025年度企业媒体广告投放策略咨询合同
- 2025版茶饮店品牌合作与经营管理协议下载
- 2025年智能农业管理系统研发合作框架协议
- 部编六年级语文上册一二单元教案
- 游泳社会指导员专项理论考试复习题库汇总(附答案)
- 乒乓球体育课教案1
- 工程量确认单
- 先进制造技术第1章
- JJG 966-2010手持式激光测距仪
- 中班语言绘本《点》课件
- 大数据与金融课件
- 浙江省地方课程《人自然社会》课件
- 新版现代西班牙语第二册课后答案
- CS4000高级过程控制实验装置设备操作说明书
评论
0/150
提交评论