编译原理实验指导书

《 编 译 原 理 》

实 验 指 导 书

适用专业：计算机科学与应用

江苏科技大学电子信息学院

2005年 2月

1

前 言

《编译原理》是计算机专业的一门核心课程，在计算机本科教学中占有十分重要的地位。由于《编译原理》课程兼有很强的理论性和实践性，并且编译程序构造的算法比较复杂，因而让学生在学习时普遍感到内容抽象、不易理解，难易掌握。但是掌握编译原理的基本理论和设计思想是非常重要的，尤其是将本课程的理论知识与计算机应用中的许多领域紧密联系与广泛应用结合。将有利于学生提高专业素质和适应社会多方面需要的能力。因此，通过理论授课和上机实践，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地加以运用。通过实验逐步提高学生的编程能力和调试程序的能力以及解决实际问题的能力。使学生培养出扎实的软件开发基本技能，并养成良好的编程风格，为进一步学习后续课程和将来从事应用软件开发奠定良好的基础。

2

实验课时具体内容安排如下：

序号 实验一 实验二 实验三 实验四 实验五

一、实验课的性质和目的

实验名称 词法分析设计 LL(1)预测分析 逆波兰表达式的产生及计算 SLR(1)语法分析设计 应用DAG进行局部优化 课时 4 3 3 4 4 必（选）做 必做 必作 必作 必做 选做 （1）深刻理解程序语言编译系统的结构及各部分的功能。 （2）熟练掌握设计和构造程序语言编译系统的基本原理和技术。 （3）能编写清晰、工整、结论正确的编译原理的源程序。

（4）能学会上机进行正确调试，并进行程序修改。即培养发现程序错误，排除错误的能力和经验。 二、实验课的基本要求：

（1）掌握编译程序的功能和结构。

（2）掌握词法分析器的设计方法与实现步骤加深对讲授内容的理解，尤其是

一些语法给定，通过上机实验帮助掌握。 （3）掌握语法分析器的设计方法与实现步骤。 （4）掌握符号表和存储空间的组织。 （5）掌握代码优化的作用与实现方法 （6）掌握错误的诊断和校正方法。 三、主要实验教学方法

实验前，由任课教师落实实验任务，每个学生必须事先完成好程序的设计的源程序编写工作。实验课上对疑难点作集中辅导。实验过程中随时针对不同的情况作个别启发式辅导。实验后，学生撰写并提交实验报告。最后，由实验教师根据每个学生的编程、上机调试能力、编程能力和实验结果及实验报告综合评定学生的实验成绩。

3

四、实验的重点与难点：

对词法分析设计、语法分析设计和中间代码的产生、代码优化等是本课程实践性环节的重点和难点。 五、实验教学手段

通过本课程的课内实验，使学生上机编程、调试来验证和巩固所学的编译原理理论及概念，逐步掌握词法分析的设计方法及实现技术。软件实验室为为每个学生提供了一台具有WINDOWS 98/XP/NT/2000操作系统的计算机和VC++/VB/JAVA/TC等软件环境。 六、实验考核成绩

《编译原理》是一门实践性很强的课程,要求在教学过程中必须十分重视实践性环节，包括平时练习作业、记分作业、上机实验等。尤其是要注重上机实验的重要性，必须通过上机实践才能真正掌握所学的知识和技能，所以要特别强调实验也将作为考核成绩的依据。实验成绩占平时成绩的20%。每次必须完成规定的实验内容，并及时写出实验报告。 七、实验报告内容：

1．实验题目、班级、学号、姓名、完成日期。 2．写出数据结构及生成的算法描述。 3．画出算法流程图。

4．打印出源程序代码和给出测试的结果。 5．实验的评价、收获与体会。

写出在调试过程中出现的问题和解决的措施；分析讨论对策成功或失败的原因。

4

目 录

