编译原理实验指导书李宏芒Word格式.docx
《编译原理实验指导书李宏芒Word格式.docx》由会员分享，可在线阅读，更多相关《编译原理实验指导书李宏芒Word格式.docx（62页珍藏版）》请在冰点文库上搜索。
实验前，由任课教师落实实验任务，每个学生必须事先独立完成好程序的设计的源程序编写工作。
实验课上对疑难点作集中辅导。
实验过程中随时针对不同
的情况作个别启发式辅导。
实验后，学生撰写并提交实验报告。
最后，由实验教师根据每个学生的编程、上机调试能力、编程能力和实验结果及实验报告综合评定学生的实验成绩。
四、实验的重点与难点：
对词法分析设计、语法分析设计和中间代码的产生、代码优化等是本课程实践性环节的重点和难点。
五、实验教学手段
通过本课程的课内实验，使学生上机编程、调试来验证和巩固所学的编译原理理论及概念，逐步掌握词法分析的设计方法及实现技术。
软件实验室为为每个学生提供了一台具有WINDOWS98/XP/NT/2000操作系统的计算机和
VC++/VB/JAVA/TC等软件环境。
六、实验考核成绩
《编译原理》是一门实践性很强的课程,要求在教学过程中必须十分重视实践性环节，包括平时练习作业、记分作业、上机实验等。
尤其是要注重上机实验的重要性，必须通过上机实践才能真正掌握所学的知识和技能，所以要特别强调实验也将作为考核成绩的依据。
实验成绩占平时成绩的20%。
每次必须完成规定的实验内容，并及时写出实验报告。
七、实验报告内容：
1．实验题目、班级、学号、姓名、完成日期。
2．写出数据结构及生成的算法描述。
3．画出算法流程图。
4．打印出源程序代码和给出测试的结果。
5．实验的评价、收获与体会。
写出在调试过程中出现的问题和解决的措施；
分析讨论对策成功或失败的原因。
实验一词法分析设计
实验学时：
实验类型：
综合实验要求：
必修
一、实验目的
通过本实验的编程实践，使学生了解词法分析的任务，掌握词法分析程序设计的原理和构造方法，使学生对编译的基本概念、原理和方法有完整的和清楚的理解，并能正确地、熟练地运用。
二、实验内容
用VC++/VB/JAVA语言实现对C语言子集的源程序进行词法分析。
通过输入源程序从左到右对字符串进行扫描和分解，依次输出各个单词的内部编码及单词符号自身值；
若遇到错误则显示“Error”，然后跳过错误部分继续显示；
同时进行标识符登记符号表的管理。
以下是实现词法分析设计的主要工作：
（1）从源程序文件中读入字符。
（2）统计行数和列数用于错误单词的定位。
（3）删除空格类字符，包括回车、制表符空格。
（4）按拼写单词，并用（内码，属性）二元式表示。
（属性值——token的机内表示）
（5）如果发现错误则报告出错
（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指向本单词存放处的开始位置。
2、词法分析过程考虑
词法分析设计流程图
u根据输入单词的第一个字符（有时还需读第二个字符），判断单词类，产生类号：
以字符k表示关键字；
id表示标识符；
ci表示常数；
s表示分界符。
◆对于标识符和常数，需分别与标识符表和常数表中已登记的元素相比较，如表中已有该元素，则记录其在表中的位置，如未出现过，将标识符按顺序填入数组id中，将常数变为二进制形式存入数组中ci中，并记录其在表中的位置。
lexical过程中嵌有两个小过程：
一个名为getchar，其功能为从instring中按顺序取出一个字符，并将其指针pint加1；
另一个名为error，当出现错误时，调用这个过程，输出错误编号。
◆要求：
所有识别出的单词都用两个字节的等长表示，称为内部码。
第一个字节为t，第二个字节为i。
t为单词的种类。
关键字的t=１；
分界符的t=２；
算术运算符的t=３；
关系运算符的t=４；
无符号数的t=５；
标识符的t=６。
i为该单词在各自表中的指针或内部码值。
表1为关键字表；
表2为
分界符表；
表3为算术运算符的i值；
表4为关系运算符的i值。
取字符和统计字符行列位置子程序
四、实验要求
1、编程时注意编程风格：
空行的使用、注释的使用、缩进的使用等。
2、将标识符填写的相应符号表须提供给编译程序的以后各阶段使用。
3、根据测试数据进行测试。
测试实例应包括以下三个部分:
u全部合法的输入。
u各种组合的非法输入。
u由记号组成的句子。
4、词法分析程序设计要求输出形式:
例：
输入VC++语言的实例程序：
Ifi=0thenn++;
a﹤=3b%）;
输出形式为：
单词二元序列类型位置（行，列）
（单词种别，单词属性）
for
（1,for）
关键字
（1，1）
i
（6,i）
标识符
（1，2）
=
（4，=）
关系运算符
（1，3）
（5，0）
常数
（1，4）
then
（1，then）
（1，5）
n
（6,n）
（1，6）
++
Error
（1，7）
（2,;
）
分界符
（1，8）
a
（6,a）
（2，1）
﹤=
（4,<
=）
（2，2）
3b
（2，4）
%
）
（2,））
（2，5）
（2，6）
五、实验步骤
1、根据流程图编写出各个模块的源程序代码上机调试。
2、编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的词法分析程序；
直至能够得到完全满意的结果。
3、书写实验报告；
实验报告正文的内容：
◆功能描述：
该程序具有什么功能？
◆程序结构描述：
函数调用格式、参数含义、返回值描述、函数功能；
函数之间的调用关系图。
◆详细的算法描述（程序总体执行流程图）。
◆给出软件的测试方法和测试结果。
◆实验总结（设计的特点、不足、收获与体会）。
实验二LL
（1）分析法
通过完成预测分析法的语法分析程序，了解预测分析法和递归子程序法的区别和联系。
使学生了解语法分析的功能，掌握语法分析程序设计的原理和构造方法，训练学生掌握开发应用程序的基本方法。
有利于提高学生的专业素质，为培养适应社会多方面需要的能力。
u根据某一文法编制调试LL
（1）分析程序，以便对任意输入的符号串进行分析。
u构造预测分析表，并利用分析表和一个栈来实现对上述程序设计语言的分析程序。
u分析法的功能是利用LL
（1）控制程序根据显示栈栈顶内容、向前看符号以及LL
（1）分析表，对输入符号串自上而下的分析过程。
三、LL
（1）分析法实验设计思想及算法
◆模块结构：
（1）定义部分：
定义常量、变量、数据结构。
（2）初始化：
设立LL
（1）分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；
（3）控制部分：
从键盘输入一个表达式符号串；
（4）利用LL
（1）分析算法进行表达式处理：
根据LL
（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->
输出的格式如下：
2、编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的LL
（1）分析程序；
u写出LL
（1）分析法的思想及写出符合LL
（1）分析法的文法。
u程序结构描述：
u详细的算法描述（程序执行流程图）。
u给出软件的测试方法和测试结果。
u实验总结（设计的特点、不足、收获与体会）。
实验三LR
（1）分析法
验证实验要求：
构造LR
（1）分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
对下列文法，用LR
（1）分析法对任意输入的符号串进行分析：
E+T
（2）E->
T
（3）T->
T*F
F
（5）F->
（E）
（6）F->
i
三、LR
（1）分析法实验设计思想及算法
（1）总控程序，也可以称为驱动程序。
对所有的LR分析器总控程序都是相同的。
（2）分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
（3）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
uLR分析器由三个部分组成：
u其中:
SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。
状态转换表用
GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
uACTION[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）报错:
当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。
3、程序输入/输出实例：
输入一以#结束的符号串（包括+*（）i#）：
在此位置输入符号串输出过程如下：
步骤状态栈符号栈剩余输入串动作
10#i+i*i#移进
i+i*i的LR分析过程
步骤
状态栈
符号栈
输入串
动作说明
1
#
i+i*i#
ACTION[0,i]=S5,状态5入栈
2
05
#i
+i*i#
r6:
F→i归约,GOTO（0,F）=3入栈
03
#F
r4:
T→F归约,GOTO（0,T）=3入栈
02
#T
r2:
E→T归约,GOTO（0,E）=1入栈
5
01
#E
ACTION[1,+]=S6,状态6入栈
6
016
#E+
i*i#
ACTION[6,i]=S5,状态5入栈
7
0165
#E+i
*i#
F→i归约,GOTO（6,F）=3入栈
8
0163
#E+F
T→F归约,GOTO（6,T）=9入栈
9
0169
#E+T
ACTION[9,*]=S7,状态7入栈
10
01697
#E+T*
i#
ACTION[7,i]=S5,状态5入栈
11
016975
#E+T*i
F→i归约,GOTO（7,F）=10入栈
12
0169710
#E+T*F
r3:
T→T*F归约,GOTO（6,T）=9入栈
13
r1:
E→E+T,GOTO（0,E）=1入栈
14
Acc：
分析成功
4、输入符号串为非法符号串（或者为合法符号串）
算术表达式文法的LR分析表
状态
ACTION
GOTO
+
*
（
E
S5
S4
S6
acc
r2
S7
r4
r6
S11
r1
r3
r5
2、编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的LR
（1）语法分析程序；
◆描述LR
（1）语法分析程序的设计思想。
◆详细的算法描述（程序执行流程图）。
实验四逆波兰表达式的产生及计算
选修
非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。
将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。
三、逆波兰表达式的产生及计算实验设计思想及算法
◆逆波兰式定义
将运算对象写在前面，而把运算符号写在后面。
用这种表示法表示的表达式也称做后缀式。
逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。
◆产生逆波兰式的前提中缀算术表达式
◆逆波兰式生成的设计思想及算法
（1）首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。
（2）读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。
（3）从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。
（4）如果不是数字，该字符则是运算符，此时需比较优先关系。
做法如下：
将该字符与运算符栈顶的运算符的优先关系相比较。
如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。
倘若不是的话，则将此
运算符栈顶的运算符从栈中弹出，将该字符入栈。
（5）重复上述操作
（1）-
（2）直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。
运用以上算法分析表达式（a+b*c）*d的过程如下：
当前符号
输入区
输出区
a+b*c）*d
+b*c）*d
*c）*d
b
c）*d
（+
）*d
ab
c
*d
（+*
abc
abc*
d
abc*+
abc*+d
（1）构造一个栈，存放运算对象。
（2）读入一个用逆波兰式表示的简单算术表达式。
（3）自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。
若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。
如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。
（4）重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。
u
逆波兰式计算的设计思想及算法
◆输入以#结束的中缀表达式（包括+-*/（）数字#）。
（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;
计算结果为:
2、编制好源程序后，设计若干用例对系统进行全面的上机测试，并通过所设计的逆波兰式的产生及计算程序；
◆描述逆波兰式的产生及计算程序的设计思想。
实验五应用DGA进行局部优化
设计实验要求：
使学生通过本次实验，能够对程序优化技术有一定的了解，掌握利于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
要求：
构造其相应的
升级会员 