編譯原理課程設(shè)計(jì)報(bào)告

1、<p>　　《編譯原理》課程設(shè)計(jì)報(bào)告</p><p><b>　　課程設(shè)計(jì)目的</b></p><p>　　通過(guò)課程設(shè)計(jì)進(jìn)一步理解高級(jí)語(yǔ)言在計(jì)算機(jī)中的執(zhí)行過(guò)程，了解現(xiàn)代編譯器的運(yùn)作機(jī)制，加深對(duì)編譯原理中重點(diǎn)算法和編譯技術(shù)的理解，提高自己自學(xué)和理解的能力。學(xué)會(huì)如何利用已有軟件JFLex、Java_cup對(duì)詞法分析器及語(yǔ)法分析器的構(gòu)造。</p>&

2、lt;p><b>　　設(shè)計(jì)概述</b></p><p>　　本tiger語(yǔ)言編譯器的編譯過(guò)程涉及到編譯五個(gè)階段中的二個(gè)，即詞法分析器、語(yǔ)法分析器。其中語(yǔ)法分析后還完成了語(yǔ)法樹(shù)的打印的構(gòu)造以及類(lèi)型檢查。詞法分析器由JFLex編譯正則式生成，詞法分析器編譯產(chǎn)生式生成，語(yǔ)法分析器由CUP生成。結(jié)果通過(guò)GUI界面呈現(xiàn)在使用者面前。</p><p>　　編譯程序需要在單詞

3、級(jí)別上來(lái)分析和翻譯源程序，所以首先要識(shí)別出單詞，而詞法分析部分的任務(wù)是：從左至右掃描源程序的字符串，按照詞法規(guī)則（正則文法規(guī)則）識(shí)別出一個(gè)個(gè)正確的單詞，并轉(zhuǎn)換成該單詞相應(yīng)的二元式（種別碼、屬性值）交給語(yǔ)法分析使用。因此，詞法分析是編譯的基礎(chǔ)。執(zhí)行詞法分析的程序稱(chēng)為詞法分析器。</p><p>　　語(yǔ)法分析是編譯程序的核心部分,其主要任務(wù)是確定語(yǔ)法結(jié)構(gòu),檢查語(yǔ)法錯(cuò)誤，報(bào)告錯(cuò)誤的性質(zhì)和位置，并進(jìn)行適當(dāng)?shù)募m錯(cuò)工作。&l

4、t;/p><p><b>　　設(shè)計(jì)過(guò)程</b></p><p><b>　　設(shè)計(jì)構(gòu)思</b></p><p>　　程序主要完成三大功能模塊：詞法分析器、語(yǔ)法分析器、GUI人機(jī)交互界面。詞法分析器由JFLex編譯正則式生成，其中必須為外界提供一個(gè)獲取記號(hào)流的接口，實(shí)驗(yàn)中定為java_cup.runtime.Symbol next

5、_token。語(yǔ)法分析器是建立在詞法分析器上的，故必須包含詞法分析器以便獲得記號(hào)流，next_token為語(yǔ)法分析器提供TOKEN，語(yǔ)法分析器的對(duì)外接口是：java_cup.runtime.Symbol debug_parse()，同時(shí)返回語(yǔ)法樹(shù)的根節(jié)點(diǎn)。</p><p>　　GUI界面是提供人機(jī)交互的，它能夠依次顯示詞法分析階段分析得到的所有TOKEN的信息，語(yǔ)法階段生成的語(yǔ)法樹(shù)，另外對(duì)于詞法和語(yǔ)法階段出現(xiàn)的錯(cuò)

6、誤在“錯(cuò)誤提示”文本框中一一列舉出來(lái)，提供用戶(hù)改進(jìn)代碼的信息。</p><p><b>　　流程圖：</b></p><p><b>　　類(lèi)及文件說(shuō)明：</b></p><p>　　包Absyn</p><p>　　Print.java//print out the syntax tr

7、ee</p><p>　　……//The abstract syntax classes for Tiger</p><p>　　包errormsg</p><p>　　ErrorMsg.java//used to produce error messages with detail information</p><p>

8、;　　包java_cup.runtime//Support for CUP parser</p><p>　　包parse</p><p>　　Grm.java//Parser analyser</p><p>　　MainInterface.java//GUI interface</p><p>　　Sym.java

9、//tokens' decimal representation</p><p>　　Yylex.java//Lexer analyser</p><p><b>　　包Semant</b></p><p>　　Entry.java//for bindings in value environment</p>

10、<p>　　Env.java//holds a value ,type environment and an error printer</p><p>　　ExpTy.java//holds the result of translating and type-checking</p><p>　　FunEntry.java//for function b

11、indings</p><p>　　Semant.java//the main type-checking module</p><p>　　VarEntry.java//for variable bindings</p><p><b>　　包Symbol</b></p><p>　　Symbol.java

12、//makes strings into unique Symbol objects</p><p>　　Table.java//does environments with Scopes</p><p>　　包Translate</p><p>　　包Types//describes Tiger_language types</p>

