前從1999年在TurboC2.0下第一次用C語(yǔ)言寫(xiě)出 行當(dāng)里也混了近15年。相信所有上機(jī)寫(xiě)過(guò) 盤(pán)敲進(jìn)去的不過(guò)是一個(gè)個(gè)普通的英文字符，C編譯器是如何神奇地發(fā)現(xiàn)哪一行出現(xiàn)了什么原理》課程后就已脫穎而出，比如大牛Linus和ChrisLattner，前者大學(xué)時(shí)就開(kāi)啟了他的Apple公司已經(jīng)不動(dòng)聲色地把公司的Object-C編譯器從GCC轉(zhuǎn)成了LLVM和Clang，各位 背后站著的仍然是CharisLattner和LLVM。私下偷偷復(fù)印那本后來(lái)被稱為曠世奇書(shū)的《萊昂Unix源代碼分析》。其實(shí)，真正曠世之作的和Linux源代碼就毫無(wú)保留地躺在那。沖動(dòng)的曾經(jīng)興奮載這些源代碼，但面對(duì)這的原型往往是不太復(fù)雜的，就如早期UnixC編譯器，而這些原型往往就是最精如果我們要分析的是開(kāi)源的相對(duì)完整的C編譯器源代碼，而不是一個(gè)教學(xué)用的toy，并編譯器，一個(gè)是UCC編譯器。如果我們還希望代碼結(jié)構(gòu)清晰，且函數(shù)名等能望文生義，能直接與C語(yǔ)言的文法吻合，不必去猜測(cè)這個(gè)函數(shù)名是哪幾個(gè)單詞的縮寫(xiě)，那UCC會(huì)更勝一籌。當(dāng)然，UCC的原作者WenjunWang( )或多或少地受到LCC編譯器的UCC就如一顆被遺落在角落的珍珠，漸漸地蒙上了塵埃。一萬(wàn)行左右的代碼量，UCC就能實(shí)現(xiàn)一個(gè)基本完整的C編譯器，雖然后端只面向32位的X86平臺(tái)。UCC沒(méi)有如LCC那樣地可變目標(biāo)，既可生成MIPS，也可生成SPARC和X86代碼。雖然偶有BUG，縱然碧玉有瑕，即便不夠知名，但只要把UCC這只麻雀解剖清楚，我們已能搞清C編譯器是如何工作的，我們已能站在編譯器實(shí)現(xiàn)的角度來(lái)品味那經(jīng)40余年而愈久愈香的C語(yǔ)言。C和C++語(yǔ)言的相關(guān)書(shū)籍中，最最經(jīng)典的如《TheCProgrammingLanguageC++Primer》和《TheC++programminglanguageCC++編譯器的最早期注的焦點(diǎn)，UCCLCC在后端優(yōu)化上都做得不夠。不過(guò)，站C程序員的角度來(lái)看，C編譯器的前C編譯器與程序員的接口C編譯器前端的實(shí)現(xiàn)，就能更深刻地理眾里尋她千，驀然回首，SheisC。那我們就啟程吧第1章基礎(chǔ)知 語(yǔ)言、文法與遞 一個(gè)較復(fù) 由文法到分析 表達(dá)式 Declaration 語(yǔ)句 UCC編譯器預(yù) UCC的使 UCC 結(jié)合C語(yǔ)言來(lái)學(xué)匯 匯編語(yǔ)言簡(jiǎn) 整數(shù)運(yùn) 浮點(diǎn)數(shù)的算術(shù)運(yùn) 浮點(diǎn)數(shù)之間的比較操 指針、數(shù)組和結(jié)構(gòu) 第2章UCC編譯器的基本模 詞法分 UCC編譯器的內(nèi)存管 C語(yǔ)言的類(lèi)型系 UCC編譯器的符號(hào)表管 第3章語(yǔ)法分 C語(yǔ)言的表達(dá) 條件表達(dá)式和二元表達(dá) 一元表達(dá)式和基本表達(dá)式 C語(yǔ)言的語(yǔ)句 C語(yǔ)言的外部 Declaration和函數(shù)定義FunctionDefinition 與Declaration有關(guān)的幾個(gè)非終結(jié) 說(shuō)明符DeclarationSpecifiers和符 第4章語(yǔ)義檢 語(yǔ)義檢查簡(jiǎn) 表達(dá)式的語(yǔ)義檢 表達(dá)式的語(yǔ)義檢查簡(jiǎn) 數(shù)組索引表達(dá) 基本表達(dá) 函數(shù)調(diào)用的語(yǔ)義檢 成員選擇運(yùn)算 相容類(lèi)型Compatible 一元運(yùn)算符表達(dá)式的語(yǔ)義檢 二元運(yùn)算符、賦值運(yùn)算符和條件表達(dá)式的語(yǔ)義檢 對(duì)語(yǔ)句Statement的語(yǔ)義檢 對(duì)的語(yǔ)義檢 類(lèi)型結(jié)構(gòu)的構(gòu) 結(jié)構(gòu)體的類(lèi)型結(jié) 結(jié)構(gòu)體和數(shù)組的初始 內(nèi)部連接和外部連 對(duì)外部進(jìn)行語(yǔ)義檢查的臨門(mén)一 第5章中間代碼生成及優(yōu) 中間代碼生成簡(jiǎn) 表達(dá)式的翻 布爾表達(dá)式的翻 再論符號(hào)symbol與公共子表達(dá) 通過(guò)“偏移”數(shù)組元素和結(jié)構(gòu)體成 后綴表達(dá)式的翻 賦值表達(dá)式的翻 一元表達(dá)式及其他表達(dá)式的翻 語(yǔ)句的翻 If語(yǔ)句和復(fù)合語(yǔ)句的翻 Switch語(yǔ)句的翻 UCC編譯器的優(yōu) 刪除無(wú)用的臨時(shí)變量和優(yōu)化跳轉(zhuǎn)目 基本塊的合 第6章匯編代碼生 匯編代碼生成簡(jiǎn) 寄存器的管 中間指令的翻 由中間指令產(chǎn)生匯編代碼的主要流 為算術(shù)運(yùn)算產(chǎn)生匯編代 為跳轉(zhuǎn)指令產(chǎn)生匯編代 為函數(shù)調(diào)用與返回產(chǎn)生匯編代 為類(lèi)型轉(zhuǎn)換產(chǎn)生匯編代 參考文 語(yǔ)言、文法與遞

