FOR循环语句的翻译程序设计(递归下降法、输出四元式表示)

武汉理工大学《编译原理》课程设计说明书

1、系统描述 ........................................................................................................................................................ 2

1.1、实验思想 ............................................................................................................................................ 2 1.2、设计内容 ............................................................................................................................................ 2 1.3、翻译过程 ............................................................................................................................................ 2

1.3.1、 词法分析： .................................................................................................................. 2 1.3.2、语法分析： ............................................................................................................................ 3 1.3.3、中间代码生成： .................................................................................................................... 4 1.3.4、属性文法： ............................................................................................................................ 4

2、递归下降法 .................................................................................................................................................... 4

2.1、递归下降法的主要思想： ................................................................................................................ 4 2.2、用程序表示递归子程序的内部结构： ............................................................................................ 4 2．3、递归下降法对文法的限制： .......................................................................................................... 5 3、语法制导翻译 ................................................................................................................................................ 5

3.1、翻译任务的处理过程 ........................................................................................................................ 5 3.2、语法制导翻译： ................................................................................................................................ 5 3．3、基于属性文法的处理方法 .............................................................................................................. 6 4、中间代码形式的描述及中间代码序列的结构设计 .................................................................................... 6 5、简要的分析与概要设计 ................................................................................................................................ 6

5.1、词法分析： ........................................................................................................................................ 6 5.2源代码 ................................................................................................................................................... 8 5.3 运行结果 .............................................................................................................................................. 9 6、测试方法和测试结果 .................................................................................................................................. 15

6.1测试过程 ............................................................................................................................................. 15 6.2测试结论 ............................................................................................................................................. 17 7、课程设计总结 .............................................................................................................................................. 18 8、参考文献 ...................................................................................................................................................... 19

- 1 -

武汉理工大学《编译原理》课程设计说明书

1、系统描述

1.1、实验思想

通过设计、编制、调试一个FOR循环语句的语法及语义分析程序，加深对语法及语义分析原理的理解，实现词法分析程序对单词序列的词法检查和分析，并且实现对单词序列的语法分析、语义分析以及中间代码生成。

1.2、设计内容

本设计按照要求设计出for语句的简单文法，并使用递归下降分析法对用户输入的程序进行分析和翻译。 对下列正确的程序输入：

for i=1 step 1 until 10 do k=j #

结果程序要对该输入进行词法分析，然后利用递归下降的分析法对词法分析得到的单词序列进行语法分析，经过语法制导翻译显示出等价的三地址表示的中间代码。 对于错误的程序输入，如：

For i=1 step 1 until 10 k=j# 结果程序要指出程序出错。

1.3、翻译过程

1.3.1、 词法分析：

词法分析是计算机科学中将字符序列转换为单词（Token）序列的过程。进行语法分析的程序或者函数叫作词法分析器（Lexical analyzer，简称Lexer），也叫扫描器（Scanner）。词法分析器一般以函数的形式存在，供语法分析器调用。

词法分析是编译过程中的第一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。简化设计、改进编译效率、增加编译系统的可移植性。词法分析是编制一个读单词的过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。

单词的分类主要分为五类：

1. 关键字：由程序语言定义的具有固定意义的标识 符。也称为保留字或基本字。

- 2 -

武汉理工大学《编译原理》课程设计说明书

2. 标识符：用来表示程序中各种名字的字符串。

3. 常 数：常数的类型一般有整型、实型、布尔型、文字型。 4. 运算符：如+、－ 、*、/ 等。 5. 界限符：如逗号、分号、括号等。

词法分析器输出的单词符号常表示成如下的二元式：（单词种别，单词符号的属性值）

1.3.2、语法分析：

语法分析是编译过程的一个逻辑阶段。语法分析的任务是在的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语法分析程序可以用YACC等工具自动生成。

语法分析是编译程序的核心部分,其主要任务是确定语法结构,检查语法错误，报告错误的性质和位置，并进行适当的纠错工作。语法分析的主要工作：是识别由词法分析给出的单词序列是否是给定的正确句子（程序）。语法分析常用的方法：自顶向下的语法分析和自底向上的语法分析两大类。此次设计中语法分析中主要通过递归下降分析法对语法分析处理过程进行控制，使输出的三地址表示的翻译的工作有条不紊的进行，同时识别语法分析中的语法错误。

递归下降法主要采用自顶向下方法，即从文法的开始符号开始进行分析，逐渐推导的往下构造语法树，使其树叶正好构造出所给定的源程序串。自顶向下方法的关键是确定在推导过程中选择候选式的问题。当进行推导时，一个非终结符可能对应多个产生式，这样我们就无法事先知道应该用哪个产生式，因此实用都作了一些限制。以便在任何情况下都能确定应该用的产生式。

自顶向下的主要思想是从开始符出发导出句型并一个符号一个符号地与给定终结符串进行匹配。如果全部匹配成功，则表示开始符号可推导出给定的终结符串。因此判定给定终结符号串是正确句子。

词法分析程序和语法分析程序的关系：

- 3 -

武汉理工大学《编译原理》课程设计说明书

1.3.3、中间代码生成：

中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。为了使编译程序有较高的目标程序质量，或要求从编译程序逻辑结构上把与机器无关和与机器有关的工作明显的分开来时，许多编译程序都采用了某种复杂性介于源程序语言和机器语言之间的中间语言。中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG表示。本次课程设计要实现的是三地址表示。

1.3.4、属性文法：

对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。所谓语法制导的翻译指的是在语法分析过程中，完成这些语义规则描述的动作，从而实现语义处理。 一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。形式上讲，属性文法是一个三元组 :A=(G，V，F)， 其中：

G:是一个上下文无关文法；

V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息；

F:关于属性的属性断言或一组属性的计算规则(称为语义规则) 。 断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性。

2、递归下降法

递归下降法又称递归子程序法。在程序语言的语法定义中有许多采用递归定义。我们在对它进行语法分析时，编制的处理程序也采取递归的方式，可使其结构简单易读。但由于频繁地调用子程序大大地降低了分析速度。

2.1、递归下降法的主要思想：

对每个非终结符按其产生式结构写出相应语法分析子程序。因为文法递归相应子程序也递归，子程序的结构与产生式结构几乎一致。所以称此种方法称为递归子程序法或递归下降法。

2.2、用程序表示递归子程序的内部结构：

- 4 -