2022年递归下降分析实验报告 .pdf

《2022年递归下降分析实验报告 .pdf》由会员分享，可在线阅读，更多相关《2022年递归下降分析实验报告 .pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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-x1x2,xn的处理架构如下：处理 x1的程序；处理 x2的程序；,处理 xn的程序；（3）如果右部为空，则不处理。（4）对于右部中的每个符号xi 如果 xi 为终结符号：if(xi= = 当前的符号 ) NextChar()

3、； /% NextChar为前进一个字符函数。 %/ return; else 出错处理名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 22 页 - - - - - - - - - 2 如果 xi 为非终结符号，直接调用相应的过程xi() 三、实验要求程序输入 / 输出示例：对下列文法，用递归下降分析法对任意输入的符号串进行分析：（1）E-TG （2）G-+TG|TG|（3）T-FS （4）S-*FS|/FS| （5）F-(E)|i 输出的格式如下：(1) 输入一以 #结

4、束的符号串 ( 包括+*/ （）i#) ：在此位置输入符号串例如：i+i*i# (2) 输出结果： i+i*i#为合法符号串备注：输入一符号串如i+i*#,要求输出为“非法的符号串” 。注意： 1. 表达式中允许使用运算符（+-*/ ） 、分割符（括号）、字符 I ，结束符 #；2. 如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3. 学有余力的同学， 可以详细的输出推导的过程， 即详细列出每一步使用的产生式。四、 实验内容4.1 功能描述这个程序是一个递归下降分析程序，能够判定输入的一个字符串是否属于给定的文法。如果不是，则会给出一定的出错信息，并且列出每一步使用的产生式。4

5、.2 全局变量及其定义char a50;/-存储输入的字符串char ch; /-暂时存储输入的字符char d200;/-记录当前堆栈中的产生式int n1;/-输入字符串的长度char token;/-当前待分析字符4.3 模块设计int E();/-E过程，对应产生式E-TG int T();/-T过程，对应产生式T-FS int G();/-G过程，对应产生式G-+TG|-TG|int S();/-S过程，对应产生式S-*FS|/FS| int F();/-F过程，对应产生式F-(E)|i void output();/-输出已分析字符串和当前字符void input1();/-输出剩

6、余字符名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 22 页 - - - - - - - - - 3 4.4 程序流程图图 1 主函数 main（）流程图图 2 E 函数（）流程图图 3 T 函数（）流程图结束输出分析信息进行递归下降分析得到第一个字符将开始符放入堆栈获取字符串长度开始输入要处理的字符串Y N 开始输出分析栈内容和当前动作将分析栈的E 换为 TG TG return 1 return 0 结束N 结束Y return 1 return 0 FS 将分析栈

7、的T 换为 FS 开始输出分析栈内容和当前动作名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 22 页 - - - - - - - - - 4 图 4 G 函数（）流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 22 页 - - - - - - - - - 5 图 5 F 函数（）流程图图 6 S 函数（）流程图五、核心代码清单：函数功能描述：

8、根据文法E-TG,先从主函数开始调入第一个非终结符函数执行，并且显示调用产生式，根据程序的状态，调用非终结符函数T（）或 G （） ，进行递归向下分析。int E() int f,t; printf(E-TGt); e0=E; e1=; e2=; e3=T; e4=G; e5=#; output(); flag=1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 22 页 - - - - - - - - - 6 input(); input1(); f=T(); if

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

10、中字符匹配的非终结符。int T() int f,t; printf(T-FSt); e0=T; e1=; e2=; e3=F; e4=S; e5=#; output(); flag=1; input(); input1(); f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1); 函数功能描述： 根据文法 T-FS,先显示算式匹配所用的显示调用的产生式，然后依次嵌套调用非终结符函数F（）和 S（） ，进行递归向下分析。int G() int f; if(ch=+) bi1=ch; 名师资料总结 - - -精品

11、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 22 页 - - - - - - - - - 7 printf(G-+TGt); e0=G; e1=; e2=; e3=+; e4=T; e5=G; e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=T(); if (f=0) return(0); G(); return(1); if(ch=-) bi1=ch; printf(G-+TGt); e0=G; e1=; e2=; e3=+; e4=

12、T; e5=G; e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=T(); if (f=0) return(0); G(); return(1); printf(G-t); e0=G; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 22 页 - - - - - - - - - 8 e1=; e2=; e3=; e4=#; output(); flag=1; input(); input1(); return(1

13、); int S() int f,t; if(ch=*) bi1=ch; printf(S-*FSt); e0=S; e1=; e2=; e3=*; e4=F; e5=S; e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1); if(ch=/) bi1=ch; printf(S-*FSt); e0=S; e1=; e2=; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

