1、编译原理课程设计指导书编译原理课程设计指导书韩丽 王治国 著郑州轻工业学院计算机与通信工程学院2003年10月目 录一、 课程设计的基本任务 3二、 课程设计的基本要求 3三、 课程设计的基本步骤和方法 4四、 课程设计说明书（含报告的书写规范） 5五、 附录（课程设计大纲等内容） 12一、 课程设计的基本任务编译原理是一门实践性很强的课程，只有通过实践，才能真正掌握。通过实验，将编译原理的相关理论运用到软件开发中，提高学生的应用程序设计能力，提高分析问题、解决问题的能力。实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原理的实践教学，采用简化编译过程的办法，选择最关键的个环
2、节词法分析、语法分析（包括语义处理、产生无优化的目标指令）、连接调试，进行编程和调试训练。每个环节作为一个实践课题。先分别编程调试，再连接在一起总调。着重实践的是词法分析与语法分析部分。二、 课程设计的基本要求课程设计按照教学要求需要一周时间完成，总共至少要上机调试程序10小时。对每个题目要有需求分析，在需求分析中，将题目中要求的功能进行叙述分析，通过实验，将编译原理的相关理论运用到软件开发中，提高学生的应用程序设计能力，提高分析问题、解决问题的能力。1选题：通过平时积累，找到适合于自己的应用或某种软件功能，该应用能利用编译原理中的某些理论。题目大小适中。请在一周前选好题目。2 对每个题目要有
3、相应的源程序（可以是一组源程序，即详细设计部分）：源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环；3选好题目后，分析该题目的应用性，可用到编译原理的哪些理论？对它们进行简单阐述。同时对软件进行需求分析，通过回答下面问题得到：软件提供哪些功能？软件有什么用？界面怎样？怎样使用该软件？对输入数据的格式有什么要求？用什么语言开发？怎样测试该软件？该软件开发的进度如何安排？出以上问题的答案，然后自问：你的分析材料别人能非常清楚地看懂吗？如果回答是肯定的，就可以搞设计了。4对软件划分功能
4、模块，将模块细化，设计出数据存放格式，写出各模块（函数）的功能、传递参数的格式和返回值的类型，画出模块结构图。最后画出程序流程图。5测试数据的设计：每组测试数据包括输入数据、预期的输出结果、实际的输出结果和预期的是否相吻合（如果不吻合，实际输出什么？可能错误的原因？检查源代码或设计进行查错，纪录结果。）。1、能力培养要求巩固和加深对编译原理的理解，提高综合运用本课程所学知识的能力。培养学生选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析 问题、解决问题的能力。过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。够按要求编写课程设计报告书，能正确阐述设计和
5、实验结果，正确绘制系统和程序框图。通过课程设计，培养学生严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。2、学生提交课程设计报告要求1）设计题目2）设计目的3）设计内容4）程序流程图5）源程序6）软件测试报告（包括结果）三、 课程设计的基本步骤和方法1、学生以自学为主，独立完成设计任务，注重学生能力的培养。2、教师要注意按学生基础和能力提出要求，辅导时要有侧重，做到因材施教。对基础差的学生要勤检查多指导，对能力强的学生应提出更高的要求，增加些选作内容，充分发挥其潜力。3、教师要教书育人。要求学生从点滴开始，每步操作都要按规定去做，以培养严肃认真的科学态度。选定方案要考虑经济效益
6、，坚持勤俭节约的原则。要教育学生团结协作，遵守纪律，爱护公物。通过设计提高业务能力，提高思想觉悟。4、课程设计安排教师下达设计任务书任务书内容包括题目、主要技术指标和要求、给定条件及原始数据、所用仪器设备和参考资料及文献等。教师讲授必要的设计思路和设计方法。生完成预设计本阶段学生应明确任务，查阅资料及文献（主要自学），掌握工程设计基本方法，确定设计方案，进行设计分析，完成预设计。实验阶段经教师审查通过预设计方案后，即可进行编程调试。实验由学生独立完成，教师定时指导。设计总结阶段本阶段学生要认真完成课程设计报告书，整理技术资料，如有需要还应写出课程设计的心得体会和改进意见。课程设计报告书包括：设
7、计任务及主要技术指标、设计方案及论证结果、系统的原理框图、设计程序、实验结果、实验中主要问题及故障现象的分析及设计结论等。四、 课程设计说明书（含报告的书写规范）课程设计要求学生在以下模块中选作一个、利用C编写语法分析程序，对C语言的简单子集进行分析。1: D-()S. 程序-主函数2: S-=E;. 赋值语句3: S-W. 组合语句4: S-i(G)S. if语句5: S-i(G)SeS. if-else语句6: S-w(G)S. while语句7: S-zL;. 变量定义8: S-(E);. 函数调用9: W-WS. 多条语句列表10: W-S. 语句列表11: L-. 变量名列表12:
8、L-L,. 多个变量名列表13: G-G&M. 逻辑表达式14: G-M.15: M-EE. 关系表达式16: M-!M. 逻辑非表达式17: M-(G). 带括号的逻辑表达式18: E-E+T. 加法表达式19: E-T.20: T-T*F. 乘法表达式21: T-F.22: F-(E). 带括号的算术表达式23: F-. 变量表达式24: F-n. 数字表达式1.1.C语言子集规定1.1.1 C语言的简介ALGOL 60是C语言的前身，它是由剑桥大学最先开发出来的一个语言。1967年，剑桥大学的Matin Richards对CPL语言进行的简化，于是产生了BCPL语言。1970年，美国贝尔
9、实验室的Ken Thompson将BCPL进行的修改，并取名为“B语言”，并用它写出了第一个UNIX操作系统。到了1973年，D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，取名为C语言。1978年，Brian W.Kernighian和Dennis M.Ritchie出版了著名的The C Programming Language，从而使C语言成为目前世界上最为流行的高级程序语言。C语言之所以在目前世界上流行、使用广泛，这是因为它有非常多的优点。首先它简洁紧凑、灵活方便，有着非常丰富的运算符和数据结构。其次他是一个结构化的语言，便于使用、维护及调试。还有就是C语言允许直接对物
10、理地址访问，可以直接对硬件操作。最后C语言生成的代码质量高，程序执行效率高，并且使用范围大，可移植性好，因此在多钟操作系统中均可以使用。由于C语言的流行，随之而来的是许许多多的编译软件和环境。其中Turbo C、Borland C编译器以及后来的VC可视化编程环境都是广大编程人员所钟爱的编程工具。为了对整个C语言的词法，语法，语义，编译等等方面有一个整体且深入的了解，因此这次的课程设计开发的编译器就以C语言为基础，对自己定义的类C的集合进行深入分析定义，设计出一个较为稳定可用的编译器。1.1.2 C子集的定义本次设计的C语言的子集（便于叙述，以后称之为Cxx），是本着简单、易懂、易操作，而且能
11、够完成一定功能的原则，尽量实现最基本的，人们最常用的部分，而抛弃那些不常使用的，或者难以实现的部分。这样考虑的目的是为了能过在短时间做出一个编译程序大的框架，并且开发出一个较为稳定的版本，来为以后的扩充更多的功能提供一定的接口和方便。这种设计是由里到外，逐步求精，也是符合一般设计的规律。下面就是Cxx的说明，由于与具体的编码有关，因此不可能使用形式化的语言，而只作简单的说明性的定义。1Cxx以main函数做为主函数，且是整个语言唯一的函数。main函数是一个无参的，无返回类型的，不需要返回语句retrun的函数。所有的程序必须写在main函数里面；2Cxx的程序是以一行或多行表达式和多个程序块
12、构成，每行表达式的结尾以分号“；”做为标志，一个程序块以大括号做为区域定义标志；3Cxx的表达包括变量定义表达式、赋值表达式、算术运算表达式、逻辑运算表达式；4Cxx的程序块包括三大程序结构，即顺序、分支和循环；5Cxx的变量定义只允许整型变量定义，并且可以赋初值，即类似int i5的定义；6Cxx的赋值语句只允许使用等号“”将一个表达式的值付给一个整型变量，例如x=3*y;7Cxx的算术表达式的符号包括, * , / , , %。对应的操作为加法，减法，乘法，除法，乘方，求模；8Cxx的逻辑表达式的符号包括&, | | , ！,= = , != , , =。对应的运算为逻辑与，逻辑或，逻辑非
13、，等于，不等于，小于，大于，小于等于，大于等于;9Cxx分支程序块包括if，if-else,if-elseif-.-else的语句，其语法定语同Ansi C的定义；10Cxx循环程序块包括while，do-while和for语句；1.1.3 简单举例下面是一个简单的标准的Cxx的源程序：（其中/* */为说明部分，不作为程序的内容）main（） /*main函数定义*/ int i=0,x=10,y=20,z=30,a,b,c; /*整型变量定义*/ a=x+y*z; /*赋值和算术表达式语句*/ b=（3*z ）%y; for（i;i=10;i=i+1） /*for循环语句*/ if（a|b
14、）&（x|y）!=0） /*ifelse分支语句和逻辑运算语句*/ c=a+b; else c=a-b;、利用C语言编制递归下降分析程序，并对C语言的简单子集进行分析。用扩充的BNF表示如下： 1: :=main() 2: := 3: :=; 4: :=| 5: :=ID= 6: :=if 7: :=while 8: := 9: :=|+|- 10: :=|*|/ 11: :=ID|NUM| 12: := |=|= =|!=、构造LR(0)分析表，并用程序实现 S-A|B A-aAb|c B-aBb|d、构造SLR(1)分析表，并用程序实现 S-Sb|bAa A-aSc|aSb|a（5）、用C
15、语言(或 C+ )作为宿主语言完成： C语言(ANSI C或turbo C 2.0)词法分析器的设计和实现。 实验要求1. 编写C语言词法分析器的源程序并调试通过； 2. 通过测试程序的验收； 3. 提交简明扼要的书面实验报告。内容包括：属性字设计；源程序主要流程；主要数据构设计。程序工作说明本程序包含三个源文件，分别是：lexmain.c、FUNCTION.h、lexical.h。程序的输入文件是任何一个目录下的C源文件，但是为了方便，就使用lexmain.c吧。程序的输出文件是程序自己生成的，在和程序的统一目录下，名称为：Rusult.txt。程序工作原理本程序没有专门建立缓冲区，而是运用
16、了操作系统对fopen()函数缓冲区的处理，从硬盘逐个独处字符进行分析。(6)、算符优先文法处理算术表达式实验目的：算术表达式的文法（你可以根据需要适当改变）： EE+E|E-E|E*E|E/E|（E）|i根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。程序要求：程序输入/输出示例：如参考C语言的运算符。输入如下表达式（以分号为结束）和输出结果：（1）10;输出：正确（2）1+2;输出：正确（3）(1+2)/3+4-(5+6/7);输出：正确（4）(1-2)/3+4输出：错误（5）1+2-3+(*4/5)输出：错误注意：1.为降低难度，表达式中不含变量（只含无符号整数）；2.
17、如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；4.对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果，计算过程用浮点表示，但要注意不要被0除。程序思路（仅供参考）：1.借用实验一的结果，可将其中的取字符函数几乎原封不动地移植过来，其中的分割和分析单词的方法可借用过来分割现在这个实验的运算符、常量和变量。2.模块结构：（1）初始化：设立算符优先关系表（或优先函数）、初始化变量空间（包括堆栈、结构体、数组等）；（2）控制部分：将一个
18、表达式从文件中读出；（3）词法分析：将表达式分割成单词序列；（4）利用算符优先文法进行表达式处理：根据算符优先关系表对表达式单词序列进行堆栈操作，如果遇到错误则显示错误信息。为了能设计好程序，主意以下事情：1.模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。2.写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。3.编程时注意编程风格：空行的使用、注释的使用、缩进的使用、变量合理命名等。附录1 课程设计任务书模板郑州轻工业学院课 程 设 计 任 务 书题目 专业、班级 学号 姓名 主要内容、基本要求、主要参考资料等：完 成 期 限： 指导教师签名： 课程负责
19、人签名： 年 月 日附录2 课程设计总结报告模板郑州轻工业学院本科编译原理课程设计总结报告设计题目：学生姓名：系 别：计算机科学与工程专 业：计算机科学与技术班 级：学 号：指导教师： 年 月 日一、 设计题目（任选其一）二、 运行环境（软、硬件环境）三、 算法设计的思想四、 算法的流程图五、 算法设计分析六、 源代码七、 运行结果分析八、 收获及体会附录3 编译原理课程设计教学大纲编译原理课程设计教学大纲（计算机科学与技术专业本科适用）参考学时：一周 学分：1 课程编号：0706311S一、本课程的性质和任务 编译程序是计算机系统软件的重要组成部分之一。编译原理是一门实践性很强的课程，不仅提
20、供了计算机科学的理论知识，同时也提供了计算机编译程序的设计方法。只有动手实践才能对编译系统的原理、分析方法和设计达到系统的掌握和理解。本课程设计试图针对编译程序实现的各个环节，包括原理、设计方法、算法描述和工程实现，进行完整的系统化的训练和练习。 本课程设计由一系列实验组成，一部分可以作为单一的实验配合课堂教学进行。几个实验的有机组合即可作为该课程设计的内容。通过课程设计这样一个教学环节，使学生得到系统化的训练，更好更系统地掌握基本的编译方法、编译程序的构造与设计技术，提高系统软件和应用软件的设计实现能力。二、 课程设计的基本内容1给出词法分析器的构造方法，说明自动机在词法分析器构造中的作用。
21、并以C语言的一个子集为例，设计与实现该子集的词法分析程序。2利用C语言编制递归下降分析程序，并对C语言的简单自己进行分析。 3构造LR(0)分析表，并用程序实现 4构造SLR(1)分析表，并用程序实现 5. 用C语言(或 C+ )作为宿主语言完成： C语言(ANSI C或turbo C 2.0)词法分析器的设计和实现。 6. 算符优先文法处理算术表达式三、 本课程设计的基本要求 受算法设计复杂性及学生对于所学基础和专业知识的综合应用能力及程序设计与调试能力的不同，一周时间大体分为三个阶段：算法设计与描述；程序设计；上机调试直到输出正确结果。提交相关软件和规范的设计说明书电子文档。要求在设计过程
22、中树立科学的设计思想，有全局观念，培养高度的协作精神。 四、 学时分配建议 课程内容理论讲授实验课时间小计算法设计1天1天程序设计2天2天上机调试2天2天合计5天5天五、其它说明1完成本课程设计必须掌握C语言，具有较好的程序设计能力。分配给学生个人的任务以23个实验为宜，并建议以语法分析程序的设计与实现为主程序。2根据编译原理课的教学实践，配合课堂教学所进行的实验，能完成的有词法分析程序的设计与实现；有限自动机的确定化等。由于实验时间限制，语法分析程序的设计与实现较难，本课程设计以第一、二个实验为重点，强调第一个实验的输出作为第二个实验的输入。3人员分组及分工建议以2-3人一小组，鼓励学生独立完成。4设计说明书要求设计说明书应用统一纸张书写。内容包括设计任务书，所有论述、原始资料和数据、计算及结构表格等，编写顺序建议如下：（1）标题页（2）设计任务书（3）目录（4）算法分析与设计（5）详细设计（6）关键代码（7）对本设计的简单评述、总结或体会（8）参考文献起草人: 马吉明 专业负责人: 黄道颖 教学院长(主任):张建伟