13、<p><b>　　詞法分析器</b></p><p>　　這部分的工作主要是熟悉JFLex的使用以及正確書(shū)寫(xiě)正則式，通過(guò)正則式的書(shū)寫(xiě)，生成相應(yīng)的詞法分析器。</p><p><b>　　JFLex的使用</b></p><p>　　修改jflex-1.4.2\bin中的jflex.bat文件中的參數(shù)，

14、JAVA_HOME=%JAVA_HOME%\lib\classes.zip;</p><p>　　JFLEX_HOME=%JFLEX_HOME%\lib\JFlex.jar；</p><p>　　運(yùn)行jflex.bat 并給選擇輸入文件（tiger.jlex），在沒(méi)有錯(cuò)誤的情況下，它在輸出目錄下生成一個(gè)Yylex.java的詞法分析器。</p><p>　

15、　tiger.jlex文件開(kāi)始部分的書(shū)寫(xiě)格式如下：</p><p>　　package parse;//將詞法分析器打包在Parse下</p><p>　　import errormsg.ErrorMsg;//導(dǎo)入類(lèi)</p><p><b>　　%%</b></p><p>　　%cup//支持與cup

16、的關(guān)聯(lián)</p><p>　　%line//支持yyline()調(diào)用</p><p>　　%column //支持yycolumn()調(diào)用</p><p><b>　　%char</b></p><p>　　%state COMMENT,STRING//聲明兩個(gè)新的狀態(tài)</p><p&g

17、t;　　%{//設(shè)置所有可能的詞法錯(cuò)誤類(lèi)型</p><p>　　StringBuffer str = new StringBuffer();</p><p>　　private static final String errorM[] = {</p><p>　　"Error: Unmatched end-of-comment punctu

18、ation.",</p><p>　　"Error: Unmatched start-of-comment punctuation.",</p><p>　　"Error: Unclosed string.",</p><p>　　"Error: Illegal character."</p

19、><p><b>　　};</b></p><p>　　private void newline() {//保持errormsg里的行數(shù)記錄變量的正確性</p><p>　　errorMsg.newline(yychar);</p><p><b>　　}</b></p>

20、<p>　　private void err(String s) { …… } //通過(guò)errormsg報(bào)錯(cuò)</p><p>　　private java_cup.runtime.Symbol tok(int kind, Object value) {</p><p>　　return new java_cup.runtime.Symbol(kind, yychar, yych

21、ar+yylength(), value);//返回所識(shí)別的TOKEN</p><p><b>　　}</b></p><p>　　public Yylex(java.io.FileReader s, ErrorMsg e) {</p><p>　　this(s);//重載Yylex構(gòu)造函數(shù)，方便錯(cuò)誤輸出</p>

22、<p>　　errorMsg = e;</p><p><b>　　}</b></p><p>　　private ErrorMsg errorMsg;// ErrorMsg對(duì)象聲明</p><p>　　private int comment_count = 0;//變量，用于處理注釋嵌套</p><p>

23、;<b>　　%}</b></p><p>　　%eofval{</p><p>　　{//到文件末尾時(shí)判斷最后的狀態(tài)是否是YYINITIAL,若不是則報(bào)相應(yīng)的錯(cuò)誤</p><p>　　if(zzLexicalState!=0){</p><p>　　switch(zzLexicalState){</p&g

24、t;<p>　　case 2:{err(errorM[E_STARTCOMMENT]);</p><p><b>　　break;}</b></p><p>　　case 4:{err(errorM[E_UNCLOSEDSTR]);</p><p><b>　　break;}</b></p>

25、;<p>　　default:{ /*do nothing*/ }</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return tok(sym.EOF, null);</p><p><b>　　}</b>&

26、lt;/p><p><b>　　%eofval}</b></p><p>　　//一些基本類(lèi)型簡(jiǎn)化表達(dá)式的定義</p><p>　　ALPHA=[A-Za-z]//字母</p><p>　　DIGIT=[0-9]//數(shù)字</p><p>　　LINE_TERMIN

27、ATOR = \r|\n|\r\n//換行符</p><p>　　NONNEWLINE_WHITE_SPACE_CHAR=[\ \t\f\b\012]//非換行空白符</p><p>　　WHITE_SPACE_CHAR ={LINE_TERMINATOR} | NONNEWLINE_WHITE_SPACE_CHAR}</p><p><b>

28、　　//空白符</b></p><p><b>　　%%</b></p><p><b>　　正規(guī)表達(dá)式的書(shū)寫(xiě)</b></p><p>　　Tiger需要識(shí)別的變量和字符有：整型常量、字符常量、操作符、括符、分隔符、關(guān)鍵字、標(biāo)識(shí)符、COMMENT。</p><p>　　整型常量： 一

29、個(gè)整形數(shù)字，即字母的任意組合。</p><p>　　字符常量： 用雙引號(hào)引起來(lái)的字符，可跨行但行尾必須以\結(jié)尾，行首\開(kāi)始。字符常量中間可包含轉(zhuǎn)義字符如：\r \n \t \f \” \\ \xyz x,y,z表示0~127的整數(shù)。</p><p>　　操作符： + - * / > >= < <= = := & | </p>&

30、lt;p>　　括符： ( ) { } [ ]</p><p>　　分隔符： ； ：</p><p>　　關(guān)鍵字： while do for to if else then let in end type var array of break nil function</p><p>　　標(biāo)識(shí)符：以字符開(kāi)頭，加上字符、數(shù)字、下劃線(xiàn)的任

