编译语法分析实验报告.doc

编译原理实验报告

实验名称： 编写语法分析程序
实验类型： 设计型
指导教师：
专业班级：
姓 名：
学 号：
实验地点：
实验成绩：____________________

日期：2013年 月日
实验二 编写语法分析程序
一、 实验目的
通过设计、编写、调试一个递归下降语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，掌握递归下降语法分析方法。

二、 实验设计
1、改写文法，消除二义性，消除左递归，提取左公因子
2、求出非终结符FIRST集，有ε表达式的FOLLOW集
3、根据每条文法编写程序
4,、测试
三、 实验过程
1、改写文法
TEST语言语法规则：
1)::={}
2)::= | ε
3)::=int ID;
4)::=| ε
5)::= |||
|| |
6)::= if () ement > [else < statement >]
7)::= while () < statement >
8)::= for(;;)
9)::=write ;
10)::=read ID;
11)::={}
12)::=< expression >;|;
13)< expression >:: ID=|
14)::=
|< additive_expr >(>|<|>=|<=|==|!=)< additive_expr >
15)< additive_expr>::={(+|-)< term >}
16)< term >::={(*| /)< factor >}
17)< factor >::=(< expression >)|ID|NUM
改写后文法:
1)::={n_list>}
2)::= | ε
消除左递归：::= |ε
3)::=int ID;
4)::=| ε
消除左递归：::=>|ε
5)::= |||
|| |
6) ::= if () [else < statement >]
7)::= while () < statement >
8)::= for(;;)ement>
9)::=write ;
10)::=read ID;
11)::={}
12)::=< expression >;|;
FRIST()={(、ID、NUM、；}
13)< expression >::= ID=|
14)::=
|< additive_expr >(>|<|>=|<=|==|!=)< additive_expr >
消除左公因子：::=|A
A::= >< additive_expr >|<< additive_expr >|>=< additive_expr >|<=< |==< additive_expr >|!=< additive_expr >|ε
15) < additive_expr>::={(+|-)< term >}
消除左递归：< additive_expr>::=< R>
< R>::=+< term >< R>|-< term >< R>|ε
16)< term >::={(*| /)< factor >}
消除左递归：< term >::=< M>
< M>::=*< factor >< term _1>|/< factor >< term _1>|ε
17)< factor >::=(< expression >)|ID|NUM
2、FIRST集：
1)FIRST({})={ { }
2)FRIST()={ int ，ε}
3)FIRST(declaration_stat)={int}
4) FIRST()={if、while、for、read、write、{、(、ID、NUM、; 、ε}
5)FIRST::={ if、while、for、read、write、command、experiession}
6) FIRST::={ if }
7)FIRST)={while}
8)FIRST())={for}
9)FIRST()={write}
10)FIRST(read ID;)={read}
11)FRIST({})={{}
12)FRIST(ion_stat>)={(、ID、NUM、；}
13)FRIST()={ID、(、NUM}
14)FRIST()={(、ID、NUM} FRIST(>< additive_expr >)={>}
FRIST(<< additive_expr >)={<} FRIST(>=< additive_expr >)={>=}
FRIST(<=< additive_expr >)={<=} FRIST(==< additive_expr >)={==}
FRIST(!=< additive_expr >)={} FRIST(ε)={ ε}
FRIST(A)={ >、<、>= , <= , == , != , ε}
15) FRIST(additive_expr) = {（，ID，NUM} FRIST(R) = {ε,+,-}
16) FRIST< term >={ （，ID，NUM } FRIST()={* 、/、 ε}
17)FIRST::={ （，ID，NUM }
3、FLLOW集
2） FOLLOW()={int、if、while、for、read、write、{、(、ID、NUM、; }
3） FOLLOW(statement_list)={ } }
14） FRIST(A)={ >、<、>= , <= , == , != , ε}
15）FOLLOW < R> ::={ < 、> 、<= 、 >= 、== 、！= 、； 、) }
16) FOLLOW(term_1)={ + 、—、< 、> 、<= 、 >= 、== 、！= 、； 、)}
4、流程图：
::= |||
|| |xpression_stat>

< expression >::= ID=|

5、编写代码

三、 实验结果
测试数据是词法分析结果
{ {
int int
ID abc
; ;
int int
NUM 123
; ;
int int
ID A
; ;
int int
ID i
; ;
int int
ID n
; ;
int int
ID b
, ,
ID c
; ;
read read
ID n
; ;
for for
( (
ID i
= =
NUM 1
; ;
ID i
<= <=
ID n
; ;
ID i
= =
ID i
+ +
NUM 1
) )
{ {
ID abc
= =
ID abc
+ +
ID i
; ;
} }
结果

四、 讨论与分析
1、对于不满足无回溯的递归下降分析条件的有（2）（4）改为右递归（14）提取左公因子（15）（16）改为右递归
2、不是，如
S→AU|BR
A→aAU|b
B→aBR|b
U→c
R→d
其中S→aAUU|bU|aBRR|bR
即S→a(AUU|BRR)|bU|R)
S→aS1|bS2
S1→AUU|BRR
S2→U|R
A→aAU|b
B→aBR|b
U→c
R→d
永远不能满足
3、递归算法的实现效率低，处理能力相对有限，通用性差，难以自动生成
五、 附录：关键代码
//分析additive_expr
//文法< additive_expr>::=< R>
// < R>::=+< term >< R>|-< term >< R>|ε

void additive_expr() //直接调用term(),R();
{
term();
R();
}
void R()
{
if (strcmp(str,"+")==0||strcmp(str,"-"))
{
getStr();
term();
R();
}
//判断是否在FOLLOW集里
else if (strcmp(str,">")==0||strcmp(str,"<")==0||strcmp(str,">=")==0||
strcmp(str,"<=")==0||strcmp(str,"==")==0||strcmp(str,"!=")==0||
strcmp(str,";")==0||strcmp(str,")")==0||)
{
getStr();
return;
}
}
六、 六、实验者自评
写代码时遇到困难就去看书，做实验时通过老实讲明白改写文法作用，必须按改写后的文法写代码才能尽可能包含所有的情况，不只是能检查出代码是对的，回来后又改写了代码