实验二递归下降实验

《实验二递归下降实验》由会员分享，可在线阅读，更多相关《实验二递归下降实验（11页珍藏版）》请在金锄头文库上搜索。

1、实验二：递归下降分析法一、实验目的：一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行 分析。本次实验的目的主要是加深对递归下降分析法的理解。 二、实验要求：二、实验要求： 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)输出

2、结果：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） 从数据流中区下

3、一个字符 fopen 文件打开函数，返回指向文件第一个字符的指针 三、功能描述：三、功能描述： 1、递归下降分析法的功能 词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造 过程。 2、递归下降分析法的前提 改造文法：消除二义性、消除左递归、提取左因子，判断是否为LL（1） 文法， 3、递归下降分析法实验设计思想及算法 为G 的每个非终结符号U 构造一个递归过程,不妨命名为U。U的产生式的右边指出这个过程的代码结构： 1) 若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出 错。 2) 若是非终结符号，则调用与此非终结符对应的过程。当A 的右部有多个产 生式时,可用

4、选择结构实现，具体为： 对于每个非终结符号U-u1|u2|un 处理的方法如下： U( ) ch=当前符号; if(ch 可能是u1 字的开头) 处理u1 的程序部分; else if(ch 可能是u2 字的开头)处理u2 的程序部分; else error(); 对于每个右部u1-x1x2xn 的处理架构如下： 处理x1 的程序； 处理x2 的程序； 处理xn 的程序； 如果右部为空，则不处理。 对于右部中的每个符号xi 如果xi 为终结符号： if(xi= = 当前的符号) NextChar()； return; else出错处理 如果xi 为非终结符号，直接调用相应的过程xi() 说明：

5、 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();

6、3、 非终结符函数G() 函数功能描述：根据以上文法要求G-+TG|TG ，G-，如果当前字符变 量ch 为“+”，则显示调用产生式，首先嵌套调用test()函数判断是算式递归 向下分析是否结束，若没有结束则继续依次嵌套调用非终结符函数T（）和 G（）；如果当前字符变量ch 为“-”，则显示调用产生式，从文件文档中读取 下一个字符，让字符指针变量指向下一个字符，继续依次嵌套调用非终结符函 数T（）和G（）；如果当前字符变量ch 既不为“+” 也不为“-”，非终结符G 指向为空，函数只用于显示指向为空，找不到可以和文件中字符匹配的非终结 符。 void G() if (ch=+) printf(

7、“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); 4、 非终结符函数F() 函数功能描述：根据以上文法要求F-(E)，F-i ，如果当前字符变量ch 为“i”，则显示调用产生式，从文件文档中读取下一个字符，让字符指针变量 指向下一个字符,如果当前字符变量ch 为“（”，则显示调用产生式，继续依 次嵌套调用非终结符函数E(),函数E()执行结束以后，

8、若果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); els

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

10、(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

11、“)=NULL) /读取文件内容，并返回文 件指针，该指针指向文件的第一个字符 fprintf(stderr,“error opening.n“); exit(0); ch=fgetc(fp); /读取字符只能读一个 p=string; printf(“递归下降分析所用产生式：n“); E(); if(ch=#) *p=ch; printf(“算式匹配成功！n 算式结果：%sn“,string);else printf(“算式匹配不成功！n“); fclose(fp); 五、实验思路五、实验思路 1、定义部分：定义常量、变量、数据结构。 2、初始化：从文件将输入符号串输入到字符缓冲区中。 3、

12、利用递归下降分析法分析，对每个非终结符编写函数，在主函数中调用文法 开始符号的函数。 4、部分代码示例： #include #include #include #include void 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：

13、全局变量在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); else printf(“没有右括号“)”匹配不成功！n“); exit

14、(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、输入一个合法

15、符号串如i+i*#:程序运行结果为：八、总结体会：八、总结体会： 本次上机实验让我认识了很多，加深了我对递归下降分析法的理解。自 上而下语法分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的 开始符号。基于上章的此法分析，通过实验我对本章的语法分析也有了深刻的 认识。同时通过本次编程，让我深刻认识编程应该注重细节，编程之前首先要 做好分析准备。也使我熟悉了构造词法分析程序的手工方式的相关原理，也锻 炼了自己编写算法以及 C 语言的能力，虽然在试验过程中存在着很多的不足， 但经过老师以及同学的指点再加上自己的努力都一一克服了，今后我也会经常 通过自己编写此类的代码来提高自己的能力。 通过此次实验，使我意识到在做实验之前一定要认真复习课本内容和老 师的要求以此来确定该实验要我们实现的是什么，怎么实现，每一步的步骤都 要按照流程图认真的去完成，做实验不能有半点马虎。此外，让我了解到如何 设计、编制并调试词法分析程序，加深对词法分析原理的理解；实验核心的