14、 - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 22 页 - - - - - - - - - 9 e3=*; e4=F; e5=S; e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1); printf(S-t); e0=S; e1=; e2=; e3=; e4=#; output(); flag=1; ai1=ch; input(); input1(); return

15、(1); printf(S-t); e0=S; e1=; e2=; e3=; e4=#; output(); flag=1; ai1=ch; input(); input1(); return(1); 函数功能描述：根据文法S-*FS|/FS| ，如果当前字符变量ch 为“ *” ，则显示调用产生式，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 22 页 - - - - - - - - - 10 从文件文档中读取下一个字符，让字符指针变量指向下一个字符，依次嵌套调用非终

16、结符函数F （）和递归调用自身S （） ；如果当前字符变量ch 为“/ ” ，则显示调用产生式，从文件文档中读取下一个字符， 让字符指针变量指向下一个字符，依次嵌套调用非终结符函数F （）和递归调用自身S （） ；如果当前字符变量ch 既不为“ * ” 也不为“ / ” ，G 中找不到可以匹配的算式则非终结符G 指向为空。int F() int f; if(ch=() bi1=ch; printf(F-(E)t); e0=F; e1=; e2=; e3=(; e4=E; e5=); e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=E(

17、); if (f=0) return(0); if(ch=) bi1=ch; printf(F-(E)t); flag=0; input(); input1(); ch=a+i1; else printf(errorn); return(0); else if(ch=i) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 22 页 - - - - - - - - - 11 bi1=ch; printf(F-it); e0=F; e1=; e2=; e3=i; e4=#;

18、output(); flag=0; input(); input1(); ch=a+i1; else printf(errorn); return(0); return(1); void input() int j=0; for (; j=i1-flag; j+) printf(%c,bj); /* 输出分析串 */ printf(tt); printf(%ctt,ch); /* 输出分析字符*/ void input1() int j; for (j=i1+1-flag; jn1; j+) printf(%c,aj); /* 输出剩余字符*/ printf(n); 六、程序运行结果：名师资料

19、总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 22 页 - - - - - - - - - 12 七、实验中遇到的问题：因为前面的好多实习，都是用JAVA 编程实现老师规定的任务，所以对C 语言的编程有点淡忘了。于是，这次决定用C 语言编程实现，以巩固我的C 语言编程能力。在这次实习的过程中，遇到了很多问题。 最令我印象深刻的是内存分配问题上。因为在 JAVA 中不涉及手动分配内存的问名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

20、 - - - - - 名师精心整理 - - - - - - - 第 12 页，共 22 页 - - - - - - - - - 13 题，而在C 语言中对于数组等变量要手动分配内存。所以，在实习中，总是忘了手动分配内存，出现内存读写错误。于是，经过一步一步的Debug 后，发现了问题的所在。还有一个问题是：在添加打印出分析栈内容的时候，打印出来的分析栈内容与自己的预期很不吻合，经过调试才发现在匹配成功后，没有返回1，然后就程序只能接着执行后面的语句，所以导致分析错误。八、实验总结：通过这次实习，不仅使我对递归下降分析过程有了更进一步的了解，而且使我对C 语言的编程进行了温习。这次实验前，花了一

21、个半小时理解书中的理论并且自己在纸上模拟了一遍分析过程。递归下降分析就是对每个非终结符按其产生式结构来构造相应语法分析子程序，其中终结符产生匹配命令，而非终极符则产生过程调用命令。因为文法递归相应子程序也递归，所以称这种方法为递归子程序下降法或递归下降法。有了前面的基础，在编程的时候对程序流程就比较熟悉了。花了一个半小时来设计程序，用了两个小时的时间调试上面出现的错误。通过这次实验，对递归下降分析程序的设计方法有了更深的理解，同时，也提高了自己的程序设计能力和调试技巧。总之，这次实习，我收获很大。九、完整代码：#include #include #include #include char a

22、50 ,b50,d200,e10; char ch; int n1,i1=0,flag=1,n=5; int E(); int E1(); int T(); int G(); int S(); int F(); void input(); void input1(); void output(); int main() /* 递归分析 */ int f,p,j=0; char x; d0=E; d1=; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 22 页 - -

23、- - - - - - - 14 d2=; d3=T; d4=G; d5=#; printf(n 请输入字符串 (长度 TGt); flag=1; input(); input1(); f=T(); if (f=0) return(0); t=G(); if (t=0) return(0); else return(1); int E() int f,t; printf(E-TGt); e0=E; e1=; e2=; e3=T; e4=G; e5=#; output(); flag=1; input(); input1(); f=T(); if (f=0) return(0); t=G();

24、if (t=0) return(0); else return(1); int T() int f,t; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 22 页 - - - - - - - - - 16 printf(T-FSt); e0=T; e1=; e2=; e3=F; e4=S; e5=#; output(); flag=1; input(); input1(); f=F(); if (f=0) return(0); t=S(); if (t=0) retur

25、n(0); else return(1); int G() int f; if(ch=+) bi1=ch; printf(G-+TGt); e0=G; e1=; e2=; e3=+; e4=T; e5=G; e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=T(); if (f=0) return(0); G(); return(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 22 页 - - - - -

26、 - - - - 17 if(ch=-) bi1=ch; printf(G-+TGt); e0=G; e1=; e2=; e3=+; e4=T; e5=G; e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=T(); if (f=0) return(0); G(); return(1); printf(G-t); e0=G; e1=; e2=; e3=; e4=#; output(); flag=1; input(); input1(); return(1); int S() int f,t; if(ch=*) bi1=ch; prin

27、tf(S-*FSt); e0=S; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 22 页 - - - - - - - - - 18 e1=; e2=; e3=*; e4=F; e5=S; e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1); if(ch=/) bi1=ch; pr

28、intf(S-*FSt); e0=S; e1=; e2=; e3=*; e4=F; e5=S; e6=#; output(); flag=0; input(); input1(); ch=a+i1; f=F(); if (f=0) return(0); t=S(); if (t=0) return(0); else return(1); printf(S-t); e0=S; e1=; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 22 页 - - - - - - -

29、- - 19 e2=; e3=; e4=#; output(); flag=1; ai1=ch; input(); input1(); return(1); printf(S-t); e0=S; e1=; e2=; e3=; e4=#; output(); flag=1; ai1=ch; input(); input1(); return(1); int F() int f; if(ch=() bi1=ch; printf(F-(E)t); e0=F; e1=; e2=; e3=(; e4=E; e5=); e6=#; output(); flag=0; input(); input1();

30、ch=a+i1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 22 页 - - - - - - - - - 20 f=E(); if (f=0) return(0); if(ch=) bi1=ch; printf(F-(E)t); flag=0; input(); input1(); ch=a+i1; else printf(errorn); return(0); else if(ch=i) bi1=ch; printf(F-it); e0=F; e1=; e2=;

31、 e3=i; e4=#; output(); flag=0; input(); input1(); ch=a+i1; else printf(errorn); return(0); return(1); void input() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 22 页 - - - - - - - - - 21 int j=0; for (; j=i1-flag; j+) printf(%c,bj); /* 输出分析串 */ printf(tt); pr

32、intf(%ctt,ch); /*输出分析字符 */ void input1() int j; for (j=i1+1-flag; j; dn+2=#; n=n+2; i=n; i=i-2; while(di!=&i!=0) i=i-1; i=i+1; while(di!=e0) i=i+1; q=i; m=q; k=q; while(dm!=) m=m-1; m=m+1; while(m!=q) dn=dm; m=m+1; n=n+1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 22 页 - - - - - - - - - 22 dn=#; for(j=3; ej!=#; j+) dn=ej; n=n+1; k=k+1; while(dk!=) dn=dk; n=n+1; k=k+1; dn=#; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 22 页 - - - - - - - - -