《編譯原理與技術(shù)》講義編譯原理與技術(shù)

1、2022/7/12編譯原理與技術(shù)講義 1編譯原理與技術(shù)2022/7/12編譯原理與技術(shù)講義 2第一章 引論什么是編譯程序？翻譯程序、解釋程序和匯編程序編譯程序的組成結(jié)構(gòu)編譯程序的生成相關(guān)話題2022/7/12編譯原理與技術(shù)講義 3語言翻譯過程算法描述，求某整數(shù)n的階乘fact(n), n0 1 / n = 0 fact(n) = n * fact( n-1 ) / n! = n * (n-1)!偽語言描述fact(n) = if n 0 then 1 else n*fact(n-1)2022/7/12編譯原理與技術(shù)講義 4語言翻譯過程高級程序設(shè)計語言描述，（如C語言）int fact( int

2、 n )if (n 記號流 position = initial + rate * 60 字符流scanner id1 = id2 + id3 * 60 記號流 標(biāo)識符 賦值運算符 標(biāo)識符 加運算符 標(biāo)識符 乘運算符 整型常量2022/7/12編譯原理與技術(shù)講義 16編譯程序的組成結(jié)構(gòu)語法分析階段parser記號流 分析樹（語法樹） id1 = id2 + id3 * 60 記號流 parser=id1id2+*id360語法樹2022/7/12編譯原理與技術(shù)講義 17編譯程序的組成結(jié)構(gòu)語義分析語義樹帶有語義信息的分析樹（語法樹）id1id2+*id360=int float進(jìn)行類型轉(zhuǎn)換202

3、2/7/12編譯原理與技術(shù)講義 18編譯程序的組成結(jié)構(gòu)中間代碼生成形式多樣 三地址碼，p-code等t1 := int_to_float( 60 )t2 := id3 * t1t3 := id2 + t2id1 := t32022/7/12編譯原理與技術(shù)講義 19編譯程序的組成結(jié)構(gòu)代碼優(yōu)化得到“優(yōu)化”后的中間代碼；也可以在最后的代碼生成階段實施“優(yōu)化”t1 := rate * 60.0 / 直接用浮點數(shù)60.0position := initial + t1 / 去除多余的/ 臨時變量較優(yōu)化前，減少2條中間代碼2022/7/12編譯原理與技術(shù)講義 20編譯程序的組成結(jié)構(gòu)代碼生成與目標(biāo)機器有密切

4、聯(lián)系，如指令選擇，寄存器的使用等。movf rate, R1mulf #60.0, R1movf initial, R2addf R2, R1movf R1, position2022/7/12編譯原理與技術(shù)講義 21編譯程序的組成結(jié)構(gòu)符號表管理名稱類型positionfloatinitialfloatratefloat編譯程序中使用的符號表2022/7/12編譯原理與技術(shù)講義 22編譯程序的組成結(jié)構(gòu)出錯處理程序錯誤分類出錯處理的目標(biāo)與方法1) if ( n = 0 return 1; / missing “)”2) if ( n = 0 ) return 1 / missing “;” el

5、se return ( n * fact(n-1) );2022/7/12編譯原理與技術(shù)講義 23編譯程序的組成結(jié)構(gòu)semanticsparserscanneroptimizercode generator符號表管理出錯處理2022/7/12編譯原理與技術(shù)講義 24編譯程序生成手工編寫耗時，“效率”問題。自動生成 各個階段基本上有相應(yīng)的自動生成工具，如 lex、yacc。自展（bootstrapping)2022/7/12編譯原理與技術(shù)講義 25編譯程序生成編譯程序的自展/自編譯T型圖S T I源語言S目標(biāo)語言T編譯程序的實現(xiàn)語言I2022/7/12編譯原理與技術(shù)講義 26編譯程序生成編譯程序

6、的自展/自編譯 我們的目標(biāo)是在機器A（目標(biāo)語言）上，用語言A（實現(xiàn)語言）構(gòu)造高級語言L（源語言）的編譯程序。L A A2022/7/12編譯原理與技術(shù)講義 27編譯程序生成編譯程序的自展/自編譯 Step1: 我們可以考慮源語言L的子集語言S, S L。在機器A（目標(biāo)語言）上，用語言A（實現(xiàn)語言）構(gòu)造語言S的編譯程序。S A A2022/7/12編譯原理與技術(shù)講義 28編譯程序生成編譯程序的自展/自編譯 Step2: 在機器A（目標(biāo)語言）上，用語言S（實現(xiàn)語言）構(gòu)造語言L的編譯程序。L A S2022/7/12編譯原理與技術(shù)講義 29編譯程序生成編譯程序的自展/自編譯 Step3: L A S

7、S A AL A A2022/7/12編譯原理與技術(shù)講義 30編譯程序生成編譯程序的移植/交叉編譯考慮將A機器上語言L的編譯實現(xiàn)移植到機器B上，即我們的目標(biāo)是：L B B2022/7/12編譯原理與技術(shù)講義 31編譯程序生成編譯程序的移植/交叉編譯我們已有的編譯程序是：L A A2022/7/12編譯原理與技術(shù)講義 32編譯程序生成編譯程序的移植/交叉編譯Step1:L B LL A AL B A用語言L編寫的語言L到語言B的編譯程序借助已有的A機器上語言L的編譯程序得到機器A上（實現(xiàn)語言）語言L到語言B的編譯程序2022/7/12編譯原理與技術(shù)講義 33編譯程序生成編譯程序的移植/交叉編譯Step2:L B LL B AL B B用語言L編寫的語言L到語言B的編譯程序新的A機器上語言L到語言B的編譯程序得到機器B上（實現(xiàn)語言）語言L到語言B的編譯程序2022/7/12編譯原理與技術(shù)講義 34編譯程序相關(guān)的軟件預(yù)處理程序preprocessor宏替換macro包含文件展開include files匯編程序assembler