31、意組合</p><p>　　評(píng)論： 以/*開(kāi)頭，以*/結(jié)尾中間可嵌套任意個(gè)但必須是封閉的。</p><p>　　一般的字符或者保留字只需返回它的名字就可以了，例如：在YYINITAIL的狀態(tài)下識(shí) 別到最長(zhǎng)匹配串為“array” ，則直接返回token，編號(hào)為sym.java中已經(jīng)定義的數(shù)字 編號(hào)，書(shū)寫(xiě)的格式如下：</p><p>　　<YYIN

32、ITIAL> "array" { return tok(sym.ARRAY,null); }</p><p>　　下面著重談一下對(duì)于字符串和注釋的處理：</p><p><b>　　字符串的處理：</b></p><p>　　在YYINITIAL狀態(tài)下遇到一個(gè) ” 時(shí)表示識(shí)別字符常量的開(kāi)始，此時(shí)就要進(jìn)入先前聲明的S

33、TRING 狀態(tài)，先前聲明的字符串str用來(lái)保存已識(shí)別的字符常量（初始化為空），代碼如下：</p><p>　　<YYINITIAL> \" { str.setLength(0); yybegin(STRING);}</p><p>　　當(dāng)識(shí)別的過(guò)程中如果碰到轉(zhuǎn)義字符\n \t \" \\，在str后添加相應(yīng)的字符，碰到非轉(zhuǎn)移字符就直接添加到str后面，忽

34、略?xún)蓚€(gè)反斜杠之間的所有空白字符，代碼如下：</p><p>　　<STRING> [^\n\r\"\\]+ { str.append(yytext()); }</p><p>　　<STRING> \\n { str.append('\n'); }</p><p>　　<STRING> \\\\ { st

35、r.append('\\'); }</p><p>　　<STRING> \\{WHITE_SPACE_CHAR}+\\ { /*do nothing*/}</p><p>　　特別是當(dāng)碰到\跟上三位數(shù)字時(shí)，應(yīng)該判斷數(shù)值范圍是否在ASCII范圍中</p><p>　　<STRING> \\0{DIGIT}{DIGIT}|\\

36、1[0-1]{DIGIT}|\\12[0-7] {</p><p>　　str.append((char)Integer.valueOf(new String(yytext().getBytes(),1,3)).intValue());}</p><p>　　當(dāng)再次識(shí)別到"時(shí)標(biāo)志著字符串的識(shí)別結(jié)束，此時(shí)將str中的字符串內(nèi)容作為String的內(nèi)容返回，同時(shí)應(yīng)該返回YYIN

37、ITIAL狀態(tài)，繼續(xù)識(shí)別其他的TOKEN</p><p>　　<STRING> \" {</p><p>　　yybegin(YYINITIAL);</p><p>　　return tok(sym.STRING,str.toString()); }</p><p>　　識(shí)別到這些token以外的其他字符，則直接報(bào)錯(cuò)

38、</p><p>　　<STRING> . {err(errorM[E_ILLEGAL]); }</p><p><b>　　注釋的處理：</b></p><p>　　在YYINITIAL狀態(tài)下遇到一個(gè) /* 時(shí)表示識(shí)別注釋的開(kāi)始，此時(shí)就要進(jìn)入先前聲明的COMMENT狀態(tài)，同時(shí)comment_count加1，以實(shí)現(xiàn)注釋嵌套的實(shí)現(xiàn)。

39、如果在COMMENT狀態(tài)下又一次識(shí)別到/*表示另一個(gè)注釋嵌套的開(kāi)始，此時(shí)也需要對(duì)comment_count進(jìn)行加1的操作，代碼如下：</p><p>　　<YYINITIAL> "/*" { </p><p>　　yybegin(COMMENT);</p><p>　　comment_count = comment_count + 1

40、; }</p><p>　　<COMMENT> "/*" { comment_count = comment_count + 1; }</p><p>　　但是如果在YYINITIAL狀態(tài)下遇到一個(gè) */則是一個(gè)錯(cuò)誤，需要報(bào)出，代碼如下：</p><p>　　<YYINITIAL> "*/" { err

41、(errorM[E_ENDCOMMENT]); }</p><p>　　在COMMENT狀態(tài)下遇到*/則表示著一個(gè)嵌套中的注釋結(jié)束，此時(shí)需要對(duì)comment_count進(jìn)行減1的操作，如果操作之后其值為0，表示整個(gè)注釋已經(jīng)結(jié)束，回到Y(jié)YINITIAL狀態(tài)，如若不然則繼續(xù)在COMMENT的狀態(tài)下識(shí)別，代碼如下：</p><p>　　<COMMENT> "*/"

42、 { </p><p>　　comment_count = comment_count - 1; </p><p>　　if (comment_count == 0)</p><p>　　yybegin(YYINITIAL)；}</p><p>　　識(shí)別到這些token以外的其他字符，則直接忽略</p><p>　　&

