編譯原理課程設(shè)計(jì)報(bào)告--- slr(1)文法與算符優(yōu)先文法程序?qū)崿F(xiàn)

1、<p>　　課 程 設(shè) 計(jì) 任 務(wù) 書</p><p>　　題目 SLR(1)文法與算符優(yōu)先文法程序?qū)崿F(xiàn) </p><p>　　專業(yè)、班級 </p><p>　　學(xué)號 姓名

2、 </p><p><b>　　主要內(nèi)容</b></p><p>　　構(gòu)造SLR(1)分析表，并用程序?qū)崿F(xiàn)</p><p><b>　　S->Sb|bAa</b></p><p>　　A->aSc|aSb|a</p><p>　　算符優(yōu)先文法處理算術(shù)表達(dá)式<

3、/p><p><b>　　基本要求</b></p><p>　　構(gòu)造SLR(1)分析表，并用程序?qū)崿F(xiàn)，測試某表達(dá)式是否該文法的句子。</p><p>　　根據(jù)算符優(yōu)先分析法并用程序?qū)崿F(xiàn)，將表達(dá)式進(jìn)行語法分析，判斷一個(gè)表達(dá)式是否正確。</p><p><b>　　主要參考資料：</b></p>

4、<p>　　[1] 呂映芝，張素琴等.編譯原理.清華大學(xué)出版社,1998</p><p>　　[2] 胡倫俊，徐蘭芳，駱婷. 編譯原理(第2版).電子工業(yè)出版社,2002</p><p>　　[3] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版). 清華大學(xué)出版社,1997</p><p>　　完 成 期 限： 一周 </p>

5、;<p>　　指導(dǎo)教師簽名： </p><p>　　課程負(fù)責(zé)人簽名： </p><p>　　2011年 6 月 24日</p><p>　　編譯原理課程設(shè)計(jì)總結(jié)報(bào)告</p><p>　　設(shè)計(jì)題目：SLR(1)文法與算符優(yōu)先文法程序?qū)崿F(xiàn)</p><

6、p><b>　　學(xué)生姓名：</b></p><p><b>　　系 別： </b></p><p>　　專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)</p><p>　　班 級：08級2班</p><p><b>　　學(xué) 號：</b></p><p

7、><b>　　指導(dǎo)教師：</b></p><p>　　2011年6月24日</p><p><b>　　目 錄</b></p><p><b>　　一、設(shè)計(jì)題目1</b></p><p><b>　　二、運(yùn)行環(huán)境1</b></p>

8、<p>　　三、算法設(shè)計(jì)思想1</p><p>　　1、LR算法思想1</p><p>　　2、算符優(yōu)先算法思想2</p><p><b>　　四、算法流程圖3</b></p><p>　　1、SLR（1）流程圖3</p><p>　　2、算符優(yōu)先流程圖4</p>

9、;<p>　　五、算法設(shè)計(jì)分析5</p><p>　　1、SLR（1）分析設(shè)計(jì)5</p><p>　　2、算符優(yōu)先文法分析與設(shè)計(jì)7</p><p>　　六、運(yùn)行結(jié)果分析8</p><p>　　1、SLR（1）運(yùn)行結(jié)果8</p><p>　　2、算符優(yōu)先運(yùn)行結(jié)果8</p><

10、p>　　七、收獲及體會(huì)10</p><p>　　附 錄：程序清單11</p><p><b>　　設(shè)計(jì)題目</b></p><p>　　SLR(1)文法與算符優(yōu)先文法程序?qū)崿F(xiàn)</p><p><b>　　二、運(yùn)行環(huán)境</b></p><p>　　操作系統(tǒng)：Micr

11、osoft Windows XP</p><p>　　可視化環(huán)境：Microsoft Visual C++6.0</p><p><b>　　算法設(shè)計(jì)思想</b></p><p><b>　　LR算法思想</b></p><p>　　LR分析方法在規(guī)范規(guī)約的過程中，一方面記住已移進(jìn)和規(guī)約出的整個(gè)符號

12、串，即記住“歷史”，另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入符號，即對未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧的頂端時(shí)，我們希望能夠根據(jù)記載的“歷史”和“展望”以及“現(xiàn)實(shí)”的輸入符號等三個(gè)方面的材料，來確定棧頂?shù)姆柎欠駱?gòu)成相對某一產(chǎn)生式的句柄。</p><p>　　LR分析器實(shí)質(zhì)上是一個(gè)帶先進(jìn)后出存儲(chǔ)器（棧）的確定有限狀態(tài)自動(dòng)機(jī)，每一步工作是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一決定的。</p

