编译原理实验(递归向下语法分析法实验).pdf

编译原理实验(递归向下语法分析法实验).pdf

《编译原理实验(递归向下语法分析法实验).pdf》由会员分享，可在线阅读，更多相关《编译原理实验(递归向下语法分析法实验).pdf（11页珍藏版）》请在冰点文库上搜索。

实验二实验二递归向下分析法递归向下分析法一、一、实验目和要求实验目和要求根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。

本次实验的目的主要是加深对递归下降分析法的理解。

二、二、实验内容实验内容（11）功能描述功能描述1、递归下降分析法的功能词法分析器的功能是利用函数之间的递归调用模拟语法树自上而下的构造过程。

2、递归下降分析法的前提改造文法：

消除二义性、消除左递归、提取左因子，判断是否为LL

（1）文法，3、递归下降分析法实验设计思想及算法为G的每个非终结符号U构造一个递归过程,不妨命名为U。

U的产生式的右边指出这个过程的代码结构：

1）若是终结符号，则和向前看符号对照，若匹配则向前进一个符号；否则出错。

2）若是非终结符号，则调用与此非终结符对应的过程。

当A的右部有多个产生式时,可用选择结构实现。

具体为：

1）对于每个非终结符号U-u1|u2|un处理的方法如下：

U（）ch=当前符号;if（ch可能是u1字的开头）处理u1的程序部分;elseif（ch可能是u2字的开头）处理u2的程序部分;elseerror（）2）对于每个右部u1-x1x2xn的处理架构如下：

处理x1的程序；处理x2的程序；处理xn的程序；3）如果右部为空，则不处理。

4）对于右部中的每个符号xi如果xi为终结符号：

if（xi=当前的符号）NextChar（）；return;else出错处理如果xi为非终结符号，直接调用相应的过程xi（）说明：

NextChar为前进一个字符函数。

（22）程序结构描述程序结构描述程序要求程序要求：

程序输入/输出示例：

对下列文法，用递归下降分析法对任意输入的符号串进行分析：

（1）E-TG

（2）G-+TG|TG（3）G-（4）T-FS（5）S-*FS|/FS（6）S-（7）F-（E）（8）F-i输入出的格式如下：

（1）E盘建立一个文本文档222.txt存储一个以#结束的符号串（包括+*/（）i#），在此位置输入符号串例如：

i+i*i#

（2）输出结果：

i+i*i#为合法符号串备注：

输入一符号串如i+i*#,要求输出为“非法的符号串”函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图。

程序所用主要参数和头文件说明：

程序所用主要参数和头文件说明：

#include#include#includeFILE*fp;/定义一个全局文件指针变量charch;/定义一个全局字符变量#defineN20/定义一个数组大小常量charstringN;/定义一个用于存储算式字符串的数组char*p;/定义一个全局字符指针变量函数说明：

函数说明：

1）非终结符函数E（）函数功能描述：

根据以上文法要求E-TG,所以从主函数开始调入第一个非终结符函数执行，显示调用产生式，依次嵌套调用非终结符函数T（）和G（），进行递归向下分析。

voidE（）printf（E-TG.%cn,ch）;T（）;G（）;2）非终结符函数T（）函数功能描述：

根据以上文法要求T-FS,首先显示算式匹配所用的显示调用的产生式，依次嵌套调用非终结符函数F（）和S（），进行递归向下分析。

voidT（）printf（T-FS.%cn,ch）;F（）;S（）;3）非终结符函数G（）函数功能描述：

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

voidG（）if（ch=+）printf（G-+TG.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;T（）;G（）;elseif（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”，又不是“（”则算式匹配失败，程序执行结束。

voidF（）if（ch=i）printf（F-i.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;elseif（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）;5）非终结符函数S（）函数功能描述：

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

voidS（）if（ch=*）printf（S-*FS.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;F（）;S（）;elseif（ch=/）printf（S-/FS.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;F（）;S（）;elseprintf（S-.%cn,ch）;6）主函数main（）函数功能描述：

