1、2022-3-161n編譯器編譯器n一個編譯程序就是一個語言翻譯程序，它把一種語言（稱作源語言）書寫的程序翻譯成另一種語言（稱作目標語言）書寫的等價的程序。第第1章章 編譯概述編譯概述2022-3-162n編譯的分析編譯的分析-綜合模型綜合模型n分析：分析源程序，計算其基本屬性，生成源程序的中間表示n綜合：將源程序的中間表示轉換為目標代碼第第1章章 編譯概述編譯概述2022-3-163n編譯的邏輯編譯的邏輯階段階段n詞法分析詞法分析n語法分析語法分析n語義分析語義分析n中間代碼生成中間代碼生成n代碼優化代碼優化n目標代碼生成目標代碼生成第第1章章 編譯概述編譯概述2022-3-164n* 符號

2、表管理n* 出錯處理第第1章章 編譯概述編譯概述2022-3-165n遍遍n對源程序或源程序中間表示的一次掃描，每一遍讀入一個文件，執行一個或幾個階段的編譯操作，并輸出源程序的一個中間表示n遍數多：編譯器結構清晰，但時間效率不高n遍數少：編譯速度快，但對機器的內存要求高第第1章章 編譯概述編譯概述2022-3-166n語言語言n某個字母表上的符號串的集合第第2章章 程序語言的基本知識程序語言的基本知識2022-3-167n文法文法 G 四元組（四元組（VT，VN，S，P）：）：n上下文無關文法上下文無關文法nA nA 第第2章章 程序語言的基本知識程序語言的基本知識2022-3-168n推導與

3、歸約推導與歸約n推導推導是用產生式的右部代替左部，歸約歸約是用產生式的左部代替右部，歸約是推導的逆過程第第2章章 程序語言的基本知識程序語言的基本知識2022-3-169n最左推導與最右推導最左推導與最右推導n最右歸約與最左歸約最右歸約與最左歸約第第2章章 程序語言的基本知識程序語言的基本知識2022-3-1610n句型句型 與與 句子句子n句型：從文法的開始符號出發進行零步或多于零步的推導得到的文法符號串n句型可以既包含終結符號又包含非終結符號，只包含終結符號的句型稱為句子第第2章章 程序語言的基本知識程序語言的基本知識2022-3-1611n語言語言的形式定義的形式定義n文法 G 推導出的

4、所有句子組成的集合，稱為語言語言，記為 L（G）第第2章章 程序語言的基本知識程序語言的基本知識2022-3-1612n句型的短語、直接短語和句型的短語、直接短語和句柄句柄n如果S A和A ，則稱是關于A的，句型的一個短語短語（子樹的葉子）*SA第第2章章 程序語言的基本知識程序語言的基本知識2022-3-1613n如果S A和 A =，則稱是關于 A的，句型的一個直接短語直接短語（只有父子兩代的子樹的葉子）*SA第第2章章 程序語言的基本知識程序語言的基本知識2022-3-1614n最左直接短語稱為句柄句柄n最左性體現在分析樹和句型中SA第第2章章 程序語言的基本知識程序語言的基本知識202

5、2-3-1615n句型的素短語、最左素短語1、是關于A的，句型的一個短語2、至少含有一個終結符3、除自身外不含更小的帶終結符的短語稱是關于A的，句型的一個素短語素短語n句型最左邊的素短語稱為最左素短語最左素短語第第2章章 程序語言的基本知識程序語言的基本知識2022-3-1616n句子、文法和語言的二義性句子、文法和語言的二義性n如果一個文法的句子有兩棵或兩棵以上的分析樹，稱此句子是二義句子是二義的n最左（右）推導與分析樹一一對應，句子二義說明它有兩個或以上最左（右）推導第第2章章 程序語言的基本知識程序語言的基本知識2022-3-1617n如果一個文法有一個句子是二義的，此文法稱為二義文法二

6、義文法n如果一個語言的所有文法都是二義的，稱此語言是二義的語言是二義的第第2章章 程序語言的基本知識程序語言的基本知識2022-3-1618n正規表達式正規表達式n正規表達式是一個表示字符串格式的模式n用來描述單詞符號的結構n遞歸定義遞歸定義第第3章章 詞法分析詞法分析2022-3-1619n有限自動機有限自動機n是具有離散輸入與離散輸出的一種數學模型n輸入：字符串n輸出：是、否n它能對輸入字符串是否屬于某個模式（正規集、正規語言）作出判斷第第3章章 詞法分析詞法分析2022-3-1620n非確定的有限自動機非確定的有限自動機 NFAnS 狀態集合狀態集合n 輸入符號集合輸入符號集合nmove