前 言......................................................... 2 目 录......................................................... 5 实验一:词法分析设计.............................................. 6 实验二：LL(1)分析法............................................. 13 实验三：逆波兰式的产生及计算.................................... 16 实验四：LR(1)分析法 ............................................. 21 实验五：应用DAG进行局部优化 .................................. 26

5

实验一 词法分析设计

实验学时：4 实验类型：综合 实验要求：必修 一、实验目的

通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。

二、实验内容

用VC++/VB/JAVA语言实现对C语言子集的源程序进行词法分析。通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；若遇到错误则显示“Error”，然后跳过错误部分继续显示 ；同时进行标识符登记符号表的管理。 以下是实现词法分析设计的主要工作： （1）从源程序文件中读入字符。

（2）统计行数和列数用于错误单词的定位。 （3）删除空格类字符，包括回车、制表符空格。

（4）按拼写单词，并用（内码，属性）二元式表示。(属性值——token的机内表示)

（5）如果发现错误则报告出错

（6）根据需要是否填写标识符表供以后各阶段使用。 单词的基本分类：

6

 关键字：由程序语言定义的具有固定意义的标识符。也称为保留字例如

if、 for、while、printf ； 单词种别码为1。     

标识符：用以表示各种名字，如变量名、数组名、函数名； 常数： 任何数值常数。如 125, 1,0.5,3.1416； 运算符：+、-、*、/；

关系运算符： <、<=、= 、>、>=、<>； 分界符： ；、，、（、）、[、]；

三、词法分析实验设计思想及算法 1、主程序设计考虑： 

程序的说明部分为各种表格和变量安排空间。

在具体实现时，将各类单词设计成结构和长度均相同的形式，较短的关键字后面补空。

k数组------关键字表，每个数组元素存放一个关键字（事先构造好关键字表）。 s 数组------存放分界符表（可事先构造好分界符表）。为了简单起见，分界符、算术运算符和关系运算符都放在s表中（编程时，应建立算术运算符表和关系运算符表，并且各有类号），合并成一类。 id 和ci 数组分别存放标识符和常数。 instring 数组为输入源程序的单词缓存。 outtoken 记录为输出内部表示缓存。 还有一些为造表填表设置的变量。  表。 

主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；主程序开始后，先以人工方式输入关键字，造k表；再输入分界符等造 p

接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。 例如，把每一单词设计成如下形式: (type,pointer)

其中type指明单词的种类，例如：Pointer指向本单词存放处的开始位置。 还有一些为造表填表设置的变量。  表。

主程序开始后，先以人工方式输入关键字，造k表；再输入分界符等造 p

7

 主程序的工作部分设计成便于调试的循环结构。每个循环处理一个单词；

接收键盘上送来的一个单词；调用词法分析过程；输出每个单词的内部码。 例如，把每一单词设计成如下形式: (type,pointer)

其中type指明单词的种类，例如：Pointer指向本单词存放处的开始位置。

8

词法分析设计流程图

2、词法分析过程考虑

 根据输入单词的第一个字符（有时还需读第二个字符）， 判断单词类，产生类号：以字符k表示关键字；id表示标识符； ci表示常数；s 表示分界符。 

对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，

如表中已有该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组 id 中，将常数变为二进制形式存入数组中 ci 中，并记录其在表中的位置。 lexical 过程中嵌有两个小过程：一个名为 getchar，其功能为从 instring 中按顺序取出一个字符，并将其指针 pint 加 1 ；另一个名为 error，当出现错误时，调用这个过程，输出错误编号。 

要求：所有识别出的单词都用两个字节的等长表示，称为内部码。第

一个字节为 t ，第二个字节为 i 。 t 为单词的种类。关键字的 t=１；分界符的 t=２；算术运算符的 t=３；关系运算符的 t=４；无符号数的 t=５；标识符的 t=６。i 为该单词在各自表中的指针或内部码值。表 1 为关键字表；表 2 为

9

