編譯原理課程設(shè)計報告畢業(yè)論文

1、 . . . 編譯原理課程設(shè)計報告一、 課程設(shè)計目的通過課程設(shè)計進一步理解高級語言在計算機中的執(zhí)行過程，了解現(xiàn)代編譯器的運作機制，加深對編譯原理中重點算法和編譯技術(shù)的理解，提高自己自學(xué)和理解的能力。學(xué)會如何利用已有軟件JFLex、Java_cup對詞法分析器與語法分析器的構(gòu)造。二、 設(shè)計概述本tiger語言編譯器的編譯過程涉與到編譯五個階段中的二個，即詞法分析器、語法分析器。其中語法分析后還完成了語法樹的打印的構(gòu)造以與類型檢查。詞法分析器由JFLex編譯正則式生成，詞法分析器編譯產(chǎn)生式生成，語法分析器由CUP生成。結(jié)果通過GUI界面呈現(xiàn)在使用者面前。編譯程序需要在單詞級別上來分析和翻譯源程序，

2、所以首先要識別出單詞，而詞法分析部分的任務(wù)是：從左至右掃描源程序的字符串，按照詞法規(guī)則（正則文法規(guī)則）識別出一個個正確的單詞，并轉(zhuǎn)換成該單詞相應(yīng)的二元式（種別碼、屬性值）交給語法分析使用。因此，詞法分析是編譯的基礎(chǔ)。執(zhí)行詞法分析的程序稱為詞法分析器。語法分析是編譯程序的核心部分,其主要任務(wù)是確定語法結(jié)構(gòu),檢查語法錯誤，報告錯誤的性質(zhì)和位置，并進行適當(dāng)?shù)募m錯工作。三、 設(shè)計過程(一) 設(shè)計構(gòu)思程序主要完成三大功能模塊：詞法分析器、語法分析器、GUI人機交互界面。詞法分析器由JFLex編譯正則式生成，其中必須為外界提供一個獲取記號流的接口，實驗中定為java_cup.runtime.Symbol

3、next_token。語法分析器是建立在詞法分析器上的，故必須包含詞法分析器以便獲得記號流，next_token為語法分析器提供TOKEN，語法分析器的對外接口是：java_cup.runtime.Symbol debug_parse()，同時返回語法樹的根節(jié)點。GUI界面是提供人機交互的，它能夠依次顯示詞法分析階段分析得到的所有TOKEN的信息，語法階段生成的語法樹，另外對于詞法和語法階段出現(xiàn)的錯誤在“錯誤提示”文本框中一一列舉出來，提供用戶改進代碼的信息。流程圖：GUI界面詞法錯誤程序輸入流記號流詞法分析器TOKEN語法樹語法分析器語法、類型錯誤類與文件說明：包AbsynPrint.jav

4、a/print out the syntax tree/The abstract syntax classes for Tiger包errormsgErrorMsg.java/used to produce error messages with detail information包java_cup.runtime/Support for CUP parser包parseGrm.java/Parser analyserMainInterface.java/GUI interfaceSym.java/tokens decimal representationYylex.java/Lexer a

5、nalyser包SemantEntry.java/for bindings in value environmentEnv.java/holds a value ,type environment and an error printerExpTy.java/holds the result of translating and type-checkingFunEntry.java/for function bindingsSemant.java/the main type-checking moduleVarEntry.java/for variable bindings包SymbolSym

6、bol.java/makes strings into unique Symbol objectsTable.java/does environments with Scopes包Translate包Types/describes Tiger_language types(二) 詞法分析器 這部分的工作主要是熟悉JFLex的使用以與正確書寫正則式，通過正則式的書寫，生成相應(yīng)的詞法分析器。1. JFLex的使用 修改jflex-1.4.2bin中的jflex.bat文件中的參數(shù)，JAVA_HOME=%JAVA_HOME%libclasses.zip; JFLEX_HOME=%JFLEX_HOME

