《编译原理》课程实验指导书
课程编号:
课程名称:编译原理/Compiler Principles
实验总学时数: 8
适用专业:计算机科学与技术、软件工程
承担实验室:计算机学院计算机科学系中心实验室、计算机技术系中心实验室
一、实验教学的目的与要求
上机实习是对学生的一种全面综合训练,是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。
通常,实习题中的问题比平时的练习题要复杂,也更接近实际。
编译原理这门课程安排的2次上机实验都属于一种设计类型的实验,每个实验的训练重点在于基本的编译技术和方法,而不强调面面俱到;实验的目的是旨在使学生进一步巩固课堂上所学的理论知识,深化理解和灵活掌握教学内容;培养学生编制算法的能力和编程解决实际问题的动手能力。
要求学生在上机前应认真做好各种准备工作,熟悉机器的操作系统和语言的集成环境,独立完成算法设计和程序代码的编写;上机时应随带有关的编译原理教材或参考书;要学会程序调试与纠错。
每次实验后要交实验报告,实验报告的内容应包括:
(1)实验题目、班级、学号、姓名、完成日期;
(2)简要的需求分析与概要设计;
(3)详细的算法描述;
(4)源程序清单;
(5)给出软件的测试方法和测试结果;
(6)实验的评价、收获与体会。
开发工具:
(1)DOS环境下使用Turbo C;
(2)Windows环境下使用Visual C++ 。
考核:
实验成绩占编译原理课程结业成绩的10%。
三、单项实验的内容和要求:
要求每个实验保证每个学生一台微机。
实验一(4学时):单词的词法分析程序设计。
(一)目的与要求
1.目的
通过设计、编制、调试一个具体的词法分析程序,加深对词法分析原理的理解,并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。
2.要求
(1)选择常用高级程序设计语言(如 PL/0语言)的源程序作为词法分析对象。
(2)根据教学要求和学生具体情况,从PL/0语言中选取它的一个适当大小的子集,可以选取一类典型单词,也可以尽可能使各种类型的单词都能兼顾到。
其基本要求是:以文本文件形式输入源程序,并对源程序从左到右进行扫描,对组成源程序的字符串拼接成为单词;并把其转换成属性字输出到文件中。
(3)实习时间为4学时。
(二)实验内容:完成对某一种常用高级语言(如PL/0语言)的各类单词的词法分析程序设计。
PL/0语言文法的EBNF描述:
〈程序〉∷=〈分程序〉。
〈分程序〉∷= [〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉
〈常量说明部分〉∷= CONST〈常量定义〉{。
〈常量定义〉};
〈常量定义〉∷=〈标志符〉=〈无符号整数〉
〈无符号整数〉∷=〈数字〉{〈数字〉}
〈变量说明部分〉∷= VAR〈标志符〉{,〈标志符〉};
〈标志符〉∷=〈字母〉{〈字母〉|〈数字〉}
〈过程说明部分〉∷=〈过程首部〉〈分程序〉{;〈过程说明部分〉};
〈过程首部〉∷= PROCEDURE〈标志符〉;
〈语句〉∷=〈赋值语句〉|〈条件语句〉|〈当型循环语句〉|〈过程调用语句〉|〈读语句〉|〈写语句〉|〈复合语句〉|〈空〉
〈赋值语句〉∷=〈标志符〉:=〈表达式〉
〈复合语句〉∷= BEGIN〈语句〉{;〈语句〉}END
〈条件〉∷=〈表达式〉〈关系运算符〉〈表达式〉|ODD〈表达式〉
〈表达式〉∷= [+|-]〈项〉{〈加法运算符〉〈项〉}
〈项〉∷=〈因子〉{〈乘法运算符〉〈因子〉}
〈因子〉∷=〈标志符〉|〈无符号整数〉|‘(’〈表达式〉‘)’
〈加法运算符〉∷=+|-
〈乘法运算符〉∷=*|/
〈关系运算符〉∷==|#|<|>|<=|>=
〈条件语句〉∷= IF〈条件〉THEN〈语句〉
〈过程调用语句〉∷= CALL〈标志符〉
〈当型循环语句〉∷= WHILE〈条件〉DO〈语句〉
〈读语句〉∷= READ‘(’〈标志符〉{,〈标志符〉}‘)’
〈写语句〉∷= WRITE‘(’〈表达式〉{,〈表达式〉}‘)’
〈字母〉∷= a|b|…..|X|Y|Z
〈数字〉∷= 0|1|2|…..|8|9
(三)提示:
(1)本实验是综合型、设计型实验,在实验中需要综合运用《离散数学》中的数理逻辑;《数据结构》中的队列;《程序设计》中的算法设计、数组、条件控制、循环控制和《编译原理》
中的自动机、文法等等方面的知识。
(2)把常用高级程序设计语言中的单词分为下几类:关键字、标识符、运算符、无符号数(常数)、界限符,其中关键字、运算符、界限符三类单词对于任何一种高级语言来说其数量和
意义均是固定的,所以此三类单词可以事先构造好相应的表进行管理;而对于标识符、无
符号数两类单词则需要边识别边建表填表。
(3)设计者要为给定语言的每类单词定义其单词属性字的结构。
(4)词法分析程序的输入为给定语言的任意用户源程序(在用ASCII码保存的文件中),输出为设计者定义的单词属性字序列(也是用ASCII码保存的文件)。
(四)示例:
下面给出词法分析总控程序和无符号数词法分析子程序的流程图:
图1 词法分析总控程序
图2 无符号数词法分析流程图
实验二(4学时):赋值语句的翻译程序设计。
1.目的
通过设计、编制、调试一个典型的语法成分的语法分析和语义分析程序,实现对词法分析程序所提供的单词序列进行语法检查和结构分析以及语义翻译工作,进一步掌握常用的语法分析方法和语义分析方法。
2.要求
(1)选择最有代表性的语法分析方法,如算符优先法(或简单优先法)、递归下降分析法、LL 分析法和LR分析法之一进行语法分析。
(2)选择对各种常见程序语言都通用的语法结构,以文本文件形式输入源程序,把其中赋值语句(尤指表达式)作为分析对象进行词法语法分析。
(3)选择最有代表性的语义分析方法,如语法制导翻译方法进行语义翻译工作,把源程序翻译
成为中间代码序列,并输出到文件中。
(4)实习时间为4~6小时。
(二)实验内容:
对于常用高级语言(如Pascal、C语言)的赋值语句用所学过的语法分析方法和语义分析方法
进行语法分析、语义分析,并把其翻译成为中间代码形式。
(三)提示:
(1)本实验是综合型、设计型实验,在实验中需要综合运用《离散数学》中的数理逻辑、图;《数据结构》中的队列、栈、链表、树;《程序设计》中的算法设计、数组、条件控制、循环控制、
指针、结构体和《编译原理》中的自动机、文法、语法树、属性文法、词法分析、语法分析、
语义分析、中间代码生成等等方面的知识。
(2)对通过词法分析程序所提供的单词序列程序从左到右进行扫描,把其中赋值语句用所学过的语法分析方法(递归下降分析法、算符优先分析法(或简单优先法)、LL分析法和LR分析法)
进行语法分析,采用语法制导翻译方法将其转换为中间代码(逆波兰式、四元式)形式输出。
四、课程特色
《编译原理》课程是理论性较强的课程。
其特点是概念多、内容抽象。
尤其是文法、形式语言及自动机的概念是计算机专业的理论学习和研究的基础。
编译原理与方法对于深刻理解程序设计语言、深入了解程序在计算机中的运行机制、掌握程序设计语言的翻译方法起到不可替代的作用。
同时《编译原理》课程也是实践性很强的课程,要求学生在基本掌握了编译理论和技术的基础上,综合应用先修课程及本课程的知识,完成课程的实验和课程设计。
五、教材及参考书
教材:
[1]张素琴、吕映芝等.编译原理(第2版).清华大学出版社.2005年2月
参考书:
[1]何炎祥.编译原理.华中科技大学出版社.2005年8月
[2]陈火旺等.程序设计语言编译原理(第3版).国防工业出版社.2003年2月
[3]Alfred V.Aho,Ravi Sethi,Jeffrey D.Ullman.Compilers:Principles,Techniques,and Tools.人民邮电出版社.2002年2月
[4]陈意云.编译原理与技术(第二版.中国科学技术大学出版社.2002年1月
[5]胡元义等.编译原理实践教程.西安电子科技大学出版社.2002年1月
[6]王雷等.编译原理课程设计.机械工业出版社.2005年3月
编写:陈天煌日期:2010年9月10日
审阅:日期:
审定:日期:。