43、lt;COMMENT> . { /*do nothing*/ }</p><p>　　詞法分析器的結(jié)構(gòu) </p><p>　　詞法分析器實(shí)現(xiàn)了Lexer接口，也就是實(shí)現(xiàn)了Token next_token()這個(gè)方法，不斷調(diào)用此方法就可以獲得所有的記號(hào)流。使用詞法分析器時(shí)需要指定輸入流InputStream以及ErrorMsg，InputStream完成源程序的讀取，ErrorM

44、sg完成對(duì)錯(cuò)誤信息的輸出。</p><p>　　至此詞法分析器的構(gòu)造已經(jīng)基本基本結(jié)束了。</p><p><b>　　語(yǔ)法分析器</b></p><p>　　完成語(yǔ)法分析器的主要步驟是cup文件的編寫(xiě)，由于語(yǔ)法樹(shù)的數(shù)據(jù)結(jié)構(gòu)已給出，所以產(chǎn)生式的編寫(xiě)可以直接參考tiger語(yǔ)言的語(yǔ)法模式，當(dāng)然這其中產(chǎn)生了許多沖突，但是可以通過(guò)設(shè)置符號(hào)的優(yōu)先級(jí)來(lái)解決移

45、進(jìn)和規(guī)約的沖突。</p><p><b>　　CUP的使用</b></p><p>　　CUP的使用需要在命令行的環(huán)境下進(jìn)行，打開(kāi)命令提示符，輸入如下所示的語(yǔ)句，</p><p>　　既可以在當(dāng)前目錄下生成語(yǔ)法分析器Grm.java，Grm.cup的書(shū)寫(xiě)格式如下所示：</p><p>　　Cup開(kāi)始部分的書(shū)寫(xiě)格式如下：&

46、lt;/p><p>　　package parse;//產(chǎn)生在parse包里面</p><p>　　import Absyn.*;</p><p>　　import javax.swing.*;</p><p>　　action code {:</p><p>　　static Symbol.Symbol sym(

47、String s) {//將字符串轉(zhuǎn)化為Symbol</p><p>　　return Symbol.Symbol.symbol(s);</p><p><b>　　}</b></p><p><b>　　:};</b></p><p>　　parser code {: </p>&

48、lt;p>　　Yylex lexer;</p><p>　　public static Exp parseResult;//記錄語(yǔ)法樹(shù)根節(jié)點(diǎn)的變量</p><p>　　errormsg.ErrorMsg errorMsg;//輸出語(yǔ)法錯(cuò)誤的ErrorMsg對(duì)象聲明</p><p>　　public void syntax_error(java_cup

49、.runtime.Symbol current) {</p><p>　　report_error("Syntax error (" + current.sym + ")", (java_cup.runtime.Symbol)current);</p><p><b>　　}</b></p><p>　　

