SLR文法與算符優(yōu)先文法程序?qū)崿F(xiàn)

1、一、設(shè)計(jì)題目1二、運(yùn)行環(huán)境1三、算法設(shè)計(jì)思想11、LR算法思想12、算符優(yōu)先算法思想2四、算法流程圖31、 SLR（1）流程圖32、算符優(yōu)先流程圖4五、算法設(shè)計(jì)分析51、SLR（1）分析設(shè)計(jì)52、算符優(yōu)先文法分析與設(shè)計(jì)7六、運(yùn)行結(jié)果分析81、SLR（1）運(yùn)行結(jié)果82、算符優(yōu)先運(yùn)行結(jié)果8七、收獲及體會(huì)10附錄：程序清單11一、設(shè)計(jì)題目SLR(1)文法與算符優(yōu)先文法程序?qū)崿F(xiàn)二、運(yùn)行環(huán)境操作系統(tǒng)：MicrosoftWindowsXP可視化環(huán)境：MicrosoftVisualC+6.0三、算法設(shè)計(jì)思想1、 LR算法思想LR分析方法在規(guī)范規(guī)約的過程中，一方面記住已移進(jìn)和規(guī)約出的整個(gè)符號(hào)串，即記住“歷史”

2、，另一方面根據(jù)所用的產(chǎn)生式推測(cè)未來可能碰到的輸入符號(hào)，即對(duì)未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號(hào)串呈現(xiàn)于分析棧的頂端時(shí)，我們希望能夠根據(jù)記載的“歷史”和“展望”以及“現(xiàn)實(shí)”的輸入符號(hào)等三個(gè)方面的材料，來確定棧頂?shù)姆?hào)串是否構(gòu)成相對(duì)某一產(chǎn)生式的句柄。LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器(棧)的確定有限狀態(tài)自動(dòng)機(jī)，每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一決定的。LR分析器的核心部分是一張分析表。這張分析表包括兩個(gè)部分，一是“動(dòng)作"(ACTION表，另一是“狀態(tài)轉(zhuǎn)換”(GOTO表。他們都是二維數(shù)組。ACTION(s,a)規(guī)定了當(dāng)狀態(tài)s面臨輸入符號(hào)a時(shí)應(yīng)采取什么動(dòng)作。GOTO(s,X)規(guī)

