試驗(yàn)四非遞歸預(yù)測(cè)分析

1、編譯原理實(shí)驗(yàn)一LR分析器院、系信B)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院專業(yè)及班級(jí)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)1403班學(xué)號(hào) 1408030322姓 名 朱浩日期 2017年5月29日一、實(shí)驗(yàn)?zāi)康呐c任務(wù)設(shè)計(jì)一個(gè)非遞歸預(yù)測(cè)分析器，實(shí)現(xiàn)對(duì)表達(dá)式語言的分析，理解自上而下語 法分析方法的基本思想，掌握設(shè)計(jì)非遞歸預(yù)測(cè)分析器的基本方法。二、實(shí)驗(yàn)要求建立文法及其LL(1)分析表表示的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)相應(yīng)的預(yù)測(cè)分析 器，對(duì)源程序經(jīng)詞法分析后生成的二元式代碼流進(jìn)行預(yù)測(cè)分析，如果輸入用是 文法定義的句子則輸出 是，否則輸出 否”。三、文法描述及其LL(1)分析表 表達(dá)式語言(XL)的語法規(guī)則如下：程序表達(dá)式項(xiàng)一項(xiàng)表達(dá)式；|表達(dá)式；程

2、序 表達(dá)式十項(xiàng)|項(xiàng)*因式|因式因式fnum_or_id|(表達(dá)式)將該語言的文法轉(zhuǎn)換為如下的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對(duì)文法中每個(gè)文法符號(hào)指定一個(gè)常數(shù)值，符號(hào)編碼表如下:文法符號(hào)常數(shù)值備注(4終結(jié)符Num6+2)5;1*3#0（#為輸入結(jié)束標(biāo)志）Expr258非終結(jié)符，expr260term259term 262factor261prgm256prgm257system_goal263四、文法及其LL（1）分析表的數(shù)據(jù)結(jié)構(gòu)文法的產(chǎn)生式可用數(shù)組 Yy_pushtab存放。數(shù)組的第一個(gè)下標(biāo)是產(chǎn)生式號(hào)，第一個(gè) 產(chǎn)生式的序號(hào)為0;每列按逆序存放該產(chǎn)生式右部各符號(hào)的常數(shù)值，并以 0結(jié)束。對(duì)于 該表達(dá)式語言XL的LL（1）分析表，可用數(shù)組Yy_d口存放

4、。第一個(gè)下標(biāo)是非終結(jié)符數(shù)值， 第二個(gè)下標(biāo)是終結(jié)符數(shù)值，數(shù)組元素的值為：0（表示接受），1（表示產(chǎn)生式號(hào)），-1（表示語法錯(cuò)）。數(shù)組Yy_d的具體內(nèi)容及表示如下：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數(shù)組Yy_pushtab的具體內(nèi)容及表示如下:0一1257,1, 253, 0

5、RSSJt： -YypOO1256,0 prgmYypOl210Yyp023-YypO3YypO4Yyp05260, 259,0axpr3 七色witWtfW/vW4052S0, 2網(wǎng)痣0expx tern +0YypOG7262, 261,0term7 factorypO7$262, 261, 2, 0term factor *YypQS90YypOS1Q_5, 258, t 0）（YyplO1L6,0史黑Yypll12_256,0好熟Yypl2五、預(yù)測(cè)分析器總控程序結(jié)構(gòu)預(yù)測(cè)分析器總控程序使用上面的兩個(gè)表 Yy_pushtab、Yy_d和一個(gè)分析棧（元 素類型為int）,其結(jié)構(gòu)如下：初始化；

6、/*把開始符號(hào)的常數(shù)值壓入分析站，輸入指向第一個(gè)輸入符號(hào)*/while（分析棧非空）if（棧頂常數(shù)表示一個(gè)終結(jié)符）if（該常數(shù)與輸入符號(hào)的常數(shù)不等）報(bào)語法錯(cuò)；else 把一個(gè)數(shù)從棧頂彈出；advance讀下一輸入符號(hào)；else /* 棧頂?shù)某?shù)表示一個(gè)非終結(jié)符*/what_to_do=Yy_d棧頂常數(shù)當(dāng)前輸入符號(hào)的常數(shù);if（what_to_do= -1）報(bào)語法錯(cuò)；else 把棧頂元素彈出棧；把Yy_pushtabwhat_to_do中歹！J出的全部常數(shù)壓入分析棧；)請(qǐng)實(shí)現(xiàn)該程序。在程序中添加輸出棧內(nèi)容的功能，以便和手工模擬分析過程 作比較。六、預(yù)測(cè)分析控制程序的測(cè)試用例用預(yù)測(cè)分析器和手工模擬

7、兩種方式對(duì)文法的句子1+2;進(jìn)行分析。綜合分析過程可用下表表示。棧(符號(hào))棧(數(shù)值)輸入用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思考：請(qǐng)考慮如何設(shè)計(jì)并實(shí)現(xiàn)LL(1)分析表的自動(dòng)生成程序。七、實(shí)驗(yàn)代碼根據(jù)上述LALR(1

9、)分析表壓縮表示方法，完成 LR分析器的程序設(shè)計(jì)，并添 加輸出狀態(tài)棧內(nèi)容的功能。用上述表達(dá)式文法G的一個(gè)句子作為輸入，進(jìn)行測(cè)試。 實(shí)驗(yàn)源程序：#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,#; /*存放非終結(jié)符 */char vn2=S,B; /* 存放終結(jié)符 */char *LR4=E-S#,S-BB#,B-aB#,B-b#;/*存放產(chǎn)生式 */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、課程設(shè)計(jì)n);printf( 汪鑫n);printf(20170527n);printf( 請(qǐng)輸入表達(dá)式n);doscanf(%c,&c1);ctop3=c1;top3=top3+1;while(c1!=#);printf( 步驟t 狀態(tài)棧 tt 符號(hào)棧 tt 輸入用 ttACTIONtGOTOn);doy=z;m=0;n=0;/*y,z指向狀態(tài)棧棧頂*/g=top;j=0;k=0;x=ctop;count+;printf(%dt,count);while(m=top1)/* 輸出狀態(tài)棧 */ printf(%d,am);m=m+1;printf(tt);while(n=top2)/* 輸出符

12、號(hào)棧 */ 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) /*處理移進(jìn) */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()