50、public void report_error(String message, java_cup.runtime.Symbol tok) {</p><p>　　errorMsg.error(tok.left, message);</p><p><b>　　}</b></p><p>　　public Grm(errormsg.ErrorM

51、sg err, JTextArea text) {</p><p>　　this();//語(yǔ)法分析器的構(gòu)造</p><p>　　errorMsg=err;</p><p>　　textin=text;</p><p><b>　　}</b></p><p><b>　　:};&l

52、t;/b></p><p>　　init with {: //語(yǔ)法分析器初始化，從界面文本框中獲取輸入流</p><p>　　lexer = new Yylex( new java.io.StringBufferInputStream(textin.getText()),errorMsg);</p><p><b>　　:};</b>

53、</p><p>　　scan with {: java_cup.runtime.Symbol symb= lexer.debug_next_token(); </p><p>　　for(;(symb.sym==sym.error)&&symb.sym!=sym.EOF;)</p><p>　　symb= lexer.debug_next_toke

54、n();</p><p>　　return symb; </p><p>　　:};//同過(guò)debug_next_token獲取token并打印出token</p><p><b>　　//終結(jié)符</b></p><p>　　terminal String STRING;</p><p>

55、;　　terminal Integer INT;</p><p>　　terminal COMMA, COLON, SEMICOLON, LPAREN, RPAREN, LBRACK, RBRACK, LBRACE, RBRACE, DOT;</p><p>　　terminal PLUS, MINUS, TIMES, DIVIDE, EQ, NEQ, LT, LE, G

56、T, GE, AND, OR, ASSIGN, UMINUS;</p><p>　　terminal ARRAY, IF, THEN, ELSE, WHILE, FOR, TO, DO, LET, IN, END, OF, BREAK, NIL, FUNCTION, VAR, TYPE, ID;</p><p>　　//終結(jié)符優(yōu)先級(jí)次序</p&g

57、t;<p>　　precedence right DO, ELSE, THEN;</p><p>　　precedence nonassoc ASSIGN;</p><p>　　precedence left OR;</p><p>　　precedence left AND;</p><p>　　precedence nona

58、ssoc EQ, NEQ, LT, LE, GT, GE;</p><p>　　precedence left PLUS, MINUS;</p><p>　　precedence left TIMES, DIVIDE;</p><p>　　precedence left UMINUS;</p><p>　　precedence left LB

59、RACK;</p><p>　　? 關(guān)于優(yōu)先級(jí)次序的說(shuō)明：由于在語(yǔ)法分析的過(guò)程中會(huì)產(chǎn)生許多移進(jìn)和規(guī)約的沖突，通過(guò)設(shè)置終結(jié)符的優(yōu)先級(jí)可以避免一些情況的發(fā)生。將PLUS、MINUS的優(yōu)先級(jí)定義在</p><p>　　TIMES、DIVIDE之前即可使乘除的優(yōu)先級(jí)高于加減運(yùn)算的優(yōu)先級(jí)。另外通過(guò)設(shè)置比較運(yùn)算符的有限次序，可以避免分析時(shí)的移進(jìn)--歸約沖突。</p><p>　

60、　此外在實(shí)際的cup生成過(guò)程中，還會(huì)出現(xiàn)一些其他的沖突，例如以下兩個(gè)沖突的解決： </p><p><b>　　№.1</b></p><p><b>　　出現(xiàn)沖突 </b></p><p>　　between lvalue ::= ID (*) </p><p>　　and lvalu

61、e ::= ID (*) LBRACK expr RBRACK </p><p>　　and expr ::= ID (*) LBRACK expr RBRACK OF expr </p><p>　　under symbol LBRACK </p><p>　　解決辦法：把left LBRACK 設(shè)為最高優(yōu)先級(jí)，這樣的話(huà)當(dāng)碰到是歸約ID還是移進(jìn) LBR

62、ACK的沖突時(shí)，系統(tǒng)會(huì)自動(dòng)根據(jù)優(yōu)先級(jí)而去執(zhí)行移進(jìn)的動(dòng)作。</p><p><b>　　№.2</b></p><p><b>　　出現(xiàn)沖突 </b></p><p>　　between expr ::= IF expr THEN expr (*) </p><p>　　and expr ::

63、= IF expr THEN expr (*) ELSE expr </p><p>　　under symbol ELSE </p><p>　　解決辦法：把right DO,ELSE,THEN設(shè)為最低優(yōu)先級(jí),通過(guò)precedence right</p><p>　　ELSE,THEN語(yǔ)句;定義為右結(jié)合的then將與else結(jié)合，故先移進(jìn)。</p>

64、<p><b>　　№.3</b></p><p>　　負(fù)號(hào)和減號(hào)識(shí)別時(shí)有沖突，解決方案是重新定義一個(gè)終結(jié)符UMINUS算數(shù)運(yùn)算符中最 高優(yōu)先級(jí)，負(fù)號(hào)時(shí)重新賦予UMINUS的優(yōu)先級(jí)。</p><p>　　2. 語(yǔ)法的書(shū)寫(xiě)</p><p>　　按照Tiger Manual上的語(yǔ)法規(guī)則，將上面的語(yǔ)法一一寫(xiě)入cup文件的后面，

65、必要的時(shí)候定義適當(dāng)?shù)姆墙K結(jié)符來(lái)完成語(yǔ)法的結(jié)構(gòu)。每一條語(yǔ)法規(guī)則都應(yīng)該返回其相應(yīng)的語(yǔ)句類(lèi)型，這些類(lèi)型都已經(jīng)在Absyn包中定義好了，只要根據(jù)語(yǔ)句的類(lèi)型按照定義返回即可。其中，要注意的是一些鏈表的連接，如ExpList、FieldList等，需要保證這些對(duì)象的連接正確性。</p><p>　　首先，在語(yǔ)法分析前完成非終結(jié)符的定義，定義如下：</p><p>　　non terminal Fie

66、ldListtype_fields, type_fields_n, type_fields_ex;</p><p>　　non terminal FieldExpListfield_list, field_list_n, field_list_ex;</p><p>　　non terminal ExpListexpr_list, expr_list_n, expr_list_ex

67、, expr_seq, expr_seq_n, expr_seq_ex;</p><p>　　non terminal DecListdeclaration_list, declaration_list_ex;</p><p>　　non terminal Tytype;</p><p>　　non terminal Decdeclaration, type

68、_declaration, variable_declaration, function_declaration;</p><p>　　non terminal Exp expr, program;//文法開(kāi)始符</p><p>　　non terminal Var lvalue;</p><p>　　其次在文法開(kāi)始符的語(yǔ)法句的執(zhí)行語(yǔ)句中，將第一

69、個(gè)Exp傳給先前定義的parseResul,代碼如下：</p><p>　　start with program;</p><p>　　program ::= expr:e {: parser.parseResult = e; :};</p><p>　　對(duì)于一些常規(guī)的語(yǔ)法，只需返回相應(yīng)的語(yǔ)句類(lèi)型即可，如賦值語(yǔ)句</p><p>　　

70、expr ::= lvalue:l ASSIGN expr:e</p><p>　　{: RESULT = new AssignExp(lleft, l, e); :}；</p><p>　　對(duì)于需要連接起來(lái)的類(lèi)型，如ExpList,FieldExpList,FieldList,DecList,可以通過(guò)消除左遞歸的方法來(lái)將多個(gè)具有向后指針的類(lèi)型的語(yǔ)句相連，另外鏈表還可以為空，下面舉ExpL

71、ist的例子來(lái)說(shuō)明處理的方法：</p><p>　　expr_list ::= expr_list_n:l…………………………………………………(1)</p><p>　　{: RESULT = l; :}</p><p>　　| {: RESULT = null; :}；</p><p>　　expr_list_n ::= expr:e

72、expr_list_ex:x…………………………………(2)</p><p>　　{: RESULT = new ExpList(e, x); :};</p><p>　　expr_list_ex::=COMMA expr_list_n:l ……………………………………(3)</p><p>　　{: RESULT = l; :}</p><p&

73、gt;　　| {: RESULT = null; :}；</p><p>　　在（1）開(kāi)始識(shí)別的時(shí)候先判斷這個(gè)表達(dá)式是否為空，若空則直接返回null，否則進(jìn)入（2），因?yàn)橹辽儆幸粋€(gè)Explist的存在，所以可以聲明一個(gè)新的ExpList，并將它的tail指向下一個(gè)可能的ExpList，當(dāng)然下一個(gè)ExpList可能為空，所以在處理expr_list_ex時(shí)需要判斷其是否為空，如空則直接返回null，否則可以將嵌套

