簡(jiǎn)單優(yōu)先分析法編譯原理課程設(shè)計(jì)

1、<p><b>　　課 程 設(shè) 計(jì)</b></p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　題 目:簡(jiǎn)單優(yōu)先分析程序的設(shè)計(jì)</p><p><b>　　初始條件：</b></p><p>　　程序設(shè)計(jì)語(yǔ)言:主要使用C語(yǔ)言的開(kāi)發(fā)工具，或者采用L

2、EX、YACC等工具，也可利用其他熟悉的開(kāi)發(fā)工具。算法：可以根據(jù)《編譯原理》課程所講授的算法進(jìn)行設(shè)計(jì)。</p><p>　　要求完成的主要任務(wù):（包括課程設(shè)計(jì)工作量及其技術(shù)要求，說(shuō)明書撰寫等具體要求）</p><p>　　1.明確課程設(shè)計(jì)的目的和重要性，認(rèn)真領(lǐng)會(huì)課程設(shè)計(jì)的題目，讀懂課程設(shè)計(jì)指導(dǎo)書的要求，學(xué)會(huì)設(shè)計(jì)的基本方法與步驟，學(xué)會(huì)如何運(yùn)用前修知識(shí)與收集、歸納相關(guān)資料解決具體問(wèn)題的方法。嚴(yán)

3、格要求自己，要獨(dú)立思考，按時(shí)、獨(dú)立完成課程設(shè)計(jì)任務(wù)。</p><p>　　2. 主要功能包括：對(duì)教材P104中的上下文無(wú)關(guān)文法，實(shí)現(xiàn)它的簡(jiǎn)單優(yōu)先分析程序，給出符號(hào)串b(aa)b的分析過(guò)程。（參考教材P103～106）</p><p>　　3.進(jìn)行總體設(shè)計(jì)，詳細(xì)設(shè)計(jì)：包括算法的設(shè)計(jì)和數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。系統(tǒng)實(shí)施、調(diào)試，合理使用出錯(cuò)處理程序。</p><p>　　4. 設(shè)計(jì)報(bào)

4、告：要求層次清楚、整潔規(guī)范、不得相互抄襲。正文字?jǐn)?shù)不少于0.3萬(wàn)字。包含內(nèi)容：</p><p><b>　?、僬n程設(shè)計(jì)的題目。</b></p><p><b>　?、谀夸洝?lt;/b></p><p>　?、壅模喊ㄒ?、需求分析、總體設(shè)計(jì)及開(kāi)發(fā)工具的選擇，設(shè)計(jì)原則（給出語(yǔ)法分析方法及中間代碼形式的描述、文法和屬性文法的設(shè)計(jì)

5、），數(shù)據(jù)結(jié)構(gòu)與模塊說(shuō)明（功能與流程圖）、詳細(xì)的算法設(shè)計(jì)、軟件調(diào)試、軟件的測(cè)試方法和結(jié)果、有關(guān)技術(shù)的討論、收獲與體會(huì)等。</p><p><b>　　④結(jié)束語(yǔ)。</b></p><p><b>　?、輩⒖嘉墨I(xiàn)。</b></p><p>　?、薷戒洠很浖鍐危ɑ蛘吒奖P）。</p><p><b&g

6、t;　　時(shí)間安排：</b></p><p>　　消化資料、系統(tǒng)調(diào)查、形式描述1天</p><p>　　系統(tǒng)分析、總體設(shè)計(jì)、實(shí)施計(jì)劃3天</p><p>　　撰寫課程設(shè)計(jì)報(bào)告書1天</p><p><b>　　目錄</b></p><p>　　1引言- 3 -</p>

7、;<p>　　2需求分析- 3 -</p><p>　　3總體設(shè)計(jì)- 3 -</p><p>　　3.1簡(jiǎn)單優(yōu)先關(guān)系的定義- 4 -</p><p>　　3.2簡(jiǎn)單優(yōu)先分析法的基本思想- 4 -</p><p>　　3.3簡(jiǎn)單優(yōu)先關(guān)系矩陣流程圖- 5 -</p><p>　　3.4簡(jiǎn)

