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

1、學(xué) 號： 課 程 設(shè) 計題 目簡單優(yōu)先分析程序的設(shè)計學(xué) 院計算機科學(xué)與技術(shù)學(xué)院專 業(yè)軟件工程專業(yè)班 級軟件工程1002班姓 名指導(dǎo)教師何九周2013年1月12日課程設(shè)計任務(wù)書學(xué)生姓名： 專業(yè)班級： 軟件工程1002班 指導(dǎo)教師： 何九周 工作單位： 計算機科學(xué)與技術(shù)學(xué)院 題 目:簡單優(yōu)先分析程序的設(shè)計初始條件：程序設(shè)計語言:主要使用C語言的開發(fā)工具，或者采用LEX、YACC等工具，也可利用其他熟悉的開發(fā)工具。算法：可以根據(jù)編譯原理課程所講授的算法進(jìn)行設(shè)計。要求完成的主要任務(wù):（包括課程設(shè)計工作量及其技術(shù)要求，說明書撰寫等具體要求）1.明確課程設(shè)計的目的和重要性，認(rèn)真領(lǐng)會課程設(shè)計的題目，讀懂課程

2、設(shè)計指導(dǎo)書的要求，學(xué)會設(shè)計的基本方法與步驟，學(xué)會如何運用前修知識與收集、歸納相關(guān)資料解決具體問題的方法。嚴(yán)格要求自己，要獨立思考，按時、獨立完成課程設(shè)計任務(wù)。2. 主要功能包括：對教材P104中的上下文無關(guān)文法，實現(xiàn)它的簡單優(yōu)先分析程序，給出符號串b(aa)b的分析過程。（參考教材P103106）3.進(jìn)行總體設(shè)計，詳細(xì)設(shè)計：包括算法的設(shè)計和數(shù)據(jù)結(jié)構(gòu)設(shè)計。系統(tǒng)實施、調(diào)試，合理使用出錯處理程序。4. 設(shè)計報告：要求層次清楚、整潔規(guī)范、不得相互抄襲。正文字?jǐn)?shù)不少于0.3萬字。包含內(nèi)容：課程設(shè)計的題目。目錄。正文：包括引言、需求分析、總體設(shè)計及開發(fā)工具的選擇，設(shè)計原則（給出語法分析方法及中間代碼形式的

3、描述、文法和屬性文法的設(shè)計），數(shù)據(jù)結(jié)構(gòu)與模塊說明（功能與流程圖）、詳細(xì)的算法設(shè)計、軟件調(diào)試、軟件的測試方法和結(jié)果、有關(guān)技術(shù)的討論、收獲與體會等。結(jié)束語。參考文獻(xiàn)。附錄：軟件清單（或者附盤）。時間安排：消化資料、系統(tǒng)調(diào)查、形式描述1天系統(tǒng)分析、總體設(shè)計、實施計劃3天撰寫課程設(shè)計報告書1天指導(dǎo)教師簽名： 2013年 1月 12日系主任（或責(zé)任教師）簽名： 2013年 1月 12日 目錄1引言- 3 -2需求分析- 3 -3總體設(shè)計- 3 -3.1簡單優(yōu)先關(guān)系的定義- 4 -3.2簡單優(yōu)先分析法的基本思想- 4 -3.3簡單優(yōu)先關(guān)系矩陣流程圖- 5 -3.4簡單優(yōu)先分析法流程圖- 6 -3.5分析器

4、構(gòu)造- 7 -4開發(fā)工具的選擇- 7 -5詳細(xì)的算法設(shè)計- 7 -5.1簡單優(yōu)先關(guān)系矩陣輸出算法- 7 -5.2字符串讀入- 8 -5.3字符串分析算法- 8 -5.4優(yōu)先關(guān)系判斷算法- 9 -5.5移近-規(guī)約算法- 9 -5.6分析結(jié)果判斷- 11 -6軟件調(diào)試- 11 -7軟件的測試方法和結(jié)果- 12 -8有關(guān)技術(shù)的討論- 13 -9收獲與體會- 14 -10結(jié)束語- 14 -11 參考文獻(xiàn)- 15 -12 附錄- 15 -簡單優(yōu)先分析程序的設(shè)計1 引言上下文無關(guān)文法是形式語言理論中一種重要的變換文法，用來描述上下文無關(guān)語言，在喬姆斯基分層中稱為2型文法。由于程序設(shè)計語言的語法基本上都是上