从E盘打开一个222.txt文本文档，读取一个字符，调用非终结符函数E（）,非终结符函数E（）,执行完以后，如果ch为“#”则算式匹配成功，否则匹配失败。

main（）if（fp=fopen（E:

222.txt,r）=NULL）/读取文件内容，并返回文件指针，该指针指向文件的第一个字符fprintf（stderr,erroropening.n）;exit（0）;ch=fgetc（fp）;/读取字符只能读一个p=string;printf（递归下降分析所用产生式：

n）;E（）;if（ch=#）*p=ch;printf（算式匹配成功！

n算式结果：

%sn,string）;elseprintf（算式匹配不成功！

n）;fclose（fp）;函数之间的调用关系图函数之间的调用关系图：

*p=（*p=i*p=*p=/*p=+*p=开始输入符号串（#结束）调用函数E（）；调用函数T（）；调用函数F（）；匹配输出，出错终止非终结符调用函数E（）；匹配），出错终止匹配输出，出错终止算式非法调用函数S（）；非终结符匹配输出，出错终止匹配输出，出错终止S-调用函数G（）；非终结符匹配输出，出错终止匹配输出，出错终止S-匹配成功输出，匹配失败终止结束调试运行结果：

调试运行结果：

1）在文件中输入：

i+i*i#运行结果如下图所示：

2）在文件中输入：

i+i-#运行结果如下图所示：

3）在文件中输入：

i+（i*i）#运行结果如下图所示：

4）在文件中输入：

i+（i*i#运行结果如下图所示：

5）在文件中输入：

i+i*i）#运行结果如下图所示：

三、三、实验过程记录实验过程记录本次实验出现3次重要错误：

（1）出错1：

全局变量在main（）函数中重新定义，编译连接执行都没有错误提示，但在运行时候出错；解决方案：

删除main（）函数FILE*fp;

（2）出错2：

算式匹配时候，如果输入字符串中只有“（”时，仍然是能够正确匹配解决方案：

由于没有考虑括号匹配是成对存在的问题，所以这种结果不符合要求，添加右括号匹配代码如下所示：

elseif（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）;elseprintf（算式匹配不成功！

n）;四、实验总结四、实验总结通过本次上机实验让我认识了很多，加深了我对递归下降分析法的理解。

自上而下语法分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。

基于第三章的此法分析，通过实验我对本章的语法分析也有了深刻的认识。

同时通过本次编程，让我深刻认识编程应该注重细节，编程之前首先要做好分析准备。

五、程序源代码五、程序源代码#include#include#includeFILE*fp;/定义一个全局文件指针变量charch;/定义一个全局字符变量#defineN20/定义一个数组大小常量charstringN;/定义一个用于存储算式字符串的数组char*p;/定义一个全局字符指针变量voidE（）;voidT（）;voidG（）;voidF（）;voidS（）;/非终结符FvoidF（）if（ch=i）printf（F-i.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;elseif（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）;voidG（）if（ch=+）printf（G-+TG.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;T（）;G（）;elseif（ch=-）printf（G-TG.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;T（）;G（）;elseprintf（G-.%cn,ch）;/非终结符TvoidT（）printf（T-FS.%cn,ch）;F（）;S（）;/非终结符SvoidS（）if（ch=*）printf（S-*FS.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;F（）;S（）;elseif（ch=/）printf（S-/FS.%cn,ch）;*p=ch;p+;ch=fgetc（fp）;F（）;S（）;elseprintf（S-.%cn,ch）;/非终结符EvoidE（）printf（E-TG.%cn,ch）;T（）;G（）;/主函数voidmain（）if（fp=fopen（E:

222.txt,r）=NULL）/读取文件内容，并返回文件指针，该指针指向文件的第一个字符fprintf（stderr,erroropening.n）;exit（0）;ch=fgetc（fp）;/读取字符只能读一个p=string;printf（递归下降分析所用产生式：

n）;E（）;if（ch=#）*p=ch;printf（算式匹配成功！

n算式结果：

%sn,string）;elseprintf（算式匹配不成功！

n）;fclose（fp）;