8、單優(yōu)先分析法流程圖- 6 -</p><p>　　3.5分析器構(gòu)造- 7 -</p><p>　　4開(kāi)發(fā)工具的選擇- 7 -</p><p>　　5詳細(xì)的算法設(shè)計(jì)- 7 -</p><p>　　5.1簡(jiǎn)單優(yōu)先關(guān)系矩陣輸出算法- 7 -</p><p>　　5.2字符串讀入- 8 -</p&g

9、t;<p>　　5.3字符串分析算法- 8 -</p><p>　　5.4優(yōu)先關(guān)系判斷算法- 9 -</p><p>　　5.5移近-規(guī)約算法- 9 -</p><p>　　5.6分析結(jié)果判斷- 11 -</p><p>　　6軟件調(diào)試- 11 -</p><p>　　7軟件的測(cè)試方

10、法和結(jié)果- 12 -</p><p>　　8有關(guān)技術(shù)的討論- 13 -</p><p>　　9收獲與體會(huì)- 14 -</p><p>　　10結(jié)束語(yǔ)- 14 -</p><p>　　11 參考文獻(xiàn)- 15 -</p><p>　　12 附錄- 15 -</p><p>　　簡(jiǎn)單

11、優(yōu)先分析程序的設(shè)計(jì)</p><p><b>　　引言</b></p><p>　　上下文無(wú)關(guān)文法是形式語(yǔ)言理論中一種重要的變換文法，用來(lái)描述上下文無(wú)關(guān)語(yǔ)言，在喬姆斯基分層中稱為2型文法。由于程序設(shè)計(jì)語(yǔ)言的語(yǔ)法基本上都是上下文無(wú)關(guān)文法，因此應(yīng)用十分廣泛。</p><p>　　簡(jiǎn)單優(yōu)先分析法是預(yù)先在文法的各種符號(hào) (終結(jié)符號(hào)和非終結(jié)符號(hào))之間建立所

12、謂優(yōu)先關(guān)系，而在分析一個(gè)句型 (指規(guī)范句型，下同)時(shí)，從左到右依次掃視其中的符號(hào)，且每掃視一個(gè)符號(hào)都檢查它和后繼符號(hào)間的優(yōu)先關(guān)系，以期找到句柄之尾，然后再?gòu)拇宋卜?hào)處回頭，進(jìn)行反向掃描，且每掃視一個(gè)符號(hào)都檢查它和其前的符號(hào)間的優(yōu)先關(guān)系，直到找到句柄之頭為止。</p><p>　　本文將采用簡(jiǎn)單優(yōu)先分析法對(duì)一個(gè)上下文無(wú)關(guān)文法進(jìn)行分析，給出文法的簡(jiǎn)單關(guān)系優(yōu)先矩陣，并對(duì)測(cè)試用例進(jìn)行分析。</p><

13、p><b>　　需求分析</b></p><p>　　本課程設(shè)計(jì)的目的是為了實(shí)現(xiàn)給定上下文無(wú)關(guān)文法的簡(jiǎn)單優(yōu)先分析程序，并給出字符串的分析過(guò)程。</p><p>　　上下文無(wú)關(guān)文法G[S]：</p><p><b>　　S::=bAb</b></p><p><b>　　A::=(B|

14、a</b></p><p><b>　　B::=Aa)</b></p><p>　　測(cè)試字符串：b(aa)b</p><p><b>　　總體設(shè)計(jì)</b></p><p>　　本文采用簡(jiǎn)單優(yōu)先分析法實(shí)現(xiàn)指定上下文無(wú)關(guān)文法的分析程序，對(duì)于任意字符串給出其分析過(guò)程。</p>&

15、lt;p><b>　　簡(jiǎn)單優(yōu)先關(guān)系的定義</b></p><p>　　設(shè)G=(VN，VT,P,S)是一已化簡(jiǎn)的文法，V=VN∪VT，并設(shè)Si和Sj是V中的任意兩個(gè)符號(hào)，若G中存在這樣的規(guī)范句型 </p><p><b>　　α=…SiSj… </b></p><p>　　則此相鄰的兩個(gè)符號(hào)Si，Sj和α的句柄之間的關(guān)

