编译原理实验递归向下语法分析法实验附C语言源码成功测试

1、实验二 递归向下分析法一、 实验目和要求根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。 本次实验的目的主要是加深对递归下降分析法的理解。 二、 实验内容 （1） 功能描述 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。 2、递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为 LL（1）文法， 3、递归下降分析法实验设计思想及算法 为 G 的每个非终结符号 U 构造一个递归过程,不妨命名为 U。 U 的产生式的右边指出这个过程的代码结构： 1)若是终结符号，则和向前看符号对照， 若匹配则向前进一

2、个符号；否则出错。 2)若是非终结符号，则调用与此非终结符对应的过程。当 A 的右部有多个产生式时,可 用选择结构实现。 具体为： （1） 对于每个非终结符号U->u1|u2|un处理的方法如下：U( ) ch=当前符号; if(ch可能是u1字的开头) 处理u1的程序部分; else if(ch可能是u2字的开头)处理u2的程序部分; else error() （2） 对于每个右部u1->x1x2xn的处理架构如下： 处理x1的程序； 处理x2的程序； 处理xn的程序；（3）如果右部为空，则不处理。 （4）对于右部中的每个符号xi 

3、0;如果xi为终结符号： if(xi= = 当前的符号)  NextChar()；  return;   else 出错处理  如果xi为非终结符号，直接调用相应的过程xi()  说明： NextChar为前进一个字符函数。 （2） 程序结构描述 程序要求： 程序输入/输出示例： 对下列文法，用递归下降分析法对任意输入的符号串进行分析： （1）E->TG （2）G->+TG|TG （3）G-> （4）T->FS （5）S->*FS| / FS （6）S-> （7）F->(E

4、) （8）F->i 输入出的格式如下： (1)E 盘建立一个文本文档" 222.txt"存储一个以#结束的符号串(包括+*/（）i#)，在此 位置输入符号串例如：i+i*i# (2)输出结果：i+i*i#为合法符号串 备注：输入一符号串如 i+i*#,要求输出为“非法的符号串” 函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。 程序所用主要参数和头文件说明： #include<stdio.h> #include<stdlib.h>#include<string.h> FILE *fp; /定义一个全局文件指针变量

5、 char ch; /定义一个全局字符变量 #define N 20 /定义一个数组大小常量 char stringN; /定义一个用于存储算式字符串的数组 char *p; /定义一个全局字符指针变量 函数说明：1） 非终结符函数 E() 函数功能描述：根据以上文法要求 E->TG,所以从主函数开始调入第一个非终结符函数 执行，显示调用产生式，依次嵌套调用非终结符函数 T（）和 G（） ，进行递归向下分析。 void E()printf("E->TG.%cn",ch); T(); G(); 2） 非终结符函数 T() 函数功能描述：根据以上文法要求 T->

6、;FS,首先显示算式匹配所用的显示调用的产生式， 依次嵌套调用非终结符函数 F（）和 S（） ，进行递归向下分析。 void T() printf("T->FS.%cn",ch); F(); S(); 3） 非终结符函数 G() 函数功能描述：根据以上文法要求 G->+TG|TG ，G->，如果当前字符变量 ch 为“+” ，则显示调用产生式，首先嵌套调用 test()函数判断是算式递归向下分析是否结束，若没有 结束则继续依次嵌套调用非终结符函数 T（）和 G（） ；如果当前字符变量 ch 为“-” ，则显 示调用产生式，从文件文档中读取下一个字符，让字符

7、指针变量指向下一个字符，继续依次 嵌套调用非终结符函数 T（）和 G（） ；如果当前字符变量 ch 既不为“+” 也不为“-” ，非 终结符 G 指向为空，函数只用于显示指向为空，找不到可以和文件中字符匹配的非终结符。 void G() if (ch='+') printf("G->+TG.%cn",ch); *p=ch; p+; ch=fgetc(fp); T(); G(); else if(ch='-') printf("G->-TG.%cn",ch); *p=ch; p+; ch=fgetc(fp); T

8、(); G(); else printf("G->.%cn",ch); 4） 非终结符函数 F() 函数功能描述：根据以上文法要求 F->(E)，F->i ，如果当前字符变量 ch 为“i” ，则显示 调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符,如果当前字 符变量 ch 为“ ，则显示调用产生式，继续依次嵌套调用非终结符函数 E(),函数 E()执行 （” 结束以后，若果 ch=“），从文件文档中读取下一个字符，让字符指针变量指向下一个字符， ” 否则算式匹配失败，程序执行结束；若果 ch 不为“i” ，又不是“ （”则算式匹配失