1礎(chǔ)知我們對(duì)語(yǔ)言這個(gè)概念再熟悉不過(guò)了，漢語(yǔ)和英語(yǔ)等都是自然語(yǔ)言。而C和C++語(yǔ)言是編程語(yǔ)言，若用更專(zhuān)業(yè)的術(shù)語(yǔ)，則這些編程語(yǔ)言被稱為Formal 別。C和C++等編程語(yǔ)言之所以被稱為形式語(yǔ)言，原因在于這些語(yǔ)言的產(chǎn)生過(guò)程是先有正式的窮集合，我E＝{x|x2n,n是非負(fù)整數(shù)}這樣的描述法。CC源代碼就是這個(gè)集合里的一個(gè)元素，合法的C源代碼有無(wú)窮多個(gè)，那我們要用什么樣的描述方法來(lái)表達(dá)C語(yǔ)言這個(gè)無(wú)窮集合？讓我們不妨先這個(gè)比C語(yǔ)言簡(jiǎn)單得多的語(yǔ)言。T＝{a,a+a,a+a+a, (1-我們不難發(fā)現(xiàn)，上述集合T是由若干個(gè)a相加構(gòu)成，這是個(gè)無(wú)窮集合，省略號(hào)“……”我們就來(lái)探索一下有沒(méi)有更好的表達(dá)方法。讓我們先把集合T一分為二。T＝ a+a+a,＝ 我們仔細(xì)觀察其中的{a+a,a+a+a,…..}，越看越覺(jué)得這個(gè)式子跟TT＝{a} a+{a,a+a,a+a+a,……}＝ a| (1-式子(1-2)告訴我們，Taa+T構(gòu)成。該式實(shí)際上由兩個(gè)式子構(gòu)成，TaT aa+11T＝ {a,a+a,a+a+a,….}＝ T a|T (1-式子(1-2)和(1-3)的區(qū)別在于，前者的遞歸出現(xiàn)a+T右側(cè)，而后者的遞歸定義出T+a{a,a+a,a+a+a,形如(1-2)和(1-3)下a+aTaTT14和1512和13) a+→a+(1- →T+a+(1-圖111述子14)psngee串a(chǎn)a言T向?yàn)門(mén)為+12的T而a和12產(chǎn)即T→a和→a+言T語(yǔ)言T法r r生為圖11根T子符文。TTa+Ta1.1.1句一個(gè)較復(fù)我們先給出一個(gè)較復(fù)法，該文法描述了一個(gè)包含“語(yǔ)句、表達(dá)式和”的程Program，如1.2.1所示 if(expression)Statement if(expression)StatementelseStatement while(expression)Statement {StatementListopt} Statement| Expression; Declaration; →AdditiveExpression AdditiveExpression→AdditiveExpression+MultiplicativeExpressionAdditiveExpression→AdditiveExpression-MultiplicativeExpressionMultiplicativeExpression→PrimaryExpressionMultiplicativeExpression→MultiplicativeExpression*PrimaryExpressionMultiplicativeExpression→MultiplicativeExpression/PrimaryExpressionPrimaryExpression→id|num|(Expression)Declaration→intDeclarator→*Declarator|PostfixDeclarator→DirectDeclarator|PostfixDeclarator[num]|PostfixDeclarator(void)DirectDeclarator→id|(Declarator)1.2.1Program按照前面的約定，圖1.2.1中的第一個(gè)產(chǎn)生式左側(cè)的非終結(jié)符Program為文法的開(kāi)始符{int}

a=b=d=d-}}c=c-}}請(qǐng)于ucc162.2.tar.gz，解壓后的文法，其實(shí)很多產(chǎn)生式與第1.1節(jié)的產(chǎn)生式(1-2)及產(chǎn)生式(1-3)本質(zhì)上是相同的。 a| (1- a|T (1-例如，以下幾個(gè)從圖1.2.1取出的產(chǎn)生式，如果把AdditveExpression視為T(mén)，把MultiplicativeExpression視為a后，就和產(chǎn)生式(1-3)是一樣的。如前文所述，產(chǎn)生式(1-3)是四則運(yùn)算符都是左結(jié)合的。所以我們選取形如(1-3)的產(chǎn)生式來(lái)表達(dá)加法運(yùn)算。與T所表達(dá)的集合類(lèi)似，AdditiveExpressionMultiplicativeExpression相加構(gòu)成。換言之，要進(jìn)MultiplicativeExpression。同理，MultiplicativeExpression由若干個(gè)引入的運(yùn)算符，如&和|等。 →AdditiveExpression+MultiplicativeExpression id|num|(Expression)讓我們?cè)賮?lái)分析圖1.2.1中的以下幾個(gè)與“語(yǔ)句Statement”有關(guān)的產(chǎn)生式。由Statement的產(chǎn)生式，我們可知，語(yǔ)if語(yǔ)句、while語(yǔ)句、復(fù)合語(yǔ)句及表達(dá)式語(yǔ)句構(gòu)成。而if語(yǔ)句則以if開(kāi)頭，后面緊跟左括號(hào)，然后是表達(dá)式expression，接著是右括號(hào)，之后又是一個(gè)語(yǔ)句IfStatement→ if(expression)Statement if(expression)StatementelseStatement →while(expression)Statement →{StatementListopt} Statement 而StatementList對(duì)應(yīng)的產(chǎn)生式實(shí)際上形如前面的產(chǎn)生式(1-3)。復(fù)合接下來(lái)，讓我們?cè)賮?lái)討論與Declaration相關(guān)的產(chǎn)生式，在C語(yǔ)言中，我們通過(guò)“聲明”表達(dá)了 程序員自定義的某個(gè)標(biāo)志符是什么類(lèi)型”的概念 * |PostfixDeclarator→DirectDeclarator|PostfixDeclarator[num]|PostfixDeclarator(void) 而PostfixDeclarator則再次與產(chǎn)生式（1-3）神似。其產(chǎn)生式實(shí)際上告訴我們對(duì)應(yīng)的產(chǎn)生式實(shí)際上表達(dá)了若干個(gè)*后面再跟一個(gè)PostfixDeclarator.通過(guò)[num]的后綴，我們實(shí)際上了一個(gè)大小為 的數(shù)組，而通過(guò)(void)的后綴,們實(shí)際上了一個(gè)無(wú)參的函數(shù)。我們知道，在中使用*，實(shí)際上是了一個(gè)指針。圖121，。intaa[30][50],Declaration出發(fā)intaa[30][50]30,50numaaid。我們還可以由Declarationint(*cc)[3][5]C的語(yǔ)法，aacc是指向數(shù)組的指針。仔細(xì)觀numnumid實(shí)際相當(dāng)numid的識(shí)別列入“詞法分析”范疇。通常，分析器指的intC語(yǔ)言的文法也不盡相同。但管中窺豹，我們已可見(jiàn)一斑。如果理表達(dá)式在這一節(jié)中，我們來(lái)討論如何為圖1.2.1中的文法構(gòu)造分析器。時(shí)，我們從基本的26個(gè)英文字母入手，然后由英文字母組成各種各樣的單詞，之后按照語(yǔ)則組成句子，之后是段落，然后是文章。同理，我們要寫(xiě)一個(gè)語(yǔ)法分析器來(lái)識(shí)別圖1.2.1文法對(duì)應(yīng)的語(yǔ)言和運(yùn)算符等。由字母表中的字符，我們可以組成基本的單1231、23這三個(gè)數(shù)字構(gòu)成abca、bc3個(gè)字母組成。在編譯領(lǐng)域，給單詞起了一個(gè)專(zhuān)門(mén)的術(shù)Token，其中包含了單詞的類(lèi)型和單詞的值。例123456同樣是數(shù)，但它們的值不一樣123abc是不同類(lèi)型的單詞。識(shí)別了token之后，我們就可以按照上一節(jié)文法所規(guī)定的法則去組成合法的、表達(dá) ucc\examples\sc中的代碼。其中l(wèi)exh中的以下結(jié)構(gòu)體描述了與Token相關(guān)的類(lèi)型和值。lex是英文單詞lexical的前綴。typedefTokenKindValuelex.cGetToken()Token1.3.16466行，我們7077行完成了對(duì)標(biāo)志符的識(shí)別，標(biāo)志符以字母開(kāi)頭，后面緊跟若干個(gè)數(shù)字和字母。因?yàn)閕f,elsewhilekeyword也符合標(biāo)志符的特征，所以我們需要在第77行調(diào)用GetKeywordKind函數(shù)，判斷一下識(shí)別出tokens.txttoken7885行，我們實(shí)現(xiàn)的是對(duì)數(shù)的識(shí)別，為簡(jiǎn)單起見(jiàn)，只完成了對(duì)十進(jìn)制整數(shù)的識(shí)別。在C編譯器中，我們要做得更復(fù)雜些，需要處理十進(jìn)制整數(shù)、十六進(jìn)制整數(shù)、floatdouble浮點(diǎn)數(shù)等。當(dāng)然，還有許多簡(jiǎn)單的單詞，是由一個(gè)字符構(gòu)成的，例如+、－、*和/R1.3.1下面我們以 。顯然，此處對(duì)PrimaryExpressionid,num和(expression)這三個(gè)候選式。如果當(dāng)前tokenTK_LPAREN1.3.25760行則去識(shí)別產(chǎn)生式PrimaryExpression的候選式(expression)。我們預(yù)期接下來(lái)的字符串應(yīng)該是加了一的宏定義，可以看到我們調(diào)用的其實(shí)就是前文所述的詞法分析器GetToken()。 do{curToken=識(shí)別左括號(hào)之后，由該產(chǎn)生式所制定的規(guī)則，我們預(yù)期接下來(lái)token會(huì)構(gòu)成一個(gè)合法的此處只要調(diào)Exprssion()即可Expression()函數(shù)返回后，我們期望當(dāng)前終結(jié)符是右Expect(TK_RPAREN)中會(huì)進(jìn)行比對(duì)，如果不是右括號(hào)，則報(bào)錯(cuò)；否則取下一個(gè)tokentoken。而53-56則是處理遇到標(biāo)idnum的情況61至63的idnum或者左括號(hào)開(kāi)頭。換言之，PrimaryExpression的首符集是{id, 圖 在圖1.3.2中第54行，我們調(diào)用了函數(shù)CreateAstNode()創(chuàng)建了一個(gè)astNode結(jié)點(diǎn)，用于存為T(mén)K_NUM，值為123。structastNode的定義如下所示。其中，op用于存放結(jié)點(diǎn)的類(lèi)型，而50這樣的表達(dá)式，分析到30時(shí)，我們會(huì)為30構(gòu)造一個(gè)astNode結(jié)點(diǎn)，遇到運(yùn)算符*時(shí)，也 點(diǎn)則是運(yùn)算符所需要的操作數(shù)。此處“抽象”反映的token流中提取信息，構(gòu)造適合我typedefstructastNode{TokenKindop;Valuevalue;structastNode*}*接下來(lái)我們就來(lái)看看如何處理分析由若干個(gè)imaExpeion()相乘或相除構(gòu)成的乘法表達(dá)式utpcaieEpeion。這里，我們把關(guān)注的焦點(diǎn)放在了如何實(shí)現(xiàn)運(yùn)算符的左結(jié)合和右結(jié)合上。例如對(duì)于表達(dá)式100102而言，如果我們規(guī)定除法運(yùn)算符是左結(jié)合的，因?yàn)?5的第71841010AT100和10on符，則可把當(dāng)前得到的AT子樹(shù)作為左操作數(shù)，用2棵新的以除法運(yùn)算符為根結(jié)點(diǎn)的T73行我們用的是he循環(huán)。而如果規(guī)定除法運(yùn)算法是右結(jié)合的，則我們可按圖1386100: PrimaryExpression* PrimaryExpression/100/10/2100/10AST，我們要看一下10后面是否還有乘法或除法運(yùn)算符，如果有，則10要與其右側(cè)的除法運(yùn)算符先結(jié)合。所以先構(gòu)造出來(lái)的AST是10/2，之后再以這棵子100作為左操作數(shù)，以除法運(yùn)算法為根結(jié)點(diǎn)，構(gòu)造一棵適合進(jìn)行右結(jié)合運(yùn)算的AST。對(duì)候選式PrimaryExpression/MultiplicativeExpression的分析過(guò)程與上述非終結(jié)符PrimaryExpression的分析過(guò)程類(lèi)似，對(duì)于候選式中的非終結(jié)符，我們直接調(diào)用與之對(duì)應(yīng)的同名函數(shù)來(lái)識(shí)別接下來(lái)的token串；對(duì)于候選式中的終結(jié)符，我們判斷一下當(dāng)前讀入的token是否與之一致。圖1.3.387、9496行實(shí)際上就完成了這個(gè)1.3.3對(duì)100/10/2，如果除法是右結(jié)合的，則運(yùn)算結(jié)果為20；而如果除法是左結(jié)合的，則運(yùn)算結(jié)果是5。如果定義一個(gè)新語(yǔ)言，硬要把除定為右結(jié)合，這是和習(xí)慣的，是a=b=c是右結(jié)合的。1.3.377行和92行，我們還看到了一NewTemp()的函a*b*c為例，如果乘法是左結(jié)合的，我們先進(jìn)行的運(yùn)算a*b,我們需要把運(yùn)算結(jié)果存到一個(gè)臨時(shí)變量中，之后再用這個(gè)臨時(shí)c進(jìn)行乘法，結(jié)果再存到一個(gè)新的臨時(shí)變量中，如下所示t1=a*bt2=t1*處理完乘除法運(yùn)算，我們?cè)賮?lái)看一下加減法運(yùn)算的處理函數(shù)AdditiveExpression()圖134uipcavexpeon()都是二元運(yùn)算符，只是運(yùn)算符不同而已。我們知道，在C語(yǔ)言中，還有許多類(lèi)似的二元運(yùn)可以考慮把對(duì)二元運(yùn)算符的處理歸并到一個(gè)函數(shù)中統(tǒng)一處理。在后續(xù)章節(jié)分析C編譯器的源代碼時(shí)，我們會(huì)在uccucexpc中看到arseinaEpesion()這個(gè)函數(shù)，C語(yǔ)言中所有的二元運(yùn)算表達(dá)式都由這個(gè)處理函數(shù)進(jìn)行分析.5再來(lái)看一下圖1.3.6中的函數(shù)void 地想起了當(dāng)年在《數(shù)據(jù)結(jié)構(gòu)》課中那熟悉的二叉樹(shù)前序、中序和后序遍歷。這里，我們對(duì)135碼。t0=a+bt1=t0*Declaration