分界符表；表 3 为算术运算符的 i 值；表 4 为关系运算符的 i 值。

10

取字符和统计字符行列位置子程序

四、实验要求

1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、将标识符填写的相应符号表须提供给编译程序的以后各阶段使用。 3、根据测试数据进行测试。测试实例应包括以下三个部分:  全部合法的输入。  各种组合的非法输入。  由记号组成的句子。 4、词法分析程序设计要求输出形式: 例：输入VC++语言的实例程序：

If i=0 then n++; a﹤= 3b %); 输出形式为：

单词 二元序列 类 型 位置（行，列） （单词种别，单词属性）

for (1,for ) 关键字 （1，1） i ( 6,i ) 标识符 （1，2）= ( 4，= ) 关系运算符 （1，3） 11

0 ( 5，0 ) 常数 （1，4） then ( 1，then) 关键字 （1，5） n (6,n ) 标识符 （1，6） ++ Error Error （1，7） ； ( 2, ; ) 分界符 （1，8） a (6,a ) 标识符 （2，1） ﹤= (4,<= ) 关系运算符 （2，2） 3b Error Error （2，4） % Error Error （2，4） ) ( 2, ) ) 分界符 （2，5） ； ( 2, ; ) 分界符 （2，6）

五、实验步骤

1、根据流程图编写出各个模块的源程序代码上机调试。

2、 编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的词法分析程序；直至能够得到完全满意的结果。 3、书写实验报告 ；实验报告正文的内容：  

功能描述：该程序具有什么功能？

程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数

之间的调用关系图。   

12

详细的算法描述（程序总体执行流程图）。 给出软件的测试方法和测试结果。

实验总结 （设计的特点、不足、收获与体会）。

实验二 LL(1)分析法

实验学时：2 实验类型：综合 实验要求：必修 一、实验目的

通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。有利于提高学生的专业素质，为培养适应社会多方面需要的能力。

二、实验内容

 根据某一文法编制调试 LL （ 1 ）分析程序，以便对任意输入的符号串

进行分析。

 构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分

析程序。

 分析法的功能是利用LL（1）控制程序根据显示栈栈顶内容、向前看符号

以及LL（1）分析表，对输入符号串自上而下的分析过程。

三、 LL（1）分析法实验设计思想及算法



模块结构：

（1）定义部分：定义常量、变量、数据结构。

