递归下降分析程序Word格式.docx
《递归下降分析程序Word格式.docx》由会员分享，可在线阅读，更多相关《递归下降分析程序Word格式.docx（22页珍藏版）》请在冰点文库上搜索。
printf（"
E-->
TG\t"
）;
//输出根据的文法
flag=1;
outDeduce（）;
//输出字符串
outputRemain（）;
//输出剩余字符
f=T（）;
if（f==0）return（0）;
//表示当前分析字符可由非终结符T推导出
t=G（）;
if（t==0）return（0）;
//表示当前分析字符可由非终结符G推导出elsereturn
（1）;
}
2.对非终结符G处理的函数G（）
这个函数主要是根据文法中G->
+TG|-TG|ε，在函数中调用了T（）和G（）函数。
将当前字符和候选式的第一个字符进行匹配，如果匹配成功，就调用该候选式中涉及到得第一个非终结符对应的函数，一次递归嵌套调用。
如果不是由第一个候选式推出然后依次匹配剩下的候选式。
intG（）
{intf;
if（ch=='
+'
）{//当前字符式‘+’
b[i1]=ch;
printf（"
G-->
+TG\t"
//说明用的是第一个候选式
e[0]='
G'
;
e[1]='
='
e[2]='
>
'
e[3]='
e[4]='
T'
e[5]='
e[6]='
#'
Compute（）;
//计算推导式
flag=0;
outDeduce（）;
outputRemain（）;
ch=a[++i1];
//读取当前字符的下一个字符
if（f==0）return（0）;
if（t==0）return（0）;
//表示当前分析字符可由非终结符G推导出
if（ch=='
-'
）{//当前字符是‘-’
//说明用的是第二个候选式
Compute（）;
//输出推导式
flag=0;
ch=a[++i1];
G（）;
//判断当前分析字符是否是非终结符G的一个产生式
return
（1）;
}
^\t"
e[0]='
^'
Compute（）;
//推导式计算
return
（1）;
3.对非终结符T处理的函数T（）
函数主要是根据文法中的T->
FS,在函数中调用F（）和S（），进行递归分析，也是构造语法树的一个分支。
intT（）
{intf,t;
T-->
FS\t"
//说明所用的推导式是T-->
F'
S'
outDeduce（）;
f=F（）;
//表示当前分析字符可由非终结符F推导出
t=S（）;
//表示当前分析字符可由非终结符S推导出
elsereturn
（1）;
4.对非终结符S处理的函数S（）
函数的主要是文法要求S->
*FS|/FS|ε，在函数中调用F（）和S（）函数。
其实这个过程和对非终结符G的处理很类似，将当然字符与该非终结符的每个候选式的第一个字符进行匹配。
比如当然字符为‘*’，说明使用第一个候选式，然后调用F（）和S（）函数进行递归分析。
如果当前字符为‘/’，就使用第二个候选式，然后也调用F（）和S（）函数进行递归分析。
如果当前字符是在和G中的任何一个候选式的第一个字符都不匹配，就返回1,说明当然字符不能由非终结符G推出。
intS（）
{
intf,t;
*'
）{//当前字符是‘*’
printf（"
S-->
*FS\t"
//说明使用的是第一个候选式
//取出当前字符的下一个字符
f=F（）;
//如果当然分析字符可由非终结符F推出
t=S（）;
//如果当然分析字符可由非终结符S推出
if（ch=='
/'
）{//当前字符是‘/’
b[i1]=ch;
//说明使用的是第二个候选式
//取出当前字符的下一个字符
//如果当然分析字符可由非终结符F推出
//如果当然分析字符可由非终结符S推出
elsereturn
（1）;
e[0]='
flag=1;
a[i1]=ch;
output（）;
5.对非终结符F处理的函数F（）
函数主要是根据文法中给出的F->
（E）|i，在函数中调用E（）。
这个过程和前面对其他非终结符的处理差不多，都是根据候选式中涉及的非终结符调用相应的函数。
将当前字符和每一个候选式的第一个字符进行匹配，比如如果当然字符是‘（’，就使用第一个候选式，然后调用E（）进行递归向下分析。
如果当前字符是‘i’,就使用第二个候选式。
intF（）
（'
）{//当前字符是‘（’
F-->
（E）\t"
E'
）'
//读取下一个字符
f=E（）;
//如果当然分析字符可由非终结符E推出
）{//当前字符是‘）’
input1（）;
else{
error\n"
return（0）;
}}
elseif（ch=='
i'
）{//当前字符是‘i’
i\t"
else
{printf（"
return（0）;
return
（1）;
四、测试结果
这个程序测试时是往命令行中输入一串字符串，来判断该字符串是否是给出文法的一个句型，测试过程窗口中都详细给了出来。
这次我测试的字符串是“i+i*i#”。
截图如下：
如果输入的字符串不是文法的一个句型，窗口中会显示error，说明输入的字符串不正确。
这里我测试的字符串是“i+E”，截图如下：
五、实习总结
这是编译原理的第二次实习，这次的实习主要是实现一个递归下降分析器，主要就是根据一个文法，判断用户输入的字符串是否是该文法的一个句型。
这个实现的过程形象点就是构造一个语法树，从开始字符开始，将输入字符串的第一个字符与文法中的非终结符的每个候选式的第一个字符进行匹配，成功后匹配下一个字符，直到字符串的所有字符都能匹配上。
这次的实习的过程让我想起了数据结构上学到的树的构建，实现的代码有的地方也参照了网上的程序，实现的过程中出现了很多错误，总之，最后还是实现了。
实习中出现的错误有的是将过程没有分析完整，也有的语法出现了错误，自己也请教了同学。
通过这次的实习，自己对递归下降分析有了深入的认识，其实课本上的知识自己看的很简单，但是实现的过程是很麻烦的，自己以后也会多多练习。
附录：
总程序：
#include<
stdio.h>
#include<
dos.h>
stdlib.h>
string.h>
chara[50],b[50],d[200],e[10];
//a存放输入的字符串
charch;
intn1,i1=0,flag=1,n=5;
intE（）;
intT（）;
intG（）;
intS（）;
intF（）;
voidoutDeduce（）;
voidoutputRemain（）;
voidCompute（）;
voidmain（）/*递归分析*/
intf,p,j=0;
charx;
d[0]='
d[1]='
d[2]='
d[3]='
d[4]='
d[5]='
*************递归下降分析器******************\n"
请输入字符串（以#号结束）\n"
do
{
scanf（"
%c"
&
ch）;
a[j]=ch;
j++;
while（ch!
n1=j;
ch=b[0]=a[0];
文法\t分析串\t\t分析字符\t剩余串\n"
f=E（）;
if（f==0）return;
if（ch=='
）
输入字符串正确\n"
p=0;
x=d[p];
else
getchar（）;
return;
\n"
E--TG\t"
outDeduce（）;
//输出分析串
outputRemain（）;
T--FS\t"
e[1]='
e[2]='
e[3]='
e[4]='
e[5]='
intf;
G--+TG\t"
e[6]='
G--^\t"
S--*FS\t"
S--^\t"
a[i1]=ch;
F--（E）\t"
return（0）;
elseif（ch=='
F--i\t"
voidoutDeduce（）
intj=0;
for（;
j<
=i1-flag;
j++）
b[j]）;
/*输出分析串*/
\t\t"
%c\t\t"
ch）;
/*输出分析字符*/
voidoutputRemain（）
intj;
for（j=i1+1-flag;
n1;
a[j]）;
/*输出剩余字符*/
voidCompute（）/*推导式计算*/
intm,k,j,q;
inti=0;
m=0;
k=0;
q=0;
i=n;
d[n]='
d[n+1]='
d[n+2]='
n=n+2;
i=i-2;
while（d[i]!
&
i!
=0）i=i-1;
i=i+1;
=e[0]）i=i+1;
q=i;
m=q;
k=q;
while（d[m]!
）m=m-1;
m=m+1;
while（m!
=q）
d[n]=d[m];
n=n+1;
for（j=3;
e[j]!
d[n]=e[j];
k=k+1;
while（d[k]!
d[n]=d[k];
升级会员 