学 号: 0120710340731
课 程 设 计
题 目
学 院
专 业
班 级
姓 名
指导教师
FOR 循环语句的翻译程序设计(递归
下降法、输出三地址表示)
计算机科学与技术
计算机科学与技术
计算机 0907 班
赵阳
邱奇志
2012 年 01 月 05 日
1
课程设计任务书
学生姓名: 赵 阳
专业班级:
计算机 0907 班
指导教师: 邱奇志
工作单位:计算机科学与技术学院
题目: FOR 循环语句的翻译程序设计(递归下降法、输出三地址表示)
初始条件:
理论:学完编译课程,掌握一种计算机高级语言的使用。
实践:计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设
计。
要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
(1) 写出符合给定的语法分析方法的文法及属性文法。
(2) 完成题目要求的中间代码三地址表示的描述。
(3) 写出给定的语法分析方法的思想,完成语法分析和语义分析程序设计。
(4) 编制好分析程序后,设计若干用例,上机测试并通过所设计的分析程序。
(5) 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括:
1 系统描述(问题域描述);
2 文法及属性文法的描述;
3 语法分析方法描述及语法分析表设计;
4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计;
5 编译系统的概要设计;
6 详细的算法描述(流程图或伪代码);
7 软件的测试方法和测试结果;
8 研制报告(研制过程,本设计的评价、特点、不足、收获与体会等);
9 参考文献(按公开发表的规范书写)。
时间安排:
设计安排一周:周 1、周 2:完成系统分析及设计。
周 3、周 4:完成程序调试及测试。
周 5:撰写课程设计报告。
设计验收安排:设计周的星期五第 1 节课开始到实验室进行上机验收。
设计报告书收取时间:设计周的次周星期一上午 10 点。
指导教师签名:
系主任(或责任教师)签名:
年 月 日
年 月 日
2
目录
(一) 系统描述
问题的描述
文法及属性文法的描述
(二) 语法分析方法描述及语法分析表设计
递归下降法的主要思想
递归程序法需要对文法加限制
(三) 三地址码形式的描述及三地址序列的结构设计
中间代码的描述
三元式的主要构造流程
(四) 软件的测试方法和测试结果
测试用例分析
显示的测试用例结果
(五) 详细的算法描述
算法流程图描述
详细算法程序描述
(六) 课程设计总结
总结体会
3
(一)系统描述
问题描述
根据所学编译原理有关词法分析,语法分析,语义分析有关规
则,对 FOR 循环语句的翻译程序进行设计,使用高级语言或者伪代码形式,进
行编写,其中要求使用到递归下降法并在程序的最终结果中显示出表达式的三
地址码。
文法的描述
->for S1 do S2
按照设计要求,设计出的 For 循环语句的符合递归下降的文法如下:
S
S1 ->S2AB
S2 ->i=j
A
B
->stepj
->untilj
(二)语法分析方法描述及语法分析表设计
递归下降法
在程序语言的语法定义中有许多采用递归定义。我们在对它进行语法分析时,
编制的处理程序也采取递归的方式,可使其结构简单易读。但由于频繁地调用子程序
大大地降低了分析速度。
1:递归下降法的主要思想
对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序
也递归,子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或
递归下降法。用程序表示递归子程序的内部结构:
2:递归程序法需要对文法加限制:
1.任一非终结符 B 都不是左递归的,否则会产生死循环。
2.对 A 的任意两个右部βi , βj ,有:first(βi)∩first(βj)=φ First(βi)表
示βi 所能导出串的第一个符号的集合。显然,每个βi 的 first(βi)是互不相同的,否
4
则无法判断应执行哪个ζ(βi )。
(三)三地址码形式的描述及三地址序列的结构设计
三地址代码实际上是一种“四元式”的等价表示。
四元式是一种更接近目标代码的中间代码形式。由于这种形式的中间代码便于优化
处理,因此,在目前许多编译程序中得到了广泛的应用。
四元式的一般形式为:
(op,arg1,arg2,result)
其中, op 为一个二元 (也可是一元或零元)运算符;arg1,arg2 分别为它的两
个运算 (或操作)对象,它们可以是变量、常数或系统定义的临时变量名;运算的结果
将放入 result 中。四元式还可写为类似于 PASCAL 语言赋值语句的形式:
result ∶= arg1 op arg2
需要指出的是,每个四元式只能有一个运算符,所以,一个复杂的表达式须由
多个四元式构成的序列来表示。例如,表达式 A+B*C 可写为序列
T1∶=B*C
T2∶=A+T1
其中,T1,T2 是编译系统所产生的临时变量名。当 op 为一元、零元运算符 (如
无条件转移)时,arg2 甚至 arg1 应缺省,即 result∶=op arg1 或 op result ;对应
的一般形式为:
(op,arg1,,result)
或
(op,,,result)
在实际产生的四元式中,op 往往用一整型数表示 (操作符的代码),它可能附带有
不止一种属性。例如,加运算可以分为定点加法和浮点加法两种,我们可用不同的整数
值区分这两种加法。至于四元式中运算对象 arg1、arg2 和结果域 result,它们可以是
指向符号表中某项的指示字,也可以是某个临时变量的序号,因此,在实际的翻译过程
中,还需要进行相应的查填符号表工作。在本章中,由于我们只作原理性讨论,所以假
定临时变量来自一个用之不竭的集合,而不去追求其经济性。
5
例如:
有表达式如:中缀式 A + B * ( C - D ) + E / ( C - D ) ^N
则其四元式表达方法如下
四元式:
D
T1
T2
T1)
T2)
T3)
B
A
(1)(- C
(2)(*
(3)(+
(4)(- C
T4
(5)(^
E
(6)(/
(7)(+
T3
D
T4)
N
T5
T5)
T6)
T6
T7)
(四) 软件的测试方法和测试结果
依照下图所示,提示输入测试用例,按照文法要求手动输入测试用例:
for i=1 step 1 until 10
do a=1#
并可得到相应三地址码结果:
100 i=1
101 goto 103
102 i:=i+1
103 if i<10 goto 105
104 goto 107
105 a:=1
106 goto 102
107 end
6
测试用例如下图:
经过调试运行,结果符合课程设计要求,经过词法分析,分析了出了运算符标示符关键字等
信息。经过语法分析将最初表达式和最终要求的结果分离出来得到符合要求的 FOR 循环语句
的语法及语义分析程序。
7
(五)详细的算法描述
算法流程图描述
开 始
N
EXIT
输入 for 循环文法文件
进行词法分析输出标示符和表达式
符合递归子程序
条件吗?
Y
进行语法分析
对表达式进行三地址码分析
输出三地址码
退出
8