《编译原理》课程设计报告
学院(系) 班 级:
学生姓名:学号
指导教师:
时间: 从 2011 年 6 月 22 日 到 2011 年 6 月 25 日
一、 课程设计目的
通过课程设计进一步理解高级语言在计算机中的执行过程,加深对编译原理中重点算法和编译技术的理解,提高自己的编程能力,培养好的程序设计风格。同时通过某种可视化编程语言的应用,具备初步的Windows环境下的编程思想。
二、 课程设计的内容及要求
按照实例学习使用ANTLR(ANother Tool for Language Recognition)。
具体内容是学习实践利用ANTLR从关系代数到SQL语句的转化实现过程,深刻理解编译理论在软件开发过程中的实际应用价值,以此来学习将程序设计与编译理论相结合的现代高效编程方法和技术。进一步加深对编译理论的理解,并把理论应用于实践中,还可以引起同学们对编译器设计的思考。
在做课程设计设计之前,要学习编译原理的基本理论:包括编译程序的一般结构和每部分的功能。上网查询有关ANTLR的资料,从ANTLR的官方网站(http:// )下载最新版本的ANTLR和相关学习资料。学习C++和JAVA程序设计语言:C++、JAVA语法以及类的设计思想。在做好这些准备后,用巴克斯-瑙尔范式写出计算器和关系代数向SQL语句转换的.g文件。通过对.g文件的读取,生成与.g文件中的巴克斯-瑙尔范式相应的词法与语法分析器。然后再编写主函数调用生成的类,再运行主文件,从而实现计算器与关系代数向SQL语句转化的功能。最后,编写课程设计报告。
三、 实现原理
1. ANTLR是一种基于LL(k)文法的语法分析程序(以下简称分析器)生成工具。
它为我们构造自己的识别器、编译器和转换器提供了一个基础。它接受语言的文法描述,产生识别这些语言的程序。它还允许编程员在文法描述中插入特定的语义动作告诉ANTLR怎样去创建抽象语法树(AST)和怎样产生输出。
2.
3. 巴科斯-瑙尔范式(BNF: Backus-Naur Form 的缩写;巴克斯-诺尔范式),是一种用于表示上下文无关文法的语言,上下文无关文法描述了一类形式语言。 由于采用BNF语法进行表述的定义规则都是符合上下文无关文法的,而
ANTLR正是基于LL(k)文法的语法分析程序,因此可以通过BNF定义计算器(关系代数向SQL的转化)的词法、语法规则,然后使用ANTLR读取该文
4. 件从而生成词法分析器、语法分析器和目标代码生成器。 词法分析器可以将用户输入的字符流转化成为一个个的token传送给语法分析
器;而语法分析器则将一个个单词转化为语法树,创建语法树结构;目标代码生成器通过在对语法树遍历的过程中执行的操作来实现目标代码的生成;最后编写一个主函数调用以上生成的类,实现将用户的输入的算是转化成计算结果或者是将关系代数转黄成SQL语句输出。
四、 算法实现流程图
语法分析器
五、 测试数据
1. 计算器
2+3*2/10;
2. 关系代数向SQL语句的转换
第一组:Sname,gender(student);
第二组:Aage>25;
第三组:Ascore>90*Aage<25;
第四组:Sname(student)~Sscore(course);
第五组:Aa>5@b!=3~Ac<6^d>8;
第六组:Sa(dd);
第七组:Sname(student)|Ascore<60;
六、 结果输出及分析
1. 计算器
输出:(+2(/(*32)10))
2.6
运行结果截图:
结果分析:
顺次读入字符流,利用词法分析器将字符流转化为单词流,语法分析器读入单词流,构建语义分析树。在对语义分析树进行遍历,计算出结果后输出。
2. 关系代数转化为SQL
第一组: Sname,gender(student);
输出:SELECT name,gender
FROM student
运行结果截图:
结果分析:首先读入字母’H’,为select 语句,读入单词name, gender;匹配左括号,读入单词student,匹配右括号。
第二组: Aage>25;
输出:WHERE age>25
运行结果截图:
结果分析:读入字符’G’,为投影子句,读入token:age, > ,25,输出WHERE age>25
第三组: Ascore>90*Aage<25;
输出:WHERE score>90
UNION
WHERE age<25
运行结果截图:
结果分析:逐个读入单词,并按分类调用不同的函数,‘A’时调用choose()函数,score 计入变量表,>填入符号表,90为数字,*代表连接,最后输出翻译的结果。
第四组: Sname(student)~Sscore(course);
输出:SELECT name
FROM student
INTERSECTION
SELECT score
FROM course
运行结果截图:
结果分析:
如上所述,‘S’调用project函数,name 填入变量表,左右括号匹配,对应from,student填入变量表,~代表连接运算,输出最后结果。
第五组: Aa>5@b!=3~Ac<6^d>8;
输出:WHERE a>5 AND b!=3
INTERSECTION
WHERE c<6 OR d>8
运行结果截图:
结果分析:
‘A’调用choose(),a,b,c,d均为变量,@代表and,~代表连接,^代表或者,输出最终结果。
第六组: Sa(dd);
输出:SELECT a
FROM dd
运行结果截图:
结果分析:‘S’调用project(),a为变量,左右括号匹配,对应与from,dd为变量。遍历树,输出结果。
第七组:Sname(student)|Ascore<60;
输出:SELECT name
FROM student
WHERE score<60
运行结果截图:
结果分析:
‘S’调用project()函数,左右括号匹配对应from,|不做任何输出但将两个条件连接起来,‘A’调用choose()函数,score为变量,<为符号,60填入数字表,遍历整个树,输出结果。
七、 创新
1. 更改.g文件,PAI:'S'; XIGEMA:'A';换掉以前的’G’,’H’,用’S’,’A’代替;
2. 增加新的运算符’|’,实现SELECT name FROM student WHERE score<60的
翻译
修改方法为:
relation:(bin|jia|njo|chu|whr);
whr:WHERE^;
WHERE:'|';
relation:(bin|jia|njo|chu|whr);
whr:(g:WHERE){;};
八、 软件运行环境及限制
软件运行环境:Windows XP
Eclipse
九、 心得体会
1. 在编写程序之前首先要明确整个表达式或者说是语法树的结构,这样才能用BNF图将其准确地表达出来。在这基础上才能够编写相关的.g文件,主函数的编写也依赖于对于整个编译架构的理解。
2. 在对每个生成的函数理解时也要结合运行的流程和逻辑思路,画流程图也可以帮助我们理解整个程序的思路
3. 这次课程设计不仅使我对编译原理这门课程有了更深入的理解,对词法分析、语法分析、语义的分析的理解,同时也使我对java语言的编成更加熟悉。锻炼了我的实际动手能力。
十、 参考文献
1.《编译原理》课本
2.课程设计指导书
3.Learning ANTLR part I By Bill Bejeck 来源——http://
4.Implementing parsers and state machines in Java By Terence Parr 来源——http://
第二篇:《系统软件课程设计-编译原理》实验报告
《系统软件课程设计》
实验报告
华东理工大学信息科学与工程学院
20xx年6 月21 日题目 专业 班级 姓名 指导教师 高 雯、叶 琪
一.课程设计题目
二.课程设计成员
组长名字写在第一个,每个同学完成的基本任务是什么。
三.课程设计内容和要求
四. 软件系统设计
须采用软件工程的思想方法进行设计。
若用面向数据流方法设计时,需给出数据流图、数据字典、软件结构图。
若用面向对象方法设计时,需给出对象模型、动态模型、功能模型,系统拓扑结构、所定义的类或函数的一览表。
五.算法设计
给出主要算法描述。
六.上机实现情况及运行结果(包括中间和最终结果)
写明源代码如何运行,并打包上交。
七.小结
1. 课程设计中遇到的问题及解决办法。
2. 课程设计还存在哪些问题。
3. 对本课程设计有哪些建议。
4. 本课程设计有哪些收获和心得体会(每个人都要写,不少于500字)。
5. 其它需要补充的问题。
八.参考文献
在实验开始时,组内对程序功能模块进行了明确的划分,但未对接口进行详细具体的设计;编写期间,对于各部分的衔接进行多次讨论,对功能进行增删完善,但是由于接口的不理导致程序汇总运行出现较多错误,反复修改花费较多时间;后期进行统一测试调试。通过此次试验对编译器有了一个系统的认识,明白编译器的工作原理,由于编译器需要应对各种各样的程序,所以对词法分析语法分析的要求很高,我们根据书上的要求进行分析,尽量考虑可能出错的地方进行分析,而且要给出错误的正确位置也不容易,由于要考虑的情况太多,一开始写出的程序并不完整,后续又添加了一些功能,基本完成了对编译器的扩充。在进行分工合作时一定要多进行交流,使程序的接口能够统一,便于程序的运行,要经常让对方检查自己的代码以发现自己没有发现的问题,对软件工程的流程也有了比较全面的了解。在此次实验中由于是第一次组内合作,分歧较多,想法不一致,合作并没有那么默契,希望在以后的试验中进一步改善。