編譯原理過程

(2016.12)割片擊X建大拿希堂修浣(2016.12)割片擊X建大拿希堂修浣,SouthwestJiaotongUniversityHopeCollege編譯原理過程及分析姓名：王偉學號：20142217編譯原理過程及分析編譯器最基本的功能就是把高級語言(例如C/Fortran)編寫的代碼轉化為機器指令(就是01串)，從這個角度來說它本質上是個轉換過程。經典的編譯過程主要包括：1、 詞法分析(LexicalAnalysis)詞法分析就是從輸入代碼中識別出各種記號(token)，例如對于C語言我們就需要知道if,else等是語言的關鍵字，myvar是個標識，而123myvar不能被識別為一個標識。負責實現詞法分析的模塊有時也稱為scanner。詞法分析的關鍵當然是語言定義的規(guī)則了，比如哪些是關鍵詞，哪些是合法的標識等，這些規(guī)則一般是通過正則表達式(RE，RegularExpression)來給出，運行時從輸入緩沖區(qū)中讀入一部分，然后看和哪個RE匹配就知道它到底是個什么token。下一個問題就是正則表達式的匹配過程如何實現，經典理論對此都會提到有限狀態(tài)機(FSM,FiniteStateMachine)o關于FSM在可行性計算里一般都會有不少篇幅分析，在編譯里談到的FSM和RE主要是如何從輸入的構成出對應的FSM。構造的過程一般分為三個步驟：根據Thompson構造法從RE構造出對應的非確定性有限狀態(tài)機(NFA,Non-deterministicAutomata)；經過不斷計算epison-閉包(也成為可到達集)構造出確定性有限狀態(tài)機(DFA,deterministicAutomata)；將DFA最小化，方法是增量式地合并不可區(qū)分(對于同一輸入的下一個狀態(tài)都一樣)的兩個狀態(tài)。2、 語法分析語法分析的輸入是一連串的token(詞法分析的輸出)，根據語言的語法規(guī)則不斷解析最后得到一棵抽象語法樹(AST,AbstractSyntaxTree)，負責語法分析模塊通常也被叫做Parser。在詞法分析中，我們經常使用正則表達式來表示語言所接受的token的規(guī)則，類似的，在語法分析中，我們使用文法(Grammar)來表示語言的語法規(guī)則，這也早期計算機語言設計中的研究熱點(同樣也是大學里學習編譯時最容易讓人頭暈的東西)。編譯里常說的文法指的是一種上下文無關文法(Context-FreeGrammar)，簡單地說文法里包含終結符(terminal，就是26個字符、數字等等)、非終結符(nonterminal，實際是一種抽象)和產生式(production)。上下文無關文法要求每個產生式的左邊必須恰好是一個非終結符，而右邊是0個或多個終結符與非終結符的組合，最后整個文法還必須有一個起始符(某個終結符)。文法里還有些很重要的基本概念，例如推導(derivation)、歸約(reduction)、二義性(ambiguity)、最左推導等等。文法中最重要的基本概念是FIRST集和FOLLOW集的構造。根據這兩個集合就可以很容易構造出一個預測分析表，每個行的名字是一個非終結符，每個列的名字是一個終結符，如果每個表格內沒有兩個以上的項，那么說明是一個LL(1)文法(Left-to-rightparse,Leftmost-derivation,1-symbollookhead)，簡單地說就是向右邊看一個符號就能確定下一步動作。當原文法不是LL(1)文法時，可以嘗試通過消除左遞歸(EliminateLeftRecursion)和提取左因子(LeftFactoring)對原文法進行變形得到等價的LL(1)文法。第二種文法就是LR(k)文法(Left-to-rightparse,Rightmostderivation,k-tokenlookhead)o這種文法的解釋過程一般通過棧輔助實現，中間主要有兩種動作：shift(就是將當前輸入入棧)和reduce(選擇產生式并從棧中彈出符號執(zhí)行歸約操作)。LR(0)的構成過程就是從起始符所在的產生式開始構造item，然后對每個item針對每個可能的input構造它的出邊(同樣還是一個item)，最終所有的item形成一個有限狀態(tài)機。接下來構造有限狀態(tài)機，對于每個狀態(tài)，如果出邊是一個終結符，在對應表格記入shift操作，如果是非終結符則記入goto操作。如果S->x.這種item集，那么對每個終結符r，都記入(S,r)位置處為shift操作。第三種是SLR文法。與LR(0)非常相似，區(qū)別在于生成分析表格時，對于S->x.這種item集，僅僅對于r輸入FOLLOW(S)才在(S,r)位置處記入shift操作。最后一種是LALR(1)文法。相對于LR(0)而言引入了活前綴，構造思路仍與LR(0)類似，但是構造出來的預測分析表更大。綜合起來，各文法表述能力：LL(0)<LR(0)<SLR<LALR(1)<LR(1)<LR(k)，LL(1)<LR(1)遞歸下降分析算法：遞歸作為一種強有力的數學和算法描述工具在Pascal語言中被廣泛使用。一個函數、過程、概念或數學結構，如果在其定義或說明內部又直接或間接地出現有定義本身的引用(在過程或自定義函數中，又包含自己調用自己)，則稱它們是遞歸的或者是遞歸定義的。一個遞歸算法僅使用少量的程序編碼就可描述出解題所需要的多次重復計算而不需要設計循環(huán)結構。使用遞歸求解問題，通?？梢詫⒁粋€比較大的問題層層轉化為一個與原問題相類似的規(guī)模較小的問題來求解，進而最終導致原問題的解決。例如：n!的定義，我們知道，在數學中n!一般定義為：~1 若n=0n!=-nX(n-1)!若n>0在n>0的公式中，又包含了(n-1)!，這就是遞歸定義。利用遞歸方法，可以用有限的語句來定義對象的無限集合。但在遞歸定義中，應該至少有一條是非遞歸的，即初始定義。如上面例子中的第一條，否則就變成了循環(huán)定義，產生邏輯性錯誤。n!的遞歸定義的程序：programfindn;varn:integer;t:longint;procedurefid(n:integer);beginifn=0thent:=1elsebeginfind(n-1);t:二t*nend;end;beginwrite(‘n=’);readln(n);find(n);writeln(n,‘！=’，t)end.遞歸調用(n進棧)達到結束條件時(n=0,t賦初值1)就停止調用開始返回，再把保存的值取出(n出棧)，使n恢復原來的值，并計算t，返回主程序，輸出結果t。follow集合算法：計算所有非終結符號A的follow(A)集合時，不斷應用下面的規(guī)則，直到再沒有新的終結符號可以被加入到任意的follow集合中為止。1、 將$放到follow(S)中，其中S是開始符號，而$是輸入右端的結束標記。2、 如果存在一個產生式A-aBP，那么first(P)中除￡之外的所有符號都在follow(B)中。3、 如果存在一個產生式A-aB，或存在產生式A-aBP且first(P)包含￡，那么follow(A)中的所有符號都在follow(B)中。舉個例子來說明下，假設有如下文法：E—TE'E'-+TE'|￡T—FT'T'—*FT'|￡F-(E)|id對于每個非終結符號，我們都可以求出其follow集：根據(1)，首先將$加入到follow(E)中，即follow(E)={$}，由⑤可知，)也應該在follow(E)中，即follow(E)={$，)}；對于E'，根據規(guī)則(3)以及產生式①，應該將follow(E)加入到follow(E‘)中，即follow(E')={$，)}；對于T，根據規(guī)則(2)以及產生式①，應該將first(E')加入到follow(T)中，即follow(T)={+}，根據規(guī)則(3)，由于first(E')包含￡，所以應該將follow(E')加入到follow(T)中，即follow(T)={+，$，)}；對于T'，根據規(guī)則(3)以及產生式③，應該將follow(T)加入到follow(T‘)中，即follow(T')={+，$，)}；對于F，根據規(guī)則(2)以及產生式③，應該將first(T')加入到follow(F)中，即follow(F)={*}，根據規(guī)則(3)，由于first(T')包含￡，所以應該將follow(T')加入到follow(F)中，即follow(F)={*，+，$，)}；3、語義分析(SematicAnalysis)語義分析包括一些經典的問題。(1)類型檢查(TypeChecking)，例如在語法樹上a+b看起來是沒問題的，因為a和b都是合法的變量名，并且語法中支持變量間+這種操作。但是可能a是一個字符串，而b是一個浮點數，這兩者之間的+操作就不符合語義規(guī)范了，這種問題在這個階段都會被找出來。(2)符號管理，最經典的問題就是如何管理變量(變量的名字，類型，變量的作用域(scope)等)，在分析代碼時，符號管理肯定是被頻繁的搜索，因此它通常會使用hash來組織。4、中間代碼(IR,intermediateRepresentation)生成IR是非常非常重要的，它被引入的初衷是提高編譯器開發(fā)的效率。IR是編譯過程的一個匯聚點，在IR之前我們通常都認為是編譯的前端，而IR之后是編譯的后端，這樣當編譯器需要多支持一種高級語言時主要工作就是提供一個前端，而當需要移植到一種新的平臺上時主要工作就是提供對應的后端。關于IR的表示典型的有三地址碼。IR生成的過程就是將一棵抽象語法樹(這是編譯器前端對源代碼的理解和抽象)變成一串IR定義的代碼(IR指令種類簡單，這便于優(yōu)化)。這個轉換過程都是比較固定的套路，例如if-else，while/for等基本結構如何轉都是一個固定的套路。5、 編譯優(yōu)化這一部分是現代編譯器最核心所在，主要有兩類，一類是通用的優(yōu)化手段，比如死代碼刪除、循環(huán)不變量外提、強度削弱等，另一類就是體系結構相關的，說白了就是某種體系結構針對某類應用提供了特殊指令，例如intel的MMX，SSE2等等。為支持優(yōu)化工作的開展，我們首先需要能夠比較方便的描述代碼。最基本的當然是一條指令，但是這個太細微，于是往上抽象出基本塊(BasicBlock)，這個基本上是所有優(yōu)化開展必備的工作，然后多個基本塊還可以構成一個超級塊(region)。此外，經典的方法還包括控制流分析和數據流分析，這里常用的包括d-u鏈等。最后一個經典的topic就是寄存器分配。6、 目標代碼生成這里直接和具體平臺相關，這里的平臺同時包括軟件和硬件，例如哪種目標文件格式(ELF,PE)，哪種平臺(指令集)。不過現在編譯器一般生成的是字符形式的匯編文件，所以前面一個問題基本不大，主要影響在后者。編譯程序的最后一項任務是生成目標代碼。目標代碼生成器把中間代碼變換成目標代碼，通常有3種變換形式：1、 立即執(zhí)行的機器語言代碼。這種方式