编译原理实验手册1.4版

1、兰州大学计算机科学与技术专业 编译原理实验手册(V1.4) 第一节概述 一、实验目的 编译原理是一门实践性很强的课程，但由于课时所限，只能在课堂上讲授一些 通用的原理和方法。而为了真正学好这门课程，必须自己动手构造出一个编译器， 才能对书里讲到的原理、方法和技术有较全面的体会，才能对学生以后的程序设计 和解决实际问题的能力有所帮助。 实际的编译程序是十分复杂的，有时由多达十几万条指令组成。为此，编译原 理的实践教学，采用简化编译过程的办法，选择最关键的三个环节一一词法分析、 语法分析、语义分析和中间代码产生，每个环节作为一个实践课题，逐步深入，扩 展功能，直至得到一个简单实用的编译器。本实验不

2、涉及到优化。 二、实验内容 任何一个实用的高级语言，其语法都比较复杂，如选其作为源语言，很难实践 全过程。故本试验将定义一个简化的语言 PASCALS言的一个子集作为源语言， 分三个课题、一步步地构造出它的编译程序。所有试验项目前后贯穿这一条主线进 行。本实验共进行6周，每周3学时，共18学时。本实验主要包括以下三个课题： 1. 词法分析：以源程序为输入，输出单词符号流； 2. 语法分析：以源语言的文法为依据，调用词法分析器，使用递归下降分析 法或算符优先分析法或LR(1)分析法，构造能识别源语言各种语法结构的语 法分析器；(语发单元，语法树碑) 3. 语义分析和中间代码产生：使用语法制导翻译

3、技术，对源语言程序进行简 单的翻译，输出四元式序列。 在本节的第三部分给出了 PASCALS言两个子集的文法，对这些文法稍加变换， 即可获得用于语法分析的LL(1)文法或LR(1)文法。学生可以直接选择一个作为编译 器的源语言，也可以对这些文法进行改造，以获得能力更为强大的源语言。学生也 可以自己设计源语言，来完成这些题目；唯一的要求是源语言必须包含三种基本的 程序设计结构(顺序、选择、循环)和至少两种不同的数据类型。 本实验要求： 所有的输入输出均采用文件形式。 *独立完成。 语言不限，开发工具不限；但必须有可运行的程序和规范的注释。 三、PASCA语言子集的文法 由于Pascal语言结构严

4、谨，层次清晰，语法与C语言接近，也便于理解，因此 本实验抽取Pascal语言的一个子集，稍加改造，作为源语言，姑且命名为LittleP 。 一个LittleP程序由一系列全局数据声明和一个主程序体组成。所有数据采用静态 存储分配，没有I/O ,只支持一种基本数据类型：无符号整数。 Procedure，procedurehead，procedurebody，variable,declare,compound, Statment，definition,list,empty,variablename,style,statement,Block， con ditio n,cycle,arithmeti

5、cexpressio n,relatio nexpressio n,term,add,muti, factor, nu m,ide ntifier,letter,digit,e ndue赋予 1. LittleP 的文法： 程序f程序首部程序体. 程序首部f program程序名; 程序体变量声明复合语句 变量声明f var变量定义列表|空 变量定义列表 f 变量定义变量定义列表|变量定义; 变量定义f变量名列表： 类型 ; 变量名列表 f 变量名|变量名，变量名列表 类型 f in teger 复合语句f begin语句块end 语句块f语句|语句；语句块 语句f赋值语句|条件语句|循环语句

6、|复合语句|空 赋值语句f左部:=右部 左部f变量名 右部f算术表达式 条件语句f if 关系表达式then语句else语句 循环语句f while关系表达式do语句 关系表达式 f算术表达式关系运算符算术表达式 算术表达式 f 项| 算术表达式加运算符项 项 f 因子|项乘运算符因子 因子f变量名| （算术表达式）|整数 程序名-标识符 变量名-标识符 标识符-字母丨标识符字母丨标识符数字 整数数字I整数数字 关系运算符f | = | | = | 1 加运算符f + | - 乘运算符f * | / 字母f a | b| | x| y| z 数字f 1|2|3|4|5|6|7|8|9|0 2.

7、 在此基础上加以扩充，可得功能较强的一个LittleP 语言的超集：LittleP+ 该语言引入了实数、一维数组和过程、函数的定义，参数传递采用传值方式。另 外，加入了 I/O支持，编译器提供两个系统函数：read()和write()。 程序f程序首部程序体. 程序首部f program程序名； 程序体f变量声明 分程序声明 复合语句 变量声明f var变量定义列表|空 变量定义列表 f 变量定义变量定义列表|变量定义; 变量定义f变量名列表： 类型 ; 变量名列表 f 变量名|变量名，变量名列表 类型 f 基本类型|数组 基本类型 f integer | real 数组 f array 下界