圖 下面，讓我們?cè)倏纯磚cc\examples\sc\decl.c,這里我們要處理的是變量或函數(shù)的。 *Declarator |PostfixDeclarator ParameterList,int 我們以”int(*f(int,int,int))[4];”這個(gè)看起來(lái)復(fù)雜一點(diǎn)的為例子，進(jìn)入命令行，運(yùn)行以下命令，我們得到的結(jié)果是fis:function(int,int,int)whichreturnspointertoarray[4]ofint”，//WindowsD:\src\ucc\examples\sc>nmake-f//Linuxiron@ubuntu:sc$由于我們?cè)谶@個(gè)簡(jiǎn)單的語(yǔ)言中只引入了int這個(gè)基本類(lèi)型，所以所有的都是以開(kāi)頭的，之后再跟上符ecaaor。在符ecaaor中，我們可以進(jìn)一步指定要聲明的標(biāo)志符為指針類(lèi)型、數(shù)組類(lèi)型或者函數(shù)類(lèi)型。如果把*、[]和()看成類(lèi)型運(yùn)算符，把nt算表達(dá)式，我們希望PU做計(jì)算，從而可以得到運(yùn)算結(jié)果；而通過(guò)類(lèi)型表達(dá)式，程序員為ecaaor{PostfixDeclarator,*PostfixDeclarator,**PostfixDeclarator,***PostfixDeclarator,而非終結(jié)符PostfixDeclarator{DirectDeclarator,DirectDeclarator[num],DirectDeclarator(ParameterList),DirectDeclarator[num][num],DirectDeclarator(ParameterList)(ParameterList),DirectDeclarator[num](ParameterList),DirectDeclarator(ParameterList)[num],}在這里，我們可以發(fā)現(xiàn) f(int)(int)竟然也是一個(gè)符合文法的，因?yàn)槲覀兺耆蒁elcarationGCC、VisualStudio、ClangUCC都會(huì)給我們一個(gè)大大的錯(cuò)誤提示，intf(int)(int)是個(gè)的，因?yàn)檫@個(gè)函數(shù)企圖把函數(shù)作為返回值。在ucc給出的錯(cuò)誤提示中，我們看到了(declchk.c,629)，這代表著我們是在ucc源代碼declchk.c629行檢查到了這個(gè)錯(cuò)誤，錯(cuò)誤提示中包含這樣的信息是為了方便對(duì)UCC編譯器源代碼進(jìn)行和分析。iron@ubuntu:test$ o.c:2:5:error:‘f’declaredasfunctionreturningafunctioniron@ubuntu:test$ucc o.c,2):error:functioncannotreturnfunctiontypeuccinvokecommanderror:/home/iron/bin/ucl-o iron@ubuntu:test$clang o.c:2:6:error:functioncannotreturnfunctiontype'int(int)'intf(int)(int);^1error引入表達(dá)能力更強(qiáng)的文法，到目前為止，我們介紹的文法被稱為上下文無(wú)關(guān)文法，cone-r,實(shí)際上存在能力更強(qiáng)的文法。用集合的觀點(diǎn)，通俗的來(lái)說(shuō)，就是我們拜和。后都會(huì)有不同的感受”，這就是所謂的”ThereareathousandHamletsinathousandpeople's的。如果有一天，再?gòu)?fù)雜的語(yǔ)義規(guī)則都可以形式化了，那按照“可以形式化，就可以自動(dòng)化”了。ecaaonpeon是ecaaon中的運(yùn)算符換成了*[]和()成了nt等基本類(lèi)型。如果你熟悉+以構(gòu)成一個(gè)完整的類(lèi)型表達(dá)式。我們會(huì)為”ntfnnint4];”構(gòu)造一棵形如圖1.3.7decl.c中的代碼，我們可畫(huà)圖1.3.7復(fù)雜的分析樹(shù)與語(yǔ)法雖然延用二叉樹(shù)的結(jié)點(diǎn)astNode，但此處我們實(shí)際上用每個(gè)astNode的kids[1]域構(gòu)成了一個(gè)鏈表來(lái)描述標(biāo)志符f的類(lèi)型信息，較特別的是在FUNCION()結(jié)點(diǎn)中，我們用其kids[0]域來(lái)記錄其形參列表。圖1.3.7所代表類(lèi)型信息可簡(jiǎn)化為以下鏈表： ----> ---->POINTER----> >我們由鏈?zhǔn)壮霭l(fā)，從左向右來(lái)構(gòu)造一個(gè)新的類(lèi)型，其含義是INT為基本類(lèi)型，所得類(lèi)型表述為,把POINTER類(lèi)型運(yùn)算符作用于上一步的結(jié)果，所得類(lèi)型pointertoarray[4]of回值的類(lèi)型，而函數(shù)的形參列表則存于結(jié)點(diǎn)FUNCTION()的kids[0]域中，所得類(lèi)型為function(int,int,int)whichreturnspointertoarray[4]ofint前一步所得的類(lèi)型即為標(biāo)志符ff function(int,int,int)whichreturnspointertoarray[4]off”fs:“f138108第109至1371.3.8接下來(lái)，我們以非終結(jié)PostfixDeclarator為例，來(lái)分析一下如何構(gòu)建形如圖1.3.7的語(yǔ)法當(dāng)然類(lèi)似于圖1.3.7，我們是把二叉樹(shù)當(dāng)單向鏈表來(lái)用了。 ----> ----> >其含義INT為基本類(lèi)型，所得類(lèi)型表述為把ARRAY[3]類(lèi)型運(yùn)算符作用于上一步的結(jié)果所得類(lèi)型為array[3] array[5]of前一步所得的類(lèi)型即為標(biāo)志符arrarr array[3]ofarray[5]of行的，最先遇到的是int，之后是[3]，然后才是[5]，但在構(gòu)造類(lèi)型信息時(shí)，我們需要先把函數(shù)，我們先構(gòu)建了int結(jié)點(diǎn)，接著在DirectDeclarator()函數(shù)中，我們構(gòu)造了arr對(duì)應(yīng)的結(jié)點(diǎn)，ARRAY[3]作為其前驅(qū)。int結(jié) 在Declaration()函數(shù)中進(jìn)行構(gòu)arr結(jié) 在DirectDeclarator()函數(shù)中進(jìn)行構(gòu) PostfixDeclarator() ----> ---->arr ----> ----> >在Declaration()函數(shù)中進(jìn)構(gòu)建Declarator、DirectDeclaratorDeclaration的處理函數(shù)，與PostfixDeclarator類(lèi)似，就不再述1.3.9觀察Declaration的產(chǎn)生式，我們可以發(fā)現(xiàn)這樣的產(chǎn)生式一次只能一個(gè)標(biāo)志符，無(wú)法同時(shí)多個(gè)標(biāo)志符，例如”int a,b;”。 這個(gè)問(wèn)題不難解決，把上述產(chǎn)生式改為如 DeclaratorList,因?yàn)閺恼Z(yǔ)法結(jié)構(gòu)上，“* c”是由一個(gè)符Declarator生成，而”d”由另一個(gè)符Declarator生成。 c,”int(*f(int,int,int))[4];”這樣的復(fù)雜，需要先看f(int,int,int)，再向外看。這不符合人的直 intARRAY[4];ARRAY* f(int,int,int);上去實(shí)現(xiàn)控制流語(yǔ)句ifwhile語(yǔ)句。與語(yǔ)statement相關(guān)的產(chǎn)生式如下所 if(Expression)Statement if(Expression)StatementelseStatementWhileStatement→while(Expression)Statement { Statement| Expression; Declaration;經(jīng)實(shí)現(xiàn)了表達(dá)式Expression和Declaration對(duì)應(yīng)的處理函數(shù)。依照C語(yǔ)言標(biāo)準(zhǔn)，此處我們把賦值操作”id=Expression”視為賦值表達(dá)式，賦值表達(dá)式之后再跟上分號(hào)，則構(gòu)成了表我們把Declaration727772行的IS_PREFIX_OF_DECL()實(shí)際用到的是我們前文介紹的首符集的概念，只有當(dāng)前token屬于Declaration的首符集時(shí)，我們才去識(shí)別Declaration。這里可能存在問(wèn)題是，如TK_IDDeclaration的首符集時(shí)，該如何處理。就跟到陌生地方遇到叉路口一樣，UCC圖 1.3.1061CreateStmtNode()CreateAstNode()這兩個(gè)不同的函數(shù)調(diào)用，從函數(shù)名中我們可以發(fā)現(xiàn)兩者都是為了創(chuàng)建一個(gè)結(jié)點(diǎn)Node。CreateStmtNode()義，我們就可以發(fā)現(xiàn)，astStmtNode對(duì)象起始部分的數(shù)據(jù)恰好可以當(dāng)作一個(gè)astNode對(duì)象來(lái)astStmtNodeastNode。這種技thenStmtIfStatementWhileStatement的處理函astNodetoken的TokenKindUCC的源代碼中，我們需要專(zhuān)門(mén)為抽象語(yǔ)法樹(shù)結(jié)點(diǎn)定義不同的類(lèi)型，可參見(jiàn)”ucc\ucl\opinfo.h”。TokenKindastNode是不夠的。以乘法運(yùn)算符*為例，該符號(hào)用于四則運(yùn)算”(a+b)*c”時(shí)，充當(dāng)乘號(hào)。而在“int*a;”中則不是作為乘號(hào)來(lái)使用。所以在”ucc\examples\sc\tokens.txt”中，我們引入了TK_MUL和_PINTR*C語(yǔ)言的運(yùn)算++astNode{TokenKindop;Valuevalue;structastNode*}*astStmtNode{TokenKindop;Valuevalue;structastNode*structastStmtNode*thenStmt;structastStmtNode*elseStmt;structastStmtNode*next;}*xpeonaementaement是遞歸定義的，atemenstStatementList→StatementList下面，我們舉例來(lái)說(shuō)明如if語(yǔ)句進(jìn)行翻譯，if語(yǔ)句可分為以下兩種，我們以帶分支的if語(yǔ)句為例來(lái)討論IfStatement→if(Expression) IfStatement→if(Expression)Statement例如a=b=}我們期望把上述語(yǔ)句翻譯為以下中間代碼，通過(guò)有條件的oo和無(wú)條件的oo，我們就實(shí)現(xiàn)了控制流的轉(zhuǎn)移。在U的指令集中，會(huì)有相應(yīng)的硬件指令來(lái)實(shí)現(xiàn)條件或無(wú)條件跳bgpcue,abe_0和abe_1ooCoof和hefSfheneeabe_0fabe_1taemenNode(if(!c)goto 在VisitStatementNode()函數(shù)產(chǎn)生此跳轉(zhuǎn)指a=goto在VisitStatementNode()函數(shù)產(chǎn)生此跳轉(zhuǎn)指Label_0else語(yǔ)句的標(biāo)號(hào)b=Else語(yǔ)句，存于astStmtNode對(duì)象elseStmtLabel_1是下一條語(yǔ)句的標(biāo)號(hào)，存于有了這樣的直觀體會(huì)后，我們?cè)賮?lái)1.3.11111行調(diào)用的CretaeLabelNode()函數(shù)就是用來(lái)創(chuàng)建一個(gè)新的標(biāo)號(hào)。給標(biāo)號(hào)取Label_0Label_1，看起來(lái)就像給變量取名a,b,c，或叫、和，在實(shí)際開(kāi)發(fā)中是要受人鄙視的，不過(guò)這些標(biāo)號(hào)圖 句對(duì)應(yīng)的AST結(jié)點(diǎn)中存放while語(yǔ)句的標(biāo)號(hào)Label_2，while語(yǔ)句的下一條語(yǔ)句的標(biāo)號(hào)對(duì)應(yīng)的處理函數(shù)見(jiàn)圖1.3.12。在圖1.3.12中，我們還看到了由一對(duì)大括號(hào)包圍的復(fù)合語(yǔ)句的處理過(guò)程，為了記錄Statement鏈表，我們?cè)诮Y(jié)構(gòu)體astStmtNode中引入了next域，在圖中150155行我們看到了構(gòu)成單向鏈表的操作。而在153行中，我們要判斷當(dāng)前面對(duì)的token是否為Statement的首符，所以再次用到了首符集的概念。a=} //while語(yǔ)句的標(biāo)號(hào)，存于kids[0]if(!c)gotoLabel_3//在VisitStatementNode()函數(shù)中生成此有條件跳轉(zhuǎn)指令a=f //Then語(yǔ)句，存于astStmtNode對(duì)象的thenStmt域gotoLabel_2//VisitStatementNode() //while語(yǔ)句的下一條語(yǔ)句的標(biāo)號(hào)，存于圖 While和復(fù)合語(yǔ)astStmtNodeStatement對(duì)語(yǔ)句對(duì)應(yīng)的AST結(jié)點(diǎn)，而第205210行則用于處理復(fù)合語(yǔ)句。圖 NextChar函數(shù)，NextCharFromMem用于從內(nèi)存中取下一個(gè)字符NextCharFromStdin則用于從當(dāng)前進(jìn)程的標(biāo)準(zhǔn)輸入中取下一個(gè)字符，在第32行，我們調(diào)用了voidNextChar=}}用動(dòng)ec的碼只通給nexer()遞同函指，們可讓ec的法析器een內(nèi)或標(biāo)輸中下個(gè)符和向象言中多異同際+虛數(shù)是過(guò)函表實(shí)的虛數(shù)是若干函指構(gòu)的要微下nux內(nèi)源碼們可找好的虛數(shù)”結(jié)體比如uct e_opeaonnux核然用C言現(xiàn)但們是用C現(xiàn)承多這的向象想只創(chuàng)虛數(shù)這的作要C程員己手有+譯代而數(shù)針實(shí)個(gè)常要概念們識(shí)別是非結(jié)符oram生字串但圖134第34我調(diào)的是opounaten這因?yàn)閛ram產(chǎn)式下示為單見(jiàn)我就再為oram造個(gè)理數(shù)。第35告我，個(gè)oram別功，們?cè)撚龅奈慕Y(jié)符O,第36用遍語(yǔ)樹(shù)產(chǎn)中代。 圖 UCC編譯器預(yù)UCC的使1.3ucc\examples\sc，我們對(duì)如何根據(jù)語(yǔ)言的文法來(lái)編寫(xiě)語(yǔ)法分析器，中間代碼，C程序員還不能得到其所要的計(jì)算結(jié)果。C編譯器還要由中間代碼產(chǎn)生匯編代碼。UCC編譯器前，讓我們先熟UCC編譯器的使用。UCC編譯器的大部分代碼Ubuntu系統(tǒng)不算太復(fù)雜，這里不再畫(huà)蛇添足。需要在ucc/makefile第1行和ucc/driver/linux.c第7行配置UCC的安裝 源代碼被解壓到”/home/iron/src/ucc” ，則經(jīng)過(guò)以下步驟就可構(gòu)建并安裝UCC到”iron@ubuntu:ucc$make-siron@ubuntu:ucc$make-stest如下所示，由cd~進(jìn)入當(dāng)前用戶主gedit打開(kāi)的.bashrc文件末尾添加一行”exportPATH=$PATH:/home/iron/bin其中”/home/iron/bin”UCCDIR，保存后退出，重新打開(kāi)一個(gè)終端，即可使用ucc命令。 cd~ 接下來(lái)，我們用一個(gè)簡(jiǎn)單的例子來(lái)解釋一下UCC的大致工作流程。編寫(xiě)以下C代碼，存為文件”o.c”。這份代碼用于求階乘，其中有if語(yǔ)句、while語(yǔ)句、庫(kù)函數(shù)調(diào)用及遞歸intf(intn){if(n<returnreturnn*f(n-}}intinti=1;}return}C源代碼o.c需要先經(jīng)過(guò)預(yù)處理器 PreProcessor)預(yù)處理。預(yù)處理器會(huì)根據(jù)預(yù)設(shè)ncude UserManual.txt”中所言”Beforereportingbugs:…….,sendtheprepocessedfilesto 關(guān)。C編譯器再根據(jù)中間代碼生成不同硬件平臺(tái)的匯編語(yǔ)言，這部分工作被稱為編譯器的后端， WriteOnce,RunAnywhere”那讓人熱血沸騰的Slogan。當(dāng)然，與運(yùn)行平臺(tái)相關(guān)的工作及優(yōu)化的重頭戲就交給了Java虛擬機(jī)。Java得到跨平臺(tái)的代價(jià)是犧牲了一部分的運(yùn)行效率，但在程序就不好玩了。生成中間代碼之后解釋執(zhí)行，比”生成機(jī)器代碼之后直接運(yùn)行速度更低”的原因，aautne”目標(biāo)模塊o.o還需要攜手函數(shù)庫(kù)和其他的目標(biāo)代碼才能得到可執(zhí)行程序o，這個(gè)工作被稱為L(zhǎng)inking，即連接，也有寫(xiě)為的，哪個(gè)是錯(cuò)誤字，已經(jīng)傻傻分不清楚了，權(quán) --->o.i --->o.s iron@ubuntu:demo$ls iron@ubuntu:demo$ucc-Eo.c-oo.iiron@ubuntu:demo$ls iron@ubuntu:demo$ucc--dump-ast--dump-IR-So.i-oo.siron@ubuntu:demo$ls iron@ubuntu:demo$ucc-c o.s-o iron@ubuntu:demo$ls iron@ubuntu:demo$ucc o.o-o iron@ubuntu:demo$ iron@ubuntu:demo$./ f(1)=1f(2)=f(3)=f(4)=f(5)=f(6)=f(7)=f(8)=f(9)=362880f(10)=按上面的分析，我們可以發(fā)現(xiàn)，要由C源代碼得到一份可執(zhí)行程序，我們需要“預(yù)處UCCCLinuxWindowsuccucc–E等不uccUCC編譯器閱讀和分析時(shí)，比較有用的參數(shù)還有”--dump-ast--dump-IR”，用于生成字符串形式表達(dá)的抽象語(yǔ)法樹(shù)AST，及優(yōu)化后的中間代碼IR。器、編譯器、匯編器和連接器。UCC驅(qū)動(dòng)的代碼在ucc\driver 編譯器的源代碼則在\ucc\ucl。按“掃，剪裙邊”的思路，下一小節(jié)，我們會(huì)先剖析一下UCC編譯器驅(qū)動(dòng)的代碼。UCC在上一小節(jié)，通過(guò)以下四條命令，我們有意地給ucc傳遞不同的參數(shù)來(lái)依次調(diào)用預(yù)處理器、編譯器、匯編器和連接器。當(dāng)然實(shí)際使用ucc命令時(shí)，我們不會(huì)繞這么大一個(gè)圈子，直接 o.c -oo”即可得到可執(zhí)行程序o。iron@ubuntu:demo$ucc-Eo.c- iron@ubuntu:demo$ucc--dump-ast--dump-IR-So.i-oo.siron@ubuntu:demo$ucc-co.s-oo.oiron@ubuntu:demo$ucco.o-o ucc\driver來(lái)分析一下ucc驅(qū)動(dòng)器的源代碼。圖1.4.1給出了ucc\driver\linux.c中的部分代碼。第17至22行是我們使用”ucc-Eo.c-oo.i”命令時(shí)，ucc驅(qū)動(dòng)真正執(zhí)行令其中的CPP代表的是CPreProcessor即C預(yù)處理器而非CPlusPlus,C++。通過(guò)-D參數(shù)，指定了GNUC等預(yù)定義的宏，而$1、$2和$3用于充當(dāng)占位符ucc-E- o.c-I../-DREAL=double- 命令中的”-I../-DREAL=double”UCCDriver提取出來(lái)，用于替換字符串”$1”;而命令中的”o.c”21行的”$2”，充當(dāng)預(yù)處理器的輸入文件；命令中的”o.ii”則替換”$3”,用來(lái)存放預(yù)處理后的結(jié)果。而”-v”參數(shù)UCC驅(qū)動(dòng)在終端上打印出實(shí)際所用到的/usr/bin/gcc-U -D_POSIX_SOURCE- -Dlinux-D =signed--I/home/iron/bin/include-I../-DREAL=double- o.c- ucc-S- o.c--dump-ast- 35行中$1、$2和$321ucl就是我UCCucc\ucl3846行分別是匯編器AssemblerLinker45行的參數(shù)"-lc","-lm"用來(lái)告訴連接器我們需要C函數(shù)庫(kù)libc.so和數(shù)算函數(shù)庫(kù)libm.so。/home/iron/bin/ucl- 1.4.1接下來(lái)的問(wèn)題就是如何在ucc驅(qū)動(dòng)中開(kāi)啟一個(gè)新進(jìn)程來(lái)執(zhí)行上述命令行所對(duì)應(yīng)的預(yù)處理器、編譯器、匯編器或者連接器。圖1.4.2給出了在Linux平臺(tái)上創(chuàng)建子進(jìn)程及裝載執(zhí)行fork()Unix。生物界中，有許多細(xì)胞進(jìn)行繁殖時(shí)，是通過(guò)細(xì)胞一分為二的來(lái)進(jìn)行，Linux創(chuàng)建子進(jìn)程的系統(tǒng)調(diào)用fork()也相當(dāng)于這個(gè)過(guò)程。英文fork是叉子行為，clone。除了進(jìn)程號(hào)PID、父進(jìn)程號(hào)PPIDfork()fork()成功后，會(huì)有兩個(gè)進(jìn)程并發(fā)執(zhí)行以下56行開(kāi)始的代碼，當(dāng)然對(duì)這兩個(gè)進(jìn)程而言，因?yàn)閒ork()的返回值不一樣，所以新創(chuàng)建的6366725859行則進(jìn)程中加載外存中的某個(gè)可執(zhí)行程序，這可借助系統(tǒng)調(diào)用execv()來(lái)實(shí)現(xiàn)。我們知道，編譯后生成的可執(zhí)行程序一般是存放在外存的，只有被裝載器Loader從外存載入內(nèi)存后，這個(gè)可執(zhí)行程序才能運(yùn)行。而Linuxexecv()系統(tǒng)調(diào)用就是起到這個(gè)裝載器的作用。如果子進(jìn)程通過(guò)execv()加載了一個(gè)可執(zhí)行程序，那對(duì)子進(jìn)程而言，其整個(gè)進(jìn)程空間中的代碼段和數(shù)據(jù)段就會(huì)被替換成新加載的可執(zhí)行程序的代碼段和數(shù)據(jù)段。這意味著一旦第63行的7273wait()有在子進(jìn)程執(zhí)行完或者出錯(cuò)時(shí)，父進(jìn)程才會(huì)執(zhí)行第74至82行之間的代碼。UCC驅(qū)動(dòng)會(huì)通過(guò)函數(shù)ParseCmdLine()分析程序員提供令行參數(shù)，并結(jié)合圖1.4.1中的CPPProg ASProg和LDProg等命令模板，通過(guò)函數(shù) mand()來(lái)構(gòu)建實(shí)際要調(diào)用令，并將其作為參數(shù)傳給圖1.4.2中的Execute()函數(shù)。函數(shù)ParseCmdLine()和 在ucc\driver\ucc.c中，主要是進(jìn)行一些字符串的處理，這里不再啰嗦。1.4.2結(jié)合C匯編匯編語(yǔ)言的語(yǔ)法和語(yǔ)義都不復(fù)雜，如果你會(huì)C語(yǔ)言，那你就一定能在很短時(shí)間內(nèi)看懂開(kāi)始C編譯器剖析的長(zhǎng)征時(shí)，我們有必要熟悉一下我們要到達(dá)的目的地。學(xué)習(xí)任何語(yǔ)言代碼來(lái)熟悉匯編的辦法。我們先簡(jiǎn)單介紹一些基本概念，然后給出一個(gè)簡(jiǎn)單C程序及由ucc\ucl\x86win32.tpl只是用到的匯編代碼語(yǔ)法格Linux平臺(tái)的有所不同，兩者沒(méi)有本質(zhì)區(qū)別。X86Linux.tpl文件名中的”.tpl”是模板temte的縮寫(xiě)，其含義是文件x86Linux.tpl中包編代碼中，%0、%1和%2是占位符，這和前一節(jié)1.4.1中的$1、$2和$3的作用類(lèi)似。以下兩條匯編指令用于比較%2和%1對(duì)應(yīng)的兩個(gè)有符號(hào)整數(shù)，如果兩者不相等，則跳轉(zhuǎn)到%0對(duì)應(yīng)的目標(biāo)地址處；若相等，則執(zhí)行下一條匯編指令。助記符cmpcompare的縮寫(xiě)，cmpl中的后綴”l”表示進(jìn)32位的比較jneJumpifNotEqualTEM "cmpl%2,%1;jne的指令集也被劃分為指令和非指令。CPU處于可以使用任何指令的狀態(tài)時(shí)，被稱管理所有的軟硬件資源，就要有權(quán)使用CPU的所有指令，所以要處于管態(tài)。而操作系統(tǒng)內(nèi)核之外的應(yīng)用程序只使用非指令，處于目態(tài)。當(dāng)然，實(shí)際上x(chóng)86CPU是有四個(gè)不同的ring0ring3Linuxring0ring3。所以概念上，我和輸出out這樣的指令在x86中都是指令，只有OS內(nèi)核才能使用。如果一個(gè)應(yīng)用程序理員擁有一樣的權(quán)力，那帶來(lái)的只能是。但在標(biāo)準(zhǔn)C語(yǔ)言里，并沒(méi)有任何語(yǔ)法結(jié)構(gòu)與開(kāi)關(guān)中斷這樣的匯編指令相對(duì)應(yīng)，而我們知道，Linux內(nèi)核主要是用C語(yǔ)言來(lái)開(kāi)發(fā)的。CC語(yǔ)言中嵌入?yún)R編代碼的機(jī)制。而我們要剖析的UCC編譯器暫時(shí)還未提C代碼中嵌入?yún)R編的機(jī)Cinterrupt在Linux中，C程序員可調(diào)用read()和write()這樣的庫(kù)函數(shù)來(lái)向內(nèi)核發(fā)出讀文件和寫(xiě)文件的言的語(yǔ)義，ucc\ucl\x86Linux.tplUCC編譯器原作者的選擇。這個(gè)選擇并頁(yè)式管理是許多現(xiàn)代CPU普遍支持的內(nèi)存管理機(jī)制，而In 的x86CPU因?yàn)橐嫒莞纱嗬@開(kāi)x86的分段機(jī)制，及如何開(kāi)啟請(qǐng)求分頁(yè)機(jī)制的工作已經(jīng)由操作系統(tǒng)內(nèi)核完成，操作棧中為該函數(shù)分配空間，這意味著C函數(shù)中的局部變量是在棧中動(dòng)態(tài)分配的?；駽++new操作，這部分動(dòng)態(tài)數(shù)據(jù)區(qū)被稱為堆Heap。我們平時(shí)會(huì)講“這一堆亂七八糟代碼數(shù)據(jù)區(qū)動(dòng)態(tài)數(shù)據(jù)區(qū)（由堆和棧構(gòu)成，運(yùn)行時(shí)分配靜態(tài)數(shù)據(jù)區(qū)（全局變量、靜態(tài)變量和常量，編譯時(shí)確定和來(lái)實(shí)現(xiàn)，由庫(kù)函數(shù)實(shí)現(xiàn)者去花心思，不用勞煩C編譯器。C編譯器對(duì)棧的管理，主現(xiàn)“?！笨臻g的分配和回收，所以?？臻g的管理不需要C程序員操心。需要另外說(shuō)明的是，1.5.1C語(yǔ)言代碼來(lái)舉例說(shuō)明動(dòng)態(tài)和靜態(tài)數(shù)據(jù)區(qū)的概念。1.5.1按C語(yǔ)言的語(yǔ)法圖1.5.1中的str1是全局變量而str2是靜態(tài)變量而第12行的” World”則是常量，這部分?jǐn)?shù)據(jù)就保存在我們前文中所述的“靜態(tài)數(shù)據(jù)區(qū)而函數(shù)h中的變量str3是個(gè)局部變量，在函數(shù)h被調(diào)用時(shí)，才會(huì)在棧中動(dòng)態(tài)為str3分配內(nèi)存，在第9行，我們讓str3指向了由malloc分配的16字節(jié)的堆空間。圖1.5.2是由”ucc-S 成的部分匯編代碼。圖1.5.2第8行的str1對(duì)應(yīng)前述C代碼中的str1，而第9行的str2.0則對(duì)應(yīng)上述C代碼中的靜態(tài)變量str2，為了避免與可能存在的全局變量str2重名，UCC為靜態(tài)變量str2加上了”.0”的后綴。第8行中的”.comm str1,4”告訴匯編器，str1是個(gè)全局變量，要占4個(gè)字節(jié)，在32位機(jī)器中，指針一般就占4個(gè)字節(jié);而第9行的” 看到了C代碼中的字符串常量"oWorld"，UCC編譯器還為之起了一個(gè)名為”.str0”的名字，因?yàn)楹戏ǖ腃語(yǔ)言中不存在以”.”為前綴的變量名，所以我們可以不用擔(dān)心”.str0”會(huì)跟C代碼中的變量重名，而第5行的”.string”則指明了緊隨其后的是以’\0’結(jié)束的字符串"oWorld"UCC編譯器對(duì)靜態(tài)數(shù)據(jù)區(qū)的管理只要做到這一層即可為這些變量分配具體位置的工作就由后續(xù)的匯編器和連接器來(lái)完成。而圖1.5.23行”.data”則告訴匯編器接下來(lái)的是靜態(tài)數(shù)據(jù)區(qū)，而第11行的”.text”則告訴匯編器接下來(lái)的又切換成代碼區(qū)了，text是正文的意思，實(shí)際上代表的就是代碼區(qū)。你可能也發(fā)現(xiàn)了，在圖1.5.2中我們沒(méi)有發(fā)strstr31.5.1C1.5.21535Ch()2320(%ebp)即為形str28行的-4(%ebp)是局部變str3。1.5.2而要比較好h對(duì)應(yīng)的匯編代碼，我們需要再介紹點(diǎn)關(guān)于寄存器的概念。X86匯編語(yǔ)言中描述的寄存器物理上存在于CPU中，而靜態(tài)數(shù)據(jù)區(qū)則存在于內(nèi)存中。因?yàn)榧拇嫫髦庇^上，CPU提供的寄存器數(shù)量似乎越多越好，但這有硬件成本的約束算機(jī)研究人點(diǎn)是放在CPU和內(nèi)存之間的Cache上。UCC編譯器使用的x86寄存器有eax、ebx、ecx、edx、esp、ebp、esi和edi等共8個(gè)寄存器。以”e”為前綴命名的32位版本的寄存器，去掉前綴得到的ax,bx,cx,dx,sp,bp,si和di，就是16位版本的寄存器。ax還可分為ah和al這兩個(gè)8位的寄存器，其中的h表示高字節(jié)，而l表示低字節(jié)，bx、cx和dx寄存器也存在類(lèi)似的8 點(diǎn)Arm的風(fēng)格了，從R0一直到R15。不過(guò)，實(shí)事求是，這些通用的寄存器Register，確IT大佬們開(kāi)會(huì)討論后的結(jié)果是：eax,ecx,edx被劃入易失寄存scratchregister，需要由主保存動(dòng)作了，因?yàn)閷?xiě)內(nèi)存是有一定的時(shí)間開(kāi)銷(xiāo)ebx,esiedi被劃preserveregisters，需要由被調(diào)callee來(lái)保存，這意味著如果主調(diào)函數(shù)在保值寄存器中存放了有用的成原樣即可。而UCC編譯器使用了最簡(jiǎn)單的策略來(lái)管理“保值寄存器”，即在函數(shù)處不棧中逆序彈出(pop)。這就是我們?cè)?.5.21719push30prologue是序言的epilogue則是尾聲的意思。 "pushl%%ebp;pushl%%ebx;pushl%%esi;pushl%%edi;movl%%esp,%%ebp") "movl%%ebp,%%esp;popl%%edi;popl%%esi;popl%%ebx;popl當(dāng)一個(gè)C函數(shù)被調(diào)用時(shí)，我們需要在棧中為該函數(shù)分配一段內(nèi)存空間，我們需要記錄86bp和esp86153圖 棧示意pushebp,ebx,esiedi1.5.3ebp0,ebx0,esi0edi043行的movl指令可用于“內(nèi)存與寄存器”或“寄存器與寄存器”之間的數(shù)據(jù)傳遞，mov是8位操作的后綴”b”,long，wordbyte的縮寫(xiě)。嚴(yán)格說(shuō)來(lái)，32CPU的字stackpointer之意。第44行的sub指令是“substract”的縮寫(xiě)，相當(dāng)“esp-=4;”的計(jì)算，放”oWorld”的地址。UCC編譯器經(jīng)過(guò)優(yōu)化后，直接在第46行把”oWorld”的地址存指令就用于取”.str0”對(duì)應(yīng)靜態(tài)數(shù)據(jù)區(qū)的首地址，并存放到寄存器eax中。第47行的mov指令則把寄存器eax的數(shù)據(jù)傳送到全局變量str1中。這正是圖1.5.1中第12行C語(yǔ)句str1= popstrmain()中完成。有了這樣的基礎(chǔ)后，我們?cè)倩仡^去看圖1.5.2h()函數(shù)對(duì)應(yīng)的匯編代碼，就應(yīng)很有感覺(jué)了。當(dāng)h()函數(shù)成為當(dāng)前正在執(zhí)行的函數(shù)時(shí)，寄存器ebp會(huì)被設(shè)置到圖1.5.3的ebp2處，而ebp+20好是第一個(gè)形參str的地址，指令”movl20(%ebp),%eax”的含義是把ebp+20處的內(nèi)容傳遞到寄存器eax中。ebp-4則對(duì)h()中的局部變量str3，匯編指令”movl%eax,1.5.3所示。需要注意esppushlesp4操作，poplesp4。Call指令會(huì)把其下一條指令的地址（即函數(shù)返回地址）入棧，這相當(dāng)了esp減4的操作，而ret指令相當(dāng)于做了esp加4的出棧操作。下一節(jié)，我們將再寫(xiě)幾個(gè)簡(jiǎn)單的C程序，來(lái)解釋ucc\ucl\x86Linux.tpl中的其他匯編代碼。圖 main()匯編代整數(shù)運(yùn)讓我們還是從熟悉的加減乘除等算術(shù)運(yùn)算入手。圖1.5.5給出了一個(gè)簡(jiǎn)單的C程序，其CCUCC編譯器生成的匯編代.5141.5.6a111320b15始化的全局變量c；而第16行對(duì)應(yīng)的是沒(méi)有作初始化的靜態(tài)變量d，為避免重名，被UCC編譯器改名為”d.0”；而第17行對(duì)應(yīng)的是初始化為5的靜態(tài)變量e，被UCC編譯器重命名 變量a和b的global，這代表變量名a,b是在全局可見(jiàn)的，但e.1是靜態(tài)的，只在當(dāng)前文件中可見(jiàn)。按照C語(yǔ)言的語(yǔ)義，全局或靜態(tài)未初始化的變量其缺省值一般為0。在生成目標(biāo)文件(后綴為.obj或.o的文件)時(shí)，我們只需要在目標(biāo)模塊中記錄這塊要被初始化為0的空間有多大就可以，沒(méi)有必要把一堆的0存到目標(biāo)文件中。確切地說(shuō)，匯編代碼中第15行的”.comm”用于未初始化的全局變量，comm是common之意，代表這是一塊公共用地，即全局變量之意，而第16行的” m”則用于未初始化的靜態(tài)變量，lcomm是localcommon之意，只在本目標(biāo)模塊中可見(jiàn)。.5517C語(yǔ)言算術(shù)運(yùn)算所對(duì)應(yīng)的匯編代碼，如下圖1.5.7所示。圖1.5.7中的第3233行對(duì)應(yīng)“c=a|b;”,32行把a(bǔ)的值從內(nèi)存加eax33beaxeax34eaxc1.5.73549行所andl,shll,sarl,addl和subland，addsub對(duì)應(yīng)按位與、加和減運(yùn)shlShiftLeftsar和邏輯shr之分，sarShiftArithmeticRightshrShiftRight的縮寫(xiě)，兩者的區(qū)別是sar右移時(shí)最要用之前的符號(hào)位來(lái)填充，而shr右移時(shí)最補(bǔ)0。例如，以下f()g()則不會(huì)。原因是：a是有符號(hào)整數(shù)，Csar匯編指令來(lái)進(jìn)行移位操作，而a的值為-1，在內(nèi)存中以補(bǔ)碼形式存放時(shí)即為0xFFFFFFFF，算術(shù)右移后仍然是-1。而b為無(wú)符號(hào)整數(shù)，C編譯器會(huì)選擇shr來(lái)進(jìn)行邏輯右移，最補(bǔ)inta=-unsignedintb=0xFFFFFFFF;voidf(){while(a>>=}voidwhile(b>>=}圖 圖1.5.7中的第50至52對(duì)應(yīng)的是”ca*b，其中第51行的imul是有符號(hào)整數(shù)乘法signedmultiplemul5356行對(duì)應(yīng)的是”c=a/b;”，第word16CPUword2字節(jié)，48字節(jié)，x86edxeax8個(gè)字節(jié)當(dāng)成被除數(shù)，edx32eax32cdq指令后，edx32位的內(nèi)容都是eax的最。如果寄存器eax最為1，edx各bit全為1；否則全為0。不難想象，如果要作無(wú)符號(hào)數(shù)的除法，因?yàn)閑ax的最不再被當(dāng)作符號(hào)位，我們需要直接把edx寄存值賦值0，相x86Linux.tpl48所示： "movl$0,%%edx;divl1.5.755idivsigneddividediv則是無(wú)符號(hào)整數(shù)unsigneddivide。整數(shù)除法運(yùn)算的結(jié)果有兩部分，一部分是商，會(huì)被存放在寄存器eax中，如圖1.5.756行所示；另一部分是余數(shù)，會(huì)被存放在寄存器edx中。當(dāng)我們進(jìn)行”c=a%b;”的運(yùn)算時(shí)，就需要用到除法運(yùn)算的余數(shù)，如圖1.5.76164行所示。第57行的incincrement16567行對(duì)應(yīng)的是”ca;”，66negnegative的縮寫(xiě)，數(shù)學(xué)上是取相反數(shù)的意思，如果有符號(hào)數(shù)a為-1，即0xFFFFFFFF，經(jīng)過(guò)neg指令的處理后，就得到a的相反數(shù)1，即 68至70行對(duì)應(yīng)的是”c=~a;”，第69行的not指令用于按位取位，如果a為-1，則按位取反為得到的是0x 讓我們?cè)賮?lái)看一下C語(yǔ)言中的以下運(yùn)算符，如圖1.5.8UCC.821cmpa0，若不相等，則跳轉(zhuǎn)到基本塊”.BB2”處，如果相等，則執(zhí)行第24行的指令，而第23行在匯編中只是個(gè)標(biāo)號(hào)。而第34則跳轉(zhuǎn)到基本塊”.BB6”;否則(即a大于b)，則執(zhí)行第36行，作”c++;”的操作。常用的條件跳JumpifJumpifNotJumpif>Jumpif>Jumpif<Jumpif<JumpifGreaterorJumpifAboveorJumpifLessorJumpif or我們以0xFFFFFFFF和0x 為例，如果都視為有符號(hào)數(shù)，則補(bǔ)碼0xFFFFFFFF是-1，而0x 為0，此時(shí)有-1要小于0；但如果視為無(wú)符號(hào)數(shù)，則0xFFFFFFFF要大果要把這兩個(gè)數(shù)的比較當(dāng)作有符號(hào)整數(shù)之間的比較，則C編譯器在產(chǎn)生cmp指令后，需要選擇有符號(hào)數(shù)的條件跳轉(zhuǎn)指令，如JG,JL，JGE和JLE；而如果要當(dāng)作無(wú)符號(hào)整數(shù)之間的比較，則C編譯器在產(chǎn)生cmp指令后，需要選擇JA,JB,JAE和JBE等指令。如圖1.5.9所示，有被執(zhí)行。圖1.5.9第5行，我們進(jìn)行的是有符號(hào)整數(shù)之間的比較，此時(shí)-1大于0不成立；而第8行進(jìn)行的是無(wú)符號(hào)整數(shù)之間的比較，此時(shí)無(wú)符號(hào)數(shù)0xFFFFFFFF大于0是成立的；我1114signedintunsignedint之間二元運(yùn)算時(shí)，signedint會(huì)被提升unsignedint。我們很少會(huì)寫(xiě)出類(lèi)似圖1.5.9第11行這樣的代碼，但是如果一不就可能寫(xiě)出下1.5.10所示，運(yùn)行結(jié)果竟然是”-1>0”。因此，有符號(hào)整數(shù)與無(wú)符號(hào)整數(shù)還是盡量不要混合在一起處理，其結(jié)果可能出乎意料。由圖1.5.1022jbe指令可以發(fā)現(xiàn)，此處是把a(bǔ)a中的值始終都是0xFFFFFFFF。1.5.10oat和doueU點(diǎn)運(yùn)算一般都會(huì)由專(zhuān)門(mén)的浮點(diǎn)運(yùn)算來(lái)實(shí)現(xiàn)，例如In的x87，就是一個(gè)典型的FloatPointUnit，縮寫(xiě)為FPU，浮點(diǎn)運(yùn)算單元。在下一小節(jié)中，我們會(huì)討論一下UCC編譯器用到的x87浮點(diǎn)運(yùn)算指令。浮點(diǎn)數(shù)的算術(shù)運(yùn)執(zhí)行該程序，通過(guò)第9和第11行的輸出語(yǔ)句，我們會(huì)得到以下結(jié)果：iron@ubuntu:1.5$ucc-ofpufpu.ciron@ubuntu:1.5$./fpu 1.0f0x3f800000，這個(gè)值正是按照“IEEE754標(biāo)準(zhǔn)”單精度格式編碼的浮點(diǎn)數(shù)，對(duì)應(yīng)的十進(jìn)制值為。1.5.11ArchitecturesSoftwareDeveloper’sManualFigure8-2，我們可知x87內(nèi)部實(shí)際上提供了864double8Figure8-2所描述的寄存器棧，當(dāng)使fld1.5.1213x87棧頂寄存器和bfadd正是用于浮點(diǎn)數(shù)的加法，同樣，后綴”s”表示14fstpc所對(duì)應(yīng)的內(nèi)存單元，fstSToreFloatingpointvalueppop16fmuls則是用于單Figure8-行所示。我們還注意到，圖1.5.12第5行用于初始化變量a的值，正是我們面看到的。1.5.12浮點(diǎn)數(shù)運(yùn)算的匯編代圖15110CCaC87151225至36”87PUonol”自n手的ue86和e48ue86為87的onold過(guò)制87名onol其中ounnn 為87下e48的4C的是”Roundtowardzero”，即把超出精度的部分直接截?cái)?。這需要我們?cè)诟↑c(diǎn)運(yùn)算前對(duì)ControlWord寄存器進(jìn)行設(shè)置，同時(shí)我們期望此處的浮點(diǎn)運(yùn)算結(jié)束后，ControlWord寄存器的內(nèi)容能恢復(fù)到運(yùn)算前的樣子，這需要在內(nèi)存中先保存之前令字，同時(shí)，通過(guò)x87轉(zhuǎn)換得來(lái)的整數(shù)也需要作為一個(gè)臨時(shí)變量存放到內(nèi)存中。這正是第26至36行的代碼要完成的主要功能。圖1.5.12的第25行用于把浮點(diǎn)數(shù)a從內(nèi)存加載到x87中，第26行通過(guò)調(diào)整esp寄27fnstcwx8716Controlword存放到位于內(nèi)存的棧中(%esp)處，fnstcwunmaskedfloating-pointexceptions”，即不對(duì)浮點(diǎn)運(yùn)算異常進(jìn)行檢查。第28movzwl是MOVewithZero-extended的縮寫(xiě)，后綴”wl”16位的整數(shù)擴(kuò)展為32位的整數(shù)，相當(dāng)于1602831行用于設(shè)Figure8-6x87ControlWordRoundingControl位，該控制位用于指定浮點(diǎn)運(yùn)算“舍入”時(shí)的行為。第31行的fldcw指令用于從內(nèi)存中加載控制字到x87控制字寄存器中。第32fistpl指令實(shí)現(xiàn)了把x87棧頂寄存器中的浮點(diǎn)數(shù)轉(zhuǎn)換成32位整數(shù)的操作，fistSToreInteger的助記符，后綴”p”表示要轉(zhuǎn)換后要把x87棧頂寄存器出棧，而后綴”l”表示要把浮點(diǎn)數(shù)轉(zhuǎn)換成32位整數(shù)。第33行用于恢復(fù)浮點(diǎn)運(yùn)算34368(%esp)32d，并恢復(fù)esp指針。所以，實(shí)現(xiàn)浮點(diǎn)數(shù)轉(zhuǎn)換成整數(shù)功能的關(guān)鍵代碼是第32行。

