基于gui的交互式編譯系統(tǒng)之中間代碼生成器的設計與實現(xiàn)

基于GUI的交互式編譯系統(tǒng)之中間代碼生成器的設計與實現(xiàn)基于GUI的交互式編譯系統(tǒng)之中間代碼生成器的設計與實現(xiàn)摘要本設計實現(xiàn)了一個編譯器前端，它將一個用C語言的子語言編寫的源程序翻譯成中間代碼。詞法分析器、語法分析器、中間代碼生成器均是采用C++語言手動書寫完成，未采用自動生成器，GUI采用Win32API實現(xiàn)以保證輕快的運行速度及良好的系統(tǒng)性能，編輯控件采用Scintilla。詞法分析器采用確定有限自動機實現(xiàn)，語法分析器是一個遞歸下降分析器，中間代碼生成器輸出的中間代碼以四元式形式表示。本設計實現(xiàn)的編譯器前端，運行在Windows平臺下，Windows系統(tǒng)版本為WindowsXP、Windows7或更高版本。本設計提供了一個可工作的界面友好的編譯器前端，可以用來理解編譯原理及解釋怎樣用一種語言如C++實現(xiàn)編譯器前端，以供學習和教學所用。關鍵詞：編譯器前端；GUI；C++

Design&ImplementationofIntermediateCodeGeneratorofInteractiveCompilationSystemBasedGUIAbstractThisfinalprojectimplementsacompilerfront-end,ittranslatessourceprogramswritteninasubsetoftheClanguageintointermediatecode.Thelexer、parserandintermediatecodegeneratorareallhand-writteninC++,noautolexerorparserareused,GUIisimplementedinWin32APIforfastrunningspeedandhighperformance,andeditcontrolusesScintilla.ThelexerisimplementedinDeterministicfiniteautomata,theparserisarecursive-descentparser,theintermediatecodesarerepresentedinquadruple。Thecompilerfront-endrunsontheWindowsplatform,WindowssystemversionisWindowsXP,Windows7orlater.Thisprojectprovideaworkinganduserinterfacefriendlycompilerfront-end,whichcanbeusedtodemonstratecompilerprincipleandhowcompilerscanbeimplementedinalanguagesuchasC++,forlearningandteaching.Keywords:compilerfront-end;GUI;C++

目錄1緒論 緒論很少有人去自己編寫或修改編譯器，那么為什么要去實現(xiàn)編譯器前端呢？很重要的一點就是，理解計算機程序怎樣被編譯以及執(zhí)行，可以幫助任何程序員理解他們寫的代碼是怎樣驅(qū)動計算機的，從而幫助他們寫出更快、更高效的程序。編譯原理經(jīng)過多年發(fā)展已日趨成熟，然而現(xiàn)代很多跟編譯原理相關的教材，內(nèi)容陳舊落后，比如以Fortran或Pascal等過時語言為例進行分析講解，或者全書充滿晦澀難懂的定理公式，不能以直觀的方式進行闡述，致使學生望而生畏。本設計用C++語言實現(xiàn)了一個編譯器前端，它將一個用C子語言編寫的源程序翻譯成中間代碼，擁有友好直觀的交互式圖形界面，有助于對編譯原理的理解，可用于學習及教學。在一段程序可以執(zhí)行之前，首先需要把它翻譯成一種其能夠被計算機接受的形式，完成這項翻譯工作的程序稱為編譯器（compiler）[1]。簡單而言，編譯器是一個程序，它將使用源語言編寫的程序轉換成另一種目標語言。在轉換階段很重要的一部分是報告用戶當前源程序的錯誤。為了將源程序從一種語言翻譯成另一種語言，編譯器必須首先把程序的各種成分拆開，并搞清其結構和含義，然后再把這些成分組合成有意義的計算機能識別的語言。編譯器的前端進行詞法分析、語法分析和語義分析，并且產(chǎn)生中間代碼，即進行分析。編譯器的后端對中間代碼進行優(yōu)化并將中間代碼翻譯成機器語言，即進行組合。詞法分析的任務是：對源程序進行從左到右逐個字符地掃描，產(chǎn)生一個個獨立的單詞符號（token）。詞法分析是編譯的基礎。語法分析的任務是：在詞法分析識別出一系列單詞符號的基礎上，分析并判定源程序的結構是否符合語法規(guī)則。語法分析可以粗略地分為兩類，一類是自頂向下，一類是自底向上[2]。對于本設計，采用的是自頂向下進行分析。語法分析得到語法樹，盡管可以直接將語法樹轉換成目標機器代碼，但這樣做不利于可移植性和模塊化設計。假設需要這樣一個編譯器：它可以編譯N種不同的源語言，然后為M臺不同的目標機生成代碼。理論上，這是N*M個編譯器，如圖1.1(a)，但實現(xiàn)這么多的編譯器是需要花費大量的人力物力。中間代碼（intermediatecode,IC）是一種抽象機器語言，它可以表示目標機的操作而不需太多涉及與機器相關的細節(jié)，而且，它也獨立于源語言的細節(jié)[3]。一個可移植的編譯器如圖1.1(b)所示，它先將源語言轉換成中間代碼，然后再將中間代碼轉化成目標機器語言，這樣便只需要實現(xiàn)N個前端和M個后端。這種實現(xiàn)要更容易合理些。即使在只需實現(xiàn)一個前端和一個后端的情況下，好的中間代碼也利于將系統(tǒng)模塊化，使得編譯器前端不會因機器相關的細節(jié)而復雜化，編譯器后端不會因源語言的特殊信息而干擾。編譯器可以使用的中間代碼有多種形式，對于本設計，采用簡單的四元式。ICIC(a)(b)圖1.1面向5種語言并支持4種目標機的編譯器：（a）沒有IC，（b）有IC編譯器的每個階段都可能遇到錯誤，如果編譯器在遇到第一個錯誤時就停止運行，對于修正程序肯定起不到多大幫助作用。詞法分析階段可以檢測出來自輸入的字符串不能形成語言的任何單詞符號（token）。語法分析階段可以檢測出違反語言語法的單詞符號串。本設計可以報告出錯誤是什么及錯誤在源程序的行號和列號。