7、%libJFlex.jar；運行jflex.bat 并給選擇輸入文件（tiger.jlex），在沒有錯誤的情況下，它在輸出目錄下生成一個Yylex.java的詞法分析器。tiger.jlex文件開始部分的書寫格式如下：package parse;/將詞法分析器打包在Parse下import errormsg.ErrorMsg;/導(dǎo)入類%cup/支持與cup的關(guān)聯(lián)%line/支持yyline()調(diào)用%column /支持yycolumn()調(diào)用%char%state COMMENT,STRING/聲明兩個新的狀態(tài)%/設(shè)置所有可能的詞法錯誤類型StringBuffer str = new Stri

8、ngBuffer();private static final String errorM = Error: Unmatched end-of-comment punctuation., Error: Unmatched start-of-comment punctuation., Error: Unclosed string., Error: Illegal character.;private void newline() /保持errormsg里的行數(shù)記錄變量的正確性 errorMsg.newline(yychar);private void err(String s) /通過error

9、msg報錯private java_cup.runtime.Symbol tok(int kind, Object value) return new java_cup.runtime.Symbol(kind, yychar, yychar+yylength(), value);/返回所識別的TOKENpublic Yylex(java.io.FileReader s, ErrorMsg e) this(s);/重載Yylex構(gòu)造函數(shù)，方便錯誤輸出 errorMsg = e;private ErrorMsg errorMsg;/ ErrorMsg對象聲明private int comment_

10、count = 0;/變量，用于處理注釋嵌套%eofval/到文件末尾時判斷最后的狀態(tài)是否是YYINITIAL,若不是則報相應(yīng)的錯誤if(zzLexicalState!=0)switch(zzLexicalState)case 2:err(errorME_STARTCOMMENT);break;case 4:err(errorME_UNCLOSEDSTR);break;default: /*do nothing*/ return tok(sym.EOF, null);%eofval/一些基本類型簡化表達式的定義ALPHA=A-Za-z/字母DIGIT=0-9/數(shù)字LINE_TERMINATOR

11、 = r|n|rn/換行符NONNEWLINE_WHITE_SPACE_CHAR= tfb012/非換行空白符WHITE_SPACE_CHAR =LINE_TERMINATOR | NONNEWLINE_WHITE_SPACE_CHAR/空白符%2. 正規(guī)表達式的書寫 Tiger需要識別的變量和字符有：整型常量、字符常量、操作符、括符、分隔符、關(guān)鍵字、標(biāo)識符、COMMENT。整型常量： 一個整形數(shù)字，即字母的任意組合。字符常量： 用雙引號引起來的字符，可跨行但行尾必須以結(jié)尾，行首開始。字符常量中間可包含轉(zhuǎn)義字符如：r n t f ” xyz x,y,z表示0127的整數(shù)。 操作符： + - *

