1、武汉理工大学编译原理课程设计说明书- 1 - 学 号： 0120910340933课 程 设 计题 目 FOR 循环语句的翻译程序设计（递归下降法、输出三地址表示）学 院 计算机科学与技术学院专 业 计算机科学与技术班 级 0909 班姓 名 王嘉辛指导教师 高曙2012 年 1 月 5 日武汉理工大学编译原理课程设计说明书- 2 - 目录课程设计任务书- 31、系统描述 41.1、实验思想 41.2、设计内容 41.3、翻译过程 42、递归下降法 62.1、递归下降法的主要思想：62.2、用程序表示递归子程序的内部结构：73、三地址代码的表示：74、语法制导翻译84.1、翻译任务的处理过程8
2、4.2、语法制导翻译：843、基于属性文法的处理方法-85、中间代码形式的描述及中间代码序列的结构设计86、简要的分析与概要设计96.1、词法分析：96.2、语法递归分析106.3、制导翻译-126.4、主函数-137、测试方法和测试结果-147.1 测试过程-147.2 测试结论-168、课程设计总结-179、参考文献-18本科生课程设计成绩评定表19武汉理工大学编译原理课程设计说明书- 3 - 课程设计任务书学生姓名： 王嘉辛 专业班级： 计算机 0909 班 指导教师： 高 曙 工作单位：计算机科学与技术学院 题目: FOR 循环语句的翻译程序设计（递归下降法、输出三地址表示）初始条件：
3、理论：学完编译课程，掌握一种计算机高级语言的使用。实践：计算机实验室提供计算机及软件环境。如果自己有计算机可以在其上进行设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）（1） 写出符合给定的语法分析方法的文法及属性文法。（2） 完成题目要求的中间代码三地址表示的描述。（3） 写出给定的语法分析方法的思想，完成语法分析和语义分析程序设计。（4） 编制好分析程序后，设计若干用例，上机测试并通过所设计的分析程序。（5） 设计报告格式按附件要求书写。课程设计报告书正文的内容应包括：1 系统描述（问题域描述） ；2 文法及属性文法的描述；3 语法分析方法描述及语法
4、分析表设计；4 按给定的题目给出中间代码形式的描述及中间代码序列的结构设计；5 编译系统的概要设计；6 详细的算法描述（流程图或伪代码） ；7 软件的测试方法和测试结果；8 研制报告（研制过程，本设计的评价、特点、不足、收获与体会等） ；9 参考文献（按公开发表的规范书写） 。时间安排：设计安排一周：周 1、周 2：完成系统分析及设计。周 3、周 4：完成程序调试及测试。周 5：撰写课程设计报告。设计验收安排：设计周的星期五第 1 节课开始到实验室进行上机验收。设计报告书收取时间：设计周的次周星期一上午 10 点。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日武汉理工大学编译
5、原理课程设计说明书- 4 - FOR 循环语句的翻译程序设计递归下降法、输出三地址表示1、系统描述1.1、实验思想通过设计、编制、调试一个 FOR 循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，实现词法分析程序对单词序列的词法检查和分析，并且实现对单词序列的语法分析、语义分析以及中间代码生成。1.2、设计内容本设计按照要求设计出 for 语句的简单文法，并使用递归下降分析法对用户输入的程序进行分析和翻译。对下列正确的程序输入： for i=1 step 1 until 10 do k=j #结果程序要对该输入进行词法分析，然后利用递归下降的分析法对词法分析得到的单词序列进行语法
6、分析，经过语法制导翻译显示出等价的三地址表示的中间代码。对于错误的程序输入，如：For i=1 step 1 until 10 k=j#结果程序要指出程序出错。1.3、翻译过程1.3.1、 词法分析：词 法 分 析 是 计 算 机 科 学 中 将 字 符 序 列 转 换 为 单 词 （ Token） 序 列 的 过 程 。 进 行 语法 分 析 的 程 序 或 者 函 数 叫 作 词 法 分 析 器 （ Lexical analyzer， 简 称 Lexer） ， 也 叫 扫描 器 （ Scanner） 。 词 法 分 析 器 一 般 以 函 数 的 形 式 存 在 ， 供 语 法 分 析 器
7、 调 用 。词法分析是编译过程中的第一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。简化设计、改进编译效率、增加编译系统的可移植性。词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常武汉理工大学编译原理课程设计说明书- 5 - 数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。单词的分类主要分为五类：1. 关键字：由程序语言定义的具有固定意义的标识 符。也称为保留字或基本字。2. 标识符：用来表示程序中各种名字的字符串。3. 常 数：常数的类
8、型一般有整型、实型、布尔型、文字型。4. 运算符：如+、 、*、/ 等。5. 界限符：如逗号、分号、括号等。词法分析器输出的单词符号常表示成如下的二元式：（单词种别，单词符号的属性值）1.3.2、语法分析：语 法 分 析 是 编 译 过 程 的 一 个 逻 辑 阶 段 。 语 法 分 析 的 任 务 是 在 的 基 础 上 将 单 词 序列 组 合 成 各 类 语 法 短 语 ， 如 “程 序 ”， “语 句 ”， “表 达 式 ”等 等 .语 法 分 析 程 序 判 断 源程 序 在 结 构 上 是 否 正 确 .源 程 序 的 结 构 由 上 下 文 无 关 文 法 描 述 .语 法 分
9、析 程 序 可 以 用YACC 等 工 具 自 动 生 成 。语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。语法分析的主要工作：是识别由词法分析给出的单词序列是否是给定的正确句子（程序） 。语法分析常用的方法：自顶向下的语法分析和自底向上的语法分析两大类。此次设计中语法分析中主要通过递归下降分析法对语法分析处理过程进行控制，使输出的三地址表示的翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。递归下降法主要采用自顶向下方法，即从文法的开始符号开始进行分析，逐渐推导的往下构造语法树，使其树叶正好构造出所给定的源程序串。自顶
10、向下方法的关键是确定在推导过程中选择候选式的问题。当进行推导时，一个非终结符可能对应多个产生式，这样我们就无法事先知道应该用哪个产生式，因此实用都作了一些限制。以便在任何情况下都能确定应该用的产生式。自顶向下的主要思想是从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。武汉理工大学编译原理课程设计说明书- 6 - 词法分析程序和语法分析程序的关系：1.3.3、中间代码生成：中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。为了使编译程序有较高的目标程序质量，或要求从编译
11、程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式） 、三地址代码（三元式、四元式）和树形表示（抽象语法树） 、DAG 表示。本次课程设计要实现的是三地址表示。1.3.4、属性文法：对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产
12、生式上。形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中：G:是一个上下文无关文法；V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息；F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。 断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。 2、递归下降法递归下降法又称递归子程序法。在程序语言的语法定义中有许多采用递归定义。我们在对它进行语法分析时，编制的处理程序也采取递归的方式，可使其结构简单易读。但由于频繁地调用子程序大大地降低了分析速度。武汉理工大学编译原理课程设计说明书- 7 - 2.1、
13、递归下降法的主要思想：对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。2.2、用程序表示递归子程序的内部结构：设 A 是一个非终结符： A1 A2An 则写 (A) if charfirst(1 ) then(1 )else if charfirst(2 ) then (2 )elseif charfirst(n ) then (n)else ERROR其中 (i)表示调用处理符号串 i 的子程序。对 A 的任一右部 i 设为： i = y1 y2 yn 则定义 ( i) begin
14、(y1);(y2);(yn) end其中 yj 可分为下列两种情况（j=1,n):1) yjVT,则( yj) if char yj then ERROR else READ(char)2) yjVN,则 (yj)表示调用关于 yj 的递归子程序。23、递归下降法对文法的限制：1、任一非终结符 B 都不是左递归的，否则会产生死循环。2、对 A 的任意两个右部 i , j ,有：first(i)first(j)= 。First(i)表示 i 所能导出串的第一个符号的集合。显然，每个 i 的 first(i)是互不相同的，否则则无法判断应执行哪个 (i )。 3、三地址代码的表示：一般形式：x :
15、= y op z 如表达式 x + y z 翻译成的三地址代码序列是：武汉理工大学编译原理课程设计说明书- 8 - t1 := y z t2 := x + t1 常用的三地址表示:赋值语句 x := y op z， x := op y， x := y 无条件转移 goto L条件转移 if x relop y goto L过程调用 param x 和 call p , n过程返回 return y索引赋值 x := yi和 xi := y 地址和指针赋值 x := cout=65 else return(false); char GetChar(int i)/读取字符 char ch; ch=
16、stri; return(ch); char GetBC(char ch)/判断是不是空格或者换行，如果是，直接读取下一个字符直道不再空白为止 if(ch=32|ch=10) turn+; ch=GetChar(turn); ch=GetBC(ch);/递归实现 return(ch); else return(ch); void Concat()/连接，即为 strtoken赋值 strTokenn=ch; n+; int Reserve()/以单词为单位查找保留字，是则返回编码，不是则返回 0，用来区分标志符和保留字 if(strcmp(strToken,“ DIM0“)=0)/调用strcmp 函数实现 , return(1); else if(strcmp(strToken,“for0“)=0) return(2); else if(strcmp(strToken,“step0“)=0) return(3); else if(strcmp(strToken,“until0“)=0) return(4); else if(strcmp(strToken,“do0“)=0) return(5); else