2基本原理一個編譯器是一個計算機程序，它可以把用某種高級語言寫的源代碼轉換成另一種形式，典型的形式是機器碼。機器碼是計算機可以執(zhí)行的一系列指令[4]。intmax(inta,intb){ if(a>b) returna; returnb;}一個編譯器由有兩部分組成，如圖2.1所示。（1）源代碼分析器：它將輸入的源代碼看作是一個字符串，然后將其翻譯成有意義的符號（變量，值，操作符等）。（2）目標代碼生成器：它將源代碼分析器的結果轉換成可執(zhí)行代碼。t1=-ct2=b*t1t3=t1+t2t1=-ct2=b*t1t3=t1+t2t4=t3目標代碼源代碼目標代碼生成器源代碼分析器目標代碼生成器源代碼分析器圖2.1編譯器結構源代碼分析器不依賴于機器，然而目標代碼生成器需要針對不同的機器類型生成不同的代碼，因此是依賴于機器的。源代碼分析器經(jīng)常被稱作編譯器的前端，目標代碼生成器被稱作后端。本設計要實現(xiàn)的正是編譯器的前端。編譯器的前端又分為三個階段，如圖2.2所示。t1=-ct2=b*t1t1=-ct2=b*t1t3=t1+t2t4=t3前端源代碼中間代碼生成器語法分析器詞法分析器源代碼中間代碼生成器語法分析器詞法分析器圖2.2編譯器前端