1.5.13中的代碼為例。在浮點(diǎn)數(shù)的編碼中，IEEE754引入了一些特殊的編碼來(lái)表示正無(wú)窮大、負(fù)無(wú)窮大，因?yàn)橐粋€(gè)IEEE754也引入了一個(gè)稱為NotANumber的特殊編碼，用來(lái)表示這樣的運(yùn)算結(jié)果為“不是一個(gè)實(shí)數(shù)”，簡(jiǎn)寫(xiě)為NaN。圖 NaN和無(wú)窮大”-inf”，而第10打印出來(lái)的結(jié)果是正窮大”inf”，但第13行打印出來(lái)的結(jié)果是NaN。iron@ubuntu:1.5$gccnan.c-onan-lmiron@ubuntu:1.5$-iron@ubuntu:1.5$uccnan.c-onaniron@ubuntu:1.5$./nan-Table3-有了這個(gè)概念后，我們?cè)倥e一個(gè)浮點(diǎn)數(shù)比較的代碼，及其對(duì)應(yīng)的匯編代碼，如 數(shù)據(jù)寄存器中一般存放操作數(shù)，如Figure8-2x87數(shù)據(jù)寄存器棧，有時(shí)需要尋址念；狀態(tài)寄存器則反映了當(dāng)前所處的狀態(tài)，例如是否處于BUSY狀態(tài)。x86CPU內(nèi)我們有意忽EFLAGS寄存器中的標(biāo)志位這樣的細(xì)節(jié)，因?yàn)橥耆梢哉驹趨R編指令的語(yǔ)義上來(lái)理解有符號(hào)和無(wú)符號(hào)整數(shù)之間的比較，就如圖1.5.8和1.5.9之間的段落所述，如果需要做更深入理解，可查看InCPU手冊(cè)的“Figure3-8Eflags1.5.14浮點(diǎn)單元x87內(nèi)部也有相應(yīng)的狀態(tài)寄存器，如In手冊(cè)的Figure8-4所示。而浮點(diǎn)數(shù)之間比較后的結(jié)果主要由x87狀態(tài)寄存器的C0C2和C3Table3-31Figure8-1.5.141213abx87數(shù)據(jù)寄存器棧的棧頂。而14行則進(jìn)行處x87數(shù)據(jù)寄存器棧頂?shù)膬蓚€(gè)浮點(diǎn)數(shù)之間的比較，pp是COMpareFloatingpointvalues的助記符，后綴”pp”表示需要進(jìn)行兩次pop操作，即浮點(diǎn)數(shù)比15fnstswx87x8616ax中，ax32eax168ahax8位，fnstswSTorex87FPUStatusWord的助記符，其中”n”表示”withoutcheckingforpendingunmaskedfloating-pointexceptions”。第16行的test指令實(shí)際上進(jìn)行的是“按位與”運(yùn)算，而a位于st(1)Table3-31，我們可歸納為下表：“C2C00b>0偶b<1奇b==0偶2偶四種比較結(jié)果中，”b<a”即”a>b”1.5.1415test指令執(zhí)行之后，得到的“C2C0”0的位數(shù)為奇數(shù)個(gè)，由此我們就可以產(chǎn)生第17行的代碼jp.BB2”1”時(shí)，跳轉(zhuǎn)到基本塊”.BB2”4行的if條件成立，則執(zhí)行”c++;”的運(yùn)算。212422fildlLoaD的助記符，后綴”l”表示要加載的是321.5.14的代碼中解釋了比較(a>b)的情況，至于(ab)等其他比較操作對(duì)應(yīng)的匯編代碼可參X86Linux.tpl67107行。指針、數(shù)組和結(jié)構(gòu)CUCC1.5.15number[0]20150。UCC編譯器采取的翻譯方memsetnumber0number[0]設(shè)為20151.5.151724行所示。CmemsetAPI如下所示：void*memset(void*s,intc,size_tcs17行的$64nnumber所占的內(nèi)存c，表示我們要把指針s所指的大小為n字節(jié)的內(nèi)存全部設(shè)為019行用于取內(nèi)存單元-64(%ebp)20行把這個(gè)地址入棧，即對(duì)應(yīng)參數(shù)s，而-64(%ebp)所對(duì)應(yīng)的內(nèi)存空間正是UCC編譯器為局部數(shù)組number在棧中分配的空間。第21行完成了對(duì)庫(kù)函數(shù)而與10行”ptr&number[1];”對(duì)應(yīng)的匯編代碼為252725number[0]的地址存到寄eax中，因number[1]number[0]4字節(jié)，所26行到了ptr所對(duì)應(yīng)的內(nèi)存單元中。11行”*ptr=2016;”對(duì)應(yīng)的匯編代1.5.152930行，第29行通過(guò)movl指令把內(nèi)存單元ptr中存放的內(nèi)容傳送到寄存器ecx中，這樣ecx中存放的數(shù)據(jù)就是n