16、系必然是下述情況之一： </p><p>　　(1) 若Si在句柄中，而Sj不在句柄中 (如圖42(a)所示)，則Si顯然為句柄的尾符號(hào)，故G中必有形如A→…Si的產(chǎn)生式，使Si先于Sj被歸約。此時(shí)，我們就說(shuō)符號(hào)Si優(yōu)于Sj，且記為Si>· Sj。此外，由于Sj出現(xiàn)在規(guī)范句型的句柄之右，故可知Sj必為終結(jié)符號(hào)。 </p><p>　　(2) 若Si與Sj同時(shí)處于α的句柄之中

17、 (如圖42(b)所示)，則G中必有形如A→…SiSj…的產(chǎn)生式，使Si和Sj同時(shí)被歸約。此時(shí)，我們就說(shuō)Si和Sj有相同的優(yōu)先關(guān)系，且記為Si=·Sj。 </p><p>　　(3) 若Sj在句柄中，而Si不在句柄之中 (如圖42(c)所示)，則Sj顯然為句柄的頭符號(hào)，故G中必有形如A→Sj…的產(chǎn)生式，使Sj先于Si被歸約。此時(shí)就Si和Sj的優(yōu)先關(guān)系而言，我們說(shuō)Si低于Sj且記為Si<·

18、Sj。 </p><p>　　(4) 若Si和Sj均不在句型α的句柄之中，由于Si和Sj已相鄰地在α中出現(xiàn)，則必有G的另一規(guī)范句型β，使Si和Sj在β中相鄰地出現(xiàn)，且與β的句柄的關(guān)系有上述三種情況之一。然而，也可能有這樣的情況，對(duì)G中的某些符號(hào)序偶(Sr,St)而言，G中并不存在任何使Sr和St相鄰出現(xiàn)的句型，此時(shí)我們就說(shuō)Sr和St間不存在任何優(yōu)先關(guān)系。</p><p>　　簡(jiǎn)單優(yōu)先分析法

19、的基本思想</p><p>　　根據(jù)優(yōu)先關(guān)系的定義，將簡(jiǎn)單優(yōu)先文法中各文法符號(hào)之間的這種關(guān)系用一個(gè)矩陣表示，稱作簡(jiǎn)單優(yōu)先矩陣。PDA讀入一個(gè)單詞后，比較棧頂符號(hào)和該單詞的優(yōu)先級(jí)，若棧頂符號(hào)優(yōu)先級(jí)低于該單詞，繼續(xù)讀入；若棧頂符號(hào)優(yōu)先級(jí)高于或等于讀入符號(hào)，則找句柄進(jìn)行歸約，找不到句柄就繼續(xù)讀入。直到最后棧內(nèi)只剩下開(kāi)始符號(hào)，輸入串讀到“?！睘橹?。此時(shí)識(shí)別正確。可分點(diǎn)描述如下:</p><p>　

20、　（1）、對(duì)句型中相鄰的文法符號(hào)規(guī)定優(yōu)先關(guān)系，以尋找句型中的句柄;</p><p>　　（2）、規(guī)定句柄內(nèi)各相鄰符號(hào)之間具有相同的優(yōu)先級(jí);</p><p>　?。?）、規(guī)定句柄兩端符號(hào)優(yōu)先級(jí)要比位于句柄之外而又和句柄相鄰的符號(hào)的優(yōu)先級(jí)高，以先歸約句柄;</p><p>　　（4）、對(duì)于文法中所有符號(hào)，只要它們可能在某個(gè)句型中相鄰，就要為它們規(guī)定相應(yīng)的優(yōu)先關(guān)系，若某兩

21、個(gè)符號(hào)永遠(yuǎn)不可能相鄰，則它們之間就無(wú)關(guān)系。</p><p>　　簡(jiǎn)單優(yōu)先關(guān)系矩陣流程圖</p><p>　　簡(jiǎn)單優(yōu)先分析法流程圖</p><p><b>　　分析器構(gòu)造</b></p><p>　　分析棧 輸入流</p><p><b

22、>　　開(kāi)發(fā)工具的選擇</b></p><p>　　開(kāi)發(fā)環(huán)境：Windows8環(huán)境下的eclipse</p><p><b>　　JDK1.7</b></p><p><b>　　開(kāi)發(fā)語(yǔ)言：Java</b></p><p><b>　　詳細(xì)的算法設(shè)計(jì)</b>&l