2.1詞法分析詞法分析器以字符流作為輸入，刪除單詞之間的空白符和注釋（程序中每一部分都有可能出現(xiàn)空白和注釋）并生成一系列的名字、關鍵字和標點符號。如果讓語法分析器來處理它們就會使得語法分析過于復雜，結構也不清晰，這便是將詞法分析成為一個獨立階段，從語法分析中分離出去的主要原因[5]。在詞法分析器中，詞法單元（token）通常包含以下幾種類型：標識符保留字（如：“if”，“while”等）數(shù)值常量（如：整數(shù)，實數(shù)等）字符串常量簡單符號（運算符如：“+”，“-”等，分隔符如：“；”，“，”等）多重符號（運算符如“+=”，“++”等）這些詞法單元將用于下一階段語法分析。2.1.1詞法分析結果對于下面一段程序：intmatch(char*str) //findazero{ if(!strncmp(str,“0”,1)) return0;}詞法分析器將產(chǎn)生如下tokens：INT ID(match) LPAREN CHAR STAR ID(str) RPARENLBRACEIF LPAREN BANG ID(strncmp) LPARENID(str)COMMASTRING(0)COMMA NUM(1) RPAREN RPARENRETURN REAL(0) SEMIRBRACEOF2.1.2確定有限自動機確定有限自動機可用來實現(xiàn)詞法分析器。有限自動機包括一個有限狀態(tài)集合和一些從一個狀態(tài)通往另一狀態(tài)的邊，每條邊上標有一個符號；其中一個狀態(tài)是初態(tài)，某些狀態(tài)是終態(tài)[6]。圖2.3給出了幾個有限自動機的例子。ifif312312IFa-za-z0-90-910-921210-92120-90-9ID NUM圖2.3詞法單詞的有限自動機在確定有限自動機中，不會有從同一狀態(tài)發(fā)出的兩條邊標記有相同的符號，確定有限自動機以如下方式接受或拒絕一個字符串：從初始狀態(tài)出發(fā)，對于輸入串中的每個字符，自動機都將沿著一條確定的邊到達另一狀態(tài)，這條邊必須是標有輸入字符的邊，對n個字符的字符串進行了n次狀態(tài)轉換后，如果自動機到達了一個終態(tài)，自動機將接受該字符串，若到達的不是終態(tài)，或者找不到與輸入字符相匹配的邊，那么自動機將拒絕接受該字符串[7]。2.2語法分析語法分析是分析如何根據(jù)一個文法生成一個終結符號串的過程。一種語言的識別器是一個程序，它把輸入看作一個字符串x，如果x是該語言的一個句子，則回答是，否則回答否。大多數(shù)分析方法都可以歸為以下兩類：自頂向下方法和自底向上方法。在自頂向下語法分析器中，構造過程從根結點開始，逐步向葉子節(jié)點方向進行，直至推出句子。自頂向下方法可以較容易地手工構造出高效的語法分析器。在自底向上語法分析器中，逐步對輸入串進行歸約，直至文法的開始符號，即從葉子節(jié)點開始，逐步向上歸約，直至語法樹的根節(jié)點。LL(1)文法表示對輸入串從左到右掃描，進行最左推導，分析時每步向前查看一個字符。LL(1)分析法需要消除左遞歸和克服回溯。LR分析法表示對輸入串從左到右掃描，構造最右推導的逆過程。LR分析法若采取手工構造，工作量非常大。本設計語法分析采用遞歸下降分析法。2.2.1遞歸下降分析法遞歸下降分析方法是一種不帶回溯的自頂向下語法分析方法，它使用一組遞歸過程來處理輸入。為文法的每個非終結符都創(chuàng)建一個相應的過程。遞歸下降分析法的一種簡單形式是預測分析法。在預測分析法中，各個非終結符號對應的過程中的控制流可以由向前看符號無二義性地確定，在分析輸入串時出現(xiàn)的過程調(diào)用序列隱式地定義了該輸入串的一棵語法樹[8]。假設用預測分析法分析以下文法(黑體字符序列被視為一個單元，也就是單個終結符號)：stmt expr; | if(expr)stmt | for(optExpr;optExpr;optExpr)stmt | otheroptExpr ε | expr則預測分析器如下所示：voidstmt(){ switch(curToken){ caseexpr: accept(expr);accept(‘;’); break; caseif: accept(if);accept(‘(’);accept(expr);accept(‘)’);stmt(); break; casefor: accept(for);accept(‘(’); optExpr();accept(‘;’);optExpr();accept(‘;’)optExpr(); accept(‘)’);stmt();break; caseother: accept(other);break; default: report(“syntaxerror”); }}voidoptExpr(){ if(curToken==expr) accept(expr);}voidaccept(terminalt){ if(curToken==t) curToken=nextTerminal; else report(“syntaxerror”);}該預測分析器中包含了兩個過程stmt()和optExpr()，分別對應于文法中非終結符號stmt和optExpr。該分析器中還包括一個額外的過程accept。這個額外的過程用來簡化stmt和optExpr()的代碼。過程accept(t)將它的參數(shù)t和向前看符號比較，如果匹配就前進到下一個輸入終結符號。因此，accept改變了全局變量curToken的值，該變量存儲了當前正被掃描的輸入終結符號。在分析過程的開始，首先調(diào)用文法的開始非終結符號stmt對應的過程，根據(jù)相應的語法規(guī)則，調(diào)用相應的處理過程。例如在處理“for(expr;expr;expr)other”輸入時，curToken被初始化為第一個終結符號for。每個非終結符都產(chǎn)生一個對相應過程的調(diào)用：accept(for);accept(‘(’);optExpr();accept(‘;’);optExpr();accept(‘;’);optExpr();accept(‘)’);stmt();2.2.2運算符的優(yōu)先級考慮表達式5+2*3。該表達式可有兩種不同的翻譯，即（5+２）*3或5+(2*3)。因此當多種運算符出現(xiàn)時，需要給出一些規(guī)則來確定運算符之間的相對優(yōu)先關系。先考慮“+-*/”這四個常用運算符之間的優(yōu)先級關系：左結合：+-左結合：*/創(chuàng)建兩個非終結符expr和term，expr對應于“左結合：+-”，term對應于“左結合：*/”，并使用另一個非終結符號factor來表示表達式中的基本單元。當前，表達式中基本單元是數(shù)字位和帶括號的表達式。factor digit|(expr)現(xiàn)在考慮具有最高優(yōu)先級的二目運算符*和/。由于這些運算符是左結合的，因此其產(chǎn)生式和左結合列表的產(chǎn)生式類似：term term*factor| term/factor| factor類似的，expr生成由加減運算符分隔的term列表：expr expr+term | expr–term| term因此最終得到的文法是：expr expr+term|expr–term|termterm term*factor|term/factor|factorfactor digit|(expr)2.3中間代碼生成目標代碼目標代碼1目標代碼分析器目標代碼分析器1中間代碼目標代碼分析器2中間代碼目標代碼分析器2目標代碼目標代碼2圖2.4中間代碼經(jīng)常會有這種情況，編譯器需要為幾個目標機器生成機器碼或匯編程序。中間代碼是跟目標機器無關的，所以相同的中間代碼可以在目標語言之間共享（如圖2.4）。那么為一臺新的機器開發(fā)編譯器時就可以減少工作量。另外，很容易對中間代碼進行優(yōu)化，優(yōu)化也是與機器無關的[9]。中間代碼生成階段將語法樹翻譯成中間語言表示形式。中間代碼是機器無關的，但是它們接近機器指令。源程序通過中間代碼生成器翻譯成等價的中間語言。中間代碼可以是不同的語言，它由編譯器的設計者決定。語法樹可以作為中間語言，后綴表達式可以作為中間語言，三地址代碼（四元式）也可以作為中間語言。在后綴表達式中，任何語句表示都可以不使用括號，如：a*(9+d)=>a9d+*后綴表達式計算可以通過棧來實現(xiàn)。然而使用后綴表達式有很多不利的地方，如后綴表達式生成的匯編代碼包含冗余的操作；這些操作只能在匯編代碼中進行優(yōu)化，而不是在中間代碼中；優(yōu)化需要針對特定的目標機器。因此需要一種接近匯編語言的中間代碼，它支持機器無關級的優(yōu)化。所以本設計采用四元式。2.3.1四元式在四元式中，所有的操作都可以歸約為一元或二元操作。這種中間代碼可以看成是一系列的執(zhí)行步驟，每步的執(zhí)行結果存儲在臨時變量中[10]。四元式由如下成分組成：操作符操作數(shù)，即兩個操作數(shù)結果，存儲運算結果（operator,arg1,arg2,result）一個簡單的表達式可以用一個四元式表示：b+c=>(+,b,c,tmp1)稍微復雜的表達式可以由一個四元式集合表示，臨時變量存儲中間結果。a*(5+d)=>(+,5,d,tmp1) (*,a,tmp1,tmp2)2.3.2四元式的常見結構算術運算和布爾表達式a+b =>(+,a,b,tmp1)a*(b+c) =>(+,b,c,tmp1),(*,a,tmp1,tmp2)按照運算順序，先計算括號中的表達式“b+c”，運算結果保存在臨時變量tmp1中，然后計算a*tmp1。a<b =>(<,a,b,tmp)一元運算-a=>(-,a,_,tmp)下劃線表示空。賦值a=a+b =>(+,a,b,tmp),(=,tmp,_,a)本設計的賦值運算只支持簡單賦值，不支持連續(xù)賦值，如a=b=0。聲明inta,b =>無inta=5 =>(=,5,_,a)聲明時可以進行初始化。數(shù)組引用a=x[i]=>(=,x[i],_,a)x[i]=a=>(=,a,_,x[i])無條件跳轉(jmp,jump_address,_,_)jump_address表示跳轉目標地址，在本設計中是一個目標標號。條件跳轉(<,i,5,tmp1) //條件(jtrue,jump_address,tmp1,_) //表示如果tmp1為真則跳轉。注：是條件調(diào)轉還是無條件調(diào)轉，由arg2決定。for循環(huán)for(i=0;i<3;i++) body=>(=, 0, _, i) //初始化(label_0:,_, _, _)(<,i,3,temp_0) //條件(jtrue,label_1,temp_0,_)(jmp, label_3,_, _)(label_1:,_, _,_)bodyofloop...(label_2:,_,_,_)(+,i,1,i) //迭代(jmp,label_0,_,_)(label_3:,_,_,_)每個for語句會產(chǎn)生四個標號，一個表示類似“i=0”的初始化，一個表示類似“i<３”的條件判斷，一個表示body,一個表示類似“i++”的表達式。if-else語句if(a<b)c=a;elsec=b;=>(<, a, b,temp_0)(jtrue, label_1, temp_0,_)(jmp, label_0, _,_)(label_1:,_, _,_)(=, a, _,c)(jmp, label_2,_,_)(label_0:,_, _,_)(=, b, _,c)(label_2:,_, _,_)一個if-else語句會產(chǎn)生3個標號，一個表示條件為真時的執(zhí)行語句，一個表示條件為假的執(zhí)行語句，一個表示跳出if-else語句。while語句while(a<b) a=a+1;=>(label_0:,_, _, _)(<, a, b,temp_0)(jtrue, label_1,temp_0,_)(jmp, label_2,_,_)(label_1:,_, _,_)(+, a,1,temp_1)(=, temp_1,_,a)(jmp, label_0,_,_)(label_2:,_,_,_)每個while語句產(chǎn)生3個標號，一個表示類似“a=0”的初始化，一個表示類似“a<b”的條件判斷，一個表示body。switch語句switch(i){ case1: a=a+1;break; default: a=a+2;}=>(jmp,label_0,_,_)(label_3:,_,_,_)(+,a,1,temp_0)(=,temp_0,_,a)(jmp,label_2,_,_)(label_1:,_,_,_)(+,a,2,temp_1)(=,temp_1,_,a)(jmp,label_2,_,_)(label_0:,_,_,_)(==,i,1,temp_2)(jtrue,label_3,temp_2,_)(jmp,label_1,_,_)(label_2:,_,_,_)每個switch語句會針對相應的case和default產(chǎn)生標號，同時，還會產(chǎn)生跳出switch的標號。函數(shù)調(diào)用intadd(inta,intb){ returna+b;}voidmain(){ inta=1,b=1,c; c=add(a,b);}=>(add:,_,_,_)(enter,16,_,_)(+,a,b,temp_0)(return,temp_0,_,_)(return,_,_,_)(main:,_,_,_)(enter,16,_,_)(=,1,_,a)(=,1,_,b)(param,b,_,_)(param,a,_,_)(call,add,_,temp_1)(incStackPtr,8,_,_)(=,temp_1,_,c)(return,_,_,_)每個函數(shù)調(diào)用會針對主調(diào)函數(shù)和被調(diào)函數(shù)產(chǎn)生相應的標號。以上只是列舉了一些簡單情況下的示例，對于復雜的源程序，翻譯成的四元式集是以上常見四元式結構組合的結果。2.4符號表符號表是一種供編譯器用于保存有關源程序構造的各種信息的數(shù)據(jù)結構，這些信息在編譯器的分析階段被逐步收集并放入符號表[11]。編譯器用符號表跟蹤作用域及名字綁定的相關信息。在源程序中每次遇到名字都會去搜索符號表。如果新的名字出現(xiàn)或關于一個已存在名字新的信息出新，要對符號表進行更新。符號表條目可在詞法分析階段、語法分析階段和語義分析階段創(chuàng)建（如圖2.5）。在本設計中，由語法分析器來創(chuàng)建這些條目。因為相對于詞法分析器而言，語法分析器知道一個程序的語法結構，它可以更好地區(qū)分一個詞法單元的實際意義，因此常更適合創(chuàng)建符號表條目。前端前端詞法分析器中間代碼生成器語法分析器詞法分析器中間代碼生成器語法分析器符號表符號表圖2.5符號表符號表通常用哈希表實現(xiàn)。KEY：詞素（lexeme），VALUE：符號（symbol）。2.4.1作用域在靜態(tài)類型編程語言中，變量在使用之前必須聲明，聲明提供了變量的類型。如：inta;charc;通常，聲明只在它的作用域內(nèi)有效。函數(shù)作用域：每個變量在函數(shù)內(nèi)部定義。塊作用域：變量只在代碼塊內(nèi)有效。floatfoo(inta,floatb){intc; //c為局部作用域中變量。{ intb=100; //塊作用域中定義的b將參數(shù)b覆蓋。c=a+b; //將參數(shù)a的值與新定義的b值之和賦值給c。}returnfloat(c)/b //此處的b為參數(shù)b。}為防止引用變量產(chǎn)生沖突，須為每個作用域設置一個符號表。2.4.2局部變量名的存儲布局從變量類型可以知道該變量在運行時刻需要的內(nèi)存數(shù)量。在編譯時刻，可以使用這些數(shù)量為每個名字分配一個相對地址。名字的類型和相對地址信息保存在相應的符號表條目中[12]。數(shù)據(jù)對象的存儲布局受目標機器的尋址約束的影響。比如，將整數(shù)相加的指令往往希望整數(shù)能夠?qū)R（aligned），也就是說，希望它們被放在內(nèi)存中特定的位置上，比如地址能夠被4整除的位置上。類型的寬度（width）是指該類型的一個對象所需的存儲單元的數(shù)量。一般情況下，字符類型（char）占用一個字節(jié)，整型（int）占用4個字節(jié)?？梢允褂靡粋€變量，比如offset，來跟蹤下一個可用的相對地址。在考慮第一個聲明之前，offset被設置為0。每處理一個變量x時，x被加入符號表，它的相對地址被設置為offset的當前值，隨后，x類型的寬度被加到offset上。