8、.上界of 基本类型 下界 f 整数 上界 f 整数 分程序声明 f 分程序分程序声明|空 分程序f 分程序首部变量声明复合语句 分程序首部f procedure过程名( 形参列表 ); | function 函数名( 形参列表 ): 基本类型; 形参列表 f 形参定义,形参列表|形参定义|空 形参定义f变量名列表： 基本类型 复合语句f begin语句块end 语句块f语句I语句；语句块 语句f赋值语句|条件语句|循环语句 |过程调用语句I复合语句I读写语句I空 赋值语句f左部:=右部 左部变量名I变量名算术表达式 右部f算术表达式 条件语句f if 关系表达式then语句else语句 循环

9、语句r while关系表达式do语句 过程调用语句-过程名（ 实参列表 ） |函数名（ 实参列表 ） 实参列表 f 算术表达式| 算术表达式,实参列表|空 读写语句f read （ 变量名列表 ）| write （实参列表 ） 关系表达式 f算术表达式关系运算符算术表达式 算术表达式 f 项| 算术表达式加运算符项 项 f 因子|项乘运算符因子 因子f变量名I （算术表达式）I 函数名（实参列表） I变量名算术表达式I整数I实数 程序名f标识符 变量名f标识符 过程名f标识符 函数名f标识符 标识符f字母I标识符字母I标识符数字 整数f数字I整数数字 实数f整数.整数 关系运算符f | = |

10、 | = | | 加运算符f + | - 乘运算符f * | div | mod 字母f a|b| |x|y|z| A B| |X| Y| Z 数字f 1|2|3|4|5|6|7|8|9|0 3. 对源程序语法的其他说明： a）出现在 里的所有字符作为注释跳过。 b）各单词符号之间的空格可有可无，但关键字和标识符必须分隔开来。 c）过程没有返回值，只能出现在过程调用语句中；函数有且只有1个返回值, 只能出现在算术表达式中或作为赋值语句的右部。函数返回值通过函数名 带回，因此在函数体内必须给函数名赋值。 d）标识符的长度不得超过8个字符。 e）关键字保留，包括read和write。 四、实验要求

11、： 每个课题完成后写出实验报告。实验报告应该包括: .程序设计时考虑的算法和主要的数据结构； 可执行的程序 至少2个测试用例，包括： 至少1个合法的源程序及其运行结果； 至少1个非法的源程序及其错误报告。 第二节词法分析 一、目的与要求 1 .目的 通过设计、调试词法分析程序，实现从源程序中分离出各种单词的方法；加深 对课堂教学的理解，尤其是对正规式、有穷自动机的原理和用途的理解；为以后软 件开发过程中设计高效率的扫描器打下基础。 2 .要求 应有适当的预处理。 输入源程序，输出定长单词符号流，均采用文件形式。 -针对选定的源语言，构造识别其合法单词符号的词法分析器。 *实现时可以借助LEX

12、（如何使用请参考教材并上网搜索资料）。 应考虑到后续阶段的需要，合理设计词法分析器的结构。 *本实验应在一周内完成。 、设计步骤（要求文档） 1. 问题分析： 分析源语言的文法，找出各种词法单位的构词规则。 工作流程：构词规则（-正规式-NFADFA 一状态转换图一程序 ； （算法的一部分 构词规则状态转换图程序 。 预处理：有哪些预处理工作要做。 2. 总体设计： 输入输出缓冲区，输出格式（等长二元式序列）； 表格设计（设计几张表，每张表登记什么信息： 关键字表 算符、分隔符表 变量表：简单变量、数组、过程与函数 错误信息表（扫描一遍源程序，登记错误信息，最后再输出到文件） 出错处理：错误位

13、置、错误消息格式、错误恢复等。 3. 程序流程设计：明确程序所使用的主要算法，一般以伪代码或程序流程图表 示。图1给出了一个程序流程图的例子，作为参考。 4. 编码与测试：编写程序并调试通过，然后自己设计至少3个测试用例。测试 用例包括两部分：输入（源程序代码）和预期结果（运行结果或错误信息）。 5. 编写实验报 初始化操作 读源程序字符 Y N 是 Y 是数字? 常数 分析程序 其它单词 分析程序 关键字和标识符 分析程序 N N Y 输出单词 的内部表示 出 口 是否结束? 1词法分析程序流程图 三、扩充 有余力的同学，可适当扩大分析对象。譬如: 1. 加入更多的基本类型，如：考虑引入布尔