74、進(jìn)行下去。</p><p><b>　　語(yǔ)法樹(shù)的生成</b></p><p>　　語(yǔ)法分析結(jié)束后，同時(shí)會(huì)返回整棵語(yǔ)法樹(shù)的根結(jié)點(diǎn)，我們可以利用這個(gè)根節(jié)點(diǎn)進(jìn)行語(yǔ)法樹(shù)的打印，調(diào)用Absyn\Print.Java中的prExp(par.parseResult,2)，將整個(gè)語(yǔ)法樹(shù)在屏幕上打印出來(lái)，同時(shí)還可以在Print.Java中定義一個(gè)string變量將需要的打印內(nèi)容儲(chǔ)存起來(lái)

75、，在屏幕上打印完之后在GUI界面的文本框內(nèi)顯示出來(lái)。</p><p><b>　　類(lèi)型檢查</b></p><p><b>　　類(lèi)型檢查運(yùn)作思想</b></p><p>　　語(yǔ)法分析結(jié)束后，我們還可以對(duì)整棵語(yǔ)法樹(shù)進(jìn)行類(lèi)型檢查，我們可以從語(yǔ)法樹(shù)的根結(jié)點(diǎn)開(kāi)始對(duì)每一個(gè)分支進(jìn)行掃描，根據(jù)Tiger語(yǔ)言所所規(guī)定的語(yǔ)法類(lèi)型規(guī)則進(jìn)行判斷

76、這一條語(yǔ)句運(yùn)算或者返回的類(lèi)型是否符合要求，如果類(lèi)型不匹配立即報(bào)出類(lèi)型錯(cuò)誤。</p><p>　　類(lèi)型檢查的關(guān)鍵是管理好符號(hào)表。整個(gè)檢查過(guò)程維護(hù)一張變量表，一張類(lèi)型表，都是Table類(lèi)型的。Table是按鍵值方式存儲(chǔ)，關(guān)鍵字是Symbol類(lèi)型，值是Binder類(lèi)型，Binder中變量value存儲(chǔ)具體的信息。變量表的value存儲(chǔ)Entry類(lèi)型，Entry說(shuō)明變量的類(lèi)型以及其它信息。類(lèi)型表的value存儲(chǔ)的是Typ

77、e類(lèi)型，保存類(lèi)型的具體信息。Binder類(lèi)是一個(gè)鏈表結(jié)構(gòu)，也就是說(shuō)一個(gè)符號(hào)可以幾個(gè)類(lèi)型，如本地變量覆蓋全局變量，本地類(lèi)型覆蓋全局類(lèi)型等。</p><p>　　類(lèi)型檢查所用到的類(lèi)的關(guān)系可以從下圖中看清：</p><p>　　每個(gè)變量或類(lèi)型都有一個(gè)有效范圍，在function的聲明過(guò)程中，其聲明的變量只在它的函數(shù)體中有效，出了函數(shù)體就失去了它的作用范圍，成為了一個(gè)無(wú)效的變量。又如在in end

78、中又嵌套了let in end 語(yǔ)句，則外面語(yǔ)句中聲明的變量在里面的語(yǔ)句中仍然有效（重復(fù)聲明會(huì)覆蓋）?？梢岳胻able中的beginscope()和endscope()來(lái)確定變量的作用范圍。調(diào)用函數(shù) beginScope() 添加一個(gè)標(biāo)記，標(biāo)記起始位置。當(dāng)這個(gè)變量的作用域到底時(shí)用調(diào)用函數(shù) endScope() 把先前的聲明都刪掉。</p><p>　　遇到的實(shí)際問(wèn)題與思考</p><p>

79、;<b>　　№.1</b></p><p>　　類(lèi)型檢查的過(guò)程中，還有一個(gè)遞歸調(diào)用的問(wèn)題，如testcase6</p><p><b>　　let</b></p><p>　　function do_nothing1(a: int, b: string)=</p><p>　　do_nothing

80、2(a+1)</p><p>　　function do_nothing2(d: int) =</p><p>　　do_nothing1(d, "str")</p><p><b>　　in</b></p><p>　　do_nothing1(0, "str2")</p&g

