解释器构造课程实践.DOC

1、CMM 语言解释器构造1解释器构造课程实践项目文档作 者： 陈业晓 200532580044完成日期： 2007-11-22 CMM 语言解释器构造2目 录1 引言 .31.1 背景 .31.2 定义 .31.3 参考资料 .32 程序系统的设计及实现 .33 测试 .34 结束语 .44.1 项目完成情况分析 .44.2 论文 .4CMM 语言解释器构造31 引言1.1 背景姓名 学号 分工说明ISSERWHU 所有说明该项目的相关开发背景，至少包括：小组成员的具体分工。1.2 定义列出本文件中用到的专门术语的定义和缩写词的原词组（如果没有，则可以去掉此部分）1.3 参考资料参考资料:编译原

2、理及实践 （Kenneth C. Louden 著）编译原理 （张素琴 吕映芝 蒋维杜 戴桂兰 编著）列出完成项目及文件用到的参考资料2 程序系统的设计及实现说明设计及实现解释器中需要说明的问题，至少包括：1、 所支持的语言的词法规则、语法规则以及语义实现及解释方法。2、 解释器实现的组织结构。3、实现使用的语言及环境说明，或者采用的开发工具。4、如果界面不够友好，说明解释器使用的基本方法，如果使用方便，则可省略此内容。1、所支持的语言的词法规则、语法规则以及语义实现及解释方法11 词法规则注：我的理解是 CMM 语言能识别的符号，不一定非要用正则表达式来表示，不知对不对我实现的解释器能识别的

