實驗五LR0分析法

實驗五：LR(0)分析法1.實驗?zāi)康模篖R(0)分析程序的分析、設(shè)計與實現(xiàn)的基本技術(shù)與一般方法。2.實驗題目：編寫并上機調(diào)試完成識別由下列文法所定義的表達(dá)式的LR(0)分析程序。EE+T|TTT*F|FF(E)|i3.實驗步驟(1)分析：1，拓廣文法： 0:E’->E 1:E->E+T2:E->T3:T->T*F4:T->F5:F->(E)6:F->i2，文法識別表達(dá)式的活前綴的DFA文法識別表達(dá)式的活前綴的DFA3，構(gòu)造LR(0)分析表LR(0)分析表狀態(tài)ACTIONGOTO+*()i#ETF0S4S51231S6Acc2R2S7R2R2R2R23R4R4R4R4R4R44S4S58235R6R6R6R6R6R66S4S5937S4S5108S6S119R1S7R1R1R1R110R3R3R3R3R3R311R5R5R5R5R5R5(2)程序算法流程圖(3)程序參考源碼：/****************************************//* 程序名稱： LR(0)分析程序 *//* 程序用途： 編譯原理實驗(五) *//* 編寫日期： 2005年11月22日 *//* 實驗題目： 對下列文法 *//* E->E+T|T *//* T->T*F|F *//* F->(E)|i *//* LR(0)分析程序 *//* 程序版本： 1.0 Final *//* 程序作者： 黃記瑤B0226047 *//* 作者郵箱： hjy2920@163.com *//****************************************//********************************************************//* 程序相關(guān)說明 *//* 0=+1=*2=(3=)4=i5=#6=E7=T8=F *//********************************************************/#include"stdio.h"#include"malloc.h"#include"math.h"/*使用絕對值函數(shù)*/structLchar{ charchar_ch; structLchar*next;}Lchar,*p,*h,*temp,*top,*base;structLint{ intint_t; structLint*next;}Lint,*itop,*ibase,*itemp;inttable[12][9]={{0,0,-4,0,-5,0,1,2,3}, {-6,0,0,0,0,100,0,0,0}, {12,-7,12,12,12,12,0,0,0}, {14,14,14,14,14,14,0,0,0}, {0,0,-4,0,-5,0,8,2,3}, {16,16,16,16,16,16,0,0,0}, {0,0,-4,0,-5,0,0,9,3}, {0,0,-4,0,-5,0,0,0,10}, {-6,0,0,-11,0,0,0,0,0}, {11,-7,11,11,11,11,0,0,0}, {13,13,13,13,13,13,0,0,0}, {15,15,15,15,15,15,0,0,0}};/*存儲LR(0)分析表，大于10為歸約，小于0為進(jìn)棧，0表示出錯，1到10表示狀態(tài)轉(zhuǎn)移，100表示接受*/charcurchar;charcurtocmp;intcurstate;intright;/*設(shè)置開關(guān)項，當(dāng)出錯時為0*/inti,j;voidpush(charpchar)/*字符棧入棧函數(shù)*/{ temp=malloc(sizeof(Lchar)); temp->char_ch=pchar; temp->next=top; top=temp;}voidpop(void)/*字符棧出棧函數(shù)*/{ if(top->next!=NULL) top=top->next;}voidipop(void)/*狀態(tài)棧出棧函數(shù)*/{ if(itop->next!=NULL) itop=itop->next;}voidipush(intpint)/*狀態(tài)棧入棧函數(shù)*/{ itemp=malloc(sizeof(Lint)); itemp->int_t=pint; itemp->next=itop; itop=itemp;}intchangchartoint(charch)/*將字符轉(zhuǎn)為數(shù)字，以得到算符優(yōu)先值*/{ intt; switch(ch) { case'+':t=0;break; case'*':t=1;break; case'(':t=2;break; case')':t=3;break; case'i':t=4;break; case'#':t=5;break; case'E':t=6;break; case'T':t=7;break; case'F':t=8;break; } returnt;}voiddoforpush(intt){ switch(t) { case1:push('E');break; case2:push('E');break; case3:push('T');break; case4:push('T');break; case5:push('F');break; case6:push('F'); }}voiddosome(void){ intt; printf("\nCharStack\tCharLink\tStateStack\n"); for(;;) { curchar=h->char_ch; curtocmp=top->char_ch; curstate=itop->int_t; i=changchartoint(curchar); t=table[curstate][i]; temp=top; printf("\n"); for(;;)/*打印棧*/ { printf("%c",temp->char_ch); if(temp->char_ch=='#') break; else temp=temp->next; } printf("\t"); temp=h; for(;;)/*打印待比較的字符*/ { printf("%c",temp->char_ch); if(temp->char_ch=='#') break; else temp=temp->next; } printf("\t"); itemp=itop; for(;;)/*打印狀態(tài)棧*/ { printf("%d",itemp->int_t); if(itemp->next==NULL) break; else itemp=itemp->next; } printf("\t"); if(t==0)/*LR(0)分析表為0，出錯*/ { right=0; break; } else/*LR(0)分析表不為0*/ { if(t<0)/*LR(0)分析表小于0，入棧*/ { push(curchar);/*字符入字符棧*/ ipush(abs(t));/*狀態(tài)棧入棧*/ h=h->next; } else/*LR(0)分析表大于0，歸約*/ { if(t==100)/*LR(0)分析表等于100，正確*/ break; if(t==12||t==14||t==16)/*產(chǎn)生式右部和狀態(tài)出棧*/ { pop(); ipop(); } else { pop();pop();pop(); ipop();ipop();ipop(); }/*產(chǎn)生式右部和狀態(tài)出棧*/ doforpush(t-10);/*產(chǎn)生式左部入棧*/ j=changchartoint(top->char_ch); curstate=itop->int_t; ipush(table[curstate][j]);/*狀態(tài)轉(zhuǎn)移，狀態(tài)入棧*/ } } }}voidmain(void){ charch; base=malloc(sizeof(Lchar)); base->next=NULL; base->char_ch='#'; top=base;/*初始化字符棧*/ ibase=malloc(sizeof(Lint)); ibase->int_t=0; ibase->next=NULL; itop=ibase;/*初始化狀態(tài)棧*/ h=malloc(sizeof(Lchar)); h->next=NULL; p=h; do{ /*輸入待比較字符串，以'#'結(jié)束*/ ch=getch(); putch(ch); if(ch=='i'||ch=='+'||ch=='*'||ch=='('||ch==')'||ch=='#')/*輸入合法字符串*/ { temp=malloc(sizeof(Lchar)); temp->next=NULL; temp->char_ch=ch; h->next=temp; h=h->next; } else/*輸入不合法字符串*/ { temp=p->next; printf("\nInputawrongchar!Inputagain:\n"); for(;;)/*打印當(dāng)前字符串*/ { if(temp!=NULL) printf