13、><p>　　LR分析器的核心部分是一張分析表。這張分析表包括兩個(gè)部分，一是“動(dòng)作”（ACTION）表，另一是“狀態(tài)轉(zhuǎn)換”（GOTO）表。他們都是二維數(shù)組。ACTION(s,a)規(guī)定了當(dāng)狀態(tài)s面臨輸入符號a時(shí)應(yīng)采取什么動(dòng)作。GOTO（s，X）規(guī)定了狀態(tài)s面對文法符號X（終結(jié)符或非終結(jié)符）時(shí)下一狀態(tài)是什么。顯然，GOTO(s，X)定義了一個(gè)以文法符號為字母表的DFA。</p><p>　　每項(xiàng)A

14、CTION(s，a)所規(guī)定的動(dòng)作不外是下述四種可能之一：</p><p>　?。?）移進(jìn) ：把（s，a）的下一個(gè)狀態(tài)s’= GOTO(s，X)和輸入符號a推進(jìn)棧,下一輸入符號變成現(xiàn)行輸入符號。</p><p>　?。?）規(guī)約 ：指用某一產(chǎn)生式A→β 進(jìn)行規(guī)約。假若β的長度為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(

15、Sm-r,A)和文法符號A推進(jìn)棧。規(guī)約動(dòng)作不改變現(xiàn)行輸入符號。執(zhí)行規(guī)約動(dòng)作意味著β（=Xm-r+1…Xm）已呈現(xiàn)于棧頂而且是一個(gè)相對于A的句柄。</p><p>　　（3）接受 ：宣布分析成功，停止分析器的工作。</p><p>　?。?）報(bào)錯(cuò) ：發(fā)現(xiàn)源程序含有錯(cuò)誤，調(diào)用出錯(cuò)處理程序。</p><p><b>　　算符優(yōu)先算法思想</b><

16、;/p><p>　　算符優(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)行歸約。</p><p>　　該文法必須滿足以下條件：文法它的任一產(chǎn)生

17、式的右部都不含兩個(gè)相繼（并列）的非終結(jié)符，即不含如下產(chǎn)生式右部：…QR…；</p><p>　　首先求出該文法的優(yōu)先關(guān)系表，在程序中用2維數(shù)組表示，-1表示小于或者等于，大于為1，其它為0表示錯(cuò)誤。</p><p>　　在輸入一串字符串以后進(jìn)行按照文法一步一步的進(jìn)行規(guī)約，我所進(jìn)行的是直接規(guī)約到文法的符號而不是規(guī)約到N。</p><p>　　數(shù)據(jù)結(jié)構(gòu)使用的是鏈表，用一

18、個(gè)STRUCT來表示一個(gè)元素，其中包含符號和下一個(gè)符號的指針。</p><p>　　算符優(yōu)先分析法的關(guān)鍵是比較兩個(gè)相繼出現(xiàn)的終結(jié)符號的優(yōu)先級而決定應(yīng)采取的動(dòng)作。要完成算符間的優(yōu)先級比較，就要先定義各種可能出相繼出現(xiàn)的運(yùn)算符的優(yōu)先級，并將其表示成矩陣形式，在分析過程中通過查詢矩陣元素而得算符間的優(yōu)先關(guān)系。</p><p><b>　　算法流程圖</b></p>

19、;<p><b>　　SLR（1）流程圖</b></p><p><b>　　算符優(yōu)先流程圖</b></p><p><b>　　算法設(shè)計(jì)分析</b></p><p>　　SLR（1）分析設(shè)計(jì)</p><p>　?。?）將文法：G[S]:S->Sb|bAa

20、 A->aSc|aSb|a 拓廣增加文法：(0) M->S </p><p>　　(1) S->Sb (2) S-> bAa (3) A->aSc (4) A-> aSb (5) A-> a</p><p>　?。?）構(gòu)造拓廣文法G的LR(0)項(xiàng)目集族，初始化項(xiàng)目G’</p><p>　　C=closure ({[

21、S·S ]})</p><p><b>　　repeat </b></p><p>　　for 對C的每個(gè)項(xiàng)目集I和每個(gè)文法符號X，</p><p>　　if goto (I, X)非空且不在C中 </p><p>　　then把goto (I, X)加入C中</p><p>　　unt

22、il 沒有更多的項(xiàng)目可以加入C</p><p><b>　　沖突分析與解決</b></p><p>　　首先檢測所有的LR（0）項(xiàng)目集，當(dāng)發(fā)現(xiàn)有移進(jìn)—規(guī)約或規(guī)約—規(guī)約沖突時(shí)，判斷其FOLLOW集是否為空，若為空，說明是SLR（1）文法，若不是，則說明不是SLR（1）文法。</p><p>　　計(jì)算FIRST、FOLLOW和unllable

23、(可為空)的算法。</p><p>　　將所有的FIRST和FLLOW初始為空集合，將所有的unllable初始為false。</p><p>　　for 每一個(gè)終結(jié)符Z</p><p>　　FIRST[Z][Z]</p><p><b>　　repeat</b></p><p>　　for 每