3、定了狀態(tài)s面對(duì)文法符號(hào)X(終結(jié)符或非終結(jié)符)時(shí)下一狀態(tài)是什么。顯然，GOTO(sX)定義了一個(gè)以文法符號(hào)為字母表的DFA每項(xiàng)ACTION(s，a)所規(guī)定的動(dòng)作不外是下述四種可能之一：(1)移進(jìn)：把(s,a)的下一個(gè)狀態(tài)s'=GOTO(sX)和輸入符號(hào)a推進(jìn)棧,下一輸入符號(hào)變成現(xiàn)行輸入符號(hào)。(2)規(guī)約：指用某一產(chǎn)生式A-3進(jìn)行規(guī)約。假若3的長(zhǎng)度為r,規(guī)約的動(dòng)作是A，去除棧頂?shù)膔個(gè)項(xiàng)，使?fàn)顟B(tài)Sm-r變成棧頂狀態(tài)，然后把(Sm-r,A的下一狀態(tài)s'=GOTO(Sm,A)和文法符號(hào)A推進(jìn)棧。規(guī)約動(dòng)作不改變現(xiàn)行輸入符號(hào)。執(zhí)行規(guī)約動(dòng)作意味著3(=Xm#1,Xm)已呈現(xiàn)1/19于棧頂而且是一

4、個(gè)相對(duì)于A的句柄。(3)接受：宣布分析成功，停止分析器的工作。(4)報(bào)錯(cuò)：發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。圖2LR分析器的模型輸出2、 算符優(yōu)先算法思想算符優(yōu)先分析方法是根據(jù)算符之間的優(yōu)先關(guān)系而設(shè)計(jì)的一種自下而上的分析方法。算符優(yōu)先分析的基本思想是只規(guī)定算符之間的優(yōu)先關(guān)系，也就是只考慮終結(jié)符之間的優(yōu)先關(guān)系。算符優(yōu)先分析過程是自下而上的歸約過程，所謂的算符優(yōu)先分析就是定義算符之間(確切地說，終結(jié)符之間)的某種優(yōu)先關(guān)系，借助于這種優(yōu)先關(guān)系尋找“可歸約串”和進(jìn)行歸約。該文法必須滿足以下條件：文法它的任一產(chǎn)生式的右部都不含兩個(gè)相繼(并列)的非終結(jié)符，即不含如下產(chǎn)生式右部：，QR;首先求出該文法的

5、優(yōu)先關(guān)系表，在程序中用2維數(shù)組表示，-1表示小于或者等于，大于為1,其它為0表示錯(cuò)誤。在輸入一串字符串以后進(jìn)行按照文法一步一步的進(jìn)行規(guī)約，我所進(jìn)行的是直接規(guī)約到文法的符號(hào)而不是規(guī)約到N。數(shù)據(jù)結(jié)構(gòu)使用的是鏈表，用一個(gè)STRUCK表示一個(gè)元素，其中包含符號(hào)和下一個(gè)符號(hào)的指針。算符優(yōu)先分析法的關(guān)鍵是比較兩個(gè)相繼出現(xiàn)的終結(jié)符號(hào)的優(yōu)先級(jí)而決定應(yīng)采取的動(dòng)作。要完成算符間的優(yōu)先級(jí)比較，就要先定義各種可能出相繼出現(xiàn)的運(yùn)算符的優(yōu)先級(jí)，并將其表示成矩陣形式，在分析過程中通過查詢矩陣元素而得算符間的優(yōu)先關(guān)系。四、算法流程圖1、 SLR(1)流程圖|Y尸找到規(guī)約左.L部的A和移,Follow(A)&&

6、、進(jìn)字母集Tfollow(B)=空?產(chǎn)求action集和goto集YY構(gòu)造SLR1分析表2、 算符優(yōu)先流程圖棧置初值K=1,SK='#'當(dāng)期輸入符號(hào)讀入aj=Kj=K-1Q=Sj,j=j-1Error(),Vsj<Q?YSj+1,SK是最左素短語(yǔ)K=j+1,SK=NN五、算法設(shè)計(jì)分析1、SLR(1)分析設(shè)計(jì)(1)將文法：GS:S->Sb|bAaA->aSc|aSb|a拓廣增加文法：(0)M->S(1)S->Sb(2)S->bAa(3)A->aSc(4)A->aSb(5)A->a(2)構(gòu)造拓廣文法GWLR(0)項(xiàng)目集族，初始化

7、項(xiàng)目G'C=closure(S5S)repeatfor對(duì)C的每個(gè)項(xiàng)目集I和每個(gè)文法符號(hào)X,ifgoto(I,X)非空且不在C中then把goto(I,X)加入C中until沒有更多的項(xiàng)目可以加入C沖突分析與解決首先檢測(cè)所有的LR(0)項(xiàng)目集，當(dāng)發(fā)現(xiàn)有移進(jìn)一規(guī)約或規(guī)約一規(guī)約沖突時(shí)，判斷其FOLLOW集是否為空，若為空，說明是SLR(1)文法，若不是，則說明不是SLR(1)文法。計(jì)算FIRSTFOLLOWSunllable(可為空)的算法。將所有的FIRSTSFLLOW初始為空集合，將所有的unllable初始為false。for每一個(gè)終結(jié)符ZFIRSTZZrepeatfor每個(gè)產(chǎn)生式X&

8、gt;Y1Y2,Ykfor每個(gè)i從1到k,每個(gè)j從i+1到k,if所有的Yi都是可為空的ThennullableXtrueifY1Y2,Yi-1都是可為空的ThenFIRSTXFIRSTXUFIRSTYiifYi+1,Yk都是可為空的ThenFOLLOWYiFLLOWYiUFOLLOWXifYi+1,Yj-1都是可為空的ThenFOLLOWYiFOLLOWYiUFIRSTYjUntilFIRSTFOLLOWEDunllable在此輪迭代中沒有改變判斷解決：ifFOLLOWYinFIRST丫卡空該文法是SLR(1)文法else該文法不是SLR(1)文法。(3)構(gòu)造該文法的項(xiàng)目規(guī)范族及轉(zhuǎn)換函數(shù)文法

9、GSLR(0須目集及轉(zhuǎn)換函分析這些項(xiàng)目集，可知在項(xiàng)目集IrI5中存在“移進(jìn)-歸約”沖突，在I9中存在“歸約-歸約”沖突，因此該文法不是LR(0)文法?？紤]含有沖突的項(xiàng)目集，能否用SLR(1)方法來解決。對(duì)于Ii=S'->?S,S->?Sb,由于FOLLOWS')nb=，Ii中的存在“移進(jìn)-歸約”沖突可以用SLR(1)方法來解決。對(duì)于i5=A->a?,S->?bAa,由于followa)nb=anb=，i5中的存在“移進(jìn)-歸約”沖突可以用SLR(1)方法來解決。對(duì)于I9=A->aSD?,S->Sb,由于FOLLOWA)nb=aAb,c,#=,I