14、型变量和逻辑运算 2. 加入复杂的数据类型，如：类似java中的String类型。 3. 加入二义性文法结构，如：单分支和双分支的选择语句。 第三节语法分析 一、目的与要求 1. 目的 通过设计、编写、调试一个典型的语法分析程序，实现对词法分析程序所提供 的单词序列进行语法分析和检查，进一步掌握常用的语法分析方法的实现技术。 2. 要求 调用词法分析器，分析源程序的语法结构（区分出各种语法结构），检查 语法错误。 推荐使用算符优先分析算术表达式，用递归子程序法分析其他各种语法 结构，如赋值语句、IF语句、WHILE语句等。也可以使用LR分析法完 成这些工作，实现时可以借助 YACC （如何使用

15、请参考教材并上网搜索 资料）0 输入文本文件形式的源程序；识别出程序中主要的语法结构，以注释的 形式给出简单的说明信息，如“变量声明语句”、“ IF语句”、“循环开始”、 “循环结束”等。若有错误，则在相应位置给出错误提示（要求比这要高 才行）0 *本课题应在两周内完成。因时间紧张，建议采用增量开发模式：从简单 到复杂、能力逐渐增强。 、设计步骤 1. 问题分析： 使用哪种语法分析方法？单独使用递归下降分析法可以完成任务吗？ 从文法中提炼出主要的语法结构，如：程序、变量声明、分程序声明、 复合语句、IF语句、算术表达式等，认真分析他们的语法结构。 如何利用前面构造的词法分析器和相关表格？ 考虑

16、错误处理的方法。 2. 总体设计： 对文法进行必要的等价变换，使之符合所选语法分析方法的要求。 若有必要，对上次实验后得到的词法分析器及相关符号表进行调整。 针对产生算术表达式（关系表达式）的文法，构造算符优先关系表，在此 基础上，编写一小段程序，分析这类语法结构。（算法示例见附录一） 针对各种语法结构，逐一产生其递归下降分析的状态转换图， 再一一翻译 为程序段。（算法示例见附录二） 设计输出的形式。 将前面的工作组合起来，形成一个完整的语法分析器。 3. 程序流程设计。 4. 编码和测试：编写代码，调试通过，并设计测试用例。 5. 编写实验报告。 三、程序流程示例： 题目：递归下降法分析表达

17、式（此题目仅供参考，而且不完全准确） 1. 分析对象的BNF定义如下： 算术表达式f项|算术表达式+项|算术表达式项 项- 因式 |项*因式 |项/因式 因式- T变量 1 （算术表达式 ) 变量- T字母 字母- - A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z 2.用递归下降法分析上述算术表达式的框图，如图2所示 返回 (b)(c) (d) 取ST的第一个 字符SYM 取ST首字符除去 后的字符串ST (e) 返 回 (f) 图2 递归下降法分析表达式之框图 (a) ZC过程；(b) E过程；(c) T过程； (d) F过程；(e)

18、函数过程 SYM ； (f)过程ADVANCE 这里，ZC过程为总控程序，主要完成： 通知外界键入算术表达式； 控制E过程分析算术表达式； 根据分析结果之正误，分别通知外界不同的信息。 ZC过程被设计成可以分析无穷多个算术表达式。E、T和F三个过程分别对应 算术表达式、项和因式三个产生式的处理。它们用到两个公共过程。一 个是函数过程SYM，它负责从输入字符串ST中取出下一个字符，并存入 SYM中 等待分析。另一个过程 ADVANCE负责剔除ST中的首字符。 四、扩充 有余力的同学，可适当扩大分析对象。譬如： 1. 加入for循环语句： for i:=1 to 5 do beg in dosom

19、eth in g() end ; 2. 引入二义性文法： stmt if cond then stmt else stmt | if cond then stmt 3. 加强语法检查，尽量 多 和 确切 地指出各种错误。 第四节 语义分析和中间代码产生 一、目的与要求 1. 目的 通过上机实习，加深对语法制导翻译和运行时存储空间分配的理解，掌握将语 法分析所识别的语法范畴变换为某种中间代码的语义翻译方法。 2. 要求 采用语法制导翻译技术。 可以考虑实现简单的静态语义检查。 语义分析的对象重点考虑经过语法分析后已是正确的语法范畴，程序设计的 重点是语义子程序的设计。 中间代码选用四元式。 以两

20、周内完成为宜。 3. 源语言的语法结构大致可分为以下六类： 声明语句：简单类型、复杂类型及其数据空间特性（如全局数据、局部数据 等），以及过程声明。重点是符号表的操作。 顺序结构：典型代表是两类表达式（算术表达式、布尔表达式）及相应的赋 值语句。重点是算术表达式的翻译方法（各种属性值的计算）。 控制结构：if语句。重点是跳转的地址问题（拉链返填）。 子程序结构：过程和函数的调用。重点是参数传递和返回地址（活动记录）。 循环结构：while语句。重点是循环的优化（本实验暂不涉及）。 格式语句：主要指输入输出语句的格式加工。在LittleP+中，read（a,b,c康示 从键盘读入三个无符号整数；