24、個(gè)產(chǎn)生式X—>Y1Y2…………Yk</p><p>　　for 每個(gè)i從1到k,每個(gè)j從i+1到k,</p><p>　　if所有的Y i都是可為空的</p><p>　　Then nullable[X]true</p><p>　　if Y1Y2……Yi—1都是可為空的</p><p>　　Then

25、 FIRST[X] FIRST[X] U FIRST[Y i]</p><p>　　if Yi+1……Yk都是可為空的</p><p>　　Then FOLLOW[Yi] FLLOW[Yi] U FOLLOW[X]</p><p>　　if Yi+1……Yj-1都是可為空的</p><p>　　Then FOLLOW[Y

26、i] FOLLOW[Yi] U FIRST[Yj]</p><p>　　Until FIRST、FOLLOW和unllable在此輪迭代中沒有改變</p><p><b>　　判斷解決：</b></p><p>　　if FOLLOW[Yi] n FIRST[Yi]=空</p><p>　　該文法是SLR（1）文

27、法</p><p><b>　　else</b></p><p>　　該文法不是SLR（1）文法。</p><p>　?。?）構(gòu)造該文法的項(xiàng)目規(guī)范族及轉(zhuǎn)換函數(shù)</p><p>　　文法G[S]LR(0)項(xiàng)目集及轉(zhuǎn)換函</p><p>　　分析這些項(xiàng)目集，可知在項(xiàng)目集I1、I5中存在“移進(jìn)-歸約”沖

28、突，在I9中存在“歸約-歸約”沖突，因此該文法不是LR（0）文法?？紤]含有沖突的項(xiàng)目集，能否用SLR（1）方法來解決。</p><p>　　對于I1={ S’ -> ?S，S -> ?Sb }，由于FOLLOW（S’）∩=Φ，I1中的存在“移進(jìn)-歸約”沖突可以用SLR（1）方法來解決。</p><p>　　對于I5={ A->a?，S ->?bAa }，由于F

29、OLLOW（A）∩={a}∩=Φ，I5中的存在“移進(jìn)-歸約”沖突可以用SLR（1）方法來解決。</p><p>　　對于I9={ A ->aSb?，S -> Sb? }，由于FOLLOW（A）∩={a}∩{b，c，#}=Φ，I9中的存在“歸約-歸約”沖突可以用SLR（1）方法來解決。</p><p>　　該文法是SLR（1）文法，相應(yīng)的文法分析</p&g

30、t;<p>　?。?）構(gòu)造G[S]的SLR（1）分析表</p><p>　　G[S]的SLR（1）分析表</p><p>　　算符優(yōu)先文法分析與設(shè)計(jì)</p><p>　?。?）對給定文法：E->E-T E->T T->T/F T->F F->(E) F->i進(jìn)行拓廣有：(0) W->#E# (1)

31、E->E-T (2)E->T (3)T->T/F (4)T->F (5)</p><p>　　F->(E) (6)F->i</p><p>　?。?）每個(gè)非終結(jié)符的FIRSTVT和LASTVT集合如下所示：</p><p>　?。?）構(gòu)造優(yōu)先關(guān)系表</p><p><b>　　運(yùn)行結(jié)果分

32、析</b></p><p>　　SLR（1）運(yùn)行結(jié)果</p><p>　　SLR(1)分析表生成</p><p>　　對句子baab#進(jìn)行分析</p><p><b>　　算符優(yōu)先運(yùn)行結(jié)果</b></p><p>　　對輸入的文法進(jìn)行拓廣</p><p>　　生

33、成各個(gè)非終結(jié)符的FIRSTVT集合LASTVT集</p><p>　　自動(dòng)生成所給文法的關(guān)系矩陣</p><p>　　對句子（i-i）/i進(jìn)行分析</p><p>　　對句子（i-i 進(jìn)行分析</p><p><b>　　收獲及體會(huì)</b></p><p>　　本課程設(shè)計(jì)任務(wù)是對兩種語法分析技術(shù)的

34、實(shí)現(xiàn)：SLR(1)類文法和算符優(yōu)先文法。實(shí)現(xiàn)對SLR(1)類文法和算符優(yōu)先文法的判斷及其相應(yīng)分析表的構(gòu)造，能夠完成對所給的句子進(jìn)行分析，判斷它是否是該文法的句子。其中算符優(yōu)先程序可以自動(dòng)對所輸入的文法進(jìn)行擴(kuò)展，并生成算符優(yōu)先關(guān)系表和各個(gè)非終結(jié)符的FIRSTVT集和LASTVT集。同時(shí)能對所給的句子進(jìn)行分析，打印輸出各個(gè)分析棧的狀態(tài)。SLR(1)程序可以對輸入的句子進(jìn)行分析，并打印輸出各個(gè)分析棧的狀態(tài)。在整個(gè)程序設(shè)計(jì)過程中，實(shí)現(xiàn)各個(gè)部分功

35、能都需要利用到程序設(shè)計(jì)語言的知識和大量編程技巧，也利用到了大量的編譯原理，自動(dòng)生成算符優(yōu)先矩陣是最困難的，其次是自動(dòng)生成FIRSTVT集和LASTVT集也是比較棘手的，代碼量比較大。而由于在SLR(1)程序中分析表不是自動(dòng)生成的，所以整個(gè)程序的難易度比算符優(yōu)先小了許多，代碼量也是比較少的。</p><p>　　本次編譯原理課程設(shè)計(jì)雖然只經(jīng)過了短短的一周時(shí)間，但是在這期間我學(xué)到了許多，提高了自己的綜合分析問題、解決

36、問題的能力，在此過程中懂得如何將書本的理論知識應(yīng)用到實(shí)踐中去，加深了對語法分析特別是算符優(yōu)先和LR分析法思想理解理論知識的理解，與此同時(shí)也鞏固了我C語言編程的基本能力，對指針、鏈表、結(jié)構(gòu)體的操作更加熟練，最重要的是本次編譯實(shí)驗(yàn)加深了我對《編譯原理》這門課程的理解。從代碼的編寫、修改到文檔的編寫，自己都付出了很大的努力。但是，由于所學(xué)知識不夠全面，課程設(shè)計(jì)在很多方面還有待完善：在算符優(yōu)先分析過程中編寫的程序原意是可以對任意文法進(jìn)行分析，但

37、是在測試時(shí)卻發(fā)現(xiàn)該程序不能對任意文法進(jìn)行分析，而只能對確定的一類文法進(jìn)行分析，問題之所在還沒有能夠找出來；在SLR(1)類文法部分，分析表不是通過程序自動(dòng)生成的，也沒有實(shí)現(xiàn)對是否是SLR(1)文法進(jìn)行判斷。我相信在以后的學(xué)習(xí)過程中，會(huì)掌握更多知識，力求做到更好。</p><p>　　本次課程設(shè)計(jì)的完成離不開老師的悉心指導(dǎo)和幫助，同時(shí)在本次課程設(shè)計(jì)過程中也得到了同學(xué)們的幫助和支持，他們在整個(gè)過程中給我提出了許多寶貴

38、的意見和建議，再此向各位老師和同學(xué)表示感謝！在老師和同學(xué)們的幫助下，我查閱了大量的資料，完成了本次課程設(shè)計(jì)。最后，在做課程設(shè)計(jì)的過程中，同學(xué)之間那種團(tuán)結(jié)互助，老師那種優(yōu)良的工作的工作作風(fēng)值得我們學(xué)習(xí)，希望在以后的學(xué)習(xí)和工作中也要不斷的發(fā)揚(yáng)這種精神。</p><p><b>　　附 錄：程序清單</b></p><p>　　一、SLR（1）程序?qū)崿F(xiàn)</p>