3設計與實現(xiàn)3.1C子語言本設計將一個用C子語言編寫的源程序翻譯成中間代碼，該Ｃ子語言描述如下：3.1.1數(shù)據(jù)類型該子語言支持兩種數(shù)據(jù)類型：int：32位有符號整型。char:8位無符號整型。只支持靜態(tài)數(shù)組。如果傳遞一個數(shù)組給函數(shù)，數(shù)組將會以指針形式傳遞，所以對于數(shù)組的任何更改，將會影響調(diào)用函數(shù)傳遞的數(shù)組。另外，如果超過了數(shù)組的長度，調(diào)用函數(shù)的棧結構將會被破壞。每個作用域中的局部變量應該在該作用域塊的開始即任何其他語句之前進行聲明，就像以前的C98標準那樣。3.1.2字面值整型，如：2343，-123字符串，如：“Hi，mynameisXiKangjie\n”字符，如：’a’,‘\n’3.1.3表達式表達式中只支持以下運算符：+，-，后綴++和--，*，/，%，<，<=，>，>=，==，||，&&布爾表達式中不支持短路代碼。在短路代碼中，布爾運算符&&、||和！被翻譯成跳轉指令。運算符本身不出現(xiàn)在代碼中，布爾表達式的值是通過代碼序列中的位置來表示的。3.1.4語句if-else語句switch語句while語句do-while語句for語句break和continue語句3.1.5函數(shù)有幾個內(nèi)建的函數(shù)用來基本的輸入輸出，它們是：-printStr(charstr[]);printStr("string");在標準輸出中打印一個以null結尾的字符串。-printChar(charc);-printInt(intn);-readStr(charbuffer[],intbufferSize);-readInt(intn)這些函數(shù)會調(diào)用標準C輸入輸出函數(shù)，如printf和scanf，另外，這些函數(shù)名被視為關鍵字，所以它們是該語言語法的一部分。可以自定義函數(shù)。但是，需要知道這里不支持函數(shù)的前向聲明：intf(intx);所以應該注意定義函數(shù)的順序，當定義了很多相互調(diào)用的函數(shù)，會使程序變得復雜。另外，本子語言盡可能合理地去實現(xiàn)作用域，局部變量的作用域和生存周期就像C語言那樣，但是沒有全局作用域，也就是說不能定義全局變量?？墒?，在函數(shù)內(nèi)部，可以自由嵌套作用域。比如：voidfoo() { intx,y; //嵌套塊，產(chǎn)生一個新的內(nèi)部作用域。 { intx;//嵌套作用域中的定義的x,它會將外部作用域中x覆蓋。 if(true) { intx;//if塊中定義的變量x,它會將外部作用域中x覆蓋。 } } }在這個子語言中有很多的限制，比如沒有類型檢測，只有少量的語義分析等等。所以在此不是創(chuàng)建一種新的語言，而是以此子語言為例編寫一個編譯器前端。3.2符號表一個符號表必須允許添加新項，查找已存在項，支持在編譯期間動態(tài)增長符號表。符號表可以實現(xiàn)為線性表和哈希表，線性表雖然容易實現(xiàn)，但表很大時性能會很差，所以本設計采用哈希表。本設計的符號表由類SymbolTable實現(xiàn)，其內(nèi)部存儲結構由哈希表實現(xiàn)（這里使用標準容器unordered_map），KEY代表詞素（lexeme），VALUE代表與該詞素對應的符號（Symbol）。符號由類Symbol實現(xiàn)。由于作用域可以嵌套，同時又要為每個作用域創(chuàng)建一個符號表，所以在類SymbolTable中，容器inner_scopes_存儲嵌套的內(nèi)部作用域，容器中的每個元素為指向內(nèi)部作用域符號表的指針。指針outer_scope_指向外部作用域符號表。在創(chuàng)建一個符號表時，要為其傳遞外部作用域符號表參數(shù)，若當前創(chuàng)建的符號表為根符號表，則默認為其傳遞參數(shù)NULL。在符號表中插入新項有兩種方式。一是插入Symbol，二是插入詞素和詞法單元標記。通過詞素獲取相應的符號，由重載運算符[]實現(xiàn)。classSymbolTable{public: SymbolTable(SymbolTable*prev=NULL):outer_scope_(prev){} ~SymbolTable(); boolInsert(Symbol*symbol); boolInsert(conststd::string&lexeme,TokenTagtag); boolIsInCurrentScope(conststd::string&lexeme)const; //重載了運算符[]，可以直接通過symboltable[key]來獲取value。Symbol*operator[](conststd::string&key); std::vector<SymbolTable*>inner_scopes_; //內(nèi)部作用域指針。 SymbolTable*outer(){returnouter_scope_;}private: SymbolTable*outer_scope_; //指向外部作用域 //用哈希map存儲符號表。 std::unordered_map<std::string,Symbol*>table_;};類Symbol表示符號表的符號，它也是類VariableSymbol和類FunctionSymbol的基類。一個符號由詞素和相應的詞法單元標記組成，一個用于關鍵字if的符號對象可以通過以下語句創(chuàng)建：Symbolsymbol_if(“if”,IF);classSymbol{public:Symbol(conststd::string&lexeme,TokenTagtag):lexeme_(lexeme),token_tag_(tag){}virtual~Symbol(){}std::stringlexeme()const{returnlexeme_;}TokenTagtoken_tag()const{returntoken_tag_;}boolIsKeyword()const;private:std::stringlexeme_; //詞素。TokenTagtoken_tag_; //詞法單元標記，表示詞法單元的屬性。};類VariableSymbol表示變量符號，用來存儲變量信息。offset_表示變量的偏移量，與變量在內(nèi)存的布局有關；width_表示變量類型的寬度；size_表示變量占用的字節(jié)數(shù)；is_array_表示變量是否是數(shù)組；data_type_表示變量的類型，DataType是一個枚舉類型，其中有三個元素，VOID_TYPE、INT_TYPE和CHAR_TYPE；kind_表示變量的種類，VariableKind是一個枚舉類型，其中有兩個元素，LOCAL表示變量是局部變量，ARGUMENT表示變量是參數(shù)。classVariableSymbol:publicSymbol{public: VariableSymbol(conststd::string&identifier):Symbol(identifier,ID){}private: unsignedintoffset_; //偏移量，即相對位置。 unsignedintwidth_; //變量類型的寬度，即占用的字節(jié)數(shù)。 unsignedintsize_; //整個符號占用的字節(jié)數(shù)。 boolis_array_; //當前符號是否是數(shù)組。 DataTypedata_type_; //數(shù)據(jù)類型，可以為int、char或void。 VariableKindkind_; //變量的種類，可以為局部變量或參數(shù)變量。};enumDataType{ INT_TYPE, CHAR_TYPE, VOID_TYPE};enumVariableKind{ LOCAL, ARGUMENT};類FunctionSymbol表示函數(shù)符號，用來存儲函數(shù)信息。包括函數(shù)標示符，返回類型及參數(shù)信息。classFunctionSymbol:publicSymbol{public: FunctionSymbol(conststd::string&identifier,DataTypereturn_type) :Symbol(identifier,ID),return_type_(return_type){} DataTypereturn_type()const{returnreturn_type_;} std::vector<Parameter>parameters_; //參數(shù)列表。private: DataTypereturn_type_; //函數(shù)的返回類型。};類Parameter保存函數(shù)的參數(shù)信息。包括參數(shù)的標示符，類型，是否是數(shù)組。classParameter{public: Parameter(DataTypetype,conststd::string&identifier,boolis_array) :type_(type),identifier_(identifier),is_array_(is_array){} DataTypetype()const{returntype_;} std::stringidentifier()const{returnidentifier_;} boolis_array()const{returnis_array_;}private: DataTypetype_; //參數(shù)的類型。 std::stringidentifier_; //參數(shù)的名字。 boolis_array_; //參數(shù)是否為數(shù)組。};每個Token有個Tag變量，表示詞素的屬性，用于做出語法分析決定。用枚舉類型TokenTag實現(xiàn)。枚舉類型TokenTag的每個元素與編程語言上下文中的符號意義無關。在詞法分析階段，符號所代表的具體意義尚未知曉，在語法分析階段，才確定符號的具體意義。比如，符號“*”叫做“ASTERISK”或者“STAR”。它可以表示不同的語言元素，比如可能是一個指針，或者乘號。所以在枚舉變量TokenTag中，把“*”叫做“ASTERISK”，直到語法分析階段才能從上下文解析出其具體意義。enumTokenTag{ END_OF_FILE=EOF, PLUS=(int)'+', MINUS=(int)'-', ASTERISK=(int)'*', FORWARD_SLASH=(int)'/', PERCENT=(int)'%', EQUAL=(int)'=', LESS=(int)'<', GREATER=(int)'>', OPEN_BRACE=(int)'{', CLOSE_BRACE=(int)'}', OPEN_PAREN=(int)'(', CLOSE_PAREN=(int)')', OPEN_BRACKET=(int)'[', CLOSE_BRACKET=(int)']', COMMA=(int)',', COLON=(int)':', SEMICOLON=(int)';', EXCLAMATION=(int)'!', LESS_OR_EQUAL=400, GREATER_OR_EQUAL=401, EQUAL_EQUAL=402, NOT_EQUAL=403, OR=404, AND=405, PLUS_PLUS=406, MINUS_MINUS=407, ID=256, NUM_LITERAL=257, STRING_LITERAL=258, //保留關鍵字。 VOID=300, INT, CHAR, IF, ELSE, FOR, DO, WHILE, SWITCH, CASE, DEFAULT, RETURN, BREAK, CONTINUE, PRINT_INT, PRINT_STR, PRINT_CHAR, READ_INT, READ_STR, GOTO};3.3詞法分析器詞法分析器的實現(xiàn)按照2.1.2節(jié)原理。狀態(tài)轉換圖用來跟蹤掃描器讀入的當前查看字符。隨著字符的讀入，從一個狀態(tài)轉換到另一個狀態(tài)。當進入一個狀態(tài)，緊接著讀入下一個字符如果有一條從當前狀態(tài)發(fā)出的邊且其上標志的字符和讀入的字符相匹配，然后轉向改變指向的下一個狀態(tài)，否則報告錯誤。詞法分析器由類Lexer實現(xiàn)，可用通過GetNextToken()獲取下一個Token，或者通過PeekNextToken()查看下一個Token。核心算法在Scan()中實現(xiàn)，忽略注釋和空白符，分析出以下類型的Token：算術運算符：+-*/%++--=關系運算符：<>>=<===!=||&&!界符：（）{}[];:,數(shù)字字面值和字符、字符串字面值：如123‘a(chǎn)’“name”標示符：如變量名、函數(shù)名等關鍵字：ifelsedowhileforreturnbreakcontinueswitchcasedefaultgotointcharvoidprintIntprintStrprintCharreadIntreadStr當遇到一個單一符號，如“+”，先假設它是多重符號，所以繼續(xù)讀取下一個字符，如果下一個字符是“+”，則返回token“++”，否則返回token“+”，并且回退一個字符。在解析注釋時，注釋可能為單行注釋“//”，也可能為塊注釋“/*…*/”，都需要做處理。classLexer{public: Lexer(conststd::string&file_name); ~Lexer(); TokenGetNextToken(SymbolTable&symbol_table); TokenPeekNextToken(SymbolTable&symbol_table); std::stringsource_file(){returnsource_file_;}private: voidGetNextChar(); //獲取下一個字符。 charPeekNextChar(); //查看下一個字符。 TokenScanToken(SymbolTable&symbol_table); std::stringsource_file_; //源程序的名字。 std::ifstreaminput_stream_; //輸入源程序保存在一個輸入文件流中。 charcurrent_character_; //當前正在分析的字符。};3.4語法分析器語法分析器從詞法分析器獲取單詞符號串，驗證其是否符合語言語法，同時報告語法錯誤。語法分析器由類Parser實現(xiàn)。對每個非終結符構造一個處理函數(shù)。語句的處理函數(shù)為ParseStatements()，遇到if則調(diào)用if處理過程，遇到for則調(diào)用for處理過程。函數(shù)ParseStatement()解析C語句，一次解析一個語句，語句包括賦值語句（為了簡化，僅支持簡單的賦值語句：var_id=expression）；if、for、while、do、switch、break、continue和空語句；IO語句如printInt。函數(shù)ParseBlock()解析塊并實現(xiàn)作用域，如果正在解析一個函數(shù)，則傳遞相應的函數(shù)符號表參數(shù)，如果是一個一般的作用域或一個條件語句，傳遞NULL，這也是默認參數(shù)。如果在表達式中遇到一個標示符，它可能是一個變量也可能是一個函數(shù)，先通過函數(shù)ParseId()將其解析為一個變量，如果不能成功則通過函數(shù)ParseFunctionCall()將其解析為函數(shù)調(diào)用。函數(shù)NextToken()從詞法分析器獲得下一個token；函數(shù)Match()匹配token并獲取下一個token，如果有錯誤，則生成錯誤信息。語法分析器在解析的過程中，通過函數(shù)Emit()生成四元式。變量offset_記錄局部變量的相對偏移量；變量temp_counter_和label_counter_記錄臨時變量和標記的計數(shù)；變量current_token_記錄當前正在解析的token。classParser{public: Parser(Lexer*lexer,IntermediateInstrsList*interm_list,std::vector<Message>*errors_list); ~Parser(); voidParse();private: voidNextToken(); boolMatchIf(TokenTagtag); voidMatch(TokenTagtag); voidMatch(TokenTagtags[],intn,conststd::string&msg); voidEmit(IntermediateInstr*instr); voidEmitLabel(conststd::string&label); voidEmitLabel(LabelOperand*label); unsignedintGetStackSize(); LabelOperand*NewLabel(); VariableOperand*NewTemp(DataTypetype=INT_TYPE,boolis_array=false,unsignedintelems=1); voidParseFunctions(); voidParseBlock(FunctionSymbol*func_symbol=NULL); voidParseDeclarations(); voidParseInitialization(conststd::string&var_id); voidParseStatements(); voidParseStatement(); voidParseAssignment(Operand*lhs_operand=NULL); Operand*ParseBool(); Operand*ParseAnd(); Operand*ParseEquality(); Operand*ParseRel(); Operand*ParseExpr(); Operand*ParseTerm(); Operand*ParseFactor(); Operand*ParseId(boolallow_func); Operand*ParseFunctionCall(conststd::string&func_id); std::vector<Operand*>*ParseArgumentsList();private: unsignedinttemp_counter_; //臨時變量計數(shù)。 unsignedintoffset_; //變量相對地址。 unsignedintlabel_counter_; //標號計數(shù)。 Lexer*lexer_; //指向詞法分析器。 std::stack<LabelOperand*>break_stack_; //用于break。 std::stack<LabelOperand*>continue_stack_; //用于continue。 SymbolTable*current_scope_table_; //當前作用域符號表。 SymbolTable*root_symbol_table_; //根符號表 FunctionSymbol*current_function_; //指向當前函數(shù)。 Tokencurrent_token_; //當前詞法單元。};3.5中間代碼生成器中間代碼的四元式表示由類IntermediateInstr實現(xiàn)，該類包含四個數(shù)據(jù)成員，operation_表示運算符，operand1_、operand2_、operand3_表示兩個操作數(shù)和結果。IntermediateOp是一個枚舉類型。針對常見結構，按照2.3.2節(jié)中的原理進行翻譯。classIntermediateInstr{public: IntermediateInstr(IntermediateOpop,Operand*operand1=NULL, Operand*operand2=NULL,Operand*operand3=NULL) :operation_(op),operand1_(operand1),operand2_(operand2),operand3_(operand3){} IntermediateOpoperation(){returnoperation_;} Operand*operand1(){returnoperand1_;} Operand*operand2(){returnoperand2_;} Operand*operand3(){returnoperand3_;} std::stringToString();private: IntermediateOpoperation_; //操作符。 Operand*operand1_; //操作數(shù)。 Operand*operand2_; //操作數(shù)。 Operand*operand3_; //操作數(shù)。};枚舉類型IntermediateOP存儲跟四元式中運算符相關的信息。enumIntermediateOp{ ASSIGN_OP=(int)'=', ADD_OP=(int)'+', SUBTRACT_OP=(int)'-', MULTIPLY_OP=(int)'*', DIVIDE_OP=(int)'/', NOT_OP=(int)'!', DIV_REMINDER_OP=(int)'%', LESS_THAN_OP=(int)'<', GREATER_THAN_OP=(int)'>', LESS_OR_EQUAL_OP=400, GREATER_OR_EQUAL_OP=401, EQUAL_EQUAL_OP=402, NOT_EQUAL_OP=403, OR_OP=404, AND_OP=405, IF_OP, GOTO_OP, LABEL_OP, INC_STACK_PTR_OP, DEC_STACK_PTR_OP, PARAM_OP, ENTER_OP, CALL_OP, RETURN_OP, PRINT_INT_OP, PRINT_STR_OP, PRINT_CHAR_OP, READ_INT_OP, READ_STR_OP};3.6GUI本設計實現(xiàn)的圖形界面包含菜單欄、標簽欄及編輯框。菜單欄包含“File”、“Edit”、“View”、“Tool”、“About”。如圖3.1所示。標簽欄支持多標簽，當前編輯的標簽上方會有黃色線條顯示。編輯框支持顯示行號，可在視圖“View”菜單中選中“LineNumberMargin”進行顯示。圖3.1菜單欄菜單“File”包含的菜單項有“New”、“Open”、“Close”、“CloseAll”、“Save”、“SaveAll”、“SaveAs”、“Exit”。如果3.2所示?！癗ew”：新建文件；“Open”：打開文件；“Close”：關閉文件；“CloseAll”：關閉所有當前打開的文件；“Save”：保存文件；“SaveAll”：保存所有當前打開的文件；“SaveAs”：將當前文件另存為；“Exit”：退出Front_end。圖3.2菜單File菜單“Edit”包含的菜單項有“Undo”、“Redo”、“Cut”、“Copy”、“Paste”、“Delete”、“SelectAll”、“Find…”、“FindNext”、“Replace”。如圖3.3所示“Undo”：撤銷；“Redo”：恢復；“Cut”：剪切；“Copy”：復制；“Paste”：粘貼；“Delete”：刪除當前所選區(qū)域；“SelectAll”：全選；“Find…”：點擊顯示查找對話框，如圖3.4所示；查找的時候，可以選擇匹配整個單詞、匹配大小寫、匹配正則表達式、循環(huán)匹配，查找方向可為上或下?！癋indNext”：查找下一個；“Replace”：點擊顯示替換對話框，如圖3.5所示。替換時可以選擇替換當前匹配的單詞，也可以選擇替換所有匹配的單詞。匹配時要進行查找，此處查找功能與“Find…”相同，同樣可以選擇匹配整個單詞、匹配大小寫、匹配正則表達式、循環(huán)匹配，查找方向可為上或下。圖3.3菜單Edit圖3.4查找對話框圖3.5替換對話框菜單“View”包含的菜單項有“LineNumberMargin”、“Zoomin”、“Zoomout”。如圖3.6所示。“LineNumberMargin實現(xiàn)顯示行號功能”；“Zoomin”和“Zoomout”實現(xiàn)放大縮小功能。圖3.6菜單View菜單“Tool”包含的菜單項有“Translate”。如圖3.7所示。點擊“Translate”將源代碼轉換成中間代碼。圖3.7菜單Tool點擊菜單“About”，會彈出關于對話框。如圖3.8所示。圖3.8關于對話框本設計的圖形界面通過類FrontEnd實現(xiàn)。classFrontEnd:publicWindow{public: FrontEnd():Window(),_mainWindowStatus(0),_pMainSplitter(NULL), _hTabPopupMenu(NULL),_pEditView(NULL),_pDocTab(NULL){}; voidinit(HINSTANCE,HWND,constchar*); virtual~FrontEnd(); voidkillAllChildren(); virtualvoiddestroy(); staticconstchar*getClassName(); voidsetTitle(constchar*title)const; voidsetTitleWith(constchar*filePath); boolisDlgMsg(MSG*msg)const; booldoOpen(constchar*fileName);private: staticconstchar_className[32]; Window*_pMainWindow; unsignedchar_mainWindowStatus; DocTabView_mainDocTab; DocTabView_subDocTab; DocTabView*_pDocTab; ScintillaEditView_mainEditView; ScintillaEditView_subEditView; ScintillaEditView*_pEditView; SplitterContainer*_pMainSplitter; SplitterContainer_subSplitter; HMENU_hTabPopupMenu; FindReplaceDlg_findReplaceDlg; AboutDlg_aboutDlg; staticLRESULTCALLBACKFrontEnd_Proc(HWNDhwnd,UINTMessage,WPARAMwParam,LPARAMlParam); LRESULTrunProc(HWNDhwnd,UINTMessage,WPARAMwParam,LPARAMlParam); voidnotify(SCNotification*notification); voidcommand(intid); voidfileNew(); voidfileOpen(); boolfileClose(); boolfileCloseAll(); voidhideCurrentView(); intdoSaveOrNot(constchar*fn); intdoReloadOrNot(constchar*fn); intdoCloseOrNot(constchar*fn); boolfileSave(); boolfileSaveAll(); boolfileSaveAs(); voidfilePrint(boolshowDialog); booldoSave(constchar*filename); voidenableMenu(intcmdID,booldoEnable); voidenableCommand(intcmdID,booldoEnable,intwhich); voidcheckClipboard(); voidcheckDocState(); voidcheckUndoState(); voiddropFiles(HDROPhdrop); voidcheckModifiedDocument(); voidreload(constchar*fileName); voidgetMainClientRect(RECT&rc)const; voidswitchEditViewTo(intgid); voiddynamicCheckMenuAndTB()const; intgetCurrentView()const; DocTabView*getNonCurrentDocTab(); ScintillaEditView*getNonCurrentEditView(); voidsynchronise(); voidchangeCheckedItemFromTo(intid2Uncheck,intid2Check)const; voidcheckMenuItem(intitemID,boolwillBeChecked)const;};類FrontEnd對創(chuàng)建一個窗口的基本過程進行了封裝，如初始化窗口類結構，注冊窗口類，顯示窗口并進入消息循環(huán)。并且根據(jù)設計要求添加了菜單欄，標簽欄和編輯框。還添加了其他一些消息處理過程，如打開文件、保存文件等。對于菜單欄、標簽欄和編輯框的使用，與Windows標準相一致，也就是說會使用如記事本之類的編輯器，就會使用該圖形界面?？旖萱I的設置，也是按照Windows的常用設置，即得即用，不會與自己平常的Windows操作習慣產(chǎn)生沖突。在實現(xiàn)本設計的圖形界面時，充分考慮各種可能出現(xiàn)的使用情況，以保證其不會崩潰。例如當打開一個文件時，若該文件已經(jīng)打開，則直接跳轉到相應的標簽欄，而不是再重復打開一個標簽。當打開的標簽數(shù)量過多以致標簽超過窗口寬度時，標簽欄右側會出現(xiàn)調(diào)控控件。

4測試（1）打開源程序點擊菜單“File”中“Open”，顯示打開對話框，選擇要打開的源程序，如圖4.1所示。此處只支持打開C源程序文件。打開文件fact-rec.c后如圖4.2所示。圖4.1打開源程序圖4.2fact-rec.c源程序（2）翻譯成中間代碼fact-rec.c由C子語言編寫，用戶輸入整數(shù)n，輸出結果為n!。點擊菜單“Tool”中的“Translate”，運行結果如圖4.3所示：圖4.3運行結果（3）現(xiàn)在更改源程序，去掉第11行的“；”號，重新翻譯以顯示錯誤信息。錯誤信息如圖4.4所示。圖4.4錯誤信息（4）在fact-rect.c中查找有哪些輸出語句?！癈trl+F”打開查找對話框，輸入print，選擇“MatchCase”和“Wraparound”，點擊“FindNext”進行查找，結果如圖4.5所示。圖4.4查找print（5）支持基本的編輯操作，如“復制”、“粘貼”、“剪切”、“全選”、“刪除”、“撤銷”和“恢復”。選中要刪除的字符串，點擊“Edit”菜單中的“Delete”或右鍵單擊編輯框，在彈出的上下文菜單中選擇“Delete”或按快捷鍵“Del”即可刪除?，F(xiàn)刪除第16行的“printChar('\n');”，刪除方法如圖4.5所示，刪除結果如圖4.6所示。圖4.5刪除方法圖4.6刪除結果（6）保存生成的中間代碼。右鍵單擊選項卡，選擇“Save”則在fact-rec.c所在目錄下生成er文件，選擇“SaveAs…”則打開“另存為”對話框，可以設計要保存的位置及文件名。如圖4.7所示。圖4.7保存文件

總結本設計實現(xiàn)的編譯器前端，擁有友好的圖形界面，可將C子語言編寫的源程序翻譯成中間代碼（四元式），若源程序有錯誤，可以指出錯誤所在的行列。該設計雖然圓滿完成了給定的任務，但仍有以下兩個問題需要改進：（1）中間代碼的正確性對于簡單源程序，翻譯成的中間代碼可以馬上看出其是否正確，但是對于復雜的程序，仍由人工驗證其代碼的正確性就有點低效了?？蛇x的解決方案是繼續(xù)完成編譯器的最后一個階段，將中間代碼生成匯編代碼，然后由匯編器將匯編代碼生成可執(zhí)行程序，通過執(zhí)行程序的運行結果驗證中間代碼的正確性。（2）垃圾回收不能被引用的數(shù)據(jù)通常稱為垃圾，如果實現(xiàn)了自動垃圾回收機制，就可以減輕手工存儲管理的負擔。

參考文獻[1][美]KENNETHC.LOUDEN著,馮博琴、馮嵐等譯.編譯原理及實踐[M]——計算機科學叢書.北京:機械工業(yè)出版社,2005.3.[2]金成植.編譯程序構造原理和實現(xiàn)技術[M].北京:高等教育出版社,2000.7.[3]陳火旺等.程序設計語言編譯原理（第3版）[M].北京:國防工業(yè)出版社,2000.1.[4]王雷、劉志成、周晶.編譯原理課程設計[M].北京:機械工業(yè)出版社,2005.3.[5]呂映芝、張素琴、蔣維杜.編譯原理[M].北京:清華大學出版社,2004.2.[6]范文慶、周彬彬、安靖.深入剖析WindowsAPI開發(fā)詳解[M].北京：人民郵電出版社，2011.3.[7][美]AlfredV、MonicaS等著,趙建華、鄭滔等譯.編譯原理（第2版）[M].北京:機械工業(yè)出版社,2012.12.[8][美]AndrewW.Appel著,趙克佳、