非递归预测分析器.doc

预测分析法1．实验目的与任务设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。2．实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。3．实验内容（1）文法描述及其LL(1)分析表表达式语言（XL）的语法规则如下：1．程序→表达式；2．|表达式；程序3．表达式→表达式+项4．|项5．项→项*因式6．|因式7．因式→num_or_id8．|(表达式)将该语言的文法转换为如下的LL(1)文法：1prgm→expr;prgm’8term→factorterm’2prgm’→prgm9term’→*factorterm’3prgm’→ε10term’→ε4expr→termexpr’11factor→(expr)5expr→ε12factor→num6expr’→+termexpr’13system_goal→prgm7expr’→ε该LL(1)文法的LL(1)分析表如下：TNNum+*();#prgm111prgm’2223expr4455expr’677term88term’1091010factor1211system_goal131313对文法中每个文法符号指定一个常数值，符号编码表如下：文法符号常数值备注（Num+);*#4625130终结符（#为输入结束标志）Exprexpr’termterm’factorprgmprgm’system_goal258260259262261256257263非终结符（2）文法及其LL(1)分析表的数据结构文法的产生式可用数组Yy_pushtab[]存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d[]存放。第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0（表示接受），1（表示产生式号），-1（表示语法错）。数组Yy_d[]的具体内容及表示如下：0123456#；+*（）Numprgm256prgm’257expr258term259expr’260factor261term’262system_goal263数组Yy_pushtab[]的具体内容及表示如下：-10-1-10-1021-1-11-11-14-1-1343-1-1-1-17-17-165-1-16-1-1-1-1-110-111-1998-19-1-112-1-112-112（3）预测分析器总控程序结构预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈（元素类型为int），其结构如下：初始化；/*把开始符号的常数值压入分析站，输入指向第一个输入符号*/while(分析栈非空){if(栈顶常数表示一个终结符)257,1,258,0prgm’;expr256,0prgm0260,259,0expr’term0260,259,2,0expr’term+0262,261,0term’factor262,261,2,0term’factor*5,258,4,0)expr(06,0Num256,0prgm0123456789101112Yyp00Yyp01Yyp02Yyp03Yyp04Yyp05Yyp06Yyp07Yyp08Yyp09Yyp10Yyp11Yyp12if(该常数与输入符号的常数不等)报语法错；else{把一个数从栈顶弹出；advance读下一输入符号；}else{/*栈顶的常数表示一个非终结符*/what_to_do=Yy_d[栈顶常数][当前输入符号的常数]；if(what_to_do==-1)报语法错；else{把栈顶元素弹出栈；把Yy_pushtab[what_to_do]中列出的全部常数压入分析栈；}}}请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。（4）用预测分析器和手工模拟两种方式对文法的句子1+2；进行分析。综合分析过程可用下表表示。栈（符号）栈（数值）输入串What_to_dosystem_goalprgmprgm’;exprprgm’;expr’termprgm’;expr’term’factorprgm’;expr’term’Numprgm’;expr’term’prgm’;expr’prgm’;expr’term+prgm’;expr’termprgm’;expr’term’factorprgm’;expr’term’Numprgm’;expr’term’prgm’;expr’prgm’;prgm’26325625712582571260259257126026226125712602626257126026225712602571260259225712602592571260262261257126026262571260262257126025712602622571+2；#1+2；#1+2；#1+2；#1+2；#1+2；#+2；#+2；#+2；#2；#2；#2；#；#；#；##120371195711962（5）请考虑如何设计并实现LL(1)分析表的自动生成程序。源程序：预测分析法源程序：#includeiostream#includefstream#includeiomanip#includestringusingnamespacestd;#definestacksize10#definestringsize20typedefstructsqst//定义分析栈{intdata[stacksize];inttop;//栈顶指针}sqstack;stringword1[]={prgm,prgm',expr,term,expr',factor,term',system_goal};stringword2[]={#,;,+,*,(,),NUM};intmain(){voidout(sqstackst,stringstr,intsp,intk);//输出函数voidinit(intYy_pushtab[13][4],intYy_d[264][7]);//初始化分析栈Yy_d[]与Yy_pushtab[]voidstr_to_st1(stringstr,intst1[]);//对输入字符串的转换voidForeparser(sqstackst,intYy_pushtab[13][4],intYy_d[264][7],intst1[],stringstr);//预测分析法intYy_pushtab[13][4],Yy_d[264][7];intst1[stringsize];stringstr;sqstackst;st.top=-1;//分析栈的初始化st.top++;st.data[st.top]=263;//分析栈初始化#cout请输入字符串:;cinstr;cout栈(符号)栈(数值)输入串What_to_doendl;str_to_st1(str,st1);init(Yy_pushtab,Yy_d);Foreparser(st,Yy_pushtab,Yy_d,st1,str);return0;}voidout(sqstackst,stringstr,intsp,intk)//输出函数{intn,m=0;for(inti=0;i=sp;i++)//输出栈(符号){if(st.data[i]7){coutword2[st.data[i]];n=word2[st.data[i]].length()+1;}else{coutword1[st.data[i]-256];n=word1[st.data[i]-256].length()+1;}m=n+m;}for(i=m;i30;i++)cout;for(i=0;i=sp;i++)//输出栈(数字)coutsetiosflags(ios::left)setw(3)st.data[i];for(inth=sp+1;h6;h++)cout;for(intj=k;jstrlen(str.c_str());j++)//输出输入串coutstr[j];for(intg=strlen(str.c_str())-k;g10;g++)cout;cout;}voidinit(intYy_pushtab[13][4],intYy_d[264][7])//初始化分析栈Yy_d[]与Yy_pushtab[]{inti,j;ifstreaminfile1(1.txt,ios::in);ifstreaminfile2(2.txt,ios::in);for(i=0;i13;i++){for(j=0;j4;j++){infile1Yy_pushtab[i][j];//coutYy_pushtab[i][j];}//coutendl;}for(i=256;i264;i++){for(j=0;j7;j++){infile2Yy_d[i][j];//coutYy_d[i][j];}//coutendl;}infile1.close();infile2.close();}voidstr_to_st1(stringstr,intst1[])//对输入字符串的转化{for(inti=0;istrlen(str.c_str());i++){switch(str[i]){case'(':st1[i]=4;break;case'+':st1[i]=2;break;case')':st1[i]=5;break;case';':st1[i]=1;break;case'*':st1[i]=3;break;case'#':st1[i]=0;break;default:st1[i]=7;}if(str[i]='0'&&str[i]='9')st1[i]=6;}}voidForeparser(sqstackst,intYy_pushtab[13][4],intYy_d[264][7],intst1[],stringstr)//预测分析法{inti,k=0,what_to_do;while(st.top!=-1){out(st,str,st.top,k);if(st.data[st.top]=0&&st.data[st.top]=6)//栈顶元素为终结符if(st.data[st.top]!=st1[k]){cout未能分析成功endl;break;}else{st.top--;k++;coutendl;}else{//栈顶元素为非终结符what_to_do=Yy_d[st.data[st.top]][st1[k]];coutwhat_to_doendl;//输出what_to_doif(what_to_do==-1){coutstr不是本文法句子。endl;break;}else{st.top--;for(i=0;i4;i++)//把Yy_pushtab[what_to_do]中列出的全部常数压入分析栈if(Yy_pushtab[what_to_do][i]!=-1&&Yy_pushtab[what_to_do][i]!=0){st.top++;st.data[st.top]=Yy_pushtab[what_to_do][i];}}}if(st.top==-1&&st1[k]==0)coutstr是本文法句子。endl;}}初始化文件需要放在代码文件夹1、初始化Yy_pushtab[]文件：2、初始化Yy_d[]文件：程序运行截图：1、对文法句子1+2;#进行分析：1+2;#是本文法句子，与手工分析一致。2、