5、下文無關(guān)文法，因此應(yīng)用十分廣泛。簡單優(yōu)先分析法是預(yù)先在文法的各種符號 (終結(jié)符號和非終結(jié)符號)之間建立所謂優(yōu)先關(guān)系，而在分析一個句型 (指規(guī)范句型，下同)時，從左到右依次掃視其中的符號，且每掃視一個符號都檢查它和后繼符號間的優(yōu)先關(guān)系，以期找到句柄之尾，然后再從此尾符號處回頭，進(jìn)行反向掃描，且每掃視一個符號都檢查它和其前的符號間的優(yōu)先關(guān)系，直到找到句柄之頭為止。本文將采用簡單優(yōu)先分析法對一個上下文無關(guān)文法進(jìn)行分析，給出文法的簡單關(guān)系優(yōu)先矩陣，并對測試用例進(jìn)行分析。2 需求分析本課程設(shè)計的目的是為了實現(xiàn)給定上下文無關(guān)文法的簡單優(yōu)先分析程序，并給出字符串的分析過程。上下文無關(guān)文法GS：S:=bAbA

6、:=(B|aB:=Aa)測試字符串：b(aa)b3 總體設(shè)計本文采用簡單優(yōu)先分析法實現(xiàn)指定上下文無關(guān)文法的分析程序，對于任意字符串給出其分析過程。3.1 簡單優(yōu)先關(guān)系的定義設(shè)G=(VN，VT,P,S)是一已化簡的文法，V=VNVT，并設(shè)Si和Sj是V中的任意兩個符號，若G中存在這樣的規(guī)范句型 =SiSj 則此相鄰的兩個符號Si，Sj和的句柄之間的關(guān)系必然是下述情況之一： (1) 若Si在句柄中，而Sj不在句柄中 (如圖42(a)所示)，則Si顯然為句柄的尾符號，故G中必有形如ASi的產(chǎn)生式，使Si先于Sj被歸約。此時，我們就說符號Si優(yōu)于Sj，且記為Si>· Sj。此外，由于S

7、j出現(xiàn)在規(guī)范句型的句柄之右，故可知Sj必為終結(jié)符號。 (2) 若Si與Sj同時處于的句柄之中 (如圖42(b)所示)，則G中必有形如ASiSj的產(chǎn)生式，使Si和Sj同時被歸約。此時，我們就說Si和Sj有相同的優(yōu)先關(guān)系，且記為Si=·Sj。 (3) 若Sj在句柄中，而Si不在句柄之中 (如圖42(c)所示)，則Sj顯然為句柄的頭符號，故G中必有形如ASj的產(chǎn)生式，使Sj先于Si被歸約。此時就Si和Sj的優(yōu)先關(guān)系而言，我們說Si低于Sj且記為Si<·Sj。 (4) 若Si和Sj均不在句型的句柄之中，由于Si和Sj已相鄰地在中出現(xiàn)，則必有G的另一規(guī)范句型，使Si和Sj在中相

8、鄰地出現(xiàn)，且與的句柄的關(guān)系有上述三種情況之一。然而，也可能有這樣的情況，對G中的某些符號序偶(Sr,St)而言，G中并不存在任何使Sr和St相鄰出現(xiàn)的句型，此時我們就說Sr和St間不存在任何優(yōu)先關(guān)系。3.2 簡單優(yōu)先分析法的基本思想根據(jù)優(yōu)先關(guān)系的定義，將簡單優(yōu)先文法中各文法符號之間的這種關(guān)系用一個矩陣表示，稱作簡單優(yōu)先矩陣。PDA讀入一個單詞后，比較棧頂符號和該單詞的優(yōu)先級，若棧頂符號優(yōu)先級低于該單詞，繼續(xù)讀入；若棧頂符號優(yōu)先級高于或等于讀入符號，則找句柄進(jìn)行歸約，找不到句柄就繼續(xù)讀入。直到最后棧內(nèi)只剩下開始符號，輸入串讀到“”為止。此時識別正確?？煞贮c描述如下:（1）、對句型中相鄰的文法符號

9、規(guī)定優(yōu)先關(guān)系，以尋找句型中的句柄; （2）、規(guī)定句柄內(nèi)各相鄰符號之間具有相同的優(yōu)先級;（3）、規(guī)定句柄兩端符號優(yōu)先級要比位于句柄之外而又和句柄相鄰的符號的優(yōu)先級高，以先歸約句柄; （4）、對于文法中所有符號，只要它們可能在某個句型中相鄰，就要為它們規(guī)定相應(yīng)的優(yōu)先關(guān)系，若某兩個符號永遠(yuǎn)不可能相鄰，則它們之間就無關(guān)系。3.3 簡單優(yōu)先關(guān)系矩陣流程圖輸入欲分析文法判定是否是簡單優(yōu)先文法分析等于關(guān)系分析小于關(guān)系分析大于關(guān)系構(gòu)造矩陣關(guān)系表NY3.4 簡單優(yōu)先分析法流程圖S1<-#,i,j<-1MSi,TRj=error?開始結(jié)束Si>TRj?K<-iSk-1<sk?a=Sk