3、符号与所给的一样，并没有增加或减少。见下表：CMM 语言解释器构造4保留字 特殊符号 其他If +else -while *十进制的整数与实数read /write =int ();/*/1.2 语法规则见附录 1：CMM 文法（EBNF 表示）1.3 语义实现和解释方法在遍历语法树的过程中，同时构造符号表和进行类型检查并且同时对程序进行解释，全过程只遍历一遍语法树。2、解释器实现的组织结构整个解释器的实现就分为三部分：词法分析 ，语法分析和语义分析。词法分析：对源代码进行扫描，分解出所有合法的 token ，并将它和它的相关信息保存在一链表中，以供后续的分析使用。语法分析：从词法分析的结果中

4、顺序读取 token 采用递归子程序分析法进行语法分析，产生一语法树，语法树的表示方式使用了编译原理与实践中所介绍的表示方式。语义分析及解释：一次遍历语法分析中产生的语法树，构造符号表并进行解释。3、实现使用的语言及环境说明，或者采用的开发工具。CMM 语言解释器构造5语言：C x = 10;write(x+101);输入命令 cmm test.cmm 开始 :图 1CMM 语言解释器构造6输入 a 输出词法分析结果：图 2接着输入 s 进行语法分析并打印分析结果：图 3再输入 i 进行解释：CMM 语言解释器构造7图 44 结束语4.1 项目完成情况分析1、 分析所完成的解释器的优点（作为评

5、分参考）隐式类型转换 界面友好 类型声明 实现作用域所使用的数据结构及算法2、 分析存在的问题及不足错误恢复 没实现函数定义功能，语言功能受限 没实现定义功能，只能将定义拆分为声明和赋值语句，这样不是很方便3、 完成解释器的感言（可选）1.1 解释器的优点1) 采用一次遍历语法树进行解释.在一次遍历树的过程中,同时进行符号表的构建和类型检查,同时到程序进行解释.提高了程序的执行效率.2) 采用了易于表示作用域的数据结构.对于每一个作用域都构造一个符号表(hashtable),然后从内到外地把所有符号表连接起来.当程序进入一个作用域,解释器构造一个最内层作用域,而当程序退出一个作用域,就把最内层

6、作用域从链表中删除.3) 实现了隐式的类型转换.将一个 REAL 类型的值当作 INT 值使用,解释器将会报错,而将一个 INT 值当作 一个 REAL 的值使用,解释器会隐式地将 INT 转化为 REAL 类型值.4) 实现了类型声明的功能.在使用一个变量之前,必先声明此变量.且变量名不能和其它同作用域的名称发生冲突.5) 界面友好.如图 1 所示,解释器提供了几个选择项.其中比较特别的一个是 r ,这个选项是当你在分析程序的过程中,修改了程序,你可以使用这个功能对程序进行重新分析.而不需要重新启动分析程序.可以一边分析程序,一边修改程序.1.2 解释器缺点.1) 没有错误恢复功能.在语法分

7、析和语义分析两过程中没有对错误进行恢复,只是对错误进行报错并终止程序.2) 没实现函数定义功能.程序功能受限 .3) 没实现变量定义功能.因为发现数组的定义比较麻烦,所以将定义拆分为声明语句和赋值语句,这样做对使用 CMM 语言的程序员不是很方便.4) 在语法分析部分,程序比较混乱 ,包括逻辑和代码的组织.语义分析程序比较清晰.CMM 语言解释器构造81.3 完成解释器感言.毫无疑问,这个解释器是我在这之前所写的所有程序中代码最多,花时间最长,花精力最多,技术含量最高的一个程序,我对我所写的这个解释器还算比较满意.在写解释器的每一阶段,开始时总是感觉比较难,有点找不到方向,但是通过努力.到最后

8、总是可以把它写出来,而且觉得也没什么.现在觉得写程序主要是有足够的耐心.我用了我刚学过的 C 语言来写这个程序 ,通过写这个程序,我对 C 更加熟悉,对数据结构更加熟悉.在写程序的过程中,提高了自己对问题的分析和解决能力.积累了一些宝贵的项目经验.总的来说，我觉得学院开这门课是一个很明智的选择。我从中学到了不少知识，得到不少的经验。相信其它同学也有相同的感受吧。4.2 技术论文基于此课程实践，谈谈对编译技术、编译器实现或相关问题的认识和探讨（不限字数） 。可另创建新文件完成此节内容。写完 CMM 解释器 ,也说不上对编译技术之类的什么认识和探讨,只不过要求写技术论文,就随便写点什么吧.那我就谈

9、一下我在实现解释器的过程中,对用到的技术的一些认识吧.总的来说,我感觉我在做这个解释器的过程中,用到以前学过的编译方面的比较难的算法方面的知识并不多,更多的是用到一些基本概念.在词法分析阶段,主要是用到正则表达式和有穷自动机的一些非常简单的知识.确切地说,就是在识别标识符和数字中用到一点.但是这已让我领会到这两方面知识的强大功能.相信这些基础知识在我以后的开发程序和学习更深的理论的过程中起到很大的作用.虽然我在开发解释器的过程中,因为 CMM 的词法比较简单,我没有用到 NFA 与 DFA 及正规文法之间的转化理论.,但是,相信以后会用到.在语法分析阶段,我用的是递归子程序分析法.感觉最重要的

10、是把文法写好,只要把文法写好,将文法转化为程序是很简单的.当然构造语法树也不是很容易,因为你要找到最能表示CMM 语言结构的树,还有确定用怎样的方式将程序的结构及其所有有用的属性(当然,还要分析有什么属性)记录下来,这两方面我感觉比较难 ,因为我当时并不知道在语义分析中到底会用到一些什么样的信息.记得当时花了不少时间去分析.在语义分析及解释阶段.主要是对树节点的类型和值进行计算,还是就是用合适的数据结构构造符号表和进行类型检查.我在实现的过程中,觉得比较困难的是采用什么样的数据结构来表示符号的作用域.因为我实现的 CMM 语言标识符要求先声明,再使用的方式,而且我想使用一次遍历进行解释的方式，

11、觉得使用编译原理与实践中提到的表示方式比较合适: 为每个作用域建立一个新的符号表，再从内到外把它们链接在一起，这样如果查找操作在当前表中没有找到名字，就自动用上一层的表继续搜索。当退出当前作用域时，就删除最CMM 语言解释器构造9内层符号表即可。感觉写程序时对数据结构的使用要比较的熟悉。其它的就没什么可说的了。附录 1CMM 语言文法描述:（EBNF）:= := := | | | | | := := int | real;:= = ;:= := :=| ():= +|-( | ):= + | -:= * | /:= while():= := | = =:= if () else:= read():= write();