试验四非递归预测分析

1、编译原理实验一LR分析器院、系信B)计算机科学与技术学院专业及班级计算机科学与技术专业1403班学号 1408030322姓 名 朱浩日期 2017年5月29日一、实验目的与任务设计一个非递归预测分析器，实现对表达式语言的分析，理解自上而下语 法分析方法的基本思想，掌握设计非递归预测分析器的基本方法。二、实验要求建立文法及其LL(1)分析表表示的数据结构，设计并实现相应的预测分析 器，对源程序经词法分析后生成的二元式代码流进行预测分析，如果输入用是 文法定义的句子则输出 是，否则输出 否”。三、文法描述及其LL(1)分析表 表达式语言(XL)的语法规则如下：程序表达式项一项表达式；|表达式；程

2、序 表达式十项|项*因式|因式因式fnum_or_id|(表达式)将该语言的文法转换为如下的LL(1)文法:1prgmfexpr;prgm8term-2prgm一 prgm9term一3prgm一10term一4expr-term expr 11factor一5expr12factor-6exprf+term expr 13system_goal7expr.factor term *factor term(expr)num一 prgm该LL(1)文法的LL(1)分析表如下:TNNum+*();#prgm111_ _ Aprgm2223expr4455，expr677term88term r i

3、oP 91010factor1211system_goal131313对文法中每个文法符号指定一个常数值，符号编码表如下:文法符号常数值备注(4终结符Num6+2)5;1*3#0（#为输入结束标志）Expr258非终结符，expr260term259term 262factor261prgm256prgm257system_goal263四、文法及其LL（1）分析表的数据结构文法的产生式可用数组 Yy_pushtab存放。数组的第一个下标是产生式号，第一个 产生式的序号为0;每列按逆序存放该产生式右部各符号的常数值，并以 0结束。对于 该表达式语言XL的LL（1）分析表，可用数组Yy_d口存放

4、。第一个下标是非终结符数值， 第二个下标是终结符数值，数组元素的值为：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-112prgm 256prgm，257expr 258term 259expr 260factor 261term 262system_goal 263数组Yy_pushtab的具体内容及表示如下:0一1257,1, 253, 0

5、RSSJt： -YypOO1256,0 prgmYypOl210Yyp023-YypO3YypO4Yyp05260, 259,0axpr3 七色witWtfW/vW4052S0, 2网痣0expx tern +0YypOG7262, 261,0term7 factorypO7$262, 261, 2, 0term factor *YypQS90YypOS1Q_5, 258, t 0）（YyplO1L6,0史黑Yypll12_256,0好熟Yypl2五、预测分析器总控程序结构预测分析器总控程序使用上面的两个表 Yy_pushtab、Yy_d和一个分析栈（元 素类型为int）,其结构如下：初始化；

6、/*把开始符号的常数值压入分析站，输入指向第一个输入符号*/while（分析栈非空）if（栈顶常数表示一个终结符）if（该常数与输入符号的常数不等）报语法错；else 把一个数从栈顶弹出；advance读下一输入符号；else /* 栈顶的常数表示一个非终结符*/what_to_do=Yy_d栈顶常数当前输入符号的常数;if（what_to_do= -1）报语法错；else 把栈顶元素弹出栈；把Yy_pushtabwhat_to_do中歹！J出的全部常数压入分析栈；)请实现该程序。在程序中添加输出栈内容的功能，以便和手工模拟分析过程 作比较。六、预测分析控制程序的测试用例用预测分析器和手工模拟

7、两种方式对文法的句子1+2;进行分析。综合分析过程可用下表表示。栈(符号)栈(数值)输入用What_to_ dosystem_goal2631+2; #12prgm2561+2; #0prgm ; expr257 1 2581+2; #3prgm ; expr term257 1 260 2591+2; #7prgm ; expr term 257 1 260 262 2611+2; #11factor257 1 260 262 61+2; #prgm ; expr term 257 1 260 262+2; #9Num257 1 260+2; #5prgm ; expr term257 1

8、260 259 2+2; #prgm ; expr257 1 260 2592； #7prgm ; expr +term257 1 260 262 2612； #11prgm ; expr term257 1 260 262 62； #prgm ; expr term 257 1 260 262；#9factor257 1 260；#6prgm ; expr term 257 1 260 262；#Num257#2prgm ; expr term，prgm ; expr_ Aprgm ;_ _ Aprgm思考：请考虑如何设计并实现LL(1)分析表的自动生成程序。七、实验代码根据上述LALR(1

9、)分析表压缩表示方法，完成 LR分析器的程序设计，并添 加输出状态栈内容的功能。用上述表达式文法G的一个句子作为输入，进行测试。 实验源程序：#include#includechar *action103=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#;int goto1102=1,2, /*QOTO 表*/0.0,0,5,0,8,0,0,0,0,0,9

10、,0,0,0,0,0,0;char vt3=a,b,#; /*存放非终结符 */char vn2=S,B; /* 存放终结符 */char *LR4=E-S#,S-BB#,B-aB#,B-b#;/*存放产生式 */int a10;char b10,c10,c1;int top1,top2,top3,top,m,n;void main()int g,h,i,j,k,l,p,y,z,count;char x,copy10,copy110;top1=0;top2=0;top3=0;top=0;a0=0;y=a0;b0=#;count=0;z=0; TOC o 1-5 h z printf( 编译原理

11、课程设计n);printf( 汪鑫n);printf(20170527n);printf( 请输入表达式n);doscanf(%c,&c1);ctop3=c1;top3=top3+1;while(c1!=#);printf( 步骤t 状态栈 tt 符号栈 tt 输入用 ttACTIONtGOTOn);doy=z;m=0;n=0;/*y,z指向状态栈栈顶*/g=top;j=0;k=0;x=ctop;count+;printf(%dt,count);while(m=top1)/* 输出状态栈 */ printf(%d,am);m=m+1;printf(tt);while(n=top2)/* 输出符

12、号栈 */ printf(%c,bn);n=n+1;printf(tt);while(g=top3)/* 输出输入用 */ printf(%c,cg);g=g+1;printf(tt);while(x!=vtj&j=2) j+;if(j=2&x!=vtj) printf(errorn);return;if(actionyj=NULL) printf(errorn);return;else strcpy(copy,actionyj);if(copy0=S) /*处理移进 */z=copy1-0;top1=top1+1;top2=top2+1;atop1=z;btop2=x;top=top+1;i

13、=0;while(copyi!=#)printf(%c,copyi);i+；)printf(n);)if(copy0=r) /*处理归约*/i=0;while(copyi!=#) printf(%c,copyi); i+;)h=copy1-0;strcpy(copy1,LRh);while(copy10!=vnk) k+;l=strlen(LRh)-4;top1=top1-l+1;top2=top2-l+1;y=atop1-1;p=goto1yk;atop1=p;btop2=copy10;z=p;printf(t);printf(%dn,p);)while(actionyj!=acc);printf(accn); getchar()