实验三-递归下降分析器设计与实现--编译原理实验报告.doc

实验三递归下降分析器设计与实现
实验目的：
（1）掌握自上而下语法分析的要求与特点。
(2）掌握递归下降语法分析的基本原理和方法。
（3）掌握相应数据结构的设计方法.
2、实验内容:
编程实现给定算术表达式的递归下降分析器。
算术表达式文法如下：
E-->E+T|T
T-—〉T＊F｜F
F--〉（E)|i3、设计说明：
首先改写文法为LL（1）文法;然后为每一个非终结符，构造相应的递归过程，过程的名字表示规则左部的非终结符；过程体按规则右部符号串的顺序编写.
4、设计分析
这个题目属于比较典型的递归下降语法分析。需要先将原算术表达式方法改写为LL（1）文法为：
E—-〉TE’
E’-->+TE’|ε
T-->FT’
T’-—〉＊FT’|ε
F—-〉(E)|i
然后再为每个非终结符设计一个对应的函数,通过各函数之间的递归调用从而实现递归下降语法分析的功能。具体方法为:
（1）当遇到终结符a时，则编写语句
If（当前读到的输入符号==a)读入下一个输入符号
（2）当遇到非终结符A时，则编写语句调用A().
（3）当遇到A-—〉ε规则时,则编写语句If(当前读到的输入符号不属于Follow(A）)error（)
（4）当某个非终结符的规则有多个候选式时,按LL（1)文法的条件能唯一地选择一个候选式进行推导。
5、程序代码
#include〈stdio.h>
voidE（);
voidT()；
voidE1（）；
voidT1();
voidF();
chars［100];
inti,SIGN;
intmain（）
｛
printf（"请输入一个语句,以＃号结束语句（直接输入#号推出）\n”）;
while(1)
｛
SIGN=0；
i=0;
scanf（”％s”,＆s）;
if（s[0］=='＃’)
return0；
E（）；
if(s［i]==’#'）
printf（”正确语句!\n”)；
printf(”请输入一个语句，以＃号结束语句\n"）;
｝
return1；
}
voidE（）
｛
if（SIGN==0)
{
T（）;
E1();
｝
｝
voidE1()
｛
if（SIGN==0)
{
if(s[i］==’+'）
｛
++i;
T();
E1（）;
｝
elseif(s［i]!='#’＆&s[i]!=')'）
｛
printf（"语句有误!\n”);
SIGN=1；
｝
｝
}
voidT（）
{
if（SIGN==0）
｛
F(）；
T1（）；
}
｝
voidT1(）
｛
if(SIGN==0）
｛
if(s［i］==’*’）
｛
++i;
F()；
T1（);
}
elseif(s［i］!=’#'&&s[i］！=’)'＆&s［i］!=’+')
｛
printf（”语句有误！\n”)；
SIGN=1;
｝
}
｝
voidF（)
{
if（SIGN==0）
{
if（s[i]==’(’）
{
++i；
E();
if（s[i］==’)’）
++i；
elseif(s[i］==’＃’)
{
printf（”语句有误！\n"）;
SIGN=1;
++i;
｝
｝
elseif（s[i］==’i’）
++i;
else
{
printf（”语句有误！\n”);
SIGN=1；
}
｝
}
6、测试用例
（1)只含有一个字符的形式:
i
a
A
(2）含有‘+’的形式：
i+i
i+i+i
i+
+++
（3)含有‘＊’的形式：
i*i
i＊i＊i
i＊
＊*
(4)含有‘（’‘）’的形式:
（i)
（)
（
(i)）
(5）综合形式:
（i+i）*i
（i+i)＊(i+i)
i+i*i
i++i*
（*i+
（i+
Iii
7、系统实施
系统实施环境为VC++6.0，在系统的实施过程中存在的问题主要是程序输入错
误，没有大的技术问题，经过调试和修改，系统最终能够运行并实现上述所有功
能。以下列出程序运行时的几个界面：
（1）系统运行初始界面：
(2)导入文法
选择要导入的文本
（3)生成非终结符集合，终结符集合,空串的非终结符集合,非终结符号的FIRST集合，非终结符号的FOLLOW集合，各产生式的SELECT集合,预测分析表：
8、实验总结
通过本次试验实践掌握了自上而下语法分析法的特点。掌握了递归下降语法分析的基本原理和方法。运用递归下降分析法完成了本试验的语法分析构造，并且成功的分析出每种正确的句子和错