实验四-非递归预测分析

《编译原理实验》—LR分析器院、系(部)计算机科学与技术学院专业及班级计算机科学与技术专业1403班学号1408030322姓名朱浩日期2017年5月29日一、实验目的与任务设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。二、实验要求建立文法及其LL(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非终结符四、文法及其LL(1)分析表的数据结构文法的产生式可用数组Yy_pushtab[]存放。数组的第一个下标是产生式号，第一个产生式的序号为0；每列按逆序存放该产生式右部各符号的常数值，并以0结束。对于该表达式语言XL的LL(1)分析表，可用数组Yy_d[]存放。第一个下标是非终结符数值，第二个下标是终结符数值，数组元素的值为：0(表示接受)，1(表示产生式号)，-1(表示语法错)。数组Yy_d[]的具体内容及表示如下：0123456#；+*()Num-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-112prgm256prgm’257expr258term259expr’260factor261term’262system_goal263数组Yy_pushtab[]的具体内容及表示如下：五、预测分析器总控程序结构预测分析器总控程序使用上面的两个表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]中列出的全部常数压入分析栈；}}}请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程作比较。六、预测分析控制程序的测试用例用预测分析器和手工模拟两种方式对文法的句子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思考：请考虑如何设计并实现LL(1)分析表的自动生成程序。七、实验代码根据上述LALR(1)分析表压缩表示方法，完成LR分析器的程序设计，并添加输出状态栈内容的功能。用上述表达式文法G的一个句子作为输入，进行测试。实验源程序：#includestdio.h#includestring.hchar*action[10][3]={S3#,S4#,NULL,/*ACTION表*/NULL,NULL,acc,S6#,S7#,NULL,S3#,S4#,NULL,r3#,r3#,NULL,NULL,NULL,r1#,S6#,S7#,NULL,NULL,NULL,r3#,r2#,r2#,NULL,NULL,NULL,r2#};intgoto1[10][2]={1,2,/*QOTO表*/0,0,0,5,0,8,0,0,0,0,0,9,0,0,0,0,0,0};charvt[3]={'a','b','#'};/*存放非终结符*/charvn[2]={'S','B'};/*存放终结符*/char*LR[4]={E-S#,S-BB#,B-aB#,B-b#};/*存放产生式*/inta[10];charb[10],c[10],c1;inttop1,top2,top3,top,m,n;voidmain(){intg,h,i,j,k,l,p,y,z,count;charx,copy[10],copy1[10];top1=0;top2=0;top3=0;top=0;a[0]=0;y=a[0];b[0]='#';count=0;z=0;printf(--------------编译原理课程设计--------------\n);printf(-------------------汪鑫-------------------\n);printf(----------------20170527----------------\n);printf(----------------请输入表达式--------------\n);do{scanf(%c,&c1);c[top3]=c1;top3=top3+1;}while(c1!='#');printf(步骤\t状态栈\t\t符号栈\t\t输入串\t\tACTION\tGOTO\n);do{y=z;m=0;n=0;/*y,z指向状态栈栈顶*/g=top;j=0;k=0;x=c[top];count++;printf(%d\t,count);while(m=top1){/*输出状态栈*/printf(%d,a[m]);m=m+1;}printf(\t\t);while(n=top2){/*输出符号栈*/printf(%c,b[n]);n=n+1;}printf(\t\t);while(g=top3){/*输出输入串*/printf(%c,c[g]);g=g+1;}printf(\t\t);while(x!=vt[j]&&j=2)j++;if(j==2&&x!=vt[j]){printf(error\n);return;}if(action[y][j]==NULL){printf(error\n);return;}elsestrcpy(copy,action[y][j]);if(copy[0]=='S'){/*处理移进*/z=copy[1]-'0';top1=top1+1;top2=top2+1;a[top1]=z;b[top2]=x;top=top+1;i=0;while(copy[i]!='#'){printf(%c,copy[i]);i++;}printf(\n);}if(copy[0]=='r'){/*处理归约*/i=0;while(copy[i]!='#'){printf(%c,copy[i]);i++;}h=copy[1]-'0';strcpy(copy1,LR[h]);while(copy1[0]!=vn[k])k++;l=strlen(LR[h])-4;top1=top1-l+1;top2=top2-l+1;y=a[top1-1];p=goto1[y][k];a[top1]=p;b[top2]=copy1[0];z=p;printf(\t);printf(%d\n,p);}}while(action[y][j]!=acc);printf(acc\n);getchar();}七、实验结果八、实验总结通过这次LR0分析器的实验，实现对词法分析程序所提供的单词系列进行语法检查和结构分析，进一步掌握了LR语法的分析过程，对于LR0文法有了更加深刻的理解。完成的LR0分析器只能对于一个特定的文法进行判断，完整的是要求能够对任意一种LR0文法都能够进行判断，在这方面上还需要对程序又进一步的了解才能最终实现，通过后续的努力，终能够将LR0分析器实现。