递归下降程序报告计算机.docx
- 文档编号:6141877
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:19
- 大小:118.73KB
递归下降程序报告计算机.docx
《递归下降程序报告计算机.docx》由会员分享,可在线阅读,更多相关《递归下降程序报告计算机.docx(19页珍藏版)》请在冰点文库上搜索。
递归下降程序报告计算机
递归下降分析程序设计报告
学院:
电信学院
班级:
计算机14
姓名:
薛尚山
学号:
2110505100
指导老师:
冯博琴教授
日期:
2013.11.10
一、实验题目
对下列文法G:
E→TE’
E’→+E|ε
T→FT’
T’→T|ε
F→PF’
F’→*F’|ε
P→(E)|a|b|^
1、构造它的预测分析表。
2、构造它的递归下降分析程序。
一、实验算法
1、构造预测分析表
算法:
输入——G1文法,输出——分析表M
首先应该构造预测分析表
①对文法的每一个A->α,做②和③;
②对于任a∈FIRST(α),把A->α加进M[A,a]
③若ε∈FIRST(α),则把A->α加进M[A,b],b∈FOLLOW(A);
若ε∈FIRST(α),$∈FOLLOW(A),则把A->α加进M[A,$]
要构造预测分析表就要找出各个符号的FIRST(α)和FOLLOW(A)
FIRST(E)={(,a,b,^}
FIRST(E’)={+,ε}
FIRST(T)={(,a,b,^}
FIRST(T’)={(,a,b,^,ε}
FIRST(F)={(,a,b,^}
FIRST(F’)={*,ε}
FIRST(P)={(,a,b,^
FOLLOW(E)={#,}}
FOLLOW(E’)={#,}}
FOLLOW(F)={+,},#}
FOLLOW(F’)={+,},#}
FOLLOW(T)={(,a,b,^,+,),#}
FOLLOW(T’)={(,a,b,^,+,),#}
FOLLOW(P)={*,(,a,b,^,+,),#}
+
*
(
)
a
b
^
#
E
E→TE’
E→TE’
E→TE’
E→TE’
E’
E’→+E
E’→ε
E’→ε
T
T→FT’
T→FT’
T→FT’
T→FT’
T’
T’→ε
T’→T
T’→ε
T’→T
T’→T
T’→T
T’→ε
F
F→PF’
F→PF’
F→PF’
F→PF’
F’
F’→ε
F’→*F’
F’→ε
F’→ε
F’→ε
F’→ε
F’→ε
F’→ε
P
P→(E)
P→a
P→b
P→^
构造预测分析表程序如下:
#include
#include
#include
#include
#include
usingnamespacestd;
structNode1
{
charvn;
charvt;
chars[15];
}MAP[20];//存储分析预测表每个位置对应的终结符,非终结符,产生式
intk;
//用R代表E',W代表T',e代表空
charG[13][13]={"E->TR","R->+E","R->e","T->FW","W->T","W->e","F->PV","V->*V","V->e","P->(E)","P->a","P->b","P->^"};//存储文法中的产生式
charVN[7]={'E','R','T','W','F','V','P'};//存储非终结符
charVT[8]={'+','*','(',')','a','b','^','#'};//存储终结符
charSELECT[13][13]={"(,a,b,^","+","),#","(,a,b,^","(,a,b,^","+,),#","(,a,b,^","*","+,(,),a,b,^","(","a","b","^"};//存储文法中每个产生式对应的SELECT集
charRight[13][13]={"->TR","->+T","->e","->FW","->T","->e","->PV","->*V","->e","->(E)","->a","->b","->^"};
stack
boolcompare(char*a,char*b)
{
inti,la=strlen(a),j,lb=strlen(b);
for(i=0;i for(j=0;j { if(a[i]==b[j]) return1; } return0; } char*Find(charvn,charvt) { inti; for(i=0;i { if(MAP[i].vn==vn&&MAP[i].vt==vt) returnMAP[i].s; } return"error"; } char*Analyse(char*word) { charp,action[15],output[15]; inti=1,j,l=strlen(word),k=0,l_act,m; while(! stak.empty()) stak.pop(); stak.push('#'); stak.push('E'); printf("________________________________________________________________________________\n"); printf("\n对符号串%s的分析过程\n",word); printf("步骤栈顶元素剩余输入串推到所用产生式或匹配\n"); p=stak.top(); while(p! ='#') { printf("%7d",i++); p=stak.top(); stak.pop(); printf("%6c",p); for(j=k,m=0;j output[m++]=word[j]; output[m]='\0'; printf("%10s",output); if(p==word[k]) { if(p=='#') { printf("接受\n"); return"SUCCESS"; } //printf(""%c"匹配\n",p); k++; } else { strcpy(action,Find(p,word[k])); if(strcmp(action,"error")==0) { printf("没有可用的产生式\n"); return"ERROR"; } printf("%c%s\n",p,action); intl_act=strlen(action); if(action[l_act-1]=='e') continue; for(j=l_act-1;j>1;j--) stak.push(action[j]); } } if(strcmp(output,"#")! =0) return"ERROR"; } intmain() { freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); charsource[100]; inti,j,flag,l,m; printf("\n*****为了方便编写程序,用R代表E',W代表T',用V代表F',e代表空*****\n\n"); printf("该文法的产生式如下: \n"); for(i=0;i<13;i++) printf("%s\n",G[i]); printf("________________________________________________________________________________\n"); printf("\n该文法的SELECT集如下: \n"); for(i=0;i<13;i++) { printf("SELECT(%s)={%s}\n",G[i],SELECT[i]); } printf("________________________________________________________________________________\n"); //判断是否是LL (1)文法 flag=1; for(i=0;i<13;i++) { for(j=i+1;j<13;j++) { if(G[i][0]==G[j][0]) { if(compare(SELECT[i],SELECT[j])) { flag=0;break; } } } if(j! =13) break; } if(flag) printf("\n有相同左部产生式的SELECT集合的交集为空,所以文法是LL (1)文法。 \n"); else printf("\n有相同左部产生式的SELECT集合的交集不为空,所以文法不是LL (1)文法。 \n"); printf("________________________________________________________________________________\n"); //预测分析表 for(i=0,k=0;i<13;i++) { l=strlen(SELECT[i]); for(j=0;j { MAP[k].vn=G[i][0]; MAP[k].vt=SELECT[i][j]; strcpy(MAP[k].s,Right[i]); k++; } } printf("\n表达式文法的预测分析表如下: \n\n"); printf(""); for(i=0;i<8;i++) printf("%6c",VT[i]); printf("\n"); for(i=0;i<7;i++) { printf("----------------------------------------------\n"); printf("%6c",VN[i]); for(j=0;j<8;j++) { for(m=0;m { if(VN[i]==MAP[m].vn&&VT[j]==MAP[m].vt) { printf("%6s",MAP[m].s); break; } } if(m==k) printf(""); } printf("\n"); } /*预测分析程序 Analyse函数*/ //输入源文件串 while(cin>>source) { printf("\n分析结果: %s\n\n",Analyse(source)); } while (1); return0; } 运行结果: 2、构造递归下降分析程序 使用一张分析表和一个栈可实现递归下降分析。 定义: 在不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交条件下,构造一个不带回溯的自上而下分析程序,该分析程序由一组递归过程组成,每个过程对应文法的一个非终结符。 每个非终结符所对应的递归子程序如下所示: 1、procedureE; begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginT;E'end elseerror end 2、procedureE'; begin ifsym='+' thenbeginadvance;Eend elseifsym<>')'andsym<>'#'thenerror end 3、procedureT; begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginF;T'end elseerror end 4、procedureT'; begin ifsym='('orsym='a'orsym='b'orsym='^' thenT elseifsym='*'thenerror end 5、procedureF; begin ifsym='('orsym='a'orsym='b'orsym='^' thenbeginP;F'end elseerror end 6、procedureF'; begin ifsym='*' thenbeginadvance;F'end end 7、procedureP; begin ifsym='a'orsym='b'orsym='^' thenadvance elseifsym='('then begin advance;E; ifsym=')'thenadvance elseerror end elseerror end; 将每个分支程序整合调用得到源程序如下: 用到的变量和几个功能识别函数: ①.lookahead=0;//字符串小标,表示使IP指向下一输入符号。 ②.voidE();//功能识别函数,表示规则E->TE' voidE1();//功能识别函数,表示规则E’→+E|ε voidT();//功能识别函数,表示规则T->FT' voidT1();//功能识别函数,表示规则T’→T|ε voidF();//功能识别函数,表示规则F→PF’ voidF1();//功能识别函数,表示规则F’→*F’|ε voidP();//功能识别函数,表示规则P→(E)|a|b|^ 程序如下: #include #include #include #include chara[10]; intlookahead=0; voidE(); voidE1(); voidT(); voidT1(); voidF(); voidF1(); voidP(); voidE() { printf("E->TE'\n"); T(); E1(); } voidE1() { if(a[lookahead]=='+') { printf("E'->+E\n"); lookahead++; //T(); E(); } else printf("E'->ε\n"); } voidT() { printf("T->FT'\n"); F(); T1(); } voidT1() { if(a[lookahead]=='('||'a'||'b'||'^') printf("T'->ε\n"); else { printf("T'->T\n"); T(); } } voidF() { printf("F->PF'\n"); P(); F1(); } voidF1() { if(a[lookahead]=='*') { printf("F'->*F'\n"); lookahead++; //P(); F1(); } else{ printf("F'->ε\n"); } } voidP() { if(a[lookahead]=='a') { printf("P->a\n"); lookahead++; } elseif(a[lookahead]=='b') { printf("P->b\n"); lookahead++; } elseif(a[lookahead]=='^') { printf("P->^\n"); lookahead++; } elseif(a[lookahead]=='(') { lookahead++; E(); if(a[lookahead]==')'){ printf("P->(E)\n"); lookahead++; } else{ printf("\n括号不匹配分析失败! \n"); exit(0); } } else{ printf("括号不匹配,分析失败! \n"); exit(0); } } intmain() { while (1) { printf("请输入算数表达式(以#键结束): "); scanf("%s",a); E(); if((a[lookahead]=='#')) printf("句子结构正确\n"); else printf("无结束标志,分析失败\n"); } return0; } 运行结果如下: 分析正确!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 递归 下降 程序 报告 计算机