（2）初始化：设立LL(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；

（3）控制部分：从键盘输入一个表达式符号串；

（4）利用LL(1)分析算法进行表达式处理：根据LL(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。

13

四、实验要求

1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。

3、对下列文法，用LL（1）分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|—TG （3）G->ε （4）T->FS （5）S->*FS|/FS （6）S->ε （7）F->(E) （8）F->i 输出的格式如下：

14

五、实验步骤

1、根据流程图编写出各个模块的源程序代码上机调试。

2、 编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的LL(1)分析程序；直至能够得到完全满意的结果。 3、书写实验报告 ；实验报告正文的内容：

 写出LL（1）分析法的思想及写出符合LL（1）分析法的文法。  程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数

之间的调用关系图。

 详细的算法描述（程序执行流程图）。  给出软件的测试方法和测试结果。

 实验总结 （设计的特点、不足、收获与体会）。

15

实验三 逆波兰表达式的产生及计算

实验学时：2 实验类型：验证 实验要求：必修 一、实验目的

非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

二、实验内容

将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。

三、逆波兰表达式的产生及计算实验设计思想及算法



逆波兰式定义

将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。 

产生逆波兰式的前提

中缀算术表达式 

逆波兰式生成的设计思想及算法

(1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

(3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

(4)如果不是数字，该字符则是运算符，此时需比较优先关系。

做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。

16

(5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

运用以上算法分析表达式(a+b*c)*d的过程如下： 当前符号 （ a + b * c ) ) ) *

输入区 a+b*c)*d +b*c)*d *c)*d c)*d )*d *d *d *d d 符号栈 ( ( (+ (+ (+* (+* (+ ( 输出区 a a ab ab abc abc* abc* abc*+ 17

d * * abc*+ abc*+d abc*+d (1)构造一个栈，存放运算对象。

(2)读入一个用逆波兰式表示的简单算术表达式。

(3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。

(4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。  逆波兰式计算的设计思想及算法

四、实验要求

1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。

18

2、如果遇到错误的表达式，应输出错误提示信息。 3、程序输入/输出实例：

 输入以#结束的中缀表达式(包括+ - */（）数字#)。 例：(1)（a+b） (2)(a+b*c) (3) B+(-(A))*C 输出逆波兰表达式的格式如下： (1) (a+b) ;→ab+)( (2)(a+b*c)→abc*+)(

(3)B+(-A(A)) *C→BA)(-)(C*+

 输入中缀表达式并计算结果：a* (b+c)+(-d)#； 输出逆波兰式:abc+*d@+ 输入：a=3; b=1;c=2;d=5; 计算结果为:4

五、实验步骤

19

1、根据流程图编写出各个模块的源程序代码上机调试。

2、 编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的逆波兰式的产生及计算程序；直至能够得到完全满意的结果。 3、书写实验报告 ；实验报告正文的内容：  

描述逆波兰式的产生及计算程序的设计思想。

程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数

之间的调用关系图。  详细的算法描述（程序执行流程图）。  给出软件的测试方法和测试结果。

 实验总结 （设计的特点、不足、收获与体会）。

20

实验四 LR(1)分析法

实验学时：2 实验类型：验证 实验要求：必修

一、实验目的

构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

二、实验内容

对下列文法，用LR（1）分析法对任意输入的符号串进行分析： （1）E- E+T （2）E- E—T （3）T- T*F （4）T- T/F （5）F- (E) （6）F- i

三、LR（1）分析法实验设计思想及算法

(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 (2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。

(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 分析器的动作就是由栈顶状态和当前输入符号所决定。  LR分析器由三个部分组成：

21

 其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用

GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。

 ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种

可能：

(1)移进：

action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。 (2)归约：

action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。 (3)接受acc:

当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。 (4)报错:

当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。

22

四、实验要求

1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。 2、如果遇到错误的表达式，应输出错误提示信息。 3、程序输入/输出实例：

输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串 输出过程如下：

步骤 状态栈 符号栈 剩余输入串 动 作 1 0 # i+i*i# 移进

i+i*i的LR分析过程 步骤 1 2 3 4 状态栈 0 05 03 02 符号栈 # #i #F #T 输入串 动作说明 ACTION[0,i]=S5,状态5入栈 r6: F→i归约,GOTO(0,F)=3入栈 r4: T→F归约,GOTO(0,T)=3入栈 r2: E→T归约,GOTO(0,E)=1入栈 i+i*i# +i*i# +i*i# +i*i# 23

5 6 7 8 9 10 11 12 13 14 01 016 0165 0163 0169 01697 016975 0169710 0169 01 #E #E+ #E+i #E+F #E+T #E+T* #E+T*i +i*i# i*i# *i# *i# *i# i# # ACTION[1,+]=S6,状态6入栈 ACTION[6,i]=S5,状态5入栈 r6: F→i归约,GOTO(6,F)=3入栈 r4: T→F归约,GOTO(6,T)=9入栈 ACTION[9,*]=S7,状态7入栈 ACTION[7,i]=S5,状态5入栈 r6:F→i归约,GOTO(7,F)=10入栈 r3: T→T*F归约,GOTO(6,T)=9入栈 r1:E→E+T,GOTO(0,E)=1入栈 Acc：分析成功 #E+T*F # #E+T #E # # 4、输入符号串为非法符号串(或者为合法符号串)

算术表达式文法的LR分析表 状 态 0 1 2 3 4 5 6 7 8 9 10 11 i S5 S5 S5 S5 + S6 r2 r4 r6 S6 r1 r3 r5 * S7 r4 r6 S7 r3 r5 ACTION ( S4 S4 S4 S4 ) r2 r4 r6 S11 r1 r3 r5 # acc r2 r4 r6 r1 r3 r5 E 1 8 GOTO T 2 2 9 3 3 10 F 3 五、实验步骤

1、根据流程图编写出各个模块的源程序代码上机调试。

24

2、编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的LR(1)语法分析程序；直至能够得到完全满意的结果。 3、书写实验报告 ；实验报告正文的内容：  描述LR(1)语法分析程序的设计思想。

 程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数

之间的调用关系图。

 详细的算法描述（程序执行流程图）。  给出软件的测试方法和测试结果。

 实验总结 （设计的特点、不足、收获与体会）。

25

实验五 应用DGA进行局部优化

实验学时：2 实验类型：设计 实验要求：必修

一、实验目的

使学生通过本次实验，能够对程序优化技术有一定的了解，掌握利于DGA进行局部优化的方法。

二、实验内容

对给定的四元式序列： （1）：T1=A*B （2）：T2=3/2 （3）：T3=T1-T2 （4）：X=T3 （5）：C=5 （6）：T4=A*B （7）：C=2 （8）：T5=18+C （9）：T6=T4*T6 （10）：Y=T6

要求：构造其相应的DGA，并利于DGA进行了删除无用赋值、消除公共子表达式、合并已知量等到局部优化技术进行优化；再从所得到的DGA重建四元式序列。

三、LR（1）分析法实验设计思想及算法

由基本块构造DGA的算法描述如下： for (i=0; i{

26

取出第i四元式Qi if (NODE(B)==NULL) {

建立一个以B为标记的叶结点，其编号为NODE（B） switch(Qi) {

case 0: NODE(B)=n; break;

case 1: if (NODE(B)是常数为标记的叶结点) {

执行P=op B;

if (NODE(B)是处理Qi时新建立的结点) 删除 NODE（B） if (NODE(P)==NULL) {建立NODE（P）；NODE（P）=n} } else {

if (DGA中已有以NODE（B）为惟一后继且标记为op的结点) 令已有结点为n; else

建立新结点n; } break;

case 2: if (NODE(C)==NULL) {

构造以C为标记的新结点；

if (NODE(B)为常数结点 && NODE(C)为常数结点) {

执行P=B op C;

if (NODE(B)或NODE(C)是处理Qi时新建立的结点) 删除之； if (NODE(P)==NULL) {建立NODE（P）；NODE（P）=n} break;

27

} } else

if (DGA中已有以NODE（B）和NODE（C）分别为左、右后继，

且标记为op的结点)

令已有结点为n; else

建立新结点n; break;

}

if (NODE(A)==NULL)

{

把A附加到结点n; NODE(A)=n; } else {

从NODE（A）的附加标识符集中将A删去； 把A附加到结点n; NODE(A)=n; } } }

四、实验要求

1、对题目给定的的四元式序列能够实现DGA 优化，使之不再出现题目所列之待优化情形；

2、能够输出优化后的四元式序列；

3、在部分同学完成实验题目的基础上，对实验程序进行改造，使之可以成为一个和般性的DGA优化程序。

28

五、实验步骤

1、根据流程图编写出各个模块的源程序代码上机调试。

2、编制好源程序后，用所给题目为例对系统进行全面的上机测试，并通过所设计的DGA优化分析实验程序；直至能够得到完全满意的结果。

3、书写实验报告 ；实验报告正文的内容：  描述DGA优化分析程序的设计思想。

 程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数

之间的调用关系图。

 详细的算法描述（程序执行流程图）。

 给出软件的测试方法和测试结果。

 实验总结 （设计的特点、不足、收获与体会）。

29