《编译原理》实验二

《编译原理》实验二1/16实验二预测分析法设计与实现实验时间：2013.5.7，5.21，6.4实验目的设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入串是文法定义的句子则输出“是”，否则输出“否”。实验内容（1）文法描述及其LL(1)分析表表达式语言（XL）的语法规则如下：1．程序→表达式；2．|表达式；程序prgm→expr;prgm’prgm’→prgmprgm’→ε3．表达式→表达式+项4．|项expr→termexpr’expr’→+termexpr’expr’→ε5．项→项*因式6．|因式term→factorterm’term’→*factorterm’term’→ε7．因式→num_or_id8．|(表达式)factor→(expr)factor→num将该语言的文法转换为如下的LL(1)文法：1prgm→expr;prgm’7term→factorterm’2prgm’→prgm8term’→*factorterm’3prgm’→ε9term’→ε4expr→termexpr’10factor→(expr)5expr’→+termexpr’11factor→num6expr’→εfirst(prgm)={(,num}first(prgm’)={(,num,ε}first(expr)={(,num}first(expr’)={+,ε}first(term)={(,num}first(term’)={*,ε}first(factor)={(,num}follow(prgm)={#}follow(prgm’)={#}follow(expr)={;,)}follow(expr’)={;,)}follow(term)={+,;,)}follow(term’)={+,;,)}follow(factor)={*,+,;}select(prgm→expr;prgm’)={(,num}select(prgm’→prgm)={(,num}《编译原理》实验二2/16select(prgm’→ε)={#}select(expr→termexpr’)={(,num}select(expr’→+termexpr’)={+}select(expr’→ε)={;,)}select(term→factorterm’)={(,num}select(term’→*factorterm’)={*}select(term’→ε)={+,;,)}select(factor→(expr))={(}select(factor→num)={num}该LL(1)文法的LL(1)分析表如下：TNNum+*();#prgm11prgm’223expr44expr’566term77term’9899factor1110对文法中每个文法符号指定一个常数值，符号编码表如下：文法符号常数值备注（Num+);*#4625130终结符（#为输入结束标志）Exprexpr’termterm’factorprgmprgm’258260259262261256257非终结符（2）文法及其LL(1)分析表的数据结构文法的产生式可用数组Yy_pushtab[]存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d[]存放。第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0（表示接受），1（表示产生式号），-1（表示语法错）。数组Yy_pushtab[]的具体内容及表示如下：《编译原理》实验二3/16数组Yy_d[]的具体内容及表示如下：0123456#；+*（）Numprgm256prgm’257expr258term259expr’260factor261term’262-1-1-1-10-102-1-1-11-11-1-1-1-13-13-1-1-1-16-16-154-1-15-1-1-1-1-19-110-1887-18-1257,1,258,0prgm’;expr256,0prgm0260,259,0expr’term260,259,2,0expr’term+0262,261,0term’factor262,261,2,0term’factor*5,258,4,0)expr(06,0Num012345678910Yyp00Yyp01Yyp02Yyp03Yyp04Yyp05Yyp06Yyp07Yyp08Yyp09Yyp10《编译原理》实验二4/16（3）预测分析器总控程序结构预测分析器总控程序使用上面的两个表Yy_pushtab、Yy_d和一个分析栈（元素类型为int），其结构如下：初始化；/*把开始符号的常数值压入分析站，输入指向第一个输入符号*/while(分析栈非空){if(栈顶常数表示一个终结符)if(该常数与输入符号的常数不等)报语法错；else{把一个数从栈顶弹出；advance读下一输入符号；}else{/*栈顶的常数表示一个非终结符*/what_to_do=Yy_d[栈顶常数][当前输入符号的常数]；if(what_to_do==-1)报语法错；else{把栈顶元素弹出栈；把Yy_pushtab[what_to_do]中列出的全部常数压入分析栈；}}}请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。（4）用预测分析器和手工模拟两种方式对文法的句子1+2；进行分析。综合分析过程可用下表表示。《编译原理》实验二5/16栈（符号）栈（数值）输入串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)分析表的自动生成程序。下面是一个实例：可作为参考//LL(1)语法分析#includeiostream#includeiomanip#includestring#defineMAX50usingnamespacestd;structT_NT{intcode;charstr[MAX];};T_NTT[7]={{0,#},{1,;},{2,+},{3,*},{4,(},{5,)},{6,Num}};//终结符T_NTNT[8]={{256,prom},{257,prom'},{258,expr},{259,term},//非终结符{260,expr'},{261,factor},{262,term'},{263,system_goal}};typedefstructsqst{intdata[MAX];inttop;}SqStack;《编译原理》实验二6/16intYy_pushtab[13][4]=/*逆序存放产生式右部内容*/{{257,1,258,0},{256,0},{0},{260,259,0},{0},{260,259,2,0},{0},{262,261,0},{262,261,2,0},{0},{5,258,4,0},{6,0},{256,0}};intYy_d[8][7]=//LL1分析表初始化{{-1,0,-1,-1,0,-1,0},{2,1,-1,-1,1,-1,1},{-1,4,-1,-1,3,4,3},{-1,-1,-1,-1,7,-1,7},{-1,6,5,-1,-1,6,-1},{-1,-1,-1,-1,10,-1,11},{-1,9,9,8,-1,9,-1},{-1,12,-1,-1,12,-1,12},};intmain(){SqStackst;inti=0,j=0,l=0;intq,k,m,n,a,what_to_do;charc,t[MAX];ints[MAX];cout请输入该文法的句型;while(c!='#'){cinc;t[l]=c;l++;if(c='0'&&c='9')s[i]=6;else{《编译原理》实验二7/16switch(c){case'(':s[i]=4;break;case'+':s[i]=2;break;case')':s[i]=5;break;case';':s[i]=1;break;case'*':s[i]=3;break;case'#':s[i]=0;break;}}i++;}coutLL1文法非递归预测分析表如下:endl;cout栈符号│|栈数值│|输入串│|what_to_doendl;st.top=-1;st.top++;st.data[st.top]=263;while(st.top!=-1)//栈非空{intp=0;while(p=st.top){for(l=0;l8;l++)if(NT[l].code==st.data[p])coutNT[l].str;for(i=0;i7;i++)if(T[i].code==st.data[p])coutT[i].str;p++;}coutleft│|;p=0;while(p=st.top){coutst.data[p];p++;}cout│|;for(a=j;a5;a++)coutt[a];if(st.data[st.top]=0&&st.data[st.top]7)//栈顶为终结符{if(st.data[st.top]!=s[j])//栈顶常数与输入符号常数不等cout语法错误;《编译原理》实验二8/16else{st.top--;//把一个数从栈顶弹出j++;//读下一输入符号}}else//栈顶常数为一个非终结符{m=st.data[st.top]-256;n=s[j];what_to_do=Yy_d[m][n];cout│|;coutwhat_to_do;if(what_to_do==-1)cout语法错误;else{st.top--;//把元素从栈顶弹出k=0;while(Yy_pushtab[what_to_do][k]!=0){st.top++;st.data[st.top]=Yy_pushtab[what_to_do][k];k++;}}}coutendl;}return0;}《编译原理》实验二9/16//简单词法分析器#includestdio.h#includeio.h#includectype.h#includealloc.h#includestdlib.h#includestring.h#defineNULL0FILE*fp;charcbuffer;char*key[21]={AND,BEGIN,CONST,DIV,DO,ELSE,END,FUNCTION,IF,INTEGER,NOT,OR,PROCEDURE,PROGRAM,READ,R