实验二递归下降实验.doc

实验二：递归下降分析法
一、实验目的：
根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。
二、实验要求：
1、程序输入/输出示例：
对下列文法，用递归下降分析法对任意输入的符号串进行分析：
（1）E->TG
（2）G->+TG|—TG
（3）G->ε
（4）T->FS
（5）S->*FS|/FS
（6）S->ε
（7）F->(E)
（8）F->i
2、输出的格式如下：
(1)递归下降分析程序，编制人：姓名，学号，班级
(2)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串例如：i+i*i#
(3)输出结果：i+i*i#为合法符号串
备注：输入一符号串如i+i*#,要求输出为“非法的符号串”。
注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；
2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，可以详细的输出推导的过程。
3、与读文件有关的函数：
FILE*fp;
if((fp=fopen("E:\\222.txt","r"))==NULL)
{//读取文件内容，并返回文件指针，该指针指向文件的第一个字符
fprintf(stderr,"erroropening.\n");
exit(1);
}
fgetc（fp）从数据流中区下一个字符
fopen文件打开函数，返回指向文件第一个字符的指针
三、功能描述：
1、递归下降分析法的功能
词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。
2、递归下降分析法的前提
改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，
3、递归下降分析法实验设计思想及算法
为G的每个非终结符号U构造一个递归过程,不妨命名为U。
U的产生式的右边指出这个过程的代码结构：
1)若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。
2)若是非终结符号，则调用与此非终结符对应的过程。当A的右部有多个产生式时,可用选择结构实现，具体为：
对于每个非终结符号U->u1|u2|…|un处理的方法如下：
U(){
ch=当前符号;
if(ch可能是u1字的开头)处理u1的程序部分;
elseif(ch可能是u2字的开头)处理u2的程序部分;
………………
elseerror();
}
对于每个右部u1->x1x2…xn的处理架构如下：
处理x1的程序；
处理x2的程序；
…
处理xn的程序；
如果右部为空，则不处理。
对于右部中的每个符号xi
①如果xi为终结符号：
if(xi==当前的符号){
NextChar()；
return;
}else{出错处理}
②如果xi为非终结符号，直接调用相应的过程xi()
说明：NextChar为前进一个字符函数。
四、函数说明：
1、非终结符函数E()
函数功能描述：根据以上文法要求E->TG,所以从主函数开始调入第一个非终结符函数
执行，显示调用产生式，依次嵌套调用非终结符函数T（）和G（），进行递归向下分析。
voidE(){
printf("E--->TG..............%c\n",ch);
T();
G();}
2、非终结符函数T()
函数功能描述：根据以上文法要求T->FS,首先显示算式匹配所用的显示调用的产生式，
依次嵌套调用非终结符函数F（）和S（），进行递归向下分析。
voidT(){
printf("T--->FS..............%c\n",ch);
F();
S();}
3、非终结符函数G()
函数功能描述：根据以上文法要求G->+TG|—TG，G->ε，如果当前字符变量ch为“+”，则显示调用产生式，首先嵌套调用test()函数判断是算式递归向下分析是否结束，若没有结束则继续依次嵌套调用非终结符函数T（）和G（）；如果当前字符变量ch为“-”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，继续依次嵌套调用非终结符函数T（）和G（）；如果当前字符变量ch既不为“+”也不为“-”，非终结符G指向为空，函数只用于显示指向为空，找不到可以和文件中字符匹配的非终结符。
voidG(){if(ch=='+'){printf("G--->+TG..............%c\n",ch);
*p=ch;
p++;
ch=fgetc(fp);
T();
G();}
elseif(ch=='-')
{printf("G--->-TG..............%c\n",ch);
*p=ch;
p++;
ch=fgetc(fp);
T();
G();
}else
printf("G--->ε..........