39、<p>　　#define NVT 4</p><p>　　#define NVN 2</p><p>　　#define NLR 6</p><p>　　char ACTION[10][NVT]={ /*ACTION表*/</p><p>　　NULL,"s2",NULL,NULL,

40、 NULL,"s3",NULL,"acc", "s5",NULL,NULL,NULL, NULL,"r1","r1","r1", "s6&qu

41、ot;,NULL,NULL,NULL, "r5","s2",NULL,NULL,</p><p>　　NULL,"r2","r2","r2", NULL,"s9","s8",NUL

42、L, "r3",NULL,NULL,NULL, "r4","r1","r1","r1"};</p><p>　　int GOTO[10][NVN]={ 1,0, 0,0, 0,4, 0,0, 0,0, 7,0,

43、 0,0, 0,0, 0,0, 0,0};</p><p>　　char Ter[NVT]={'a','b','c','#'};</p><p>　　char ImTer[NVN]={'S','A'};</p><p>　　char Rule[NLR]=<

44、/p><p>　　{"M->S","S->Sb","S->bAa","A->aSc","A->aSb","A->a"}; /*存放產(chǎn)生式*/</p><p>　　int State[10];//狀態(tài)棧</p><p&g

45、t;　　char Symbol[10],Input[10],ch;</p><p>　　void Print_LR(){</p><p><b>　　int v,c;</b></p><p>　　printf("1>SLR(1)分析表:\n");</p><p>　　printf("

46、 ACTION \t\t GOTO\n");</p><p>　　for(v=0;v<70;v++) printf("-");</p><p>　　printf("\t\t");</p><p>　　printf(" 狀 態(tài) a\t b\tc \t# \tS A\n");&l

47、t;/p><p>　　for(v=0;v<70;v++)printf("-");</p><p>　　printf("\t\t");</p><p>　　for(v=0;v<10;v++){</p><p>　　printf("%5d",v);</p><

48、p>　　for(c=0;c<4;c++){</p><p>　　if(ACTION[v][c]==NULL)</p><p>　　ACTION[v][c]=" ";</p><p>　　printf(" %8s",ACTION[v][c]);}</p><p>　　printf("

49、\t ");</p><p>　　for(c=0;c<2;c++){</p><p>　　if(GOTO[v][c]==0)</p><p>　　printf(" ");</p><p>　　else printf("%4d",GOTO[v][c]);}</p>

50、<p>　　printf("\n");}</p><p>　　for(v=0;v<70;v++)</p><p>　　printf("-");</p><p>　　printf("\t\t");</p><p>　　for(v=0;v<70;v++)</

51、p><p>　　printf("-");</p><p>　　printf("\t\t");}</p><p>　　void main(){</p><p>　　int StateTop=0; //狀態(tài)棧棧頂</p><p>　　int SymbolTop=0; //符號棧棧頂

52、</p><p>　　int InputTop=0; //目前輸入串的位置</p><p>　　int InputIndex=0; //輸入棧棧頂</p><p>　　int i,j,k,y,z,StepCount=0,index;</p><p>　　char x,copy[4],copy1[10];</p><

53、p>　　State[0]=0;y=State[0];</p><p>　　Symbol[0]='#';z=0;Print_LR();</p><p>　　printf("\n2>請輸入表達(dá)式(以#結(jié)束):");</p><p><b>　　do{</b></p><p>　

54、　scanf("%c",&ch);</p><p>　　nput[InputTop]=ch;</p><p>　　InputTop++;}while(ch!='#');</p><p>　　printf("\n");</p><p>　　for(int v=0;v<70;v

55、++)printf("-");</p><p>　　printf("\n");</p><p>　　printf("步驟\t狀態(tài)棧\t\t符號棧\t\t輸入串\t\tACTION GOTO\n");</p><p>　　do{y=z; index=0; <

56、;/p><p>　　j=0;k=0;x=Input[InputIndex];StepCount++;</p><p>　　printf("%3d\t",StepCount);while(index<=StateTop) /*輸出狀態(tài)棧*/{ </p><p>　　printf("%d"

57、,State[index]);index++;}</p><p>　　printf("\t\t");index=0;</p><p>　　while(index<=SymbolTop) /*輸出符號棧</p><p>　　{ printf("%c",Symbol[index]);index++;}</p>

58、<p>　　printf("\t\t");</p><p>　　index=InputIndex;</p><p>　　while(index<=InputTop) /*輸出輸入串*{ </p><p>　　printf("%c",Input[index]);index

59、++;}</p><p>　　printf("\t\t");</p><p>　　while(x!=Ter[j]&&j<NVT) j++;</p><p>　　if(j==NVT&&x!=Ter[j]){ </p><p>　　printf("\n輸入字符串不是由終結(jié)符組成\

60、n");return;}</p><p>　　if(ACTION[y][j]==NULL){</p><p>　　printf("Error: Action IS NULL!\n");</p><p><b>　　return;}</b></p><p>　　else strcpy(cop

61、y,ACTION[y][j]);</p><p>　　if(copy[0]=='s') /*處理移進(jìn)*/</p><p>　　{ if(copy[2]!='\0') z=(copy[1]-'0')*10+copy[2]-'0';</p><p>　　Else z=copy[1]-

62、9;0';</p><p>　　StateTop++; SymbolTop++; </p><p>　　State[StateTop]=z;</p><p>　　Symbol[SymbolTop]=x;</p><p>　　InputIndex++; i=0;</p><p>　　while(copy[i]

63、!='\0')</p><p>　　{ printf("%c",copy[i]);</p><p><b>　　i++; }</b></p><p>　　printf("\n");}</p><p>　　if(copy[0]=='r') /*處

64、理歸約*/{ </p><p><b>　　i=0;</b></p><p>　　while(copy[i]!='\0')</p><p>　　{ printf("%c",copy[i]);i++;</p><p>　　} strcp

65、y(copy1,Rule[copy[1]-'0']);</p><p>　　while(copy1[0]!=ImTer[k]) k++; StateTop=StateTop-(strlen(Rule[copy[1]-'0'])-4); SymbolTop=SymbolTop-(strlen(Rule[copy[1]-'0'])-4);</p&g

66、t;<p>　　y=State[StateTop-1]; State[StateTop]=GOTO[y][k]; Symbol[SymbolTop]=copy1[0];</p><p>　　z=GOTO[y][k];printf("\t"); printf("%4d\n",GOTO[y][k]);}</p><p&g

67、t;　　}while(ACTION[y][j]!="acc");</p><p>　　printf("acc\n");</p><p>　　for(int f=0;f<70;f++)printf("-");</p><p><b>　　算符優(yōu)先程序?qū)崿F(xiàn)</b></p>

68、;<p>　　typedef struct{</p><p><b>　　char NT;</b></p><p><b>　　char T;</b></p><p><b>　　int flag;</b></p><p><b>　　}array;&l

69、t;/b></p><p>　　typedef struct{</p><p><b>　　char E;</b></p><p><b>　　char e;</b></p><p>　　}charLode;</p><p>　　typedef struct{</

70、p><p>　　charLode *base;</p><p><b>　　int top;</b></p><p>　　}charstack;</p><p>　　array F[20]; char str[50][50];</p><p>　　char Firstvt[50][50]; </

71、p><p>　　char Lastvt[50][50]; int Fnum; </p><p>　　int Tnum; int NTnum; </p><p>　　int lec; int FF=1; char r[20];</p><p>　　int Fsignal[30][30];</p><p>　　int FLAG

72、=0; char Tsig1[1][30];</p><p>　　char Tsig2[30][1]; </p><p>　　void Initstack(charstack *s) {</p><p>　　s->base=(charLode *)malloc(30*sizeof(charLode));</p><p>　　s->

73、top=-1;</p><p><b>　　}</b></p><p>　　void Push(charstack *s,charLode w) {</p><p><b>　　s->top++;</b></p><p>　　s->base[s->top].E=w.E;</p

74、><p>　　s->base[s->top].e=w.e;</p><p><b>　　}</b></p><p>　　void Pop(charstack *s,charLode *w){</p><p>　　w->E=s->base[s->top].E;</p><p&g

75、t;　　w->e=s->base[s->top].e;</p><p>　　s->top--;}</p><p>　　int IsEmpty(charstack s) {</p><p>　　if(s.top==-1) return 1;</p><p>　　else return 0;</p><

76、;p><b>　　}</b></p><p>　　int ISTerminator(char ch) {</p><p>　　if(ch>='A'&&ch<='Z') return 1;</p><p>　　else return 0;</p><p>

77、;<b>　　}</b></p><p>　　int YN_Operator_Grammar(int n) {</p><p>　　int j=3,flag=1,i;</p><p>　　for(i=0;i<=n;i++)</p><p>　　while(str[i][j]!='\0'){</

78、p><p>　　char a=str[i][j];</p><p>　　char b=str[i][j+1]; if(ISTerminator(a)&&ISTerminator(b)){</p><p>　　flag=0;break;</p><p>　　}else j++;</p>&l

79、t;p>　　} return flag;</p><p><b>　　}</b></p><p>　　void IS_Operator_priority_grammar(int n){</p><p><b>　　int i;</b></p><p>　　for(i=0;i<=n;i+

80、+) if(str[i][3]=='~'||YN_Operator_Grammar(n)==0||FLAG==1){</p><p>　　printf("文法G不是算符優(yōu)先文法!\n");</p><p>　　FF=0;break;</p><p><b>　　}</b></p><

81、p><b>　　if(i>n)</b></p><p>　　printf("G是算符優(yōu)先文法!\n");}</p><p>　　int search1(char r[],int Tnum,char a)int i;</p><p>　　for(i=0;i<Tnum;i++)</p><

82、p>　　if(r[i]==a) break;</p><p>　　if(i==Tnum) return 0;</p><p>　　else return 1;</p><p><b>　　}</b></p><p>　　void createF(int n) {</p><p>　　i

83、nt k=0,i=1; char c; int j;</p><p>　　char t[10]; t[0]=str[0][0];</p><p>　　while(i<=n){</p><p>　　if(t[k]!=str[i][0]){</p><p>　　k++; t[k]=str[i][0]; i++;</p&g

84、t;<p><b>　　}</b></p><p>　　Else i++;</p><p><b>　　}</b></p><p><b>　　Tnum=0;</b></p><p>　　for(i=0;i<=n;i++){</p><

85、p><b>　　j=3;</b></p><p>　　while(str[i][j]!='\0'){</p><p>　　c=str[i][j];</p><p>　　if(ISTerminator(c)==0){if(!search1(r,Tnum,c))</p><p>　　r[Tnum]=c

86、;</p><p><b>　　Tnum++;}</b></p><p><b>　　j++;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　Fnum=

87、0;</b></p><p>　　for(i=0;i<k;i++)</p><p>　　for(j=0;j<Tnum-1;j++){</p><p>　　F[Fnum].NT=t[i]; F[Fnum].T=r[j]; F[Fnum].flag=0; Fnum++;</p><p><

88、b>　　}</b></p><p><b>　　}</b></p><p>　　void search(charLode w) {</p><p><b>　　int i;</b></p><p>　　for(i=0;i<Fnum;i++)if(F[i].NT==w.E&

89、amp;&F[i].T==w.e){</p><p>　　F[i].flag=1;break;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void FirstVT(int n) {</p><p>　　cha

90、rstack sta;charLode ww;</p><p>　　charLode w; int i=0,k; </p><p>　　char a,b; Initstack(&sta); </p><p>　　while(i<=n){</p><p>　　k=3;w.E=str[i][0];</p><

91、p>　　a=str[i][k];b=str[i][k+1];</p><p>　　if(!ISTerminator(a)){</p><p>　　w.e=a;Push(&sta,w);</p><p>　　search(w);</p><p><b>　　i++;</b></p><p&

92、gt;<b>　　}</b></p><p>　　else if(ISTerminator(a)&&b!='\0'</p><p>　　&&!ISTerminator(b)){</p><p>　　w.e=b; Push(&sta,w);</p><p>　　se

93、arch(w); i++;</p><p><b>　　}</b></p><p>　　Else i++;</p><p><b>　　}</b></p><p>　　while(!IsEmpty(sta)){</p><p>　　Pop(&sta,&

94、ww);</p><p>　　for(i=0;i<=n;i++){</p><p>　　w.E=str[i][0]; if(str[i][3]==ww.E&&str[i][4]=='\0'){</p><p>　　w.e=ww.e;Push(&sta,w);</p><p>

95、　　search(w);break;</p><p><b>　　}</b></p><p>　　else if(str[i][3]==ww.E&&w.E!=ww.E{</p><p>　　w.e=ww.e;Push(&sta,w);</p><p>　　search(w);break;</

96、p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　NTnum=0;k=1;i=1;</p><p>　　while(i<Fnum){</p><p

97、>　　if(F[i-1].flag==1){</p><p>　　Firstvt[NTnum][0]=F[i-1].NT; Firstvt[NTnum][k]=F[i-1].T;</p><p>　　} while(F[i].flag==0&&i<Fnum)</p><p><b>　　i++

98、;</b></p><p>　　if(F[i].flag==1){ </p><p>　　if(F[i].NT==Firstvt[NTnum][0])</p><p><b>　　k++;</b></p><p><b>　　else{</b></p><p>　

99、　Firstvt[NTnum][k+1]='\0';</p><p><b>　　NTnum++;</b></p><p><b>　　k=1;</b></p><p><b>　　}</b></p><p><b>　　i++;</b>&

100、lt;/p><p><b>　　}} }</b></p><p>　　void LastVT(int n){</p><p>　　charstack sta;</p><p>　　charLode w; charLode e;</p><p>　　char a,b; int k,i;<

101、;/p><p>　　for(i=0;i<Fnum;i++)</p><p>　　F[i].flag=0; i=0;</p><p>　　Initstack(&sta);</p><p>　　while(i<=n){</p><p>　　int k=strlen(str[i]);</p>

102、<p>　　w.E=str[i][0];</p><p>　　a=str[i][k-1]; b=str[i][k-2]; if(!ISTerminator(a)){</p><p>　　w.e=a;Push(&sta,w);//進(jìn)棧</p><p>　　search(w); i++;</p><

103、;p><b>　　}</b></p><p>　　else if(ISTerminator(a)&&!ISTerminator(b)){</p><p>　　w.e=b; Push(&sta,w);search(w);</p><p><b>　　i++;</b></p>&l

104、t;p><b>　　}</b></p><p><b>　　elsei++;</b></p><p><b>　　}</b></p><p>　　while(!IsEmpty(sta)){</p><p>　　Pop(&sta,&e);</p>

105、;<p>　　for(i=0;i<=n;i++){</p><p>　　w.E=str[i][0]; if(str[i][3]==e.E&&str[i][4]=='\0'){</p><p>　　w.e=e.e;Push(&sta,w);</p><p>　　search(w);<

106、;/p><p><b>　　} } }</b></p><p>　　k=1;i=1; lec=0;</p><p>　　while(i<Fnum){if(F[i-1].flag==1){ </p><p>　　Lastvt[lec][0]=F[i-1].NT; Lastvt

107、[lec][k]=F[i-1].T;</p><p>　　} while(F[i].flag==0&&i<Fnum) i++;</p><p>　　if(F[i].flag==1){</p><p>　　if(F[i].NT==Firstvt[lec][0])</p><p><b

108、>　　k++;</b></p><p>　　else{Lastvt[lec][k+1]='\0';</p><p>　　lec++;k=1;</p><p><b>　　} i++;</b></p><p><b>　　}</b></p>

109、<p><b>　　} </b></p><p><b>　　}</b></p><p>　　void create_Priority_List(int n){</p><p>　　int i,j; int I,mm,pp,J;</p><p>　　for(j=1;j<=T

110、num;j++)</p><p>　　Tsig1[0][j]=r[j-1]; for(i=1;i<=Tnum;i++)</p><p>　　Tsig2[i][0]=r[i-1]; for(i=1;i<=Tnum;i++)</p><p>　　for(j=1;j<=Tnum;j++) Fsignal[i][j]=0;

111、</p><p><b>　　I=0,J=3;</b></p><p>　　while(I<=n) {</p><p>　　if(str[I][J+1]=='\0'){</p><p>　　I++;J=3;}</p><p>　　else{while(str[I][J+

112、1]!='\0'){</p><p>　　char aa=str[I][J];char bb=str[I][J+1]; if(!ISTerminator(aa)&&</p><p>　　!ISTerminator(bb)){</p><p>　　for(i=1;i<=Tnum;i++)

113、 if(Tsig2[i][0]==aa) break; for(j=1;j<=Tnum;j++) if(Tsig1[0][j]==bb) break; </p><p>　　if(Fsignal[i][j]==0) Fsigna

114、l[i][j]=1; else{FLAG=1;I=n+1;</p><p><b>　　}</b></p><p><b>　　J++;</b></p><p>　　} if(!ISTerminator(aa)&&ISTermi

115、nator(bb)&&str[I][J+2]!='\0'&&!ISTerminator(str[I][J+2])){ for(i=1;i<=Tnum;i++) if(Tsig2[i][0]==aa) break; for(j=1;j&l

116、t;=Tnum;j++) if(Tsig1[0][j]==str[I][J+2]) break; if(Fsignal[i][j]==0) Fsignal[i][j]=1;</p><p>　　else{FLAG=1;I=n+

117、1;</p><p>　　}} if(!ISTerminator(aa)&&ISTerminator(bb)){ </p><p>　　for(i=1;i<=Tnum;i++) if(aa==Tsig2[i][0]) break; for(j=0;j&

118、lt;=NTnum;j++) if(bb==Firstvt[j][0]) break; for(mm=1;Firstvt[j][mm]!='\0';mm++){</p><p>　　for(pp=1;pp<=Tnum;pp++) if(Tsig1[0][

119、pp]==Firstvt[j][mm]) break; if(Fsignal[i][pp]==0) Fsignal[i][pp]=2;</p><p>　　else{FLAG=1;I=n+1;</p><p><b&

120、gt;　　}</b></p><p><b>　　} J++;</b></p><p>　　} if(ISTerminator(aa)&&!ISTerminator(bb)){</p><p>　　for(i=1;i<=Tnum;i++)

121、 if(Tsig1[0][i]==bb) break; for(j=0;j<=lec;j++) if(aa==Lastvt[j][0]) break; for(mm=1;Lastvt[j][mm]!='\0';mm++){ </p><p>　　for(pp

122、=1;pp<=Tnum;pp++) if(Tsig2[pp][0]==Lastvt[j][mm]) break; if(Fsignal[pp][i]==0) Fsignal[pp][i]=3;

123、 else{FLAG=1;I=n+1;</p><p><b>　　}</b></p><p><b>　　}J++;</b></p><p>　　}} } } }</p><p>　　int Priority_Type(char s,char a{</

124、p><p>　　int i=1,j=1;</p><p>　　while(Tsig2[i][0]!=s) i++;</p><p>　　while(Tsig1[0][j]!=a) j++; if(Fsignal[i][j]==3) return 3;</p><p>　　elseif(Fsignal[i][j]==2) retur

125、n 2;</p><p>　　elseif(Fsignal[i][j]==1) return 1;</p><p>　　else return 0;</p><p><b>　　}</b></p><p>　　void print(char s[],char STR[][20],int q,int u,int i

126、i,int k) {</p><p>　　int i;printf("%4d\t\t",u); for(i=0;i<=k;i++)printf("%c",s[i]);</p><p>　　printf("\t\t");</p><p>　　for(i=q;i<=ii;i++) printf(

127、"%c",STR[0][i]);printf("\t\t");</p><p><b>　　}</b></p><p>　　void process(char STR[][20],int ii) {</p><p>　　int k=0,q=0,u=0,b,i,j;</p><p>

128、　　char s[40],a;</p><p>　　printf(" 步驟\t\t字符棧\t\t輸入串\t\t動(dòng)作\n");</p><p>　　s[k]='#'; print(s,STR,q,u,ii,k);</p><p>　　printf("\n"); k++;u++;</p>

129、<p>　　s[k]=STR[0][q]; q++;</p><p>　　print(s,STR,q,u,ii,k);</p><p>　　printf("移進(jìn)\n");</p><p>　　while(q<=ii){ a=STR[0][q];</p><p>　　if(!ISTerminator(

130、s[k]))j=k;</p><p>　　elsej=k-1;</p><p>　　b=Priority_Type (s[j],a);</p><p>　　if(b==3){char Q=s[j];</p><p>　　loop: while(ISTerminator(s[j-1]))</p><p>　　j--;

131、 if(Priority_Type (s[j-1],Q)==2) {for(i=j;i<k;i++) s[i]='\0';k=j;s[k]='N';u++; rint(s,STR,q,u,ii,k);}else {Q=s[--j];goto loop;}printf("歸約\n");</p><p><b&g

132、t;　　}</b></p><p>　　else if(b==2||b==1){</p><p>　　k++; s[k]=a; u++;</p><p>　　q++; print(s,STR,q,u,ii,k); if(s[0]=='#'&&s[1]=='N'&

133、&s[2]=='#')</p><p>　　printf("移進(jìn)\n");</p><p>　　elseprintf("接受\n");</p><p><b>　　} else{</b></p><p>　　printf("error\n&qu