12、 / = = = := & | 括符： ( ) 分隔符： ； ： 關(guān)鍵字： while do for to if else then let in end type var array of break nil function 標(biāo)識符：以字符開頭，加上字符、數(shù)字、下劃線的任意組合 評論： 以/*開頭，以*/結(jié)尾中間可嵌套任意個但必須是封閉的。 一般的字符或者保留字只需返回它的名字就可以了，例如：在YYINITAIL的狀態(tài)下識 別到最長匹配串為“array” ，則直接返回token，編號為sym.java中已經(jīng)定義的數(shù)字 編號，書寫的格式如下： array return tok(sym.ARR

13、AY,null); 下面著重談一下對于字符串和注釋的處理：字符串的處理：在YYINITIAL狀態(tài)下遇到一個 ” 時表示識別字符常量的開始，此時就要進入先前聲明的STRING 狀態(tài)，先前聲明的字符串str用來保存已識別的字符常量（初始化為空），代碼如下： str.setLength(0); yybegin(STRING);當(dāng)識別的過程中如果碰到轉(zhuǎn)義字符n t ，在str后添加相應(yīng)的字符，碰到非轉(zhuǎn)移字符就直接添加到str后面，忽略兩個反斜杠之間的所有空白字符，代碼如下： nr+ str.append(yytext(); n str.append(n); str.append(); WHITE_SP

14、ACE_CHAR+ /*do nothing*/特別是當(dāng)碰到跟上三位數(shù)字時，應(yīng)該判斷數(shù)值圍是否在ASCII圍中 0DIGITDIGIT|10-1DIGIT|120-7 str.append(char)Integer.valueOf(new String(yytext().getBytes(),1,3).intValue();當(dāng)再次識別到時標(biāo)志著字符串的識別結(jié)束，此時將str中的字符串容作為String的容返回，同時應(yīng)該返回YYINITIAL狀態(tài)，繼續(xù)識別其他的TOKEN yybegin(YYINITIAL);return tok(sym.STRING,str.toString(); 識別到這些

15、token以外的其他字符，則直接報錯 . err(errorME_ILLEGAL); 注釋的處理：在YYINITIAL狀態(tài)下遇到一個 /* 時表示識別注釋的開始，此時就要進入先前聲明的COMMENT狀態(tài)，同時comment_count加1，以實現(xiàn)注釋嵌套的實現(xiàn)。如果在COMMENT狀態(tài)下又一次識別到/*表示另一個注釋嵌套的開始，此時也需要對comment_count進行加1的操作，代碼如下： /* yybegin(COMMENT); comment_count = comment_count + 1; /* comment_count = comment_count + 1; 但是如果在YYI

16、NITIAL狀態(tài)下遇到一個 */則是一個錯誤，需要報出，代碼如下： */ err(errorME_ENDCOMMENT); 在COMMENT狀態(tài)下遇到*/則表示著一個嵌套中的注釋結(jié)束，此時需要對comment_count進行減1的操作，如果操作之后其值為0，表示整個注釋已經(jīng)結(jié)束，回到Y(jié)YINITIAL狀態(tài)，如若不然則繼續(xù)在COMMENT的狀態(tài)下識別，代碼如下： */ comment_count = comment_count - 1; if (comment_count = 0)yybegin(YYINITIAL)；識別到這些token以外的其他字符，則直接忽略 . /*do nothing*

17、/ 3. 詞法分析器的結(jié)構(gòu) 詞法分析器實現(xiàn)了Lexer接口，也就是實現(xiàn)了Token next_token()這個方法，不斷調(diào)用此方法就可以獲得所有的記號流。使用詞法分析器時需要指定輸入流InputStream以與ErrorMsg，InputStream完成源程序的讀取，ErrorMsg完成對錯誤信息的輸出。 至此詞法分析器的構(gòu)造已經(jīng)基本基本結(jié)束了。(三) 語法分析器完成語法分析器的主要步驟是cup文件的編寫，由于語法樹的數(shù)據(jù)結(jié)構(gòu)已給出，所以產(chǎn)生式的編寫可以直接參考tiger語言的語法模式，當(dāng)然這其中產(chǎn)生了許多沖突，但是可以通過設(shè)置符號的優(yōu)先級來解決移進和規(guī)約的沖突。1. CUP的使用CUP的使

18、用需要在命令行的環(huán)境下進行，打開命令提示符，輸入如下所示的語句，既可以在當(dāng)前目錄下生成語法分析器Grm.java，Grm.cup的書寫格式如下所示：Cup開始部分的書寫格式如下：package parse;/產(chǎn)生在parse包里面import Absyn.*;import javax.swing.*;action code :static Symbol.Symbol sym(String s) /將字符串轉(zhuǎn)化為Symbolreturn Symbol.Symbol.symbol(s);:;parser code : Yylex lexer;public static Exp parseResul

19、t;/記錄語法樹根節(jié)點的變量errormsg.ErrorMsg errorMsg;/輸出語法錯誤的ErrorMsg對象聲明public void syntax_error(java_cup.runtime.Symbol current) report_error(Syntax error ( + current.sym + ), (java_cup.runtime.Symbol)current);public void report_error(String message, java_cup.runtime.Symbol tok) errorMsg.error(tok.left, messa

20、ge);public Grm(errormsg.ErrorMsg err, JTextArea text) this();/語法分析器的構(gòu)造errorMsg=err;textin=text;:;init with : /語法分析器初始化，從界面文本框中獲取輸入流 lexer = new Yylex( new java.io.StringBufferInputStream(textin.getText(),errorMsg);:;scan with : java_cup.runtime.Symbol symb= lexer.debug_next_token(); for(;(symb.sym=s

21、ym.error)&symb.sym!=sym.EOF;)symb= lexer.debug_next_token();return symb; :;/同過debug_next_token獲取token并打印出token/終結(jié)符terminal String STRING;terminal Integer INT;terminal COMMA, COLON, SEMICOLON, LPAREN, RPAREN, LBRACK, RBRACK, LBRACE, RBRACE, DOT;terminal PLUS, MINUS, TIMES, DIVIDE, EQ, NEQ, LT, LE, GT

22、, GE, AND, OR, ASSIGN, UMINUS;terminal ARRAY, IF, THEN, ELSE, WHILE, FOR, TO, DO, LET, IN, END, OF, BREAK, NIL, FUNCTION, VAR, TYPE, ID;/終結(jié)符優(yōu)先級次序precedence right DO, ELSE, THEN;precedence nonassoc ASSIGN;precedence left OR;precedence left AND;precedence nonassoc EQ, NEQ, LT, LE, GT, GE;precedence le

23、ft PLUS, MINUS;precedence left TIMES, DIVIDE;precedence left UMINUS;precedence left LBRACK;關(guān)于優(yōu)先級次序的說明：由于在語法分析的過程中會產(chǎn)生許多移進和規(guī)約的沖突，通過設(shè)置終結(jié)符的優(yōu)先級可以避免一些情況的發(fā)生。將PLUS、MINUS的優(yōu)先級定義在TIMES、DIVIDE之前即可使乘除的優(yōu)先級高于加減運算的優(yōu)先級。另外通過設(shè)置比較運算符的有限次序，可以避免分析時的移進-歸約沖突。此外在實際的cup生成過程中，還會出現(xiàn)一些其他的沖突，例如以下兩個沖突的解決： .1出現(xiàn)沖突 between lvalue :=

24、ID (*) and lvalue := ID (*) LBRACK expr RBRACK and expr := ID (*) LBRACK expr RBRACK OF expr under symbol LBRACK 解決辦法：把left LBRACK 設(shè)為最高優(yōu)先級，這樣的話當(dāng)碰到是歸約ID還是移進 LBRACK的沖突時，系統(tǒng)會自動根據(jù)優(yōu)先級而去執(zhí)行移進的動作。.2出現(xiàn)沖突 between expr := IF expr THEN expr (*) and expr := IF expr THEN expr (*) ELSE expr under symbol ELSE 解決辦法：把

25、right DO,ELSE,THEN設(shè)為最低優(yōu)先級,通過precedence right ELSE,THEN語句;定義為右結(jié)合的then將與else結(jié)合，故先移進。.3 負(fù)號和減號識別時有沖突，解決方案是重新定義一個終結(jié)符UMINUS算數(shù)運算符中最 高優(yōu)先級，負(fù)號時重新賦予UMINUS的優(yōu)先級。 2. 語法的書寫按照Tiger Manual上的語法規(guī)則，將上面的語法一一寫入cup文件的后面，必要的時候定義適當(dāng)?shù)姆墙K結(jié)符來完成語法的結(jié)構(gòu)。每一條語法規(guī)則都應(yīng)該返回其相應(yīng)的語句類型，這些類型都已經(jīng)在Absyn包中定義好了，只要根據(jù)語句的類型按照定義返回即可。其中，要注意的是一些鏈表的連接，如ExpL

26、ist、FieldList等，需要保證這些對象的連接正確性。首先，在語法分析前完成非終結(jié)符的定義，定義如下：non terminal FieldListtype_fields, type_fields_n, type_fields_ex;non terminal FieldExpListfield_list, field_list_n, field_list_ex;non terminal ExpListexpr_list, expr_list_n, expr_list_ex, expr_seq, expr_seq_n, expr_seq_ex;non terminal DecListdecl

27、aration_list, declaration_list_ex;non terminal Tytype;non terminal Decdeclaration, type_declaration, variable_declaration, function_declaration;non terminal Exp expr, program;/文法開始符non terminal Var lvalue;其次在文法開始符的語法句的執(zhí)行語句中，將第一個Exp傳給先前定義的parseResul,代碼如下：start with program;program := expr:e : parser.

28、parseResult = e; :;對于一些常規(guī)的語法，只需返回相應(yīng)的語句類型即可，如賦值語句 expr := lvalue:l ASSIGN expr:e: RESULT = new AssignExp(lleft, l, e); :；對于需要連接起來的類型，如ExpList,FieldExpList,FieldList,DecList,可以通過消除左遞歸的方法來將多個具有向后指針的類型的語句相連，另外鏈表還可以為空，下面舉ExpList的例子來說明處理的方法：expr_list := expr_list_n:l(1): RESULT = l; : | : RESULT = null; :

29、；expr_list_n := expr:e expr_list_ex:x(2): RESULT = new ExpList(e, x); :;expr_list_ex:=COMMA expr_list_n:l (3): RESULT = l; : | : RESULT = null; :；在（1）開始識別的時候先判斷這個表達式是否為空，若空則直接返回null，否則進入（2），因為至少有一個Explist的存在，所以可以聲明一個新的ExpList，并將它的tail指向下一個可能的ExpList，當(dāng)然下一個ExpList可能為空，所以在處理expr_list_ex時需要判斷其是否為空，如空則直接

30、返回null，否則可以將嵌套進行下去。3. 語法樹的生成語法分析結(jié)束后，同時會返回整棵語法樹的根結(jié)點，我們可以利用這個根節(jié)點進行語法樹的打印，調(diào)用AbsynPrint.Java中的prExp(par.parseResult,2)，將整個語法樹在屏幕上打印出來，同時還可以在Print.Java中定義一個string變量將需要的打印容儲存起來，在屏幕上打印完之后在GUI界面的文本框顯示出來。4. 類型檢查類型檢查運作思想語法分析結(jié)束后，我們還可以對整棵語法樹進行類型檢查，我們可以從語法樹的根結(jié)點開始對每一個分支進行掃描，根據(jù)Tiger語言所所規(guī)定的語法類型規(guī)則進行判斷這一條語句運算或者返回的類型是

31、否符合要求，如果類型不匹配立即報出類型錯誤。類型檢查的關(guān)鍵是管理好符號表。整個檢查過程維護一變量表，一類型表，都是Table類型的。Table是按鍵值方式存儲，關(guān)鍵字是Symbol類型，值是Binder類型，Binder中變量value存儲具體的信息。變量表的value存儲Entry類型，Entry說明變量的類型以與其它信息。類型表的value存儲的是Type類型，保存類型的具體信息。Binder類是一個鏈表結(jié)構(gòu)，也就是說一個符號可以幾個類型，如本地變量覆蓋全局變量，本地類型覆蓋全局類型等。類型檢查所用到的類的關(guān)系可以從下圖中看清：Envvenv: Tabletenv: TableerrorM

32、sg: ErrorMsgSemantFunEntry Entry VarEntryTabledic: Dictionarytop: Symbolmarks: BinderTypesBinder value: Objectprevtop: Symboltail: Binder每個變量或類型都有一個有效圍，在function的聲明過程中，其聲明的變量只在它的函數(shù)體中有效，出了函數(shù)體就失去了它的作用圍，成為了一個無效的變量。又如在in end中又嵌套了let in end 語句，則外面語句中聲明的變量在里面的語句中仍然有效（重復(fù)聲明會覆蓋）?？梢岳胻able中的beginscope()和endsc

33、ope()來確定變量的作用圍。調(diào)用函數(shù) beginScope() 添加一個標(biāo)記，標(biāo)記起始位置。當(dāng)這個變量的作用域到底時用調(diào)用函數(shù) endScope() 把先前的聲明都刪掉。遇到的實際問題與思考.1類型檢查的過程中，還有一個遞歸調(diào)用的問題，如testcase6letfunction do_nothing1(a: int, b: string)=do_nothing2(a+1)function do_nothing2(d: int) =do_nothing1(d, str)indo_nothing1(0, str2)End其中do_nothing1函數(shù)的body需要調(diào)用do_nothing2,但是

34、按照函數(shù)按順序聲明的話，此時do_nothing2還沒有被聲明，因而不能夠被識別，會報錯。解決方法：在let語句檢查declist之前將所有的dec（包括type_declaration，function_declaration）置入相應(yīng)的表中，這樣的話當(dāng)檢查上述的函數(shù)do_nothing1時就不會出現(xiàn)do_nothing2還未被聲明的情況了。.2類型檢查的過程中，還有一個循環(huán)定義的問題，如testcase16let type a=ctype b=atype c=dtype d=ainend解決方法：在這四個類型定義中，都用到了其他一起聲明的類型，存在類似a-c-d-a的類型循環(huán)定義，到最后四

35、個四個變量的類型還是沒有被實在定義，這是不允許的。解決的方法是在檢查類型定義之前用bind(ExpTy)函數(shù)將新聲明的類型的binding設(shè)為聲明中將要被賦予的類型。這樣在進入類型聲明的檢查中，只需通過isloop()函數(shù)判斷是否是循環(huán)定義就可知道是否出錯。在這樣的設(shè)計之下，代碼let type a=ctype b=atype c=dtype d=intinend就不會出現(xiàn)如上的錯誤了，a-c-d-int就會跳出檢查，返回false.3在Declist中的聲明中要求函數(shù)和類型的聲明分別必須放在一起，如letfunction g(a:int):int = atype t = intfunctio

36、n g(a:int):int = ainend示例中說這是合法的，應(yīng)為聲明的時候是以類處理的，funcDec和后面的funcDec一起處理，typeDec和后面的typeDec一起處理，導(dǎo)致檢查不出這個重復(fù)定義函數(shù)。我認(rèn)為這里有點不太合理，我的想法是可以在let語句的檢查中將所有的聲明都放入環(huán)境變量中，這樣的話既可以檢查出是否重復(fù)定義，有可以使類型的前后調(diào)用不受阻礙。即在ExpTy transExp(LetExp e)中添加如下代碼：ArrayList list =new ArrayList();for(DecList tmp=e.decs;tmp!=null;tmp=tmp.tail)Dec

37、 head=tmp.head;if(head instanceof TypeDec)/置入新的類型TypeDec td=(TypeDec)head;if(list.contains(.toString()env.errorMsg.error(td.pos,type++ has been already defined);list.add(.toString();env.tenv.put(,new NAME();if(head instanceof FunctionDec)/置入新的函數(shù)變量FunctionDec fd=(Fu

38、nctionDec)head;Type re=transTy(fd.result);RECORD rc=transTypeFields(fd.params);if(list.contains(.toString()env.errorMsg.error(fd.pos,function ++ already defined);elselist.add(.toString();env.venv.put(, new FunEntry(rc,re);list.clear();這樣的處理過后，就會達到上述的效果，不過這只是我的個人意見，雖然與tiger語言的要求有矛盾，但我認(rèn)為這不失為一種好的改進。處于這種改動，t