81、t;<p><b>　　End</b></p><p>　　其中do_nothing1函數(shù)的body需要調(diào)用do_nothing2,但是按照函數(shù)按順序聲明的話(huà)，此時(shí)do_nothing2還沒(méi)有被聲明，因而不能夠被識(shí)別，會(huì)報(bào)錯(cuò)。</p><p>　　解決方法：在let語(yǔ)句檢查declist之前將所有的dec（包括type_declaration，funct

82、ion_declaration）置入相應(yīng)的表中，這樣的話(huà)當(dāng)檢查上述的函數(shù)do_nothing1時(shí)就不會(huì)出現(xiàn)do_nothing2還未被聲明的情況了。</p><p><b>　　№.2</b></p><p>　　類(lèi)型檢查的過(guò)程中，還有一個(gè)循環(huán)定義的問(wèn)題，如testcase16</p><p><b>　　let </b>

83、</p><p><b>　　type a=c</b></p><p><b>　　type b=a</b></p><p><b>　　type c=d</b></p><p><b>　　type d=a</b></p><p>

84、;<b>　　in</b></p><p><b>　　end</b></p><p>　　解決方法：在這四個(gè)類(lèi)型定義中，都用到了其他一起聲明的類(lèi)型，存在類(lèi)似a-c-d-a的類(lèi)型循環(huán)定義，到最后四個(gè)四個(gè)變量的類(lèi)型還是沒(méi)有被實(shí)在定義，這是不允許的。解決的方法是在檢查類(lèi)型定義之前用bind(ExpTy)函數(shù)將新聲明的類(lèi)型的binding設(shè)為聲明中將要

85、被賦予的類(lèi)型。這樣在進(jìn)入類(lèi)型聲明的檢查中，只需通過(guò)isloop()函數(shù)判斷是否是循環(huán)定義就可知道是否出錯(cuò)。在這樣的設(shè)計(jì)之下，代碼</p><p><b>　　let </b></p><p><b>　　type a=c</b></p><p><b>　　type b=a</b></p>

86、<p><b>　　type c=d</b></p><p>　　type d=int</p><p><b>　　in</b></p><p><b>　　end</b></p><p>　　就不會(huì)出現(xiàn)如上的錯(cuò)誤了，a-c-d-int就會(huì)跳出檢查，返回false

87、</p><p><b>　　№.3</b></p><p>　　在Declist中的聲明中要求函數(shù)和類(lèi)型的聲明分別必須放在一起，如</p><p><b>　　let</b></p><p>　　function g(a:int):int = a</p><p>　　typ

88、e t = int</p><p>　　function g(a:int):int = a</p><p><b>　　in</b></p><p><b>　　end</b></p><p>　　示例中說(shuō)這是合法的，應(yīng)為聲明的時(shí)候是以類(lèi)處理的，funcDec和后面的funcDec一起處理，type

89、Dec和后面的typeDec一起處理，導(dǎo)致檢查不出這個(gè)重復(fù)定義函數(shù)。我認(rèn)為這里有點(diǎn)不太合理，我的想法是可以在let語(yǔ)句的檢查中將所有的聲明都放入環(huán)境變量中，這樣的話(huà)既可以檢查出是否重復(fù)定義，有可以使類(lèi)型的前后調(diào)用不受阻礙。</p><p>　　即在ExpTy transExp(LetExp e)中添加如下代碼：</p><p>　　ArrayList<String> list

