編譯原理復(fù)習(xí)提綱

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

2、表管理n* 出錯(cuò)處理第第1章章 編譯概述編譯概述2022-3-165n遍遍n對(duì)源程序或源程序中間表示的一次掃描，每一遍讀入一個(gè)文件，執(zhí)行一個(gè)或幾個(gè)階段的編譯操作，并輸出源程序的一個(gè)中間表示n遍數(shù)多：編譯器結(jié)構(gòu)清晰，但時(shí)間效率不高n遍數(shù)少：編譯速度快，但對(duì)機(jī)器的內(nèi)存要求高第第1章章 編譯概述編譯概述2022-3-166n語(yǔ)言語(yǔ)言n某個(gè)字母表上的符號(hào)串的集合第第2章章 程序語(yǔ)言的基本知識(shí)程序語(yǔ)言的基本知識(shí)2022-3-167n文法文法 G 四元組（四元組（VT，VN，S，P）：）：n上下文無(wú)關(guān)文法上下文無(wú)關(guān)文法nA nA 第第2章章 程序語(yǔ)言的基本知識(shí)程序語(yǔ)言的基本知識(shí)2022-3-168n推導(dǎo)與

3、歸約推導(dǎo)與歸約n推導(dǎo)推導(dǎo)是用產(chǎn)生式的右部代替左部，歸約歸約是用產(chǎn)生式的左部代替右部，歸約是推導(dǎo)的逆過(guò)程第第2章章 程序語(yǔ)言的基本知識(shí)程序語(yǔ)言的基本知識(shí)2022-3-169n最左推導(dǎo)與最右推導(dǎo)最左推導(dǎo)與最右推導(dǎo)n最右歸約與最左歸約最右歸約與最左歸約第第2章章 程序語(yǔ)言的基本知識(shí)程序語(yǔ)言的基本知識(shí)2022-3-1610n句型句型 與與 句子句子n句型：從文法的開(kāi)始符號(hào)出發(fā)進(jìn)行零步或多于零步的推導(dǎo)得到的文法符號(hào)串n句型可以既包含終結(jié)符號(hào)又包含非終結(jié)符號(hào)，只包含終結(jié)符號(hào)的句型稱為句子第第2章章 程序語(yǔ)言的基本知識(shí)程序語(yǔ)言的基本知識(shí)2022-3-1611n語(yǔ)言語(yǔ)言的形式定義的形式定義n文法 G 推導(dǎo)出的

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

5、2-3-1615n句型的素短語(yǔ)、最左素短語(yǔ)1、是關(guān)于A的，句型的一個(gè)短語(yǔ)2、至少含有一個(gè)終結(jié)符3、除自身外不含更小的帶終結(jié)符的短語(yǔ)稱是關(guān)于A的，句型的一個(gè)素短語(yǔ)素短語(yǔ)n句型最左邊的素短語(yǔ)稱為最左素短語(yǔ)最左素短語(yǔ)第第2章章 程序語(yǔ)言的基本知識(shí)程序語(yǔ)言的基本知識(shí)2022-3-1616n句子、文法和語(yǔ)言的二義性句子、文法和語(yǔ)言的二義性n如果一個(gè)文法的句子有兩棵或兩棵以上的分析樹(shù)，稱此句子是二義句子是二義的n最左（右）推導(dǎo)與分析樹(shù)一一對(duì)應(yīng)，句子二義說(shuō)明它有兩個(gè)或以上最左（右）推導(dǎo)第第2章章 程序語(yǔ)言的基本知識(shí)程序語(yǔ)言的基本知識(shí)2022-3-1617n如果一個(gè)文法有一個(gè)句子是二義的，此文法稱為二義文法二

6、義文法n如果一個(gè)語(yǔ)言的所有文法都是二義的，稱此語(yǔ)言是二義的語(yǔ)言是二義的第第2章章 程序語(yǔ)言的基本知識(shí)程序語(yǔ)言的基本知識(shí)2022-3-1618n正規(guī)表達(dá)式正規(guī)表達(dá)式n正規(guī)表達(dá)式是一個(gè)表示字符串格式的模式n用來(lái)描述單詞符號(hào)的結(jié)構(gòu)n遞歸定義遞歸定義第第3章章 詞法分析詞法分析2022-3-1619n有限自動(dòng)機(jī)有限自動(dòng)機(jī)n是具有離散輸入與離散輸出的一種數(shù)學(xué)模型n輸入：字符串n輸出：是、否n它能對(duì)輸入字符串是否屬于某個(gè)模式（正規(guī)集、正規(guī)語(yǔ)言）作出判斷第第3章章 詞法分析詞法分析2022-3-1620n非確定的有限自動(dòng)機(jī)非確定的有限自動(dòng)機(jī) NFAnS 狀態(tài)集合狀態(tài)集合n 輸入符號(hào)集合輸入符號(hào)集合nmove

