1.2 TheStructure of a Compiler
compiler的兩個重要組成部分：analysis（分析） and synthesis（合成）
- analysis：將source program分成一些組成部分，給它們加上一些語法分析結(jié)構(gòu)（grammatical structure），然后用這些結(jié)構(gòu)去創(chuàng)造出一些源程序的中間表達(dá)方式。如果分析時發(fā)現(xiàn)源程序在句法組成(syntactically formed)或語義(semanitically)上有錯誤，那么它就會提供一些情報(bào)信息，讓用戶能夠采取正確的行動。在分析階段，也會搜集源程序的信息并將它們存儲進(jìn)一個叫做symbol table的數(shù)據(jù)結(jié)構(gòu)中，與中間表示一起傳遞到合成部分。
- synthesis：用中間表達(dá)和symbol table中的信息構(gòu)建希望的目標(biāo)程序。
analysis part通常被稱為compiler的前端，synthesis part通常被成為compiler的后端。
在實(shí)際中，幾個階段可能會被組織在一起，兩個被組織的階段之間的表達(dá)方式并不需要被構(gòu)造地非常精確。symbol table被所有階段所共用。有的編譯器在前端和后端之間有機(jī)器依賴的優(yōu)化階段(optimization phases)，這個優(yōu)化階段的目的執(zhí)行中間表達(dá)的轉(zhuǎn)換，使得后端可以創(chuàng)造出更好的目標(biāo)程序。
1.2.1 Lexical Analysis(詞法分析)：
compiler的第一個階段，被稱為lexical analysis或者scanning。
詞法分析器讀取組成源程序的字符流(stream of characters)并將這些字符分組為有意義的序列，lexemes。對每個lexeme，詞法分析器會產(chǎn)生這樣一種形式的標(biāo)記：
<token-name,attribute-value> 以這個形式傳遞給下一個階段，syntax analysis（語法分析）
token name是一個抽象符號在syntax analysis階段被使用,attribute value在這個symbol table中的這個標(biāo)記的入口。來自symbol table入口的信息對semantic analysis和code generation來說是需要的。
比如源程序有這樣一句賦值語句：
position = initial + rate * 60 （1.1）
- position是一個lexeme被映射到標(biāo)記<id , 1>，其中id是一個代表標(biāo)識符(identifier)的抽象符號，1指向symbol-table中position的入口。一個identifier的symbol-table entry擁有這個identifier的信息，包括它的名字和類型。
- 賦值符號 = 是一個lexeme，映射到標(biāo)記<=>。因?yàn)檫@個標(biāo)記不需要attribute-value，所以我們忽略了第二個組成部分。我們可以用任何抽象符號比如assign來作為token-name，但是為了計(jì)數(shù)的方便，我們使用這個lexeme本身作為抽象符號的名字。
- 為什么它不需要attribute-value？
- initial是一個lexeme映射到標(biāo)記<id，2>，2指向initial的symbol-table entry。
- 是一個lexeme映射到標(biāo)記< + >
- rate是一個lexeme映射到標(biāo)記<id ，3>，3指向rate的symbol-table entry。
- 是一個lexeme映射到標(biāo)記<>
- 60是一個lexeme映射到<60>
lexemes之間的空格會被lexical analyzer丟棄。
這是上述賦值語句經(jīng)過了lexical analysis后的表示：
<id,1> <=> <id,2> <+> <id,3> <*> <60> （1.2）
在這個表達(dá)式中，token names：=，+ 和 * 分別是賦值、加法、乘法運(yùn)算符的抽象標(biāo)識。
Translation of an assignment statement Fig.1
1.2.2 Syntax Analysis（語法分析）
compiler的第二個階段是syntax或parsing，語法分析器使用lexical analyzer創(chuàng)造的標(biāo)記的第一個部分來生成一個樹狀的中間表達(dá)，用來描述這個標(biāo)記流在語法上的結(jié)構(gòu)。一種典型的表示方法就是syntax tree，它的內(nèi)部節(jié)點(diǎn)表示一個操作，而節(jié)點(diǎn)的孩子表示這個操作的參數(shù)。（參見上圖Fig.1）
compiler后面的階段會用到這個語法結(jié)構(gòu)去幫助分析源程序和產(chǎn)生目標(biāo)程序。
1.2.3 Semantic Analysis（語義分析）
語義分析使用了syntax tree和symbol table里面的信息，根據(jù)語言的定義，來檢查源程序的連貫性。
語義分析的一個重要部分是類型檢測（type checking），compiler會檢查每個操作符是否有匹配的操作數(shù)。比如，許多編程語言的定義要求一個數(shù)組的數(shù)據(jù)必須是integer，當(dāng)數(shù)組中出現(xiàn)了浮點(diǎn)數(shù)的時候，compiler就必須報(bào)告這個錯誤。
語言規(guī)范也許會允許一些強(qiáng)制的類型轉(zhuǎn)換，這被叫做coercions。比如，一個二進(jìn)制運(yùn)算符被用在一對整數(shù)或一對浮點(diǎn)數(shù)之間。如果運(yùn)算符被用在一個整數(shù)和一個浮點(diǎn)數(shù)之間時，compiler也許會轉(zhuǎn)換或強(qiáng)制轉(zhuǎn)換使整數(shù)變?yōu)楦↑c(diǎn)數(shù)。
如圖Fig.1中的rate被看作一個浮點(diǎn)數(shù)，而就被應(yīng)用在一個浮點(diǎn)數(shù)rate和整數(shù)60之間，此時發(fā)現(xiàn)semantic analyzer有一個額外的節(jié)點(diǎn)inttofloat*，這明確表示將它的整數(shù)參數(shù)轉(zhuǎn)換為了浮點(diǎn)數(shù)參數(shù)。
1.2.4 Intermediate Code Generation（中間代碼生成）
在將源程序轉(zhuǎn)化為目標(biāo)程序的過程中，compiler也許會構(gòu)造出一個或多個具有多種多樣形式的中間表達(dá)方式，它們通常在syntax和semantic analysis中使用。
對源程序執(zhí)行完語法和語義分析后，許多compiler會生成一個低級的或機(jī)器有好的（machine-like）中間表達(dá)，我們可以把這看作是代表了一個抽象機(jī)器的程序。這個中間表達(dá)應(yīng)該有兩個重要性質(zhì)：它應(yīng)該是易于產(chǎn)生的而且應(yīng)該易于被轉(zhuǎn)化為目標(biāo)機(jī)器。
在Chapter 6中，我們會考慮一種叫做three-address code（三地址代碼）的中間表達(dá)形式，它由一系列，一個指令帶著三個操作數(shù)的裝配式指令（assembly-like instructions）組成。每個操作數(shù)都可以表現(xiàn)得像一個寄存器一樣。Fig.1的中間代碼的輸出由三地址代碼序列組成。
t1 = inttofloat(60)
t2 = id3 * tq
t3 = id2 + t2
id1 = t3 （1.3）
幾個值得注意的地方：
- 每個三地址分配指令的右側(cè)做多只能有一個操作符，因此，這些指令確定了執(zhí)行操作的順序；乘法在加法之前。
- compiler必須生成一個臨時的名字去代表被一條三地址指令計(jì)算出來的值。
- 一些三地址指令，比如（1.3）所示的第一條和最后一條指令，擁有的操作數(shù)小于三個。
1.2.5 Code Optimization（代碼優(yōu)化）
機(jī)器依賴(machine-independent)的代碼優(yōu)化階段嘗試改善中間代碼使得得到的目標(biāo)代碼的結(jié)果更好。通常來說這意味著更快，但是還有被期望的其他目的，比如更短的代碼，或者目標(biāo)代碼消耗更少的能源。例如，一個簡單的算法使用來自語義分析器的樹表示中的每個操作符的指令來生成中間代碼（1.3）。
一個簡單的中間代碼生成算法緊跟著一個代碼優(yōu)化，是一個產(chǎn)生良好目標(biāo)代碼的合理方法。優(yōu)化器可以推導(dǎo)出，60從整數(shù)到浮點(diǎn)數(shù)的轉(zhuǎn)換可以在編譯時一次性完成，所以可以通過將整數(shù)60替換為浮點(diǎn)數(shù)60.0來消除操作inttofloat。更甚者，t3可以只使用一次來將其值傳輸?shù)絠d1，因此優(yōu)化器可以將(1.3)轉(zhuǎn)換為較短的序列
t1 = id3 * 60.0
id1 = id2 + t1 (1.4)
不同編譯器執(zhí)行的代碼優(yōu)化量差別很大。在那些做得最多的，所謂“優(yōu)化編譯器”中，這一階段花費(fèi)了大量的時間。有一些簡單的優(yōu)化方法可以顯著改善運(yùn)行速度，而不會過多的減慢編譯速度。
1.2.6 Code Generation（代碼生成）
代碼生成器將源程序的中間表示作為輸入，并將其映射到目標(biāo)語言。如果目標(biāo)語言是機(jī)器代碼，程序中所用到的每一個變量在寄存器或內(nèi)存中的位置將會被選擇。然后，中間指令會被翻譯為一系列的機(jī)器指令來執(zhí)行相同的任務(wù)。代碼生成的一個重要方面是明智地分配寄存器來保存變量。
比如，使用寄存器R1和R2，（1.4）中的中間代碼或許會被翻譯為如下的機(jī)器代碼
LDF R2, id3
MULF R3, R2, #60.0
LDF R1, id2 (1.5)
ADDF R1, R1, R2
STF id1, R1
每個指令的第一個操作數(shù)指定了一個目的地。每個指令中的F告訴我們它處理的是浮點(diǎn)數(shù)。（1.5）中的代碼將地址id3中的內(nèi)容加載到寄存器R2中，然后將它與浮點(diǎn)常量60.0相乘。#代表60.0被作為一個中間常量。第三條指令將id2移動到寄存器R1中，第四條指令將它與之前計(jì)算出來存儲在R2中的值相加。最終R1中的值被放入地址id1中，代碼正確地完成了賦值語句（1.1）。
這個關(guān)于代碼生成的討論忽略了源程序中標(biāo)識符的存儲分配這一重要問題。我們將在Chapter 7中看到，運(yùn)行時存儲的組織取決于要編譯的語言。存儲分配決策是在中間代碼生成或代碼生成期間完成的。
1.2.7 Symbol-Table Management
compiler的一個基本功能是記錄源程序中使用的變量名，并收集有關(guān)每個名稱的各種屬性的信息。這些屬性可以提供有關(guān)為名稱分配的存儲的信息，它的類型、它的作用域（在程序中可以使用它的值），對于過程名，例如它的參數(shù)的數(shù)據(jù)和類型，傳遞每個參數(shù)的方法（例如，通過值或引用），和返回的類型。
symbol table是一個包含了每個變量名稱的記錄，并帶有名稱屬性的字段的數(shù)據(jù)結(jié)構(gòu)。這個數(shù)據(jù)結(jié)構(gòu)應(yīng)該被設(shè)計(jì)來允許編譯器快速找到每個名稱的記錄，并快速地存儲或檢索該記錄中的數(shù)據(jù)。
1.2.8 The Grouping of Phases into Passes
階段的討論涉及編譯器的邏輯組織。在實(shí)現(xiàn)中，來自幾個階段地活動可以組合在一起成為讀取輸入文件和寫入輸入文件的pass。比如，在lexical analysis，syntactic analysis，semantic analysis和intermediate code generation這些前端階段或許會被組合進(jìn)一個pass。Code optimization或許會變成一個可選的pass。然后可能會有一個后端過程，包括為特定目標(biāo)機(jī)器生成代碼。
一些編譯器集合是圍繞著精心表示的中間表示創(chuàng)建的，這些表示允許特定語言的前端與特定目標(biāo)機(jī)器的后端交互。使用這些集合，我們可以通過將目標(biāo)計(jì)算機(jī)的不同前端與后端結(jié)合起來，為一臺目標(biāo)計(jì)算機(jī)生成針對不同源語言的編譯器。
1.2.9 Compiler-Construction Tools
- Parser generators：從編譯語言的語法自動生成語法分析器的解析器生成器。
- Scanner generator：從一種語言符號的常規(guī)表達(dá)式描述生成詞法分析器的掃描生成器。
- Syntax-directed translation：生成用于遍歷解析樹和生成中間代碼的例程集合。
- Code-generator generators：從用于將中間語言的每個操作翻譯成用于目標(biāo)機(jī)器的機(jī)器語言的規(guī)則集合生成代碼生成器。
- Data-flow analysis engines：有助于聚集有關(guān)值如何從程序的一個部分傳遞到另一個部分的信息。Data-flow analysis是code optimization的一個關(guān)鍵部分。
- Compiler-construction toolkits：提供了一組集成的例程，用于構(gòu)造編譯器的各個階段。
