实验二递归下降实验.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-i2、输出的格式如下：(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,error opening.n); exit(1); fgetc（fp） 从数据流中区下一个字符fopen 文件打开函数，返回指向文件第一个字符的指针三、功能描述：1、递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。2、递归下降分析法的前提改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1）文法，3、递归下降分析法实验设计思想及算法为G 的每个非终结符号U 构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构：1) 若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。2) 若是非终结符号，则调用与此非终结符对应的过程。当A 的右部有多个产生式时,可用选择结构实现，具体为：u 对于每个非终结符号U-u1|u2|un 处理的方法如下：U( )ch=当前符号;if(ch 可能是u1 字的开头) 处理u1 的程序部分;else if(ch 可能是u2 字的开头)处理u2 的程序部分;else error();u 对于每个右部u1-x1x2xn 的处理架构如下：处理x1 的程序；处理x2 的程序；处理xn 的程序；u 如果右部为空，则不处理。u 对于右部中的每个符号xi如果xi 为终结符号：if(xi= = 当前的符号)NextChar()；return;else出错处理如果xi 为非终结符号，直接调用相应的过程xi()说明： NextChar 为前进一个字符函数。四、函数说明：1、 非终结符函数E()函数功能描述：根据以上文法要求E-TG,所以从主函数开始调入第一个非终结符函数执行，显示调用产生式，依次嵌套调用非终结符函数T（）和G（），进行递归向下分析。void E()printf(E-TG.%cn,ch);T();G();2、 非终结符函数T()函数功能描述：根据以上文法要求T-FS,首先显示算式匹配所用的显示调用的产生式，依次嵌套调用非终结符函数F（）和S（），进行递归向下分析。void T()printf(T-FS.%cn,ch);F();S();3、 非终结符函数G()函数功能描述：根据以上文法要求G-+TG|TG ，G-，如果当前字符变量ch 为“+”，则显示调用产生式，首先嵌套调用test()函数判断是算式递归向下分析是否结束，若没有结束则继续依次嵌套调用非终结符函数T（）和G（）；如果当前字符变量ch 为“-”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，继续依次嵌套调用非终结符函数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();G();elseprintf(G-.%cn,ch); 4、 非终结符函数F()函数功能描述：根据以上文法要求F-(E)，F-i ，如果当前字符变量ch 为“i”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符,如果当前字符变量ch 为“（”，则显示调用产生式，继续依次嵌套调用非终结符函数E(),函数E()执行结束以后，若果ch=“）”，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，否则算式匹配失败，程序执行结束；若果ch 不为“i”，又不是“（”则算式匹配失败，程序执行结束。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(匹配不成功！n);exit(0);5、 非终结符函数S()函数功能描述：根据以上文法要求S-*FS| / FS，S-，如果当前字符变量ch 为“*”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，依次嵌套调用非终结符函数F（）和递归调用自身S（）；如果当前字符变量ch 为“/”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量指向下一个字符，依次嵌套调用非终结符函数F（）和递归调用自身S（）；如果当前字符变量ch 既不为“*” 也不为“/”，G 中找不到可以匹配的算式则非终结符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 文本文档，读取一个字符，调用非终结符函数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=#) *p=ch;printf(算式匹配成功！n 算式结果：%sn,string);elseprintf(算式匹配不成功！n);fclose(fp);五、实验思路1、定义部分：定义常量、变量、数据结构。2、初始化：从文件将输入符号串输入到字符缓冲区中。3、利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法开始符号的函数。4、部分代码示例：#include#include#include#includevoid main() FILE *fp;char sym； if(fp=fopen(E:222.txt,r)=NULL) /读取文件内容，并返回文件指针，该指针指向文件的第一个字符fprintf(stderr,error opening.n); exit(1); sym=fgetc(fp);/*把第一个输入符号读进sym*/六、调试验过程：本次实验出现3 次重要错误：（1）出错1：全局变量在main（）函数中重新定义，编译连接执行都没有错误提示，但在运行时候出错；解决方案：删除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);elseprintf(没有右括号“)”匹配不成功！n);exit(0);（3） 出错3：调用非终结符E()执行完以后，则对于一些非法的算式还是成功输出例如i-、i*等；解决方案：在主函数main（）中需要对调用非终结符E()执行完以后的ch 进行判断，如果ch 为“#”则算式匹配成功，否则算式匹配失败，在主函数中添加代码如下：if(ch=#) *p=ch;printf(算式匹配成功！n 算式结果：%sn,string);else printf(算式匹配不成功！n); 七、运行结果：输入一以#结束的符号串(包括+*/（）i#)，并显示输出结果：1、输入一个合法符号串如i+i*i#:程序运行结果为：2、输入一个合法符号串如i+i*#:程序运行结果为：八、总结体会：本次上机实验让我认识了很多，加深了我对递归下降分析法的理解。自上而下语法分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。基于上章的此法分析，通过实验我对本章的语法分析也有了深刻的认识。同时通过本次编程，让我深刻认识编程应该注重细节，编程之前首先要做好分析准备。也使我熟悉了构造词法分析程序的手工方式的相关原理，也锻炼了自己编写算法以及C语言的能力，虽然在试验过程中存在着很多的不足，但经过老师以及同学的指点再加上自己的努力都一一克服了，今后我也会经常通过自己编写此类的代码来提高自己的能力。通过此次实验，使我意识到在做实验之前一定要认真复习课本内容和老师的要求以此来确定该实验要我们实现的是什么，怎么实现，每一步的步骤都要按照流程图认真的去完成，做实验不能有半点马虎。此外，让我了解到如何设计、编制并调试词法分析程序，加深对词法分析原理的理解；实验核心的部分在于如何识别初各个单词的所属类别，实验前可先规划一下试验流程，这样编写起来比较方便容易。我也更多的认识到了自己的不足，也有了很大收获。在理论与实践相结合的基础上，加深对计算机整机概念的了解，也进一步理解了计算机的内部结构和时空关系，进一步理解和掌握微程序控制器的设计思想和具体方法、步骤，从而提高了自己自行设计、调试和分析问题的能力。当然在以后的学习重要更加认真细心，不断的提高自己，才能不断的体会到成功的快乐，也才能不断的提升自己的能力。不什么时候学习都要一丝不苟，在计算机方面更是如此，出现的错误要及时找出并改正，遇到问题要去查相关的资料，反复的上机训练，把各个要注意的问题要想到，同时要形成自己的风格，从每个细节出发，不放过每个知识点。另外，要注意符号的使用。争取让自己有一个明确的知识体系，以牢固掌握所学内容。九、源代码：#include#include#includeFILE *fp; /定义一个全局文件指针变量char ch; /定义一个全局字符变量#define N 20 /定义一个数组大小常量char stringN; /定义一个用于存储算式字符串的数组char *p; /定义一个全局字符指针变量void E();void T();void G();void F();void S();/非终结符Fvoid 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);elseprintf(没有右括号“)”匹配不成功！n);exit(0);elseprintf(算式匹配不成功！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();elseprintf(G-.%cn,ch);/非终结符Tvoid T()printf(T-FS.%cn,ch);F();S();/非终结符Svoid 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();elseprintf(S-.%cn,ch);/非终结符Evoid E()printf(E-TG.%cn,ch);T();G();/主函数void main() printf(:*:nn); p