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

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

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

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

4、構(gòu)造- 7 -4開(kāi)發(fā)工具的選擇- 7 -5詳細(xì)的算法設(shè)計(jì)- 7 -5.1簡(jiǎn)單優(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軟件的測(cè)試方法和結(jié)果- 12 -8有關(guān)技術(shù)的討論- 13 -9收獲與體會(huì)- 14 -10結(jié)束語(yǔ)- 14 -11 參考文獻(xiàn)- 15 -12 附錄- 15 -簡(jiǎn)單優(yōu)先分析程序的設(shè)計(jì)1 引言上下文無(wú)關(guān)文法是形式語(yǔ)言理論中一種重要的變換文法，用來(lái)描述上下文無(wú)關(guān)語(yǔ)言，在喬姆斯基分層中稱為2型文法。由于程序設(shè)計(jì)語(yǔ)言的語(yǔ)法基本上都是上

5、下文無(wú)關(guān)文法，因此應(yīng)用十分廣泛。簡(jiǎn)單優(yōu)先分析法是預(yù)先在文法的各種符號(hào) (終結(jié)符號(hào)和非終結(jié)符號(hào))之間建立所謂優(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)系，直到找到句柄之頭為止。本文將采用簡(jiǎn)單優(yōu)先分析法對(duì)一個(gè)上下文無(wú)關(guān)文法進(jìn)行分析，給出文法的簡(jiǎn)單關(guān)系優(yōu)先矩陣，并對(duì)測(cè)試用例進(jìn)行分析。2 需求分析本課程設(shè)計(jì)的目的是為了實(shí)現(xiàn)給定上下文無(wú)關(guān)文法的簡(jiǎn)單優(yōu)先分析程序，并給出字符串的分析過(guò)程。上下文無(wú)關(guān)文法GS：S:=bAbA

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

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

8、鄰地出現(xiàn)，且與的句柄的關(guān)系有上述三種情況之一。然而，也可能有這樣的情況，對(duì)G中的某些符號(hào)序偶(Sr,St)而言，G中并不存在任何使Sr和St相鄰出現(xiàn)的句型，此時(shí)我們就說(shuō)Sr和St間不存在任何優(yōu)先關(guān)系。3.2 簡(jiǎn)單優(yōu)先分析法的基本思想根據(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í)別正確?？煞贮c(diǎn)描述如下:（1）、對(duì)句型中相鄰的文法符號(hào)

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

10、SK+1Sia是句柄，用它來(lái)查產(chǎn)生式表a與一產(chǎn)生式右部相同？Si=#且TRj=#？errori<-k Si<-U U是該產(chǎn)生式左部符號(hào)K<-k-1errori<-i+1Si<-TRij<j+1YNYNYYNYNN3.5 分析器構(gòu)造分析棧 輸入流 ST語(yǔ)法分析程序優(yōu)先關(guān)系矩陣產(chǎn)生式表4 開(kāi)發(fā)工具的選擇開(kāi)發(fā)環(huán)境：Windows8環(huán)境下的eclipse JDK1.7開(kāi)發(fā)語(yǔ)言：Java5 詳細(xì)的算法設(shè)計(jì)5.1 簡(jiǎn)單優(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("錯(cuò)誤關(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自帶的功能對(duì)源代碼進(jìn)行了調(diào)試，直至沒(méi)有語(yǔ)法錯(cuò)誤和語(yǔ)義錯(cuò)誤。7 軟件的測(cè)試方法和結(jié)果1.程序界面:2.給定測(cè)試字符串:b(aa)b#3.測(cè)試任意字符串:8 有關(guān)技術(shù)的討論簡(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ì)通常的文法而言，它的某些符號(hào)對(duì)之間的優(yōu)先關(guān)系往往會(huì)多于一種，也就是說(shuō)，所給的文法常常并非簡(jiǎn)單優(yōu)先文法。特別是當(dāng)文法具有左遞歸時(shí)，就往往會(huì)導(dǎo)致這種情況的發(fā)生。所以,在

17、實(shí)際使用過(guò)程中,簡(jiǎn)單優(yōu)先分析法存在很大局限性。9 收獲與體會(huì)在本課程設(shè)計(jì)的過(guò)程中，我學(xué)習(xí)到了好多書(shū)本上學(xué)不到的東西，真正體會(huì)到了編譯原理的強(qiáng)大。也同時(shí)為自己能夠編寫出這樣一個(gè)強(qiáng)大的程序而感到欣慰。通過(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)了自己的動(dòng)手能力。在課程設(shè)計(jì)過(guò)程中，我也發(fā)現(xiàn)了自己存在

18、的問(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)材料得以解決?？傊?，這次課程設(shè)計(jì)讓我受益匪淺。不僅加深了我對(duì)編譯原理、數(shù)據(jù)結(jié)構(gòu)和Java語(yǔ)言程序設(shè)計(jì)等課程的了解，而且也通過(guò)查閱資料和實(shí)踐彌補(bǔ)了自己的不足之處。在今后的學(xué)習(xí)中，我會(huì)加強(qiáng)自己的動(dòng)手能力，讓理論和實(shí)踐相結(jié)合，并且加強(qiáng)在專業(yè)課方面的學(xué)習(xí)。10 結(jié)束語(yǔ)編譯原理一般認(rèn)為是較難的一門課.不過(guò)我認(rèn)為這門課其實(shí)并不是特別難，只要課前提前做好預(yù)習(xí)工作，課后認(rèn)真做習(xí)題，學(xué)好這門課并非難事。經(jīng)過(guò)這次課程設(shè)計(jì),也讓我深刻的認(rèn)識(shí)到實(shí)踐操作的重要性

19、。書(shū)本只能教給我們基礎(chǔ)知識(shí),只有通過(guò)實(shí)踐才能將那些知識(shí)真正吸收,轉(zhuǎn)化為自己的智慧。編譯原理是一門實(shí)用性很強(qiáng),對(duì)我們的專業(yè)很有幫助的科目,雖然已經(jīng)結(jié)課,但是在以后的生活和學(xué)習(xí)中我將會(huì)繼續(xù)努力,不斷增加自己的知識(shí)面,深入的理解和運(yùn)用編譯原理，使自己成為一名合格的IT人才。 11參考文獻(xiàn)1編譯原理 主編：胡倫俊 徐蘭芳 駱婷 出版社：電子工業(yè)出版社2Java語(yǔ)言程序設(shè)計(jì)主編：呂鳳翥 馬皓 出版社：清華大學(xué)出版社3編譯原理（第二版） 主編：張素琴 呂映芝 出版社：清華大學(xué)出版社4數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 主編：嚴(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("簡(jiǎn)單優(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("請(qǐng)輸入測(cè)試用例（以“#”結(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("分析失敗");/* * 對(duì)棧中符號(hào)規(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 &#