7、 轉換函數（轉換函數（S 2S）nS0 開始狀態開始狀態nF 接受狀態集合接受狀態集合第第3章章 詞法分析詞法分析2022-3-1621n確定的有限自動機確定的有限自動機 DFAn沒有邊轉移n一個狀態面臨一個輸入符號時最多只轉移到一個狀態第第3章章 詞法分析詞法分析2022-3-1622nNFA-DFA 的轉換的轉換 子集構造法子集構造法n從正規表達式構造從正規表達式構造 NFAnDFA 的化簡（最小化）的化簡（最小化）第第3章章 詞法分析詞法分析2022-3-1623n自頂向下分析：自頂向下分析：n從根到葉子來建立句子的分析樹n或，給出句子的一個從開始符號出發的推導序列第第4章章 語法分析語

8、法分析2022-3-1624n自底向上分析：自底向上分析：n從葉子到根來建立句子的分析樹n或，給出一個從句子出發到開始符號的歸約序列第第4章章 語法分析語法分析2022-3-1625n不確定的自頂向下分析：不確定的自頂向下分析：n帶回溯的分析方法n本質上是一種基于窮舉原理的試探方法一種基于窮舉原理的試探方法，是個反復使用不同的產生式謀求匹配輸入串的過程n不確定性體現在每次選擇的產生式不一定是每次選擇的產生式不一定是正確的正確的第第4章章 語法分析語法分析2022-3-1626n確定的自頂向下分析：確定的自頂向下分析：n基本思想：從文法的開始符號出發，根據當前的輸入符號輸入符號和其它信息其它信息

9、，唯一地確定選用哪條產生式往下推導，構造分析樹。n無論對錯，都沒有回溯第第4章章 語法分析語法分析2022-3-1627nFIRST集：集：nFOLLOW集：集：nSELECT集集n構造構造LL（1）分析表）分析表nLL（1）文法）文法第第4章章 語法分析語法分析2022-3-1628n提取左因子提取左因子n含有上面產生式的文法不是 LL（1）的，因為: SELECT（ A ） SELECT（ A ） n文法中可能含有形如：A | 的產生式第第4章章 語法分析語法分析2022-3-1629A 1 | 2 | 3 | | n A （1 | 2 | 3 | | n） A A A 1 | 2 | 3

10、 | | n第第4章章 語法分析語法分析2022-3-1630n消除左遞歸消除左遞歸n文法可能含有形如 A A | 的產生式或 A A的推導，稱為左遞歸文法左遞歸文法n左遞歸文法不是 LL（1）文法，第第4章章 語法分析語法分析2022-3-1631n自底向上分析法自底向上分析法，又稱為，又稱為移進移進-歸約法歸約法，它的實現思想：它的實現思想：n對輸入符號串自左向右進行掃描，并將輸入符逐個移入一個先進后出棧中，邊移進移進邊分析，一旦棧頂符號串形成某個句型的可歸約可歸約串串時，就用相應產生式的左部非終結符代替此可歸約串。重復這一過程，直到歸約到棧中只剩下文法的開始符號時分析成功。第第4章章 語

11、法分析語法分析2022-3-1632n算符優先分析的基本思想：算符優先分析的基本思想：n利用算符優先關系來尋找可歸約串n算符優先分析算符優先分析第第4章章 語法分析語法分析2022-3-1633nLR（k）分析技術：）分析技術：nL 指從左至右掃描輸入符號串nR 指構造一個最右推導的逆過程（最左歸約）nk 指在作出分析決定前要向前看的輸入符號個數，通常為 0 或 1nLR 分析技術是功能最強的（自底向上）語法分析技術，適用文法廣，效率高，分析能力強第第4章章 語法分析語法分析2022-3-1634nLR分析過程中的性質與特點：分析過程中的性質與特點：n棧中的文法符號串并上剩余的輸入串構成一個右

12、句型（規范句型）n當該右句型的句柄出現在棧頂時，歸約，否則，移進n棧中的文法符號串是當前句型的前綴，該前綴不包含句型句柄后面的符號，稱之為活前綴活前綴第第4章章 語法分析語法分析2022-3-1635n語義分析階段分析源程序的含義，并作相語義分析階段分析源程序的含義，并作相應的處理，語義分析的基本功能：應的處理，語義分析的基本功能：n確定類型確定類型n類型檢查類型檢查n產生中間代碼產生中間代碼n語義分析的主流技術語義分析的主流技術 語法制導翻譯語法制導翻譯技術技術第第5章章 語法制導翻譯語法制導翻譯2022-3-1636n文法符號的屬性：文法符號的屬性：1、綜合屬性綜合屬性：屬性值是分析樹中該