23、t;/p><p>　　簡(jiǎn)單優(yōu)先關(guān)系矩陣輸出算法</p><p>　　for(int i=1;i<9;i++){</p><p>　　a[0][i]=token[i-1];</p><p><b>　　}</b></p><p>　　for(int j=1;j<9;j++){</p&g

24、t;<p>　　a[j][0]=token[j-1];</p><p><b>　　}</b></p><p>　　for(int i=1;i<9;i++){</p><p>　　for(int j=1;j<9;j++){</p><p>　　a[i][j]=relation[i-1][j-1]

25、;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(int i=0;i<9;i++){</p><p>　　for(int j=0;j<9;j++){</p><p>　　System.out.print

26、(a[i][j]+" ");</p><p><b>　　}</b></p><p>　　System.out.print("\n");</p><p><b>　　}</b></p><p><b>　　字符串讀入</b></p

27、><p>　　Scanner scanner = new Scanner(System.in); </p><p>　　String testStr = scanner.nextLine();</p><p>　　char[] c= testStr.toCharArray();</p><p><b>　　字符串分析算法</b&g

28、t;</p><p>　　while(!s.isEmpty()){</p><p>　　char pre = s.pop();</p><p>　　if(compare(pre,c[i])){//移進(jìn)</p><p>　　s.push(pre);</p><p>　　s.push(c[i]);</p>&

29、lt;p>　　System.out.println("移進(jìn)"+c[i]);</p><p>　　}else{//規(guī)約</p><p>　　s.push(pre);</p><p>　　System.out.println("規(guī)約");</p><p><b>　　i--;</b&g

30、t;</p><p>　　statute();</p><p><b>　　}</b></p><p><b>　　i++;</b></p><p><b>　　}</b></p><p><b>　　優(yōu)先關(guān)系判斷算法</b><

31、;/p><p>　　private static boolean compare(char pre, char d) throws Exception {</p><p>　　// TODO Auto-generated method stub</p><p>　　int i = map.get(pre);</p><p>　　int j = m

32、ap.get(d);</p><p>　　char rel = relation[i][j];</p><p>　　if(rel == ' '){</p><p>　　System.out.println("錯(cuò)誤關(guān)系");</p><p>　　throw new Exception();</p>

33、<p><b>　　}</b></p><p>　　if(rel=='>'){</p><p>　　return false;</p><p><b>　　}</b></p><p>　　if(rel=='='||rel=='<

34、9;){</p><p>　　return true;</p><p><b>　　}</b></p><p>　　return false;</p><p><b>　　}</b></p><p><b>　　移近-規(guī)約算法</b></p>

35、<p>　　switch (c){</p><p>　　case 'S'://結(jié)束</p><p>　　if(s.pop()=='#'){</p><p><b>　　return;</b></p><p><b>　　}</b></p>

36、<p>　　throw new Exception();</p><p>　　case 'b'://S</p><p>　　if(s.pop()=='A'){</p><p>　　if(s.pop()=='b'){</p><p>　　s.push('S');</

37、p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　throw new Exception();</p><p>　　case 'B'://A&l

38、t;/p><p>　　if(s.pop()=='('){</p><p>　　s.push('A');</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　throw new Except

39、ion();</p><p>　　case 'a'://A</p><p>　　s.push('A');</p><p><b>　　return;</b></p><p>　　case ')'://B</p><p>　　if(s.pop()==&

40、#39;a'){</p><p>　　if(s.pop()=='A'){</p><p>　　s.push('B');</p><p><b>　　return;</b></p><p><b>　　}</b></p><p><

41、b>　　}</b></p><p>　　throw new Exception();</p><p><b>　　default:</b></p><p>　　throw new Exception();</p><p><b>　　}</b></p><p&g

42、t;<b>　　分析結(jié)果判斷</b></p><p>　　if(s.isEmpty()){</p><p>　　System.out.println("分析成功");</p><p><b>　　}else{</b></p><p>　　System.out.println(&q

43、uot;分析失敗");</p><p><b>　　}</b></p><p>　　catch(Exception e){</p><p>　　System.out.println("分析失敗");</p><p><b>　　}</b></p><

44、p><b>　　軟件調(diào)試</b></p><p>　　使用eclipse自帶的功能對(duì)源代碼進(jìn)行了調(diào)試，直至沒(méi)有語(yǔ)法錯(cuò)誤和語(yǔ)義錯(cuò)誤。</p><p>　　軟件的測(cè)試方法和結(jié)果</p><p><b>　　1.程序界面:</b></p><p>　　2.給定測(cè)試字符串:b(aa)b#</p&

45、gt;<p>　　3.測(cè)試任意字符串:</p><p><b>　　有關(guān)技術(shù)的討論</b></p><p>　　簡(jiǎn)單優(yōu)先分析法簡(jiǎn)單易行，已有一套構(gòu)造簡(jiǎn)單優(yōu)先矩陣的形式化算法，從設(shè)計(jì)分析程序到具體地進(jìn)行語(yǔ)法分析都可機(jī)械地進(jìn)行。似乎是一種可靠和有效的方法，其實(shí)并非如此。這主要表現(xiàn)在對(duì)文法有較強(qiáng)的要求,例如本課程設(shè)計(jì)分析的文法為上下文無(wú)關(guān)文法。因?yàn)閷?duì)通常的文法

46、而言，它的某些符號(hào)對(duì)之間的優(yōu)先關(guān)系往往會(huì)多于一種，也就是說(shuō)，所給的文法常常并非簡(jiǎn)單優(yōu)先文法。特別是當(dāng)文法具有左遞歸時(shí)，就往往會(huì)導(dǎo)致這種情況的發(fā)生。所以,在實(shí)際使用過(guò)程中,簡(jiǎn)單優(yōu)先分析法存在很大局限性。</p><p><b>　　收獲與體會(huì)</b></p><p>　　在本課程設(shè)計(jì)的過(guò)程中，我學(xué)習(xí)到了好多書本上學(xué)不到的東西，真正體會(huì)到了編譯原理的強(qiáng)大。也同時(shí)為自己能夠

47、編寫出這樣一個(gè)強(qiáng)大的程序而感到欣慰。</p><p>　　通過(guò)本次課程設(shè)計(jì)很好的復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)中所學(xué)的相關(guān)知識(shí)，尤其是對(duì)棧的運(yùn)用有了更深的理解。同時(shí)也對(duì)本學(xué)期所學(xué)Java語(yǔ)言程序設(shè)計(jì)有了更深層次的理解，并將其在實(shí)踐中得以運(yùn)用。本次設(shè)計(jì)最深的感觸是簡(jiǎn)單優(yōu)先文法是一個(gè)非常準(zhǔn)確，規(guī)范但分析效率很低的一種文法。此次課程設(shè)計(jì)，也讓我對(duì)簡(jiǎn)單優(yōu)先分析法有了比較全面的了解，并且通過(guò)上機(jī)操作等更好的理解了相關(guān)理論知識(shí)，增強(qiáng)了自己的

48、動(dòng)手能力。</p><p>　　在課程設(shè)計(jì)過(guò)程中，我也發(fā)現(xiàn)了自己存在的問(wèn)題。例如，對(duì)數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)的掌握不夠牢固，對(duì)棧的使用存在錯(cuò)誤；Java語(yǔ)言的運(yùn)用不夠嫻熟，對(duì)方法的調(diào)用存在誤區(qū)等。這些問(wèn)題都在后來(lái)的調(diào)試過(guò)程中通過(guò)查閱相關(guān)材料得以解決。</p><p>　　總之，這次課程設(shè)計(jì)讓我受益匪淺。不僅加深了我對(duì)編譯原理、數(shù)據(jù)結(jié)構(gòu)和Java語(yǔ)言程序設(shè)計(jì)等課程的了解，而且也通過(guò)查閱資料和實(shí)踐彌補(bǔ)