21、write（x, Y+2）表示向屏幕打印两个表达式的值。 、设计步骤 1. 问题分析： 如何把语法分析和语义分析结合起来（语义子程序的处理时机）； 如何设计语义子程序来产生四元式； 有哪些静态语义检查工作？（应着重考虑实现以下几点：） i. 标识符必须先说明，再使用； ii. 同一作用域内不得重复定义（在符号表中记录标识符的作用域）； iii. 操作数与操作符的类型匹配 a）定义在integer上的运算：+ - * div mod和关系运算符; b）定义在boolean上的运算：not or and ； c）赋值运算符：=两端的类型应该相同。 iv. 对于不满足上述规则的，应给出错误提示。 2

22、. 总体设计： 对文法进行必要的等价变换，并为每条产生式添加语义子程序。 针对表达式的产生式，自下而上地计算其综合属性。 针对各种语句的产生式，自上而下地计算其继承属性。 将各种语法结构翻译为四元式序列(四元式的格式见本节第四部分)。 把四元式按顺序编号，输出到文件。 3. 程序流程设计：核心是语法制导翻译的实现算法。 4. 编码与测试。 5. 编写实验报告。 三、算法示例 1. 题目：在对简化的算术表达式进行语法分析的同时生成四元式(仅作参考)。 2. 四元式生成程序的核心部分(指表达式、项和因式的处理)的算法，可描述如下: PROCEDURE E; BEGIN E1PLACE:=T; WH

23、ILE SYM=+ OR - DO BEGIN ADVANCE; E2PLACE:=T; T1:=NEWTEMP; GEN( ,E1PLACE,E2PLACE,T1); E1PLACE:=T1 END; RETURN(E1PLACE) END; PROCEDURE T; BEGIN T1PLACE:=F; WHILE SYM=* OR 7 DO BEGIN ADVANCE: T2PLACE:=F; T1:=NEWTEMP; GEN(*/,T1PLACE,T2PLACE, T1); T1PLACE:=T1 END; RETURN(TIPLACE) END; PROCEDURE F: BEGIN

24、IF SYM= 标识符 THEN BEGIN ADVANCE; RETURN(ENTRY(i) END ELSE IF SYM=( THEN BEGIN ADVANCE; PLACE:=E; IF SYM=) THEN BEGIN ADVANCE; RETURN(PLACE) END ELSE ERROR END ELSE ERROR END. 这里： E表达式；T项；F因子； ADVANCE 将输入串指针调整至指向下一个输入字符； NEWTEMP分配一个新的工作单元； GEN 将一个四元式填入四元式表； ENTRY查找变量名表，并获得名字所在位置值。 四、建议生成的四元式统一采用如下的形式：

25、 形如x := y op z的赋值语句，其中op是二元运算符；或者形如 x := op z的赋 值语句，其中op是not。 形如x:=y的复制语句，将y的值复制给x。 无条件跳转goto L , L是接下来要执行的四元式的编号或地址。 条件跳转jump x L ,若x为真，则跳转至L所指的四元式；否则顺序执行。 过程调用系列： 传参数param x，有n个参数就生成n条传参数四元式； 过程调用call p, n，其中：p是过程或函数名，n表示参数的个数； 返回值return y 。 形如x := yi和xi := y的变址赋值语句。 读写语句： 传参数param x，有n个参数就生成n条传参数

26、四元式； 过程调用call read/write, n，其中n表示参数的个数。 附录 算符优先分析算法示例 Tree term2Rest( Tree t , i nt min prec) / min prec is the lowest precede nee of all binary operators. Tree odStack = newOdStack(); /stack of operands; int opStack = newOpStack(); /stack of operators. int top = 0;/top poin ter of stack. odStack0 =

27、 t ; int startPos = S.pos ;/ S is a sca nn er. It retur ns a toke n and its positi on everytime . /topOp is always the top eleme nt of opStack. Its in itial value iserror. int topOp = ERROR; while ( prec( S.toke n) = min prec) 移进 opStacktop = topOp; top+; topOp = S.toke n; int pos = S.pos ; S.n extToke n(); odStacktop = term();/ term()分析表达式中的项” 规约 while ( top0 top-; topOp = opStacktop; 附录二递归下降分析算法示例 Syn taxTree* Parser:Stateme nt() Syn taxTree *tree = NULL; switch(curre ntToke n.type) case I