90、=new ArrayList<String>();</p><p>　　for(DecList tmp=e.decs;tmp!=null;tmp=tmp.tail){</p><p>　　Dec head=tmp.head;</p><p>　　if(head instanceof TypeDec){//置入新的類(lèi)型</p><p

91、>　　TypeDec td=(TypeDec)head;</p><p>　　if(list.contains(td.name.toString()))</p><p>　　env.errorMsg.error(td.pos,"type '"+td.name+"' has been already defined

92、");</p><p>　　list.add(td.name.toString());</p><p>　　env.tenv.put(td.name,new NAME(td.name));</p><p><b>　　}</b></p><p>　　if(head instanceof FunctionDec)

93、{//置入新的函數(shù)變量</p><p>　　FunctionDec fd=(FunctionDec)head;</p><p>　　Type re=transTy(fd.result);</p><p>　　RECORD rc=transTypeFields(fd.params);</p><p>　　if(list.contains(

94、fd.name.toString()))</p><p>　　env.errorMsg.error(fd.pos,"function '"+fd.name+"' already defined");</p><p><b>　　else{</b></p><p>

95、　　list.add(fd.name.toString());</p><p>　　env.venv.put(fd.name, new FunEntry(rc,re));</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}<

96、/b></p><p>　　list.clear();</p><p>　　這樣的處理過(guò)后，就會(huì)達(dá)到上述的效果，不過(guò)這只是我的個(gè)人意見(jiàn)，雖然與tiger語(yǔ)言的要求有矛盾，但我認(rèn)為這不失為一種好的改進(jìn)。處于這種改動(dòng)，testcases中的有點(diǎn)不應(yīng)該報(bào)錯(cuò)的例子，在本編譯器中會(huì)出錯(cuò)，像上述例子就會(huì)報(bào)“重復(fù)定義”的類(lèi)型錯(cuò)誤，所以請(qǐng)使用者注意這一點(diǎn)。</p><p>&

97、lt;b>　　GUI界面</b></p><p>　　最后介紹一下本編譯器GUI界面的實(shí)現(xiàn)及結(jié)構(gòu)。在界面中有一個(gè)工具欄和三個(gè)顯示窗口和一個(gè)輸入窗口，分別為：</p><p>　　源程序輸入窗口-------用于獲取需要檢查的代碼</p><p>　　語(yǔ)法樹(shù)輸出窗口-------顯示語(yǔ)法樹(shù)</p><p>　　TOKEN輸出窗

98、口--------顯示所識(shí)別的TOKEN</p><p>　　錯(cuò)誤信息輸出窗口-----顯示源程序中的詞法、語(yǔ)法和類(lèi)型錯(cuò)誤</p><p>　　打開(kāi)-----------------從文件輸入程序</p><p>　　檢查-----------------執(zhí)行編譯程序，檢查錯(cuò)誤</p><p>　　退出-----------------退出程

99、序</p><p><b>　　文件輸入</b></p><p>　　點(diǎn)擊“打開(kāi)”按鈕會(huì)觸發(fā)鼠標(biāo)事件，會(huì)新建一個(gè)JFileChooser，選擇文件并確定后，會(huì)從所選文件路徑中將內(nèi)容讀出來(lái)并置入輸入文本框。另外，還記錄下本次的路徑，當(dāng)下一次再次打開(kāi)時(shí)就以上次的路徑為當(dāng)前路徑。</p><p><b>　　樹(shù)的輸出</b>&l

100、t;/p><p>　　修改Absyn中的Print.Java文件，在其中定義一個(gè)String變量str，在語(yǔ)法樹(shù)向屏幕輸出的同時(shí)也將信息保存在str中，當(dāng)屏幕輸出完成之后，可將str傳遞給界面中的文本框，達(dá)到語(yǔ)法樹(shù)的輸出功能。</p><p><b>　　錯(cuò)誤輸出</b></p><p>　　詞法分析，語(yǔ)法分析、類(lèi)型檢查階段錯(cuò)誤信息都是由Error

101、Msg類(lèi)實(shí)現(xiàn)。這個(gè)類(lèi)中添加了一個(gè)JtextArea的變量，在定義的時(shí)候?qū)⑼獠康恼{(diào)入，這樣的話(huà)當(dāng)調(diào)用error函數(shù)時(shí)就可以直接在界面的文本框內(nèi)輸出錯(cuò)誤信息。</p><p><b>　　總結(jié)與感想</b></p><p>　　這次編譯原理課程設(shè)計(jì)主要是實(shí)現(xiàn)Tiger語(yǔ)言編譯器前面一些分析階段的功能，包括詞法分析、語(yǔ)法分析和類(lèi)型檢查等。詞法分析部分既詞法分析器的設(shè)計(jì)，詞法

102、分析是編譯的基礎(chǔ)，詞法分析器從輸入流獲取源程序，進(jìn)行分析之后給語(yǔ)法分析器提供token，語(yǔ)法分析器從中進(jìn)行語(yǔ)法分析，同時(shí)生成語(yǔ)法樹(shù)，之后根據(jù)這棵語(yǔ)法素進(jìn)行類(lèi)型檢查?？偟膩?lái)說(shuō)，一個(gè)編譯器的實(shí)現(xiàn)過(guò)程是很復(fù)雜的，但又是井井有條的。本編譯器所能實(shí)現(xiàn)的功能只是其中的一小部分，要想完整地實(shí)現(xiàn)一個(gè)編譯器的功能確實(shí)還有很多的工作要做。</p><p>　　在本次課程設(shè)計(jì)中，充分體現(xiàn)了上半學(xué)期編譯原理課程中的一些基礎(chǔ)的知識(shí)，對(duì)于后

103、來(lái)的debug和設(shè)計(jì)思路都提供了很大的幫助，也達(dá)到了課程設(shè)計(jì)的目的。另外在課程設(shè)計(jì)的過(guò)程中也用到了很多java語(yǔ)言方面的知識(shí)和大量編程技巧，在程序的實(shí)際編寫(xiě)方面提供了許多的經(jīng)驗(yàn)。可以說(shuō)通過(guò)本次課程設(shè)計(jì)不僅對(duì)編譯原理這一門(mén)課程也有了更加深刻的了解，同時(shí)自己的編程能力也有所提高，對(duì)于java程序的理解和運(yùn)用也有所感悟和提高。同時(shí)，我也發(fā)現(xiàn)自己在所學(xué)知識(shí)不夠全面，自己的自學(xué)和理解能力有所欠缺，以后需要在這些方面多加注意，多加完善，為今后其他的

104、課程設(shè)計(jì)甚至今后的就業(yè)打下扎實(shí)的基礎(chǔ)。</p><p><b>　　鳴謝</b></p><p>　　對(duì)于在本次編譯原理課程設(shè)計(jì)中給予我?guī)椭闹汤蠋熀屯瑢W(xué)表示由衷的感謝！特別感謝Herr Gu同學(xué)對(duì)我耐心的指導(dǎo)，以及在一些問(wèn)題上給予我解決問(wèn)題的思想。</p><p><b>　　參考文獻(xiàn)</b></p>&