编译原理实验指导Word文件下载.docx
《编译原理实验指导Word文件下载.docx》由会员分享，可在线阅读，更多相关《编译原理实验指导Word文件下载.docx（20页珍藏版）》请在冰点文库上搜索。
4）在计算机屏幕或者文本框中输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。
四、实验环境
PC微机
DOS操作系统或Windows操作系统
TurboC程序集成环境或VisualC++程序集成环境
五、实验步骤
1、根据文法定义，设计出文法数据结构
2、用学生选择的语言，实现文法的数据结构
3、编写调试文法读入和输出程序，
4、测试程序运行效果：
从文本文件中读入一个文法，在屏幕上输出，检查输出结果。
六、测试数据
输入数据：
编辑一个文本文文件g.txt，在文件中输入如下内容：
S->
Qc;
c;
Q->
Rb;
b;
R->
Sa;
a;
正确结果：
上述文法整理后的输出形式：
Qc|c;
Rb|b;
R->
Sa|a;
七、实验报告要求
实验报告应包括以下几个部分：
1、文法数据结构的设计和实现；
2、文法的读入算法
3、文法的输出方法
4、程序的测试结果和问题
5、实验总结
八、思考题
1、如何让设计的文法结构满足各种文法的要求？
2、如何设计文法才能跟简单地表示文法，同时又降低程序编写难度？
实验2词法分析程序的设计
掌握计算机语言的词法分析程序的开发方法。
编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。
1、根据以下的正规式，编制正规文法，画出状态图；
标识符<
字母>
（<
|<
数字字符>
）*
十进制整数0|（（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*）
八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）*
十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）*
运算符和界符+-*/>
<
=（）；
关键字ifthenelsewhiledo
2、根据状态图，设计词法分析函数intscan（），完成以下功能：
1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词，
2）以二元式形式输出单词<
单词种类，单词属性>
其中单词种类用整数表示：
0：
标识符
1：
十进制整数
2：
八进制整数
3：
十六进制整数
运算符和界符，关键字采用一字一符，不编码
其中单词属性表示如下：
标识符，整数由于采用一类一符，属性用单词表示
运算符和界符，关键字采用一字一符，属性为空
3、编写测试程序，反复调用函数scan（），输出单词种别和属性。
1、根据正规式，画出状态转换图；
2、根据状态图，设计词法分析算法；
3、采用C或C++语言，设计函数scan（），实现该算法；
4、编制测试程序（主函数main）；
5、调试程序：
读入文本文件，检查输出结果。
编辑一个文本文件program.txt，在文件中输入如下内容：
1、词法的正规式描述；
2、变换后的状态图；
3、词法分析程序的数据结构与算法。
1、词法分析能否采用空格来区分单词？
2、程序设计中哪些环节影响词法分析的效率？
如何提高效率？
实验3LL
（1）文法构造
熟悉LL
（1）文法的分析条件，了解LL
（1）文法的构造方法。
1、编制一个能够将一个非LL
（1）文法转换为LL
（1）文法；
2、消除左递归；
3、消除回溯。
1、将一个可转换非LL
（1）文法转换为LL
（1）文法，要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。
2、提取文法左因子算法：
1）对文法G的所有非终结符进行排序
2）按上述顺序对每一个非终结符Pi依次执行:
for（j=1；
j<
i-1；
j++）
将Pj代入Pi的产生式（若可代入的话）；
消除关于Pi的直接左递归：
Pi->
Piα|β，其中β不以Pi开头，则修改产生式为：
Pi—＞βPi′
Pi′—＞αPi′|ε
3）化简上述所得文法。
3、提取左因子的算法：
A—＞δβ1|δβ2|…|δβn|γ1|γ2|…|γm
（其中,每个γ不以δ开头）
那么,可以把这些产生式改写成
A—＞δA′|γ1|γ2…|γm
A′—＞β1|β2|…|βn
4、利用上述算法，实现构造一个LL
（1）文法：
1）从文本文件g.txt中读入文法，利用实验1的结果，存入实验1设计的数据结构；
2）设计函数remove_left_recursion（）和remove_left_gene（）实现消除左递归和提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子；
3）整理得到的新文法；
4）在一个新的文本文件newg.txt输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。
1、学习LL
（1）文法的分析条件；
2、学习构造LL
（1）文法的算法；
3、结合实验1给出的数据结构，编程实现构造LL
（1）文法的算法；
4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL
（1）文法形式；
5、把实验结果写入一个新建立的文本文件。
S->
Qc|c|cab;
Q->
R->
本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：
Qc|cT;
T->
@|ab;
//由于无法输出ε，用@代替
bcaU|caU|cabaU|aU;
U->
bcaU|@;
1、满足LL
（1）文法的分析条件；
2、构造LL
（1）文法的算法；
3、消除左递归文法和提取左因子算法实现方法；
4、整个测试程序的流程；
5、程序的测试结果和问题；
6、实验总结。
1、是不是所有的文法都可以通过上述程序构造LL
（1）文法？
2、LL
（1）文法在整个语法分析中的作用？
3、实验1中设计的文法数据结构对本实验的影响？
4、如何更好地组合实验1和实验3，使之具有更高的效率？
实验4语法分析程序的设计
（1）
通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中递归下降分析方法。
设计一个文法的递归下降分析程序，判断特定表达式的正确性。
1、给出文法如下：
G[E]
E->
T|E+T;
T->
F|T*F;
F->
i（E）;
利用实验3的方法将上述文法转化为LL
（1）文法；
2、根据递归下降分析方法为转化后的文法设计递归下降分析程序，利用C语言或C++语言实现；
3、利用递归下降分析程序完成下列功能：
1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；
”表示结束；
2）读入文本文件中的表达式；
3）调用实验2中的词法分析程序搜索单词；
4）把单词送入递归下降分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；
5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。
1、分析文法，将给出的文法转化为LL
（1）文法；
2、学习递归下降分析程序的结构，设计合理的递归下降分析程序；
3、编写测试程序，包括表达式的读入和结果的输出；
4、测试程序运行效果，测试数据可以参考下列给出的数据。
编辑一个文本文文件expression.txt，在文件中输入如下内容：
10;
1+2;
（1+2）*3+（5+6*7）;
（（1+2）*3+4;
1+2+3+（*4+5）;
（a+b）*（c+d）;
（（ab3+de4）**5）+1;
正确结果：
（1）10;
输出：
正确
（2）1+2;
（3）（1+2）*3+（5+6*7）;
（4）（（1+2）*3+4
错误
（5）1+2+3+（*4+5）
（6）（a+b）*（c+d）
（7）（（ab3+de4）**5）+1
1、给定文法的LL
（1）形式；
2、递归下降分析程序的算法和结构；
3、程序运行流程；
4、程序的测试结果和问题；
5、实验总结。
1、为什么文法必须先转化为LL
（1）文法再来做递归下降分析？
2、如果用预测分析法来改写本程序，如何来实现？
实验5语法分析程序的设计
（2）
通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中算法优先分析方法。
设计一个文法的算法优先分析程序，判断特定表达式的正确性。
1、给出文法如下：
可以构造算符优先表如下：
+
*
（
）
i
2、计算机中表示上述优先关系，优先关系的机内存放方式有两种1）直接存放，2）为优先关系建立优先函数，这里由学生自己选择一种方式；
3、给出算符优先分析算法如下：
k:
=1;
S[k]:
=‘#’;
REPEAT
把下一个输入符号读进a中；
IFS[k]∈VTTHENj:
=kELSEj:
=k-1;
WHILES[j]aDO
BEGIN
REPEAT
Q:
=S[j];
IFS[j-1]∈VTTHENj:
=j-1ELSEj:
=j-2
UNTILS[j]Q
把S[j+1]…S[k]归约为某个N；
k:
=j+1;
=N;
ENDOFWHILE;
IFS[j]aORS[j]aTHEN
=k+1;
S[k]:
=a
END
ELSEERROR
UNTILa=‘#’
4、根据给出算法，利用适当的数据结构实现算符优先分析程序；
5、利用算符优先分析程序完成下列功能：
4）把单词送入算法优先分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；
1、分析文法中终结符号的优先关系；
2、存放优先关系或构造优先函数；
3、利用算符优先分析的算法编写分析程序；
4、写测试程序，包括表达式的读入和结果的输出；
5、程序运行效果，测试数据可以参考下列给出的数据。
6、给定文法优先关系和存放方式；
7、算符优先分析程序的算法和结构；
8、程序运行流程；
9、程序的测试结果和问题；
10、实验总结。
1、算符优先关系表示的是一种什么样的关系，它在自下而上的分析中起到了什么作用？
2、比较本实验和实验4，实现同样的功能，两种方法有什么不同？
实验6逆波兰式的翻译和计算
通过实验加深对语法指导翻译原理的理解，掌握算符优先分析的方法，将语法分析所识别的表达式变换成中间代码的翻译方法。
设计一个表示能把普通表达式（中缀式）翻译成后缀式，并计算出结果的程序。
对应的转化为逆波兰式的语义动作如下：
E->
E
（1）opE
（2）{E.CODE:
=E
（1）.CODE||E
（2）.CODE||op}
（E
（1））{E.CODE:
=E
（1）.CODE}
id{E.CODE:
=id}
2、利用实验5中的算符优先分析算法，结合上面给出的语义动作实现逆波兰式的构造；
3、利用栈，计算生成的逆波兰式，步骤如下：
1）中缀表达式，从文本文件读入，每一行存放一个表达式，为了降低难度，表达式采用常数表达式；
2）利用结合语法制导翻译的算符优先分析，构造逆波兰式；
3）利用栈计算出后缀式的结果，并输出；
1、了解语法制导翻译的方法，学习后缀式构造的语义动作；
2、结合实验5的算符优先程序，设计程序构造后缀式；
3、利用栈，编程实现后缀式的计算；
4、测试程序运行效果：
从文本文件中读表达式，在屏幕上输出，检查输出结果。
（1+2）*3;
（10+20）*30+（50+60*70）;
（1）1+2;
1,2,+3
（2）（1+2）*3;
1,2,+,3,*9
（3）（10+20）*30+（50+60*70）
10,20,+30,*50,60,70,*,+,+5150
1、构造逆波兰式的语义动作；
2、结合算符优先分析构造逆波兰式的算法和过程；
3、语法制导翻译的运行方法；
1、语法制导翻译的工作方式？
2、为什么编译程序要设计生成中间代码方式？
实验7语法制导的三地址代码生成
掌握计算机语言的语法分析程序设计与属性文法应用的实现方法。
编制一个能够进行语法分析并生成三地址代码的微型编译程序。
1、考虑下述语法制导定义中文法，采用递归子程序法，改写文法，构造语法分析程序；
2、考虑下述语法制导定义中语义规则，改写语法分析程序，构造三地址代码生成程序。
产生式
语义规则
id=E;
S.code=E.code||gen（id.place’:
=’E.place）
ifCthenS
C.true=newlabel;
C.false=S.next;
S1.next=S.next;
S.code=C.code||gen（E.true’:
’）||S1.code
whileCdoS
S.begin=newlabel;
S1.next=S.begin;
S.code=gen（S.begin’:
’）||C.code||
gen（E.true’:
’）||S1.code||gen（‘goto’S.begin）;
C->
E1>
E2
C.code=E1.code||E2.code||
gen（‘if’E1.place’>
’E2.place’goto’C.true）||
gen（‘goto’C.false）
E1<
gen（‘if’E1.place’<
E1=E2
gen（‘if’E1.place’=’E2.place’goto’C.true）||
E1+T
E.place=newtemp;
E.code=E1.code||T.code||
gen（E.place’:
=’E1.place’+’T.place）
E1-T
E.code=E1.code||T.code||
=’E1.place’-’T.place）
T1*F
T.place=newtemp;
T.code=T1.code||F.code||
gen（T.place’:
=’T1.place’*’F.place）
T1/F
=’T1.place’/’F.place）
F->
（E）
F.place=E.place;
F.code=E.code
id
F.place=id.name;
F.code=‘‘
int8
F.place=int8.value;
int10
F.place=int10.value;
int16
F.place=int16.value;
1、考虑给定的文法，消除左递归，提取左因子。
2、编制并化简语法图
3、编制递归子程序的算法
4、编制各个递归子程序函数
5、连接实验一的词法分析函数scan（），进行测试
6、设计三地址代码生成的数据结构和算法
7、将各个递归子程序函数改写为代码生成函数
8、编制测试程序（main函数）
9、调试程序：
输入一个语句，检查输出的三地址代码
输入数据例：
while（a3+15）>
0xadoifx2=07thenwhiley<
zdoy=x*y/z;
等效的三地址代码序列
L1:
t1:
=a3+15
ift1>
10gotoL2
gotoL0
L2:
L3:
ifx2>
7gotoL4
gotoL1
L4:
ify<
zgotoL5
L5:
t2=x*y
t3=t2/z
y=t3
gotoL3
L0:
//S.next
1、语法制导定义
2、改写后的产生式集合
3、化简后的语法图
4、递归子程序的算法
5、三地址代码生成器的数据结构
6、程序结构的说明
1、生成的三地址代码可否直接输出（不采用数据结构来实现属性code
升级会员 