實驗四-非遞歸預(yù)測分析

《編譯原理實驗》—LR分析器院、系(部)計算機科學與技術(shù)學院專業(yè)及班級計算機科學與技術(shù)專業(yè)1403班學號1408030322姓名朱浩日期2023年5月29日一、實驗?zāi)康呐c任務(wù)設(shè)計一個非遞歸預(yù)測分析器，實現(xiàn)對表達式語言的分析，理解自上而下語法分析方法的根本思想，掌握設(shè)計非遞歸預(yù)測分析器的根本方法。二、實驗要求建立文法及其LL(1)分析表表示的數(shù)據(jù)結(jié)構(gòu)，設(shè)計并實現(xiàn)相應(yīng)的預(yù)測分析器，對源程序經(jīng)詞法分析后生成的二元式代碼流進行預(yù)測分析，如果輸入串是文法定義的句子那么輸出“是〞，否那么輸出“否〞。三、文法描述及其LL(1)分析表表達式語言(XL)的語法規(guī)那么如下：程序→表達式；|表達式；程序表達式→表達式+項|項項→項*因式|因式因式→num_or_id|(表達式)將該語言的文法轉(zhuǎn)換為如下的LL(1)文法：prgm→expr;prgm’8term→factorterm’prgm’→prgm9term’→*factorterm’prgm’→ε10term’→εexpr→termexpr’11factor→(expr)expr→ε12factor→numexpr’→+termexpr’13system_goal→prgmexpr’→ε該LL(1)文法的LL(1)分析表如下：TNNum+*();#prgm111prgm’2223expr4455expr’677term88term’1091010factor1211system_goal131313對文法中每個文法符號指定一個常數(shù)值，符號編碼表如下：文法符號常數(shù)值備注(Num+);*#4625130終結(jié)符(#為輸入結(jié)束標志)Exprexpr’termterm’factorprgmprgm’system_goal258260259262261256257263非終結(jié)符四、文法及其LL(1)分析表的數(shù)據(jù)結(jié)構(gòu)文法的產(chǎn)生式可用數(shù)組Yy_pushtab[]存放。數(shù)組的第一個下標是產(chǎn)生式號，第一個產(chǎn)生式的序號為0；每列按逆序存放該產(chǎn)生式右部各符號的常數(shù)值，并以0結(jié)束。對于該表達式語言XL的LL(1)分析表，可用數(shù)組Yy_d[]存放。第一個下標是非終結(jié)符數(shù)值，第二個下標是終結(jié)符數(shù)值，數(shù)組元素的值為：0(表示接受)，1(表示產(chǎn)生式號)，-1(表示語法錯)。數(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-112prgm256prgm’257expr258term259expr’260factor261term’262system_goal263數(shù)組Yy_pushtab[]的具體內(nèi)容及表示如下：五、預(yù)測分析器總控程序結(jié)構(gòu)預(yù)測分析器總控程序使用上面的兩個表Yy_pushtab、Yy_d和一個分析棧(元素類型為int)，其結(jié)構(gòu)如下：初始化；/*把開始符號的常數(shù)值壓入分析站，輸入指向第一個輸入符號*/while(分析棧非空){if(棧頂常數(shù)表示一個終結(jié)符)if(該常數(shù)與輸入符號的常數(shù)不等)報語法錯；else{把一個數(shù)從棧頂彈出；advance讀下一輸入符號；}else{/*棧頂?shù)某?shù)表示一個非終結(jié)符*/what_to_do=Yy_d[棧頂常數(shù)][當前輸入符號的常數(shù)]；if(what_to_do==-1)報語法錯；else{把棧頂元素彈出棧；把Yy_pushtab[what_to_do]中列出的全部常數(shù)壓入分析棧；}}}請實現(xiàn)該程序。在程序中添加輸出棧內(nèi)容的功能，以便和手工模擬分析過程作比擬。六、預(yù)測分析控制程序的測試用例用預(yù)測分析器和手工模擬兩種方式對文法的句子1+2；進行分析。綜合分析過程可用下表表示。棧(符號)棧(數(shù)值)輸入串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思考：請考慮如何設(shè)計并實現(xiàn)LL(1)分析表的自動生成程序。七、實驗代碼根據(jù)上述LALR(1)分析表壓縮表示方法，完成LR分析器的程序設(shè)計，并添加輸出狀態(tài)棧內(nèi)容的功能。用上述表達式文法G的一個句子作為輸入，進行測試。實驗源程序：#include<stdio.h>#include<string.h>char*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','#'};/*存放非終結(jié)符*/charvn[2]={'S','B'};/*存放終結(jié)符*/char*LR[4]={"E->S#","S->BB#","B->aB#","B->b#"};/*存放產(chǎn)生式*/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("--------------編譯原理課程設(shè)計--------------\n");printf("-------------------汪鑫-------------------\n");printf("----------------20230527----------------\n");printf("----------------請輸入表達式--------------\n");do{scanf("%c",&c1);c[top3]=c1;top3=top3+1;}while(c1!='#');printf("步驟\t狀態(tài)棧\t\t符號棧\t\t輸入串\t\tACTION\tGOTO\n");do{y=z;m=0;n=0;/*y,z指向狀態(tài)棧棧頂*/g=top;j=0;k=0;x=c[top];count++;printf("%d\t",count);while(m<=top1){/*輸出狀態(tài)棧*/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(a