递归下降分析器设计与实现.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、实验总结
通过本次试验实践掌握了自上而下语法分