10、SK+1Sia是句柄，用它來查產(chǎn)生式表a與一產(chǎn)生式右部相同？Si=#且TRj=#？errori<-k Si<-U U是該產(chǎn)生式左部符號K<-k-1errori<-i+1Si<-TRij<j+1YNYNYYNYNN3.5 分析器構(gòu)造分析棧 輸入流 ST語法分析程序優(yōu)先關(guān)系矩陣產(chǎn)生式表4 開發(fā)工具的選擇開發(fā)環(huán)境：Windows8環(huán)境下的eclipse JDK1.7開發(fā)語言：Java5 詳細(xì)的算法設(shè)計5.1 簡單優(yōu)先關(guān)系矩陣輸出算法for(int i=1;i<9;i+)a0i=tokeni-1; for(int j=1;j<9;j+) aj0=toke

11、nj-1; for(int i=1;i<9;i+) for(int j=1;j<9;j+) aij=relationi-1j-1; for(int i=0;i<9;i+) for(int j=0;j<9;j+) System.out.print(aij+" "); System.out.print("n"); 5.2 字符串讀入Scanner scanner = new Scanner(System.in); String testStr = scanner.nextLine(); char c= testStr.toCharAr

12、ray();5.3 字符串分析算法while(!s.isEmpty()char pre = s.pop();if(compare(pre,ci)/移進(jìn)s.push(pre);s.push(ci);System.out.println("移進(jìn)"+ci);else/規(guī)約s.push(pre);System.out.println("規(guī)約");i-;statute();i+;5.4 優(yōu)先關(guān)系判斷算法private static boolean compare(char pre, char d) throws Exception / TODO Auto-gene

13、rated method stubint i = map.get(pre);int j = map.get(d);char rel = relationij;if(rel = ' ')System.out.println("錯誤關(guān)系");throw new Exception();if(rel='>')return false;if(rel='='|rel='<')return true;return false;5.5 移近-規(guī)約算法switch (c)case 'S':/結(jié)束if

14、(s.pop()='#')return;throw new Exception();case 'b':/Sif(s.pop()='A')if(s.pop()='b')s.push('S');return;throw new Exception();case 'B':/Aif(s.pop()='(')s.push('A');return;throw new Exception();case 'a':/As.push('A');return

15、;case ')':/Bif(s.pop()='a')if(s.pop()='A')s.push('B');return;throw new Exception();default:throw new Exception();5.6 分析結(jié)果判斷if(s.isEmpty()System.out.println("分析成功");elseSystem.out.println("分析失敗");catch(Exception e)System.out.println("分析失敗"

16、);6 軟件調(diào)試使用eclipse自帶的功能對源代碼進(jìn)行了調(diào)試，直至沒有語法錯誤和語義錯誤。7 軟件的測試方法和結(jié)果1.程序界面:2.給定測試字符串:b(aa)b#3.測試任意字符串:8 有關(guān)技術(shù)的討論簡單優(yōu)先分析法簡單易行，已有一套構(gòu)造簡單優(yōu)先矩陣的形式化算法，從設(shè)計分析程序到具體地進(jìn)行語法分析都可機械地進(jìn)行。似乎是一種可靠和有效的方法，其實并非如此。這主要表現(xiàn)在對文法有較強的要求,例如本課程設(shè)計分析的文法為上下文無關(guān)文法。因為對通常的文法而言，它的某些符號對之間的優(yōu)先關(guān)系往往會多于一種，也就是說，所給的文法常常并非簡單優(yōu)先文法。特別是當(dāng)文法具有左遞歸時，就往往會導(dǎo)致這種情況的發(fā)生。所以,在

17、實際使用過程中,簡單優(yōu)先分析法存在很大局限性。9 收獲與體會在本課程設(shè)計的過程中，我學(xué)習(xí)到了好多書本上學(xué)不到的東西，真正體會到了編譯原理的強大。也同時為自己能夠編寫出這樣一個強大的程序而感到欣慰。通過本次課程設(shè)計很好的復(fù)習(xí)了數(shù)據(jù)結(jié)構(gòu)中所學(xué)的相關(guān)知識，尤其是對棧的運用有了更深的理解。同時也對本學(xué)期所學(xué)Java語言程序設(shè)計有了更深層次的理解，并將其在實踐中得以運用。本次設(shè)計最深的感觸是簡單優(yōu)先文法是一個非常準(zhǔn)確，規(guī)范但分析效率很低的一種文法。此次課程設(shè)計，也讓我對簡單優(yōu)先分析法有了比較全面的了解，并且通過上機操作等更好的理解了相關(guān)理論知識，增強了自己的動手能力。在課程設(shè)計過程中，我也發(fā)現(xiàn)了自己存在

18、的問題。例如，對數(shù)據(jù)結(jié)構(gòu)相關(guān)知識的掌握不夠牢固，對棧的使用存在錯誤；Java語言的運用不夠嫻熟，對方法的調(diào)用存在誤區(qū)等。這些問題都在后來的調(diào)試過程中通過查閱相關(guān)材料得以解決。總之，這次課程設(shè)計讓我受益匪淺。不僅加深了我對編譯原理、數(shù)據(jù)結(jié)構(gòu)和Java語言程序設(shè)計等課程的了解，而且也通過查閱資料和實踐彌補了自己的不足之處。在今后的學(xué)習(xí)中，我會加強自己的動手能力，讓理論和實踐相結(jié)合，并且加強在專業(yè)課方面的學(xué)習(xí)。10 結(jié)束語編譯原理一般認(rèn)為是較難的一門課.不過我認(rèn)為這門課其實并不是特別難，只要課前提前做好預(yù)習(xí)工作，課后認(rèn)真做習(xí)題，學(xué)好這門課并非難事。經(jīng)過這次課程設(shè)計,也讓我深刻的認(rèn)識到實踐操作的重要性

19、。書本只能教給我們基礎(chǔ)知識,只有通過實踐才能將那些知識真正吸收,轉(zhuǎn)化為自己的智慧。編譯原理是一門實用性很強,對我們的專業(yè)很有幫助的科目,雖然已經(jīng)結(jié)課,但是在以后的生活和學(xué)習(xí)中我將會繼續(xù)努力,不斷增加自己的知識面,深入的理解和運用編譯原理，使自己成為一名合格的IT人才。 11參考文獻(xiàn)1編譯原理 主編：胡倫俊 徐蘭芳 駱婷 出版社：電子工業(yè)出版社2Java語言程序設(shè)計主編：呂鳳翥 馬皓 出版社：清華大學(xué)出版社3編譯原理（第二版） 主編：張素琴 呂映芝 出版社：清華大學(xué)出版社4數(shù)據(jù)結(jié)構(gòu)（C語言版） 主編：嚴(yán)蔚敏 吳偉民 出版社：清華大學(xué)出版社12附錄程序源代碼：import java.util.Ha

20、shMap;import java.util.Stack;import ;import java.util.Scanner;import java.io.*;public class test public static char token='S','b','A','(','B','a',')','#'public static Stack<Character> s=new Stack<Character>();public static H

21、ashMap<Character,Integer> map= new HashMap<Character,Integer>();public static char relation = new chartoken.lengthtoken.length;static for(int i=0;i<token.length;i+)map.put(tokeni, i);for(int i=0;i<token.length;i+)for(int j=0;j<token.length;j+)relationij=' 'relation07=

22、9;>'relation12='='relation13='<'relation15='<'relation17='>'relation21='='relation25='='relation32='<'relation33='<'relation34='='relation35='<'relation41='>'relation45='>'r

23、elation51='>'relation55='>'relation56='='relation61='>'relation65='>'relation70='<'relation71='<'relation77='='public test()/* * param args */public static void main(String args) char a=new char99;System.out.println(&q

24、uot;文法GS:");System.out.println("S:=bAb");System.out.println("A:=(B|a");System.out.println("B:=Aa)");System.out.println("簡單優(yōu)先關(guān)系矩陣:");for(int i=1;i<9;i+)a0i=tokeni-1; for(int j=1;j<9;j+) aj0=tokenj-1; for(int i=1;i<9;i+) for(int j=1;j<9;j+) aij=

25、relationi-1j-1; for(int i=0;i<9;i+) for(int j=0;j<9;j+) System.out.print(aij+" "); System.out.print("n"); System.out.println("請輸入測試用例（以“#”結(jié)束）：");/shiyan4 s4= new shiyan4();Scanner scanner = new Scanner(System.in); String testStr = scanner.nextLine(); char c= testS

26、tr.toCharArray(); s.push('#');tryint i=0;while(!s.isEmpty()char pre = s.pop();if(compare(pre,ci)/移進(jìn)s.push(pre);s.push(ci);System.out.println("移進(jìn)"+ci);else/規(guī)約s.push(pre);System.out.println("規(guī)約");i-;statute();i+;if(s.isEmpty()System.out.println("分析成功");elseSystem.

27、out.println("分析失敗");catch(Exception e)System.out.println("分析失敗");/* * 對棧中符號規(guī)約 * return false 規(guī)約失敗 * throws Exception */private static void statute() throws Exception char c = s.pop();switch (c)case 'S':/結(jié)束if(s.pop()='#')return;throw new Exception();case 'b':/Sif(s.pop()='A')if(s.pop()='b')s.push('S');return;throw new Exception();case &#