7、 轉(zhuǎn)換函數(shù)（轉(zhuǎn)換函數(shù)（S 2S）nS0 開(kāi)始狀態(tài)開(kāi)始狀態(tài)nF 接受狀態(tài)集合接受狀態(tài)集合第第3章章 詞法分析詞法分析2022-3-1621n確定的有限自動(dòng)機(jī)確定的有限自動(dòng)機(jī) DFAn沒(méi)有邊轉(zhuǎn)移n一個(gè)狀態(tài)面臨一個(gè)輸入符號(hào)時(shí)最多只轉(zhuǎn)移到一個(gè)狀態(tài)第第3章章 詞法分析詞法分析2022-3-1622nNFA-DFA 的轉(zhuǎn)換的轉(zhuǎn)換 子集構(gòu)造法子集構(gòu)造法n從正規(guī)表達(dá)式構(gòu)造從正規(guī)表達(dá)式構(gòu)造 NFAnDFA 的化簡(jiǎn)（最小化）的化簡(jiǎn)（最小化）第第3章章 詞法分析詞法分析2022-3-1623n自頂向下分析：自頂向下分析：n從根到葉子來(lái)建立句子的分析樹(shù)n或，給出句子的一個(gè)從開(kāi)始符號(hào)出發(fā)的推導(dǎo)序列第第4章章 語(yǔ)法分析語(yǔ)

8、法分析2022-3-1624n自底向上分析：自底向上分析：n從葉子到根來(lái)建立句子的分析樹(shù)n或，給出一個(gè)從句子出發(fā)到開(kāi)始符號(hào)的歸約序列第第4章章 語(yǔ)法分析語(yǔ)法分析2022-3-1625n不確定的自頂向下分析：不確定的自頂向下分析：n帶回溯的分析方法n本質(zhì)上是一種基于窮舉原理的試探方法一種基于窮舉原理的試探方法，是個(gè)反復(fù)使用不同的產(chǎn)生式謀求匹配輸入串的過(guò)程n不確定性體現(xiàn)在每次選擇的產(chǎn)生式不一定是每次選擇的產(chǎn)生式不一定是正確的正確的第第4章章 語(yǔ)法分析語(yǔ)法分析2022-3-1626n確定的自頂向下分析：確定的自頂向下分析：n基本思想：從文法的開(kāi)始符號(hào)出發(fā)，根據(jù)當(dāng)前的輸入符號(hào)輸入符號(hào)和其它信息其它信息

9、，唯一地確定選用哪條產(chǎn)生式往下推導(dǎo)，構(gòu)造分析樹(shù)。n無(wú)論對(duì)錯(cuò)，都沒(méi)有回溯第第4章章 語(yǔ)法分析語(yǔ)法分析2022-3-1627nFIRST集：集：nFOLLOW集：集：nSELECT集集n構(gòu)造構(gòu)造LL（1）分析表）分析表nLL（1）文法）文法第第4章章 語(yǔ)法分析語(yǔ)法分析2022-3-1628n提取左因子提取左因子n含有上面產(chǎn)生式的文法不是 LL（1）的，因?yàn)? SELECT（ A ） SELECT（ A ） n文法中可能含有形如：A | 的產(chǎn)生式第第4章章 語(yǔ)法分析語(yǔ)法分析2022-3-1629A 1 | 2 | 3 | | n A （1 | 2 | 3 | | n） A A A 1 | 2 | 3

10、 | | n第第4章章 語(yǔ)法分析語(yǔ)法分析2022-3-1630n消除左遞歸消除左遞歸n文法可能含有形如 A A | 的產(chǎn)生式或 A A的推導(dǎo)，稱為左遞歸文法左遞歸文法n左遞歸文法不是 LL（1）文法，第第4章章 語(yǔ)法分析語(yǔ)法分析2022-3-1631n自底向上分析法自底向上分析法，又稱為，又稱為移進(jìn)移進(jìn)-歸約法歸約法，它的實(shí)現(xiàn)思想：它的實(shí)現(xiàn)思想：n對(duì)輸入符號(hào)串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入一個(gè)先進(jìn)后出棧中，邊移進(jìn)移進(jìn)邊分析，一旦棧頂符號(hào)串形成某個(gè)句型的可歸約可歸約串串時(shí)，就用相應(yīng)產(chǎn)生式的左部非終結(jié)符代替此可歸約串。重復(fù)這一過(guò)程，直到歸約到棧中只剩下文法的開(kāi)始符號(hào)時(shí)分析成功。第第4章章 語(yǔ)

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

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

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

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

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

16、語(yǔ)句等，得到中間代碼碼n參考例子，掌握方法第第7章章 中間代碼生成中間代碼生成2022-3-1646n代碼優(yōu)化代碼優(yōu)化n編譯時(shí)刻為改進(jìn)目標(biāo)程序的編譯時(shí)刻為改進(jìn)目標(biāo)程序的質(zhì)量質(zhì)量而進(jìn)行的各而進(jìn)行的各項(xiàng)工作項(xiàng)工作n與機(jī)器相關(guān)的優(yōu)化與機(jī)器相關(guān)的優(yōu)化n與機(jī)器無(wú)關(guān)的優(yōu)化與機(jī)器無(wú)關(guān)的優(yōu)化第第9章章 代碼優(yōu)化代碼優(yōu)化2022-3-1647n根據(jù)優(yōu)化范圍根據(jù)優(yōu)化范圍n局部?jī)?yōu)化 針對(duì)程序基本塊基本塊n循環(huán)優(yōu)化 針對(duì)循環(huán)體n全局優(yōu)化 針對(duì)整個(gè)程序第第9章章 代碼優(yōu)化代碼優(yōu)化2022-3-1648n名字的聯(lián)編n名字的左值左值 內(nèi)存地址，存儲(chǔ)名字的瞬時(shí)值n名字的右值右值 名字的瞬時(shí)值n名字的聯(lián)編聯(lián)編 將一個(gè)內(nèi)存地址與

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