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

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

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

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

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

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

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

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

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

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

10、SK+1Sia是句柄，用它來查產生式表a與一產生式右部相同？Si=#且TRj=#？errori<-k Si<-U U是該產生式左部符號K<-k-1errori<-i+1Si<-TRij<j+1YNYNYYNYNN3.5 分析器構造分析棧 輸入流 ST語法分析程序優(yōu)先關系矩陣產生式表4 開發(fā)工具的選擇開發(fā)環(huán)境：Windows8環(huán)境下的eclipse JDK1.7開發(fā)語言：Java5 詳細的算法設計5.1 簡單優(yōu)先關系矩陣輸出算法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)/移進s.push(pre);s.push(ci);System.out.println("移進"+ci);else/規(guī)約s.push(pre);System.out.println("規(guī)約");i-;statute();i+;5.4 優(yōu)先關系判斷算法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("錯誤關系");throw new Exception();if(rel='>')return false;if(rel='='|rel='<')return true;return false;5.5 移近-規(guī)約算法switch (c)case 'S':/結束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 分析結果判斷if(s.isEmpty()System.out.println("分析成功");elseSystem.out.println("分析失敗");catch(Exception e)System.out.println("分析失敗"

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

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

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

19、。書本只能教給我們基礎知識,只有通過實踐才能將那些知識真正吸收,轉化為自己的智慧。編譯原理是一門實用性很強,對我們的專業(yè)很有幫助的科目,雖然已經結課,但是在以后的生活和學習中我將會繼續(xù)努力,不斷增加自己的知識面,深入的理解和運用編譯原理，使自己成為一名合格的IT人才。 11參考文獻1編譯原理 主編：胡倫俊 徐蘭芳 駱婷 出版社：電子工業(yè)出版社2Java語言程序設計主編：呂鳳翥 馬皓 出版社：清華大學出版社3編譯原理（第二版） 主編：張素琴 呂映芝 出版社：清華大學出版社4數據結構（C語言版） 主編：嚴蔚敏 吳偉民 出版社：清華大學出版社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)先關系矩陣:");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("請輸入測試用例（以“#”結束）：");/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)/移進s.push(pre);s.push(ci);System.out.println("移進"+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':/結束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 &#