10、中的存在“歸約-歸約”沖突可以用SLR(1)方法來解決。該文法是SLR(1)文法，相應(yīng)的文法分析(4)構(gòu)造GS的SLR(1)分析表狀態(tài)ACTION劭作)GOT%換)abc#SA0S211S3acc2rS5r43r1r1r14S65r5S276r2r2r27S9S88r39r4r1r4r1GS的SLR(1)分析表2、算符優(yōu)先文法分析與設(shè)計(jì)(1)對(duì)給定文法：E->E-TE->TT->T/FT->FF->(E)F->i進(jìn)行拓廣有：(0)W->#E#(1)E->E-T(2)E->T(3)T->T/F(4)T->F(5)F->(E)

11、(6)F->i(2)每個(gè)非終結(jié)符的FIRSTV和LASTV磔合如下所示:FIRSTVTLASTVTE-,/,(,I-,/,),IT/,(,I/,iF(,I,IW#(3)構(gòu)造優(yōu)先關(guān)系表-/()i#-><<><>/>><><>(1<<<=<)>>>>i>>>>#<<<<=六、運(yùn)行結(jié)果分析1、SLR(1)運(yùn)行結(jié)果SLR(1分析表生成窯LHCO實(shí)現(xiàn)程序1濾LR。分析表：ACTIONGOTO對(duì)句子baab#進(jìn)行分析2用例惻試.請(qǐng)輸入

12、表達(dá)了卜以H結(jié)束步驟狀態(tài)核符號(hào)楊輸入串ACTIONGOTO16#Jbaah#s2282曲aahKs53S25血dbNr544&24ttbAabUsBS眈4EVhAabitv21601#Sbits37013ttSbftFl1801#Sact扁幅束，請(qǐng)按任意盤結(jié)品.>>.a2、算符優(yōu)先運(yùn)行結(jié)果對(duì)輸入的文法進(jìn)行拓廣苴0=O算符優(yōu)先程序（4=?藏44染整官的產(chǎn)生式的個(gè)數(shù)"汴E->E-TE->TT->TzFT->FF-XE>F->i2經(jīng)添加擴(kuò)展后的產(chǎn)生式如下；E->E-TE->TT->T/FT->FF-XE>

13、F->iW->#E#文涿是算符文法，生成各個(gè)非終結(jié)符的FIRSTV磔合LASTVT!3，各mE終結(jié)件的FIRSTUT臭如F：Fir£tUI(E>=<-,Z,<,OFirstUI<!>*/,<,i>FirstVT(F>-<Ci>FirstUI(M>=<l>La3tUT(T>=/>>i>LastUKF>=<>,1>LaEtUT<U>><H>自動(dòng)生成所給文法的關(guān)系矩陣對(duì)句子（i-i）/i進(jìn)行分析Q清輸入要分析的字符串以回車作

14、為結(jié)束符、Es星規(guī)約的過程；輸入串12rtci-o/in3tKN4#<N5>/i#6ItNT>/ift78ttCN)/iH9ttN10tN/itt11ttH/iIt12itN/NIt13ttHit14ttHH歸為成功，該字符串是該文法的句子，對(duì)句子(i-i進(jìn)行分析戶請(qǐng)輸入要分析的字符串以回車作為結(jié)束符：物的過程：字符枝1L-iB2-i#3-ill4#<N-itt5#<H-in67tt<Hrror歸約失敗.謖字符串不是該文法的句工，七、收獲及體會(huì)本課程設(shè)計(jì)任務(wù)是對(duì)兩種語(yǔ)法分析技術(shù)的實(shí)現(xiàn)：SLR(1/文法和算符優(yōu)先文法。實(shí)現(xiàn)對(duì)SLR(1/文法和算符優(yōu)先文法的判斷

15、及其相應(yīng)分析表的構(gòu)造，能夠完成對(duì)所給的句子進(jìn)行分析，判斷它是否是該文法的句子。其中算符優(yōu)先程序可以自動(dòng)對(duì)所輸入的文法進(jìn)行擴(kuò)展，并生成算符優(yōu)先關(guān)系表和各個(gè)非終結(jié)符的FIRSTVT集和LASTVT集。同時(shí)能對(duì)所給的句子進(jìn)行分析，打印輸出各個(gè)分析棧的狀態(tài)。SLR(1程序可以對(duì)輸入的句子進(jìn)行分析，并打印輸出各個(gè)分析棧的狀態(tài)。在整個(gè)程序設(shè)計(jì)過程中，實(shí)現(xiàn)各個(gè)部分功能都需要利用到程序設(shè)計(jì)語(yǔ)言的知識(shí)和大量編程技巧，也利用到了大量的編譯原理，自動(dòng)生成算符優(yōu)先矩陣是最困難的，其次是自動(dòng)生成FIRSTVT集和LASTVT集也是比較棘手的，代碼量比較大。而由于在SLR(1程序中分析表不是自動(dòng)生成的，所以整個(gè)程序的難易

16、度比算符優(yōu)先小了許多，代碼量也是比較少的。本次編譯原理課程設(shè)計(jì)雖然只經(jīng)過了短短的一周時(shí)間，但是在這期間我學(xué)到了許多，提高了自己的綜合分析問題、解決問題的能力，在此過程中懂得如何將書本的理論知識(shí)應(yīng)用到實(shí)踐中去，加深了對(duì)語(yǔ)法分析特別是算符優(yōu)先和LR分析法思想理解理論知識(shí)的理解，與此同時(shí)也鞏固了我C語(yǔ)言編程的基本能力，對(duì)指針、鏈表、結(jié)構(gòu)體的操作更加熟練，最重要的是本次編譯實(shí)驗(yàn)加深了我對(duì)編譯原理這門課程的理解。從代碼的編寫、修改到文檔的編寫，自己都付出了很大的努力。但是，由于所學(xué)知識(shí)不夠全面，課程設(shè)計(jì)在很多方面還有待完善：在算符優(yōu)先分析過程中編寫的程序原意是可以對(duì)任意文法進(jìn)行分析，但是在測(cè)試時(shí)卻發(fā)現(xiàn)該

17、程序不能對(duì)任意文法進(jìn)行分析，而只能對(duì)確定的一類文法進(jìn)行分析，問題之所在還沒有能夠找出來；在SLR(1次文法部分，分析表不是通過程序自動(dòng)生成的，也沒有實(shí)現(xiàn)對(duì)是否是SLR(1良法進(jìn)行判斷。我相信在以后的學(xué)習(xí)過程中，會(huì)掌握更多知識(shí)，力求做到更好。本次課程設(shè)計(jì)的完成離不開老師的悉心指導(dǎo)和幫助，同時(shí)在本次課程設(shè)計(jì)過程中也得到了同學(xué)們的幫助和支持，他們?cè)谡麄€(gè)過程中給我提出了許多寶貴的意見和建議，再此向各位老師和同學(xué)表示感謝！在老師和同學(xué)們的幫助下，我查閱了大量的資料，完成了本次課程設(shè)計(jì)。最后，在做課程設(shè)計(jì)的過程中，同學(xué)之間那種團(tuán)結(jié)互助，老師那種優(yōu)良的工作的工作作風(fēng)值得我們學(xué)習(xí)，希望在以后的學(xué)習(xí)和工作中也要

18、不斷的發(fā)揚(yáng)這種精神。附錄：程序清單一、SLR(1)程序?qū)崿F(xiàn)#defineNVT4#defineNVN2#defineNLR6charACTION10NVT=/*ACTION表*/NULL,"s2",NULL,NULL,NULL,"s3",NULL,"acc","s5",NULL,NULL,NULL,NULL,"r1","r1","r1","s6",NULL,NULL,NULL,"r5","s2",

19、NULL,NULL,NULL,"r2","r2","r2",NULL,"s9","s8",NULL,"r3",NULL,NULL,NULL,"r4","r1","r1","r1"intGOTO10NVN=1,0,0,0,0,4,0,0,0,0,7,0,0,0,0,0,0,0,0,0;charTerNVT='a','b','c','#'

20、charImTerNVN='S','A'charRuleNLR="M->S","S->Sb","S->bAa","A->aSc","A->aSb","A->a"/*存放產(chǎn)生式*/intState10;/狀態(tài)棧charSymbol10,Input10,ch;voidPrint_LR()intv,c;printf("1>SLR(1)分析表：n");printf("ACTIONt

21、tGOTO'n");for(v=0;v<70;v+)printf("-");printf("tt");printf("狀態(tài)atbtct#tSAn");for(v=0;v<70;v+)printf("-");printf("tt");for(v=0;v<10;v+)printf("%5d",v);for(c=0;c<4;c+)if(ACTIONvc=NULL)ACTIONvc=""printf("%8s&q

22、uot;,ACTIONvc);printf("t");for(c=0;c<2;c+)if(GOTOvc=0)printf("");elseprintf("%4d",GOTOvc);printf("n");for(v=0;v<70;v+)printf("-");printf("tt");for(v=0;v<70;v+)printf("-");printf("tt");voidmain()intStateTop=0;/狀態(tài)

23、棧棧頂intSymbolTop=0;/符號(hào)棧棧頂intInputTop=0;目前輸入串的位置intInputIndex=0;/輸入棧棧頂inti,j,k,y,z,StepCount=0,index;charx,copy4,copy110;State0=0;y=State0;Symbol0='#'z=0;Print_LR();printf("n2>請(qǐng)輸入表達(dá)式(以#結(jié)束):")；doscanf("%c",&ch);nputInputTop=ch;InputTop+;while(ch!='#');printf(&

24、quot;n");for(intv=0;v<70;v+)printf("-");printf("n");printf("步驟t狀態(tài)棧tt符號(hào)棧tt輸入串ttACTIONGOTOn");doy=z;index=0;j=0;k=0;x=InputInputIndex;StepCount+;printf("%3dt",StepCount);while(index<=StateTop)/*輸出狀態(tài)棧*/printf("%d",Stateindex);index+;printf(&q

25、uot;tt");index=0;while(index<=SymbolTop)/*輸出符號(hào)棧printf("%c",Symbolindex);index+;printf("tt");index=InputIndex;while(index<=InputTop)/*輸出輸入串*printf("%c",Inputindex);index+;printf("tt");while(x!=Terj&&j<NVT)j+;if(j=NVT&&x!=Terj)print

26、f("n輸入字符串不是由終結(jié)符組成n");return;if(ACTIONyj=NULL)printf("Error:ActionISNULL!n");return;elsestrcpy(copy,ACTIONyj);if(copy0='s')/*處理移進(jìn)*/if(copy2!='0')z=(copy1-'0')*10+copy2-'0'Elsez=copy1-'0'StateTop+;SymbolTop+;StateStateTop=z;SymbolSymbolTop=x;

27、InputIndex+;i=0;while(copyi!='0')printf("%c",copyi);i+；printf("n");if(copy0='r')/*處理歸約*/i=0;while(copyi!='0')printf("%c",copyi);i+;strcpy(copy1,Rulecopy1-'0');while(copy10!=ImTerk)k+;StateTop=StateTop-(strlen(Rulecopy1-'0')-4)；Sym

28、bolTop=SymbolTop-(strlen(Rulecopy1-'0')-4);y=StateStateTop-1;StateStateTop=GOTOyk;SymbolSymbolTop=copy10;z=GOTOyk;printf("t");printf("%4dn",GOTOyk);while(ACTIONyj!="acc");printf("acc'n");for(intf=0;f<70;f+)printf("-");二、算符優(yōu)先程序?qū)崿F(xiàn)typedef

29、structcharNT;charT;intflag;array;typedefstructcharE;chare;charLode;typedefstructcharLode*base;inttop;charstack;arrayF20;charstr5050;charFirstvt5050;charLastvt5050;intFnum;intTnum;intNTnum;intlec;intFF=1;charr20;intFsignal3030;intFLAG=0;charTsig1130;charTsig2301;voidInitstack(charstack*s)s->base=(

30、charLode*)malloc(30*sizeof(charLode);s->top=-1;voidPush(charstack*s,charLodew)s->top+;s->bases->top.E=w.E;s->bases->top.e=w.e;voidPop(charstack*s,charLode*w)w->E=s->bases->top.E;w->e=s->bases->top.e;s->top-;intIsEmpty(charstacks)if(s.top=-1)return1;elsereturn0;

31、intISTerminator(charch)if(ch>='A'&&ch<='Z')return1;elsereturn0;intYN_Operator_Grammar(intn)intj=3,flag=1,i;for(i=0;i<=n;i+)while(strij!='0')chara=strij;charb=strij+1;if(ISTerminator(a)&&ISTerminator(b)flag=0;break;elsej+;returnflag;voidIS_Operator_pri

32、ority_grammar(intn)inti;for(i=0;i<=n;i+)if(stri3=''|YN_Operator_Grammar(n)=0|FLAG=1)printf("文法G不是算符優(yōu)先文法!n");FF=0;break;if(i>n)printf("G是算符優(yōu)先文法！n");intsearch1(charr,intTnum,chara)inti;for(i=0;i<Tnum;i+)if(ri=a)break;if(i=Tnum)return0;elsereturn1;voidcreateF(intn)i

33、ntk=0,i=1;charc;intj;chart10;t0=str0;while(i<=n)if(tk!=stri0)k+;tk=stri0;i+;Elsei+;Tnum=0;for(i=0;i<=n;i+)j=3;while(strij!='0')c=strij;if(ISTerminator(c)=0)if(!search1(r,Tnum,c)rTnum=c;Tnum+;j+;Fnum=0;for(i=0;i<k;i+)for(j=0;j<Tnum-1;j+)FFnum.NT=ti;FFnum.T=rj;FFnum.flag=0;Fnum+;vo

34、idsearch(charLodew)inti;for(i=0;i<Fnum;i+)if(Fi.NT=w.E&&Fi.T=w.e)Fi.flag=1;break;voidFirstVT(intn)charstacksta;charLodeww;charLodew;inti=0,k;chara,b;Initstack(&sta);while(i<=n)k=3;w.E=stri0;a=strik;b=strik+1;if(!ISTerminator(a)w.e=a;Push(&sta,w);search(w);i+；elseif(ISTerminator

35、(a)&&b!='0'&&!ISTerminator(b)w.e=b;Push(&sta,w);search(w);i+;Elsei+;while(!IsEmpty(sta)Pop(&sta,&ww);for(i=0;i<=n;i+)w.E=stri0;if(stri3=ww.E&&stri4='0')w.e=ww.e;Push(&sta,w);search(w);break;elseif(stri3=ww.E&&w.E!=ww.Ew.e=ww.e;Push(&

36、amp;sta,w);search(w);break;NTnum=0;k=1;i=1;while(i<Fnum)if(Fi-1.flag=1)FirstvtNTnum0=Fi-1.NT;FirstvtNTnumk=Fi-1.T;while(Fi.flag=0&&i<Fnum)i+；if(Fi.flag=1)if(Fi.NT=FirstvtNTnum0)k+;elseFirstvtNTnumk+1='0'NTnum+;k=1;i+；voidLastVT(intn)charstacksta;charLodew;charLodee;chara,b;intk

37、,i;for(i=0;i<Fnum;i+)Fi.flag=0;i=0;Initstack(&sta);while(i<=n)intk=strlen(stri);w.E=stri0;a=strik-1;b=strik-2;if(!ISTerminator(a)w.e=a;Push(&sta,w);/進(jìn)棧search(w);i+;elseif(ISTerminator(a)&&!ISTerminator(b)w.e=b;Push(&sta,w);search(w);i+;elsei+;while(!IsEmpty(sta)Pop(&sta

38、,&e);for(i=0;i<=n;i+)w.E=stri0;if(stri3=e.E&&stri4='0')w.e=e.e;Push(&sta,w);search(w);)k=1;i=1;lec=0;while(i<Fnum)if(Fi-1.flag=1)Lastvtlec0=Fi-1.NT;Lastvtleck=Fi-1.T;while(Fi.flag=0&&i<Fnum)i+;if(Fi.flag=1)if(Fi.NT=Firstvtlec0)k+;elseLastvtleck+1='0'l

39、ec+;k=1;i+;voidcreate_Priority_List(intn)inti,j;intI,mm,pp,J;for(j=1;j<=Tnum;j+)Tsig10j=rj-1;for(i=1;i<=Tnum;i+)Tsig2i0=ri-1;for(i=1;i<=Tnum;i+)for(j=1;j<=Tnum;j+)Fsignalij=0;I=0,J=3;while(I<=n)if(strIJ+1='0')I+;J=3;elsewhile(strIJ+1!='0')charaa=strIJ;charbb=strIJ+1;if

40、(!ISTerminator(aa)&&!ISTerminator(bb)for(i=1;i<=Tnum;i+)if(Tsig2i0=aa)break;for(j=1;j<=Tnum;j+)if(Tsig10j=bb)break;if(Fsignalij=0)Fsignalij=1;elseFLAG=1;I=n+1;J+;if(!ISTerminator(aa)&&ISTerminator(bb)&&strIJ+2!='0'&&!ISTerminator(strIJ+2)for(i=1;i<=Tn

41、um;i+)if(Tsig2i0=aa)break;for(j=1;j<=Tnum;j+)if(Tsig10j=strIJ+2)break;if(Fsignalij=0)Fsignalij=1;elseFLAG=1;I=n+1;if(!ISTerminator(aa)&&ISTerminator(bb)for(i=1;i<=Tnum;i+)if(aa=Tsig2i0)break;for(j=0;j<=NTnum;j+)if(bb=Firstvtj0)break;for(mm=1;Firstvtjmm!='0'mm+)for(pp=1;pp<

42、;=Tnum;pp+)if(Tsig10pp=Firstvtjmm)break;if(Fsignalipp=0)Fsignalipp=2;elseFLAG=1;I=n+1;J+；if(ISTerminator(aa)&&!ISTerminator(bb)for(i=1;i<=Tnum;i+)if(Tsig10i=bb)break;for(j=0；j<=lec；j+)if(aa=Lastvtj0)break;for(mm=1;Lastvtjmm!='0'mm+)for(pp=1;pp<=Tnum;pp+)if(Tsig2pp0=Lastvtjmm

43、)break;if(Fsignalppi=0)Fsignalppi=3;elseFLAG=1;I=n+1;J+;intPriority_Type(chars,charainti=1,j=1;while(Tsig2i0!=s)i+;while(Tsig10j!=a)j+;if(Fsignalij=3)return3;elseif(Fsignalij=2)return2;elseif(Fsignalij=1)return1;elsereturn0;voidprint(chars口,charSTR口20,intq,intu,intii,intk)inti;printf("%4dtt&quo

44、t;,u);for(i=0;i<=k;i+)printf("%c",si);printf("tt");for(i=q;i<=ii;i+)printf("%c",STR0i);printf("tt");voidprocess(charSTR口20,intii)intk=0,q=0,u=0,b,i,j;chars40,a;printf("步驟tt字符棧tt輸入串tt動(dòng)作n");sk='#'print(s,STR,q,u,ii,k);printf("n"

45、);k+;u+;sk=STR0q;q+;print(s,STR,q,u,ii,k);printf("移進(jìn)n");while(q<=ii)a=STRq;if(!ISTerminator(sk)j=k;elsej=k-1;b=Priority_Type(sj,a);if(b=3)charQ=sj;loop:while(ISTerminator(sj-1)j-;if(Priority_Type(sj-1,Q)=2)for(i=j;i<k;i+)si='0'k=j;sk尸N'u+;rint(s,STR,q,u,ii,k);elseQ=s-j;go

46、toloop;printf("歸約n");elseif(b=2|b=1)k+;sk=a;u+;q+;print(s,STR,q,u,ii,k);if(s0='#'&&s1='N'&&s2='#')printf("移進(jìn)n");elseprintf("接受n");elseprintf("errorn");break;if(s0='#'&&s1='N'&&s2='#

47、9;)printf("歸約成功n");elseprintf("歸約失敗n");voidmain()intn,i,j;printf("1>請(qǐng)輸入你要定義的文法G的產(chǎn)生式的個(gè)數(shù)n:");cin>>n;printf("請(qǐng)輸入%d個(gè)文法產(chǎn)生式:n",n);for(i=0;i<n;i+)gets(stri);j=strlen(stri);strij='0'stri0=W;stri1='-'stri2='>'stri3='#'stri4=str00;stri5='#