9、败，程序 执行结束。 void F() if(ch='i') printf("F->i.%cn",ch); *p=ch; p+; ch=fgetc(fp); else if (ch='(') printf("F->(E).%cn",ch); *p=ch; p+; ch=fgetc(fp); E(); if(ch=')') *p=ch; p+;ch=fgetc(fp); else printf("没有右括号“)”匹配不成功！n"); exit(0); elseprintf(&q

10、uot;匹配不成功！n"); exit(0); 5） 非终结符函数 S() 函数功能描述：根据以上文法要求 S->*FS| / FS，S->，如果当前字符变量 ch 为“*” ， 则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，依次 嵌套调用非终结符函数 F（）和递归调用自身 S（） ；如果当前字符变量 ch 为 “/” ，则显示 调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，依次嵌套调 用非终结符函数 F （） 和递归调用自身 S ；如果当前字符变量 ch 既不为“*” 也不为“/” （） ， G 中找不到可以匹配的算

11、式则非终结符 G 指向为空。 void S() if(ch='*') printf("S->*FS.%cn",ch); *p=ch; p+; ch=fgetc(fp); F(); S(); else if(ch='/') printf("S->/FS.%cn",ch); *p=ch; p+; ch=fgetc(fp); F(); S(); else printf("S->.%cn",ch); 6） 主函数 main（） 函数功能描述： E 盘打开一个 222.txt 文本文档， 从 读

12、取一个字符， 调用非终结符函数 E(), 非终结符函数 E(),执行完以后，如果 ch 为“#”则算式匹配成功，否则匹配失败。 main（） if(fp=fopen("E:222.txt","r")=NULL) /读取文件内容，并返回文件指针，该指针指向文件的第一个字符 fprintf(stderr,"error opening.n"); exit(0); ch=fgetc(fp); /读取字符只能读一个 p=string; printf("递归下降分析所用产生式：n"); E(); if(ch='#

13、9;) *p=ch; printf("算式匹配成功！n 算式结果：%sn",string); else printf("算式匹配不成功！n"); fclose(fp); 函数之间的调用关系图：调试运行结果： 1) 在文件中输入：i+i*i# 运行结果如下图所示：2）在文件中输入：i+i-# 运行结果如下图所示：3）在文件中输入：i+(i*i)# 运行结果如下图所示：4）在文件中输入：i+(i*i# 运行结果如下图所示：5）在文件中输入：i+i*i)# 运行结果如下图所示：三、 实验过程记录 本次实验出现 3 次重要错误： （1）出错 1：全局变量在 ma

14、in（）函数中重新定义，编译连接执行都没有错误提示，但在 运行时候出错； 解决方案：删除 main（）函数 FILE *fp; （2）出错 2：算式匹配时候，如果输入字符串中只有“ （”时，仍然是能够正确匹配 解决方案：由于没有考虑括号匹配是成对存在的问题，所以这种结果不符合要求，添 加右括号匹配代码如下所示： else if (ch='(') printf("F->(E).%cn",ch); *p=ch; p+; ch=fgetc(fp); E(); if(ch=')') *p=ch; p+; ch=fgetc(fp);else pr

15、intf("没有右括号“)”匹配不成功！n"); exit(0); （3） 出错 3： 调用非终结符 E()执行完以后， 则对于一些非法的算式还是成功输出例如 i-、 i*等； 解决方案：在主函数 main（）中需要对调用非终结符 E()执行完以后的 ch 进行判断， 如果 ch 为“#”则算式匹配成功，否则算式匹配失败，在主函数中添加代码如下： if(ch='#') *p=ch; printf("算式匹配成功！n 算式结果：%sn",string); else printf("算式匹配不成功！n"); 四、实验总结

16、通过本次上机实验让我认识了很多，加深了我对递归下降分析法的理解。自上而下语法 分析法就是从输入串开始，逐步进行“归约” ，直至归约到文法的开始符号。基于第三章的 此法分析，通过实验我对本章的语法分析也有了深刻的认识。同时通过本次编程，让我深刻 认识编程应该注重细节，编程之前首先要做好分析准备。 五、程序源代码 #include<stdio.h> #include<stdlib.h> #include<string.h> FILE *fp; /定义一个全局文件指针变量 char ch; /定义一个全局字符变量 #define N 20 /定义一个数组大小常量

17、char stringN; /定义一个用于存储算式字符串的数组 char *p; /定义一个全局字符指针变量 void E(); void T(); void G(); void F(); void S(); /非终结符 F void F() if(ch='i') printf("F->i.%cn",ch); *p=ch; p+; ch=fgetc(fp); else if (ch='(') printf("F->(E).%cn",ch); *p=ch; p+; ch=fgetc(fp); E(); if(ch

18、=')') *p=ch; p+; ch=fgetc(fp); else printf("没有右括号')'匹配不成功！n"); exit(0); else printf("算式匹配不成功！n"); exit(0); void G() if (ch='+') printf("G->+TG.%cn",ch); *p=ch; p+; ch=fgetc(fp);T(); G(); else if(ch='-') printf("G->-TG.%cn",ch); *p=ch; p+; ch=fgetc(fp); T();G(); else printf("G->.%cn",ch); /非终结符 T void T() printf("T->FS.%cn",ch); F(); S(); /非终结符 S void S() if(ch='*') printf("S