13、結點的子結點的屬性值的函數 2、繼承屬性繼承屬性：屬性值是分析樹中該結點的父結點和和/或或兄弟結點的屬性值的函數第第5章章 語法制導翻譯語法制導翻譯2022-3-1637n語法制導定義：語法制導定義：n為每一條產生式（A ）引入一套語義規則n規則形式：b := f (c1,c2,ck)第第5章章 語法制導翻譯語法制導翻譯2022-3-1638n語法制導翻譯語法制導翻譯:n根據語法分析中產生式對應的語義規則語義規則進行翻譯的方法稱為語法制導翻譯語法制導翻譯。第第5章章 語法制導翻譯語法制導翻譯2022-3-1639nS -屬性定義屬性定義n只含有綜合屬性的語法制導定義第第5章章 語法制導翻譯語法

14、制導翻譯2022-3-1640nL -屬性定義屬性定義n是一種語法制導定義n對于產生式 AX1X2Xn 右部 Xj 的繼承屬性，它依賴于：1、 X1，X2，Xj-1 （ Xj左邊的文法符號）的屬性2、A 的繼承屬性n* L-屬性定義包含 S-屬性定義第第5章章 語法制導翻譯語法制導翻譯2022-3-1641n翻譯模式：翻譯模式：n將語義規則放到 中，并插入到產生式右部的適當位置，以反映語義規則的計算順序，這種書寫形式稱之為翻譯模式翻譯模式第第5章章 語法制導翻譯語法制導翻譯2022-3-1642n從 L-屬性定義出發，構造一個滿足要求的翻譯模式n 將計算產生式右邊某文法符號的繼承屬性的語義規則

15、插入到此符號之前n將計算產生式左邊非終結符號綜合屬性的語義規則放在產生式右端的末尾第第5章章 語法制導翻譯語法制導翻譯2022-3-1643nL-屬性定義 深度優先翻譯 兩遍掃描nS-屬性定義 自底向上翻譯 一遍掃描第第5章章 語法制導翻譯語法制導翻譯2022-3-1644n三地址代碼三地址代碼n一般形式：x := y op zn一般含三個地址（名字、常數、臨時變量），兩個操作數，一個運算結果n中間代碼中間代碼第第7章章 中間代碼生成中間代碼生成2022-3-1645n根據給定語法制導定義，翻譯賦值語句、根據給定語法制導定義，翻譯賦值語句、布爾表達式、控制流語句等，得到中間代布爾表達式、控制流

16、語句等，得到中間代碼碼n參考例子，掌握方法第第7章章 中間代碼生成中間代碼生成2022-3-1646n代碼優化代碼優化n編譯時刻為改進目標程序的編譯時刻為改進目標程序的質量質量而進行的各而進行的各項工作項工作n與機器相關的優化與機器相關的優化n與機器無關的優化與機器無關的優化第第9章章 代碼優化代碼優化2022-3-1647n根據優化范圍根據優化范圍n局部優化 針對程序基本塊基本塊n循環優化 針對循環體n全局優化 針對整個程序第第9章章 代碼優化代碼優化2022-3-1648n名字的聯編n名字的左值左值 內存地址，存儲名字的瞬時值n名字的右值右值 名字的瞬時值n名字的聯編聯編 將一個內存地址與

17、一個名字聯系起來n在程序的一次運行中，一個名字右值（瞬時值）可能會經常改變，一個名字也可能被聯編到多個地址（如遞歸調用中）第第6章章 運行時刻環境的組織運行時刻環境的組織2022-3-1649n運行時刻內存的典型劃分運行時刻內存的典型劃分n操作系統收到運行目標程序的指令，分配一塊連續的內存空間使目標程序在其上運行n棧棧：支持過程的遞歸調用n堆堆：支持動態內存申請第第6章章 運行時刻環境的組織運行時刻環境的組織代碼代碼靜態數據靜態數據棧棧堆堆2022-3-1650n活動記錄活動記錄n是一段連續的存儲區，用以存放過程的一次執行所需要的信息，如局部數據第第6章章 運行時刻環境的組織運行時刻環境的組織2022-3-1651第第6章章 運行時刻環境的組織運行時刻環境的組織n參數域、狀態域、數據域返回的值返回的值臨時變量臨時變量實在參數實在參數控制鏈（可選擇的）控制鏈（可選擇的）存取鏈（可選擇的）存取鏈（可選擇的）保存的機器狀態保存的機器狀態局部數據局部數據TOPTOP_SP2022-3-1652n靜態存儲分配靜態存儲分配n動態存儲分配動態存儲分配棧式分配棧式分配 和 堆式分配堆式分配第第6章章 運行時刻環境的組織運行時刻環境的組織2022-3-1653n棧式存儲分配的思想：棧式存儲分配的思想：n在運行空間中劃分一塊存儲空間作為棧區n程序運行時每