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

编译原理实验报告

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

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

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

< expression >::= ID=<bool_expr>|<bool_expr>

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)|b(U|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>::=<term>< 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;
}
}
六、 六、实验者自评
写代码时遇到困难就去看书，做实验时通过老实讲明白改写文法作用，必须按改写后的文法写代码才能尽可能包含所有的情况，不只是能检查出代码是对的，回来后又改写了代码