递归下降分析程序.doc

一、实验目的： 根据某一文法编制调试递归下降分析程序，以便对任意输入的符号串进行分析。本次实验的目的主要是加深对递归下降分析法的理解。二、程序算法描述这次的实习主要是根据以下文法实现一个递归下降分析器，依据文法如下：（1）E->TG（2）G->+TG|TG|（3）T->FS（4）S->*FS|/FS|（5）F->(E)|i在这个递归下降分析器程序中每一个非终结符E、G、T、S和F构造相应的递归函数，函数的名字表示文法左部的非终结符，函数中就是按文法中每个非终结符右部的候选式依次进行匹配，根据对输入串的分析如果非终结符可以用其中的一个候选式替代就返回1，否则返回0。因为该文法中有五个非终结符，所以定义了五个函数，分别为E（），G（），T()，S()和F（）。当输入一串字符串后，就对该字符串进行分析，首先从开始符号分析，所以首先调用E()函数，在E（）函数中会调用T（）和G(),就是每个非终结符的候选式中出现了哪个非终结符就调用哪个函数。所以，将字符串的第一个字符和E中的每个候选式匹配，如果成功就匹配输入字符串的下一个字符，当最后剩下的字符为#时，匹配成功。其实这个工程就是构造一个语法树。 程序总流程图如下：图1 程序总流程图三、关键性代码这个工程的主要工作用五个非终结符生成的句子是否和输入字符串匹配，所以主要的工作是函数E（），G（），T()，S()和F（）的编写。1. 对非终结符E处理的函数E()这个函数主要是根据文法中的E->TG，在E（）中调用了T（）和G（）来进行递归分析，这个就是构造生成树的一个分支。 int E() int f,t;/变量printf("E->TGt");/输出根据的文法 flag=1; outDeduce ();/输出字符串 outputRemain ();/输出剩余字符f=T();if (f=0) return(0); /表示当前分析字符可由非终结符T推导出t=G(); if (t=0) return(0); /表示当前分析字符可由非终结符G推导出else return(1);2. 对非终结符G处理的函数G()这个函数主要是根据文法中G->+TG|-TG|，在函数中调用了T()和G()函数。将当前字符和候选式的第一个字符进行匹配，如果匹配成功，就调用该候选式中涉及到得第一个非终结符对应的函数，一次递归嵌套调用。如果不是由第一个候选式推出然后依次匹配剩下的候选式。int G() int f; if(ch=+) /当前字符式+ bi1=ch; printf("G->+TGt");/说明用的是第一个候选式e0=G;e1=;e2=>e3=+;e4=T;e5=G;e6=#; Compute ();/计算推导式 flag=0;outDeduce ();/输出字符串 outputRemain ();/输出剩余字符 ch=a+i1;/读取当前字符的下一个字符 if (f=0) return(0); /表示当前分析字符可由非终结符T推导出 t=G(); if (t=0) return(0); /表示当前分析字符可由非终结符G推导出 if(ch=-) /当前字符是-bi1=ch;printf("G->+TGt");/说明用的是第二个候选式e0=G;e1=;e2=>e3=+;e4=T;e5=G;e6=#; Compute();/输出推导式 flag=0;outDeduce ();/输出字符串 outputRemain ();/输出剩余字符ch=a+i1;/读取当前字符的下一个字符f=T();if (f=0) return(0); /表示当前分析字符可由非终结符T推导出G();/判断当前分析字符是否是非终结符G的一个产生式return(1);printf("G->t");e0=G;e1=;e2=>e3=;e4=#;Compute ();/推导式计算flag=1;outDeduce ();/输出字符串 outputRemain ();/输出剩余字符 return(1);3.对非终结符T处理的函数T()函数主要是根据文法中的T->FS,在函数中调用F()和S()，进行递归分析，也是构造语法树的一个分支。int T() int f,t;printf("T->FSt");/说明所用的推导式是T->FSe0=T;e1=;e2=>e3=F;e4=S;e5=#; Compute ();/推导式计算flag=1;outDeduce ();/输出字符串outputRemain ();/输出剩余字符f=F();if (f=0) return(0);/表示当前分析字符可由非终结符F推导出t=S();/表示当前分析字符可由非终结符S推导出if (t=0) return(0);else return(1);4. 对非终结符S处理的函数S()函数的主要是文法要求S->*FS|/FS|，在函数中调用F()和S()函数。其实这个过程和对非终结符G的处理很类似，将当然字符与该非终结符的每个候选式的第一个字符进行匹配。比如当然字符为*，说明使用第一个候选式，然后调用F()和S()函数进行递归分析。如果当前字符为/，就使用第二个候选式，然后也调用F()和S()函数进行递归分析。如果当前字符是在和G中的任何一个候选式的第一个字符都不匹配，就返回1,说明当然字符不能由非终结符G推出。int S()int f,t;if(ch=*) /当前字符是*bi1=ch;printf("S->*FSt");/说明使用的是第一个候选式e0=S;e1=;e2=>e3=*;e4=F;e5=S;e6=#;Compute ();/推导式计算flag=0;outDeduce ();/输出字符串 outputRemain ();/输出剩余字符ch=a+i1;/取出当前字符的下一个字符f=F();if (f=0) return(0); /如果当然分析字符可由非终结符F推出t=S();if (t=0) return(0); /如果当然分析字符可由非终结符S推出 else return(1);if(ch=/) /当前字符是/bi1=ch;printf("S->*FSt");/说明使用的是第二个候选式e0=S;e1=;e2=>e3=*;e4=F;e5=S;e6=#;Compute ();/推导式计算flag=0;outDeduce ();/输出字符串 outputRemain ();/输出剩余字符ch=a+i1; /取出当前字符的下一个字符f=F();/如果当然分析字符可由非终结符F推出if (f=0) return(0);t=S();/如果当然分析字符可由非终结符S推出if (t=0) return(0);else return(1); printf("S->t"); e0=S;e1=;e2=>e3=;e4=#; Compute ();/推导式计算 flag=1; ai1=ch; outDeduce ();/输出字符串 outputRemain ();/输出剩余字符 return(1); printf("S->t"); e0=S;e1=;e2=>e3=;e4=#; output();/推导式计算 flag=1; ai1=ch; outDeduce ();/输出字符串 outputRemain ();/输出剩余字符 return(1);5.对非终结符F处理的函数F()函数主要是根据文法中给出的F->(E)|i ，在函数中调用E()。这个过程和前面对其他非终结符的处理差不多，都是根据候选式中涉及的非终结符调用相应的函数。将当前字符和每一个候选式的第一个字符进行匹配，比如如果当然字符是（，就使用第一个候选式，然后调用E()进行递归向下分析。如果当前字符是i,就使用第二个候选式。int F() int f; if(ch=() /当前字符是（bi1=ch;printf("F->(E)t");/说明使用的是第一个候选式 e0=F;e1=;e2=>e3=(;e4=E;e5=);e6=#;Compute ();/推导式计算flag=0;outDeduce ();/输出字符串 outputRemain ();/输出剩余字符ch=a+i1;/读取下一个字符f=E();if (f=0) return(0); /如果当然分析字符可由非终结符E推出if(ch=) /当前字符是)bi1=ch;printf("F->(E)t");/说明使用的是第一个候选式 flag=0;outDeduce ();/输出字符串 input1();/输出剩余字符ch=a+i1;else printf("errorn");return(0); else if(ch=i) /当前字符是ibi1=ch;printf("F->it");/说明使用的是第二个候选式e0=F;e1=;e2=>e3=i;e4=#;Compute ();/推导式计算flag=0;outDeduce ();/输出字符串 outputRemain ();/输出剩余字符ch=a+i1; else printf("errorn");return(0); return(1);四、测试结果这个程序测试时是往命令行中输入一串字符串，来判断该字符串是否是给出文法的一个句型，测试过程窗口中都详细给了出来。这次我测试的字符串是“i+i*i#”。截图如下：如果输入的字符串不是文法的一个句型，窗口中会显示error，说明输入的字符串不正确。这里我测试的字符串是“i+E”，截图如下：五、实习总结这是编译原理的第二次实习，这次的实习主要是实现一个递归下降分析器，主要就是根据一个文法，判断用户输入的字符串是否是该文法的一个句型。这个实现的过程形象点就是构造一个语法树，从开始字符开始，将输入字符串的第一个字符与文法中的非终结符的每个候选式的第一个字符进行匹配，成功后匹配下一个字符，直到字符串的所有字符都能匹配上。这次的实习的过程让我想起了数据结构上学到的树的构建，实现的代码有的地方也参照了网上的程序，实现的过程中出现了很多错误，总之，最后还是实现了。实习中出现的错误有的是将过程没有分析完整，也有的语法出现了错误，自己也请教了同学。通过这次的实习，自己对递归下降分析有了深入的认识，其实课本上的知识自己看的很简单，但是实现的过程是很麻烦的，自己以后也会多多练习。附录：总程序：#include <stdio.h>#include<dos.h>#include<stdlib.h>#include<string.h>char a50 ,b50,d200,e10;/a存放输入的字符串char ch;int n1,i1=0,flag=1,n=5;int E();int T();int G();int S();int F();void outDeduce();void outputRemain();void Compute();void main()/*递归分析*/ int f,p,j=0; char x; d0=E; d1=; d2=> d3=T; d4=G; d5=#; printf("*递归下降分析器*n"); printf("请输入字符串(以#号结束)n"); do scanf("%c",&ch); aj=ch; j+; while(ch!=#); n1=j; ch=b0=a0; printf("文法t分析串tt分析字符t剩余串n"); f=E(); if (f=0) return; if (ch=#) printf("输入字符串正确n"); p=0; x=dp; else printf("errorn"); getchar(); getchar(); return; printf("n"); getchar(); getchar();int E() int f,t; printf("E-TGt"); flag=1; outDeduce();/输出分析串 outputRemain();/输出剩余字符 f=T(); if (f=0) return(0); t=G(); if (t=0) return(0); else return(1);int T() int f,t; printf("T-FSt"); e0=T; e1=; e2=> e3=F; e4=S; e5=#; Compute(); flag=1; outDeduce(); outputRemain(); f=F(); if (f=0) return(0); t=S(); if (t=0) return(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=#; Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; f=T(); if (f=0) return(0); G(); return(1); printf("G-t"); e0=G; e1=; e2=> e3=; e4=#; Compute(); flag=1; outDeduce(); outputRemain(); return(1);int S() int f,t; if(ch=*) bi1=ch; printf("S-*FSt"); e0=S; e1=; e2=> e3=*; e4=F; e5=S; e6=#; Compute(); flag=0; outDeduce(); outputRemain(); 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=#; Compute(); flag=1; ai1=ch; outDeduce(); outputRemain(); return(1);int F() int f; if(ch=() bi1=ch; printf("F-(E)t"); e0=F; e1=; e2=> e3=(; e4=E; e5=); e6=#; Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; f=E(); if (f=0) return(0); if(ch=) bi1=ch; printf("F-(E)t"); flag=0; outDeduce(); outputRemain(); ch=a+i1; else printf("errorn"); return(0); else if(ch=i) bi1=ch; printf("F-it"); e0=F; e1=; e2=> e3=i; e4=#; Compute(); flag=0; outDeduce(); outputRemain(); ch=a+i1; else printf("errorn"); return(0); return(1);void outDeduce() int j=0; for (; j<=i1-flag; j+) printf("%c",bj);/*输出分析串*/ printf("tt"); printf("%ctt",ch); /*输出分析字符*/void outputRemain() int j; for (j=i1+1-flag; j<n1; j+) printf("%c",aj); /*输出剩余字符*/ printf("n");void Compute()/*推导式计算*/ int m,k,j,q; int i=0; m=0; k=0; q=0; i=n; dn=; dn+1=> 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; 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=#;