《编译原理》实验教案设计.docx
《《编译原理》实验教案设计.docx》由会员分享,可在线阅读,更多相关《《编译原理》实验教案设计.docx(24页珍藏版)》请在冰点文库上搜索。
《编译原理》实验教案设计
《编译原理》实验教案
《编译原理》是国内外各高等院校计算机科学技术类专业,特别是计算机软件专业的一门重要专业课程。
该课程系统地向学生介绍编译程序的结构、工作流程及编译程序各组成部分的设计原理和实现技术。
由于该课程理论性和实践性都比较强,内容较为抽象复杂,涉及到大量的软件设计算法,因此,一直是一门比较难学的课程。
为了使学生更好地理解和掌握编译技术的基本概念、基本原理和实现方法,实践环节非常重要,只有通过上机进行程序设计,才能使学生对比较抽象的教学内容产生具体的感性认识,增强学生综合分析问题、解决问题的能力,并对提高学生软件设计水平大有益处。
本实验内容在《编译原理》课程教学的同时,安排学生进行相关的实验。
实验平台可选择在MS-DOS或Windows操作系统环境,使用C/C++的任何版本作为开发工具。
学生在做完试验后,应认真撰写实验报告,内容应包括实验名称、实验目的、实验要求、实验内容、测试或运行结果等。
实验一词法分析设计与实现
实验时间:
2013.4.09,4.23
实验目的
对C语言的一个子集设计并实现一个简单的词法分析器,掌握利用状态转换图设计词法分析器的基本方法。
实验要求
利用该词法分析器完成对源程序字符串的词法分析。
输出形式是源程序的单词符号二元式的代码,并保存到文件中。
实验内容
(1)假设该语言中的单词符号及种别编码如下表所示。
单词符号及种别编码
单词符号
种别编码
单词符号
种别编码
main
1
[
28
int
2
]
29
char
3
{
30
if
4
}
31
else
5
32
for
6
:
33
while
7
;
34
标识符ID
10
>
35
整型常数NUM
20
<
36
=
21
>=
37
+
22
<=
38
-
23
==
39
*
24
!
=
40
/
25
&
41
(
26
&&
42
)
27
||
43
(2)关键字mainintcharifelseforwhile都是小写并都是保留字。
算符和界符=+-*/&<<=>>=== !
=&&||,:
;{}[]()
ID和NUM的正规定义式为:
ID→letter(letter|didit)*
NUM→digitdigit*
letter→a|…|z|A|…|Z
digit→0|…|9
如果关键字、标识符和常数之间没有确定的算符或界符作间隔,则至少用一个空格作间隔。
空格由空白、制表符和换行符组成。
(3)设计词法分析器的步骤:
1首先根据上面单词符号表及ID和NUM的正规定义式,构造出状态转换图;
2定义相关的变量和数据结构。
关键字作为特殊标识符处理,把它们预先安排在一张表格中(称为关键字表),当扫描程序识别出标识符时,查关键字表。
如能查到匹配的单词,则该单词为关键字,否则为一般标识符。
关键字表为一个字符串数组,其描述如下:
char*KEY_WORDS[7]={″main″,″int″,″char″,″if″,″else″,″for″,″while″};
用以存放单词符号二元式的数据结构可如下定义:
#defineMAXLENGTH255/*一行允许的字符个数*/
unionWORDCONTENT{/*存放单词符号的内容*/
charT1[MAXLENGTH];/*存放标识符及由两个(以上)字符组成的符号*/
intT2;/*存放整型常数的拼数*/
charT3;/*存放其他符号*/
};
typedefstructWORD{/*单词符号二元式*/
intcode;/*存放种别编码*/
unionWORDCONTENTvalue;
}WORD;
3按照编译程序一遍扫描的要求,把词法分析器Scaner作为一个独立的子程序来设计,通过对Scaner的反复调用识别出所有的单词符号;
4当Scaner识别出一个单词符号时,则将该单词符号的二元式写入到输出文件中。
若Scaner无法识别出一个单词符号时,则调用错误处理程序PrintError,显示当前扫描到的字符及其所在行、列位置,并跳过该字符重新开始识别单词符号。
(4)测试该设计词法分析器,可对下面的源程序进行词法分析:
输出如下二元式代码序列:
main()
{
inti=10;
while(i)i=i-1;
}
输出如下二元式代码序列:
(1,main)(26,()(27,))(30,{)(2,int)(10,i)(21,=)(20,10)(34,;)(7,while)(26,()(10,i)(27,))(10,i)(21,=)(10,i)(23,-)(20,1)(34,;)(31,})
实验结果:
实验运行情况:
实验二预测分析法设计与实现
实验时间:
2013.5.7,5.21,6.4
实验目的
设计一个非递归预测分析器,实现对表达式语言的分析,理解自上而下语法分析方法的基本思想,掌握设计非递归预测分析器的基本方法。
实验要求
建立文法及其LL
(1)分析表表示的数据结构,设计并实现相应的预测分析器,如果输入串是文法定义的句子则输出“是”,否则输出“否”。
实验内容
(1)文法描述及其LL
(1)分析表
表达式语言(XL)的语法规则如下:
1.程序→表达式;
2.|表达式;程序
3.表达式→表达式+项
4.|项
5.项→项*因式
6.|因式
7.因式→num_or_id
8.|(表达式)
将该语言的文法转换为如下的LL
(1)文法:
1prgm→expr;prgm’8term→factorterm’
2prgm’→prgm9term’→*factorterm’
3prgm’→ε10term’→ε
4expr→termexpr’11factor→(expr)
5expr→ε12factor→num
6expr’→+termexpr’13system_goal→prgm
7expr’→ε
该LL
(1)文法的LL
(1)分析表如下:
T
N
Num
+
*
(
)
;
#
prgm
1
1
1
prgm’
2
2
2
3
expr
4
4
5
5
expr’
6
7
7
term
8
8
term’
10
9
10
10
factor
12
11
system_goal
13
13
13
对文法中每个文法符号指定一个常数值,符号编码表如下:
文法符号
常数值
备注
(
Num
+
)
;
*
#
4
6
2
5
1
3
0
终结符
(#为输入结束标志)
Expr
expr’
term
term’
factor
prgm
prgm’
system_goal
258
260
259
262
261
256
257
263
非终结符
(2)文法及其LL
(1)分析表的数据结构
文法的产生式可用数组Yy_pushtab[]存放。
数组的第一个下标是产生式号,第一个产生式的序号为0;每列按逆序存放该产生式右部各符号的常数值,并以0结束。
对于该表达式语言XL的LL
(1)分析表,可用数组Yy_d[]存放。
第一个下标是非终结符数值,第二个下标是终结符数值,数组元素的值为:
0(表示接受),1(表示产生式号),-1(表示语法错)。
数组Yy_pushtab[]的具体内容及表示如下:
Yyp00
0
1
2
3
4
5
6
7
8
9
10
11
12
257,1,258,0
prgm’;expr
Yyp01
256,0
prgm
Yyp02
0
Yyp03
260,259,0
expr’term
Yyp04
0
Yyp05
260,259,2,0
expr’term+
Yyp06
0
Yyp07
262,261,0
term’factor
Yyp08
262,261,2,0
term’factor*
Yyp09
0
Yyp10
5,258,4,0
)expr(
Yyp11
6,0
Num
Yyp12
256,0
prgm
数组Yy_d[]的具体内容及表示如下:
0123456
#;+*()Num
-1
0
-1
-1
0
-1
0
2
1
-1
-1
1
-1
1
-1
4
-1
-1
3
4
3
-1
-1
-1
-1
7
-1
7
-1
6
5
-1
-1
6
-1
-1
-1
-1
-1
10
-1
11
-1
9
9
8
-1
9
-1
-1
12
-1
-1
12
-1
12
rgm256
prgm’257
expr258
term259
expr’260
factor261
term’262
system_goal263
(3)预测分析器总控程序结构
预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈(元素类型为int),其结构如下:
初始化;/*把开始符号的常数值压入分析站,输入指向第一个输入符号*/
while(分析栈非空){
if(栈顶常数表示一个终结符)
if(该常数与输入符号的常数不等)
报语法错;
else{
把一个数从栈顶弹出;
advance读下一输入符号;
}
else{/*栈顶的常数表示一个非终结符*/
what_to_do=Yy_d[栈顶常数][当前输入符号的常数];
if(what_to_do==-1)
报语法错;
else{
把栈顶元素弹出栈;
把Yy_pushtab[what_to_do]中列出的全部常数压入分析栈;
}
}
}
请实现该程序。
在程序中添加输出栈内容的功能,以便和手工模拟分析过程作比较。
(4)用预测分析器和手工模拟两种方式对文法的句子1+2;进行分析。
综合分析过程可用下表表示。
栈(符号)
栈(数值)
输入串
What_to_do
system_goal
prgm
prgm’;expr
prgm’;expr’term
prgm’;expr’term’factor
prgm’;expr’term’Num
prgm’;expr’term’
prgm’;expr’
prgm’;expr’term+
prgm’;expr’term
prgm’;expr’term’factor
prgm’;expr’term’Num
prgm’;expr’term’
prgm’;expr’
prgm’;
prgm’
263
256
2571258
2571260259
2571260262261
25712602626
2571260262
2571260
25712602592
2571260259
2571260262261
25712602626
2571260262
2571260
2571260262
257
1+2;#
1+2;#
1+2;#
1+2;#
1+2;#
1+2;#
+2;#
+2;#
+2;#
2;#
2;#
2;#
;#
;#
;#
#
12
0
3
7
11
9
5
7
11
9
6
2
(5)请考虑如何设计并实现LL
(1)分析表的自动生成程序。
湘南学院计算机科学系
2012学年度第2学期信计专业本层次2010级期末课程
《编译原理》实验操作考核方案
一、操作考核对象:
计算机科学与技术系计科专业2010级本科全体学生
二、操作考核时间:
2013年6月18日下午
三、操作考核地点:
湘南学院四教413
四、操作考核内容及评分标准:
1.考试要求
本次考核每个学生的实验项目情况,每个小组须在规定时间内完成。
按照每个学生题目的完成情况来决定。
2.考核原则
所选题目在上机编程调试通过后即为考核通过。
教师依据学生编程及调试通过与否情况给予考核成绩。
3.考核成绩评分标准
①所选题目按照提出来的要求编写出程序并调试通过,成绩为优(90分及以上,具体分数根据编写的代码质量和是否与需求报告一致考虑)
②所选题目编写出程序,但只有一部分能上机调试通过,有些部分稍作修改可上机调试通过,成绩为良(80分~89分,具体分数根据编写的代码质量考虑)
③所选题目编写出程序,但只有一部分能上机调试通过,成绩为中(70分~79分,具体分数根据编写的代码质量考虑)
④所选题目编写出程序,但均有小差错不能上机调试通过,成绩为及格(60~69分,具体分数根据编写的代码质量考虑)
⑤没有编写出任何完整的程序代码,成绩为不及格(50分及以下,具体分数根据编写的代码质量考虑)
4.考核时间
120分钟
5.考核项目
题目一:
词法分析设计与实现:
能够采用一种编程语言实现简单的词法分析程序;能够使用自己编写的分析程序对简单的程序段进行词法分析。
题目二:
预测分析法设计与实现:
能够采用一种编程语言实现简单的语法分析程序;能够使用自己编写的分析程序对简单的程序段进行语法判断。
实验三LR
(1)设计与实现
1.实验目的
设计一个LR分析器,实现对表达式语言的分析,加深对LR语法分析方法的基本思想的理解,掌握LR分析器设计与实现的基本方法。
2.实验要求
建立文法及其LR分析表表示的数据结构,设计并实现一个LALR
(1)的分析器,对源程序经词法分析后生成的二元式代码流进行分析,如果输入串是文法定义的句子则输出“是”,否则输出“否”。
3.实验内容
(1)文法描述及其LALR
(1)分析表
描述表达式语言的文法G如下:
1.S→E
2.E→E+T
3.E→T
4.T→T*F
5.T→F
6.F→(E)
7.F→ID
该文法的LALR
(1)分析表如下:
分析表
状态
动作Action表(Yy_action)
转移Goto表(Yy_goto)
#
ID
+
*
(
)
S
E
T
F
0
-
S1
-
-
S2
-
-
3
4
5
1
R6
-
R6
R6
-
R6
-
-
-
-
2
-
S1
-
-
S2
-
-
6
4
5
3
A
-
S7
-
-
-
-
-
-
-
4
R2
-
R2
S8
-
R2
-
-
-
-
5
R4
-
R4
R4
-
R4
-
-
-
-
6
-
-
S7
-
-
S9
-
-
-
-
7
-
S1
-
-
S2
-
-
-
10
5
8
-
S1
-
-
S2
-
-
-
-
11
9
R5
-
R5
R5
-
R5
-
-
-
-
10
R1
-
R1
S8
-
R1
-
-
-
-
11
R3
-
R3
R3
-
R3
-
-
-
-
SN=移进并转移到状态NA=accept接受
RN=按第N条产生式进行规约-=error转移
(2)LR分析器总控程序框架如下:
push(0);
advance();
while(Action[tos][sym]!
=accept)
if(Action[tos][sym]==’-’)
error();
else
if(Action[tos][sym]==SN){
push(N);
advance();
}
elseif(Action[tos][sym]==RN){
act(N);
pop(产生式N的右部的符号个数);
push(Goto[新tos][产生式N的左部符号]);
accept();
上述算法中的有关函数与符号的意义如下:
accept()返回成功状态,LR分析器停止工作
act(N)执行利用产生式N的归约的动作,通常为产生代码
advance()丛输入流读下一单词到sym
error()出错处理
pop(N)从栈顶弹出N个符号(状态)
push(N)把状态N压入状态栈
sym当前输入的单词符号
tos栈顶状态号
(3)存放LR分析表的数据结构
1实现方法一:
用一个二维整数数组表示
数组元素为表示动作的整数。
数组的行下标为状态号,列下标用来表示终结符与非终结符的整数表示。
数组元素可作如下约定:
正整数:
表示移进动作,如S6用数6表示;
负整数:
表示归约动作,如R5用数-5表示;
1:
表示接受,通常为按产生式0归约;
状态号也用整数表示;
用不可能是状态号的较大的整数表示错误转移。
请将上述LALR
(1)分析表用这种表示方法,完成LR分析器的程序设计,并添加输出状态栈内容的功能。
用上述表达式文法G的一个句子作为输入,进行测试。
2实现方法二:
采用压缩表示法
动作Action表的每一行用一个数组表示,数组的第一个元素是本数组中存放的数偶个数,第二个元素到最后一个元素都以[终结符,动作]的数偶的形式存放。
再用一个以状态号为下标的下标数组,每个元素含一个指向数偶数组的指针。
若数组元素的值为NULL,则表示从此状态无转移弧发出。
若分析表有几行相同,则只需保存一行,其它元素则都指向存放这一行表的数组即可。
转移Goto表也按同样方式组织,只是这个行数组的数偶为[非终结符,下一状态号]。
每个行数组Yyan表示动作表Yy_action的一行,每个行数组Yygn表示转移表Yy_goto的一行。
假定上述表达式文法G中终结符及非终结符的整数值为:
终结符:
#ID+*()非终结符:
SETF
整数值:
012345整数值:
0123
Yy_action数组是以状态号为下标的下标数组,每个元素含有指向数组Yyan的指针;下标数组Yy_goto的每个元素含有指向数组Yygn的指针。
表达式文法G的LALR
(1)分析表的具体压缩表示如下:
2
4,2
1,1
Yya000
Yy_action
.
.
.
.
.
.
.
.
.
.
.
.
0
4
5,-6
3,-6
2,-6
0,-6
Yya001
1
Yya003
2
2
0,0
2,7
3
4
5,-2
2,-2
0,-2
3,8
Yya004
4
Yya005
4
5,-4
3,-4
2,-4
0,-4
5
2
5,9
2,7
Yya006
6
7
Yya009
8
4
5,-5
3,-5
2,-5
0,-5
9
4
5,-1
2,-1
0,-1
3,8
Yya010
10
Yya011
4
5,-3
5,-3
2,-3
0,-3
11
Yyg000
Yy_goto
.
NULL
.
NULL
NULLNULL
NULL
.
.
NULL
NULL
NULL
3
3,5
2,4
1,3
0
Yyg002
1
3
3,5
2,4
1,6
2
3
4
5
Yyg007
6
2
3,5
2,10
7
1
3,11
Yyg008
8
9
10
11
以上分析表用C语言程序描述如下:
/*
*Yy_action表
*/
intYya000[]={2,4,2,1,1};
intYya001[]={4,5,-6,3,-6,2,-6,0,-6};
intYya003[]={2,0,0,2,7};
intYya004[]={4,5,-2,2,-2,0,-2,3,8};
intYya005[]={4,5,-4,3,-4,2,-4,0,-4};
intYya006[]={2,5,9,2,7};
intYya009[]={4,5,-5,3,-5,2,-5,0,-5};
intYya010[]={4,5,-1,2,-1,0,-1,3,8};
intYya011[]={4,5,-3,3,-3,2,-3,0,-3};
intYy_action[]=
{
Yya000,Yya001,Yya000,Yya003,Yya004,Yya005,
Yya006,Yya000,Yya000,Yya009,Yya010,Yya011
};
/*
*Yy_goto表
*/
intYyg000[]={3,3,5,2,4,1,3};
intYyg002[]={3,3,5,2,4,1,6};
intYyg007[]={2,3,5,2,10};
intYyg008[]={1,3,11};
intYy_goto[]=
{
Yyg000,NULL,Yyg002,NULL,NULL,NULL,
NULL,Yyg007,Yyg008,NULL,NULL,NULL
};
/*
*为了进行归约,使用一个Yy_lhs[]数组,其值为代表产生式左部符号的
*整数,数组的下标为产生式号
*/
intYy_lhs[7]=
{
/*0*/0,
/*