49、了自己的不足之處。在今后的學(xué)習(xí)中，我會(huì)加強(qiáng)自己的動(dòng)手能力，讓理論和實(shí)踐相結(jié)合，并且加強(qiáng)在專業(yè)課方面的學(xué)習(xí)。</p><p><b>　　結(jié)束語(yǔ)</b></p><p>　　編譯原理一般認(rèn)為是較難的一門課.不過(guò)我認(rèn)為這門課其實(shí)并不是特別難，只要課前提前做好預(yù)習(xí)工作，課后認(rèn)真做習(xí)題，學(xué)好這門課并非難事。</p><p>　　經(jīng)過(guò)這次課程設(shè)計(jì),也讓我

50、深刻的認(rèn)識(shí)到實(shí)踐操作的重要性。書本只能教給我們基礎(chǔ)知識(shí),只有通過(guò)實(shí)踐才能將那些知識(shí)真正吸收,轉(zhuǎn)化為自己的智慧。編譯原理是一門實(shí)用性很強(qiáng),對(duì)我們的專業(yè)很有幫助的科目,雖然已經(jīng)結(jié)課,但是在以后的生活和學(xué)習(xí)中我將會(huì)繼續(xù)努力,不斷增加自己的知識(shí)面,深入的理解和運(yùn)用編譯原理，使自己成為一名合格的IT人才。 </p><p><b>　　11參考文獻(xiàn)</b></p><p>　　

51、[1]《編譯原理》 主編：胡倫俊 徐蘭芳 駱婷 出版社：電子工業(yè)出版社</p><p>　　[2]《Java語(yǔ)言程序設(shè)計(jì)》主編：呂鳳翥 馬皓 出版社：清華大學(xué)出版社</p><p>　　[3]《編譯原理》（第二版） 主編：張素琴 呂映芝 出版社：清華大學(xué)出版社</p><p>　　[4]《數(shù)據(jù)結(jié)構(gòu)》（C語(yǔ)言版） 主編：嚴(yán)蔚敏 吳偉民 出版社：清華大學(xué)出版

52、社</p><p><b>　　12附錄</b></p><p><b>　　程序源代碼：</b></p><p>　　import java.util.HashMap;</p><p>　　import java.util.Stack;</p><p>　　import j

53、ava.util.Vector;</p><p>　　import java.util.Scanner;</p><p>　　import java.io.*;</p><p>　　public class test {</p><p>　　public static char[] token={'S','b'

54、,'A','(','B','a',')','#'};</p><p>　　public static Stack<Character> s=new Stack<Character>();</p><p>　　public static HashMap<Charact

55、er,Integer> map= new HashMap<Character,Integer>();</p><p>　　public static char[][] relation = new char[token.length][token.length];</p><p><b>　　static {</b></p><p

56、>　　for(int i=0;i<token.length;i++){</p><p>　　map.put(token[i], i);</p><p><b>　　}</b></p><p>　　for(int i=0;i<token.length;i++){</p><p>　　for(int j=0

57、;j<token.length;j++){</p><p>　　relation[i][j]=' ';</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　relation[0][7]='>';</p&

58、gt;<p>　　relation[1][2]='=';</p><p>　　relation[1][3]='<';</p><p>　　relation[1][5]='<';</p><p>　　relation[1][7]='>';</p><p&

59、gt;　　relation[2][1]='=';</p><p>　　relation[2][5]='=';</p><p>　　relation[3][2]='<';</p><p>　　relation[3][3]='<';</p><p>　　relation[

60、3][4]='=';</p><p>　　relation[3][5]='<';</p><p>　　relation[4][1]='>';</p><p>　　relation[4][5]='>';</p><p>　　relation[5][1]='

61、>';</p><p>　　relation[5][5]='>';</p><p>　　relation[5][6]='=';</p><p>　　relation[6][1]='>';</p><p>　　relation[6][5]='>';&

62、lt;/p><p>　　relation[7][0]='<';</p><p>　　relation[7][1]='<';</p><p>　　relation[7][7]='=';</p><p><b>　　}</b></p><p>　

63、　public test(){</p><p><b>　　}</b></p><p><b>　　/**</b></p><p>　　* @param args</p><p><b>　　*/</b></p><p>　　public static

64、 void main(String[] args) {</p><p>　　char a[][]=new char[9][9];</p><p>　　System.out.println("文法G[S]:");</p><p>　　System.out.println("S::=bAb");</p><p&

65、gt;　　System.out.println("A::=(B|a");</p><p>　　System.out.println("B::=Aa)");</p><p>　　System.out.println("簡(jiǎn)單優(yōu)先關(guān)系矩陣:");</p><p>　　for(int i=1;i<9;i++)

66、{</p><p>　　a[0][i]=token[i-1];</p><p><b>　　}</b></p><p>　　for(int j=1;j<9;j++){</p><p>　　a[j][0]=token[j-1];</p><p><b>　　}</b>&l

67、t;/p><p>　　for(int i=1;i<9;i++){</p><p>　　for(int j=1;j<9;j++){</p><p>　　a[i][j]=relation[i-1][j-1];</p><p><b>　　}</b></p><p><b>　　}&l

68、t;/b></p><p>　　for(int i=0;i<9;i++){</p><p>　　for(int j=0;j<9;j++){</p><p>　　System.out.print(a[i][j]+" ");</p><p><b>　　}</b></p>

69、<p>　　System.out.print("\n");</p><p><b>　　}</b></p><p>　　System.out.println("請(qǐng)輸入測(cè)試用例（以“#”結(jié)束）：");</p><p>　　//shiyan4 s4= new shiyan4();</p>

70、;<p>　　Scanner scanner = new Scanner(System.in); </p><p>　　String testStr = scanner.nextLine();</p><p>　　char[] c= testStr.toCharArray();</p><p>　　s.push('#');</p&

71、gt;<p><b>　　try{</b></p><p><b>　　int i=0;</b></p><p>　　while(!s.isEmpty()){</p><p>　　char pre = s.pop();</p><p>　　if(compare(pre,c[i])){/

72、/移進(jìn)</p><p>　　s.push(pre);</p><p>　　s.push(c[i]);</p><p>　　System.out.println("移進(jìn)"+c[i]);</p><p>　　}else{//規(guī)約</p><p>　　s.push(pre);</p><

73、;p>　　System.out.println("規(guī)約");</p><p><b>　　i--;</b></p><p>　　statute();</p><p><b>　　}</b></p><p><b>　　i++;</b></p>

74、;<p><b>　　}</b></p><p>　　if(s.isEmpty()){</p><p>　　System.out.println("分析成功");</p><p><b>　　}else{</b></p><p>　　System.out.print

75、ln("分析失敗");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　catch(Exception e){</p><p>　　System.out.println("分析失敗");</p>

76、<p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　/**</b></p><p><b>　　* 對(duì)棧中符號(hào)規(guī)約</b></p><p>　　* @return false 規(guī)約失敗</p

77、><p>　　* @throws Exception </p><p><b>　　*/</b></p><p>　　private static void statute() throws Exception {</p><p>　　char c = s.pop();</p><p>　　switc

78、h (c){</p><p>　　case 'S'://結(jié)束</p><p>　　if(s.pop()=='#'){</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　throw n

79、ew Exception();</p><p>　　case 'b'://S</p><p>　　if(s.pop()=='A'){</p><p>　　if(s.pop()=='b'){</p><p>　　s.push('S');</p><p>&l

80、t;b>　　return;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　throw new Exception();</p><p>　　case 'B'://A</p><p>

81、;　　if(s.pop()=='('){</p><p>　　s.push('A');</p><p><b>　　return;</b></p><p><b>　　}</b></p><p>　　throw new Exception();</p>

82、<p>　　case 'a'://A</p><p>　　s.push('A');</p><p><b>　　return;</b></p><p>　　case ')'://B</p><p>　　if(s.pop()=='a'){</p

83、><p>　　if(s.pop()=='A'){</p><p>　　s.push('B');</p><p><b>　　return;</b></p><p><b>　　}</b></p><p><b>　　}</b>

84、</p><p>　　throw new Exception();</p><p><b>　　default:</b></p><p>　　throw new Exception();</p><p><b>　　}</b></p><p><b>　　}<

85、/b></p><p><b>　　/**</b></p><p>　　* 根據(jù)優(yōu)先關(guān)系矩陣決定規(guī)約還是移進(jìn) <=移進(jìn)；>規(guī)約</p><p>　　* @param pre</p><p>　　* @param d</p><p>　　* @return 移進(jìn)返回true<

86、/p><p>　　* @throws Exception </p><p><b>　　*/</b></p><p>　　private static boolean compare(char pre, char d) throws Exception {</p><p>　　// TODO Auto-generated m

87、ethod stub</p><p>　　int i = map.get(pre);</p><p>　　int j = map.get(d);</p><p>　　char rel = relation[i][j];</p><p>　　if(rel == ' '){</p><p>　　System

88、.out.println("錯(cuò)誤關(guān)系");</p><p>　　throw new Exception();</p><p><b>　　}</b></p><p>　　if(rel=='>'){</p><p>　　return false;</p><p&

89、gt;<b>　　}</b></p><p>　　if(rel=='='||rel=='<'){</p><p>　　return true;</p><p><b>　　}</b></p><p>　　return false;</p><