四川大學(xué)編譯原理復(fù)習(xí)要點(diǎn)

1、四川大學(xué)編譯原理復(fù)習(xí)要點(diǎn)2013 版1、編譯器各個(gè)階段的功能，輸入、輸出，前端、后端1） 詞法分析： 將字符序列收集到稱(chēng)作記號(hào)(t o k e n）的有意義單元中掃描程序輸入：源代碼輸出：記號(hào)2）語(yǔ)法分析： 從掃描程序中獲取記號(hào)形式的源代碼，并完成定義程序結(jié)構(gòu)的語(yǔ)法分析，語(yǔ)法分析定義了程序的結(jié)構(gòu)元素及其關(guān)系。輸入：記號(hào)輸出：語(yǔ)法樹(shù)3） 語(yǔ)義分析程序：分析程序的靜態(tài)語(yǔ)義，輸入：語(yǔ)法樹(shù)輸出：注釋樹(shù)包括聲明和類(lèi)型檢查。4） 源代碼優(yōu)化程序：編譯器通常包括許多代碼改進(jìn)或優(yōu)化步驟。絕大多數(shù)最早的優(yōu)化步驟是在語(yǔ)義分析之后完成的，而此時(shí)代碼改進(jìn)可能只依賴(lài)于源代碼?！緦?duì)源代碼進(jìn)行優(yōu)化，并產(chǎn)生中間代碼】輸入：注

2、釋樹(shù)輸出：中間代碼5） 目標(biāo)代碼生成：得到中間代碼，生成目標(biāo)機(jī)器的代碼代碼生成器輸入：中間代碼輸出：目標(biāo)代碼6） 目標(biāo)代碼優(yōu)化程序：編譯器改進(jìn)由代碼生成器生成的目標(biāo)代碼。輸入：目標(biāo)代碼輸出：目標(biāo)代碼掃描程序、分析程序和語(yǔ)義分析程序是前端，代碼生成器是后端，前后端分開(kāi)的好處：可以給編譯器帶來(lái)更方便的可移植性，此時(shí)的編譯器既能改變?cè)创a，又能改變目標(biāo)代碼?！颈椤烤幾g器發(fā)現(xiàn)，在生成代碼之前多次處理整個(gè)源程序很方便，這些重復(fù)就是遍。首遍是從源中構(gòu)造一個(gè)語(yǔ)法樹(shù)或中間代碼，在它之后的遍是由處理中間表示、向它增加信息、更換結(jié)構(gòu)或生成不同的表示組成二、 解釋器和編譯器的區(qū)別與聯(lián)系？讀入源語(yǔ)言后，解釋器和編譯器

3、都要進(jìn)行詞法分析、語(yǔ)法分析和語(yǔ)義分析，之后，二者開(kāi)始有所分別。解釋器在語(yǔ)義分析后選擇了直接執(zhí)行語(yǔ)句；編譯器在語(yǔ)義分析后選擇將將語(yǔ)義存儲(chǔ)成某一種中間語(yǔ)言，之后通過(guò)不同的后端翻譯成不同的機(jī)器語(yǔ)言（可執(zhí)行程序）編譯器是把源語(yǔ)言（如 C,Pascal，java 等高級(jí)語(yǔ)言）轉(zhuǎn)換為目標(biāo)語(yǔ)言（匯編語(yǔ)言、機(jī)器語(yǔ)言等低級(jí)語(yǔ)言），要產(chǎn)生目標(biāo)代碼。解釋器是以一個(gè)源語(yǔ)言（ C，Pascal，java 等高級(jí)語(yǔ)言）為輸入，一邊解釋一邊執(zhí)行源程序，但不產(chǎn)生目標(biāo)代碼。3、算法描述（偽代碼） p41構(gòu)造一個(gè)掃描程序的自動(dòng)過(guò)程：正則表達(dá)式NFA DFA程序1、正則表達(dá)式 NFA（ 1） 建立字母表。輸入的正則表達(dá)式由于一般不

4、輸入“與”操作符，因此首先給表達(dá)式加入 .作為與操作。再利用逆波蘭式的堆棧操作，把操作符與字母分開(kāi)，便得到了字母表。（ 2） Thompson 構(gòu)造法。首先將構(gòu)成正則表達(dá)式的各個(gè)元素分解，對(duì)于每一個(gè)元素，按照下述規(guī)則1 和規(guī)則 2 生成 NFA 。 注意：如果r 中記號(hào) a 出現(xiàn)了多次，那么對(duì)于 a 的每次出現(xiàn)都需要生成一個(gè)單獨(dú)的NFA 。2、NFADFA從單個(gè)輸入字符的某個(gè)狀態(tài)中去除 -轉(zhuǎn)換和多重轉(zhuǎn)換。（ 1）利用 -closure 規(guī)則即閉包規(guī)則，把 NFA 狀態(tài)劃分成集合，而后把每個(gè)集合作為 DFA 的狀態(tài)。詳細(xì)描述：從 NFA 的狀態(tài) S 開(kāi)始經(jīng)過(guò) 到達(dá)的狀態(tài)存儲(chǔ)下，然后再把存儲(chǔ)結(jié)果中

5、的狀態(tài)有經(jīng)過(guò) 到達(dá)的新?tīng)顟B(tài)也存儲(chǔ)在一起，這樣通過(guò)閉包規(guī)則就可以這些集合，再把集合作為 DFA 的狀態(tài)。（ 2）子集構(gòu)造3、DFA程序DFA 狀態(tài)最小化取出 DFA 狀態(tài)中的不可達(dá)的狀態(tài)。構(gòu)造最小狀態(tài)的等價(jià)DFA 的算法是通過(guò)創(chuàng)建統(tǒng)一到單個(gè)狀態(tài)的狀態(tài)集來(lái)進(jìn)行。構(gòu)造 NFA（使用 Thompson 結(jié)構(gòu)） :1) 基本正則表達(dá)式 基本正則表達(dá)式格式 a 或 ，其中 a 表示字母表中單個(gè)字符的匹配， 表示空串的匹配。與正則表達(dá)式a 等同的 N FA（即在其語(yǔ)言中準(zhǔn)確接受）的是：與 等同的 N FA 是：2) 并置我們希望構(gòu)造一個(gè)與正則表達(dá)式r s 等同的 N FA，其中 r 和 s 都是正則表達(dá)式。

6、可將與rs 對(duì)應(yīng)的 N FA 構(gòu)造如下：3) 在各選項(xiàng)中選擇我們希望在與前面相同的假設(shè)下構(gòu)造一個(gè)與r | s 相對(duì)應(yīng)的NFA。如下進(jìn)行：4) 重復(fù)我們需要構(gòu)造與r* 相對(duì)應(yīng)的機(jī)器，現(xiàn)假設(shè)已有一臺(tái)與r 相對(duì)應(yīng)的機(jī)器。那么就如下進(jìn)行：構(gòu)造 NFA的一個(gè)例子：例：根據(jù)Thompson 結(jié)構(gòu)將正則表達(dá)式 a b | a 翻譯為 N FA。首先為正則表達(dá)式 a和 b 分別構(gòu)造機(jī)器：接著再為并置ab 構(gòu)造機(jī)器：現(xiàn)在再為a 構(gòu)造另一個(gè)機(jī)器復(fù)件，并利用它們組成a b|a 完整的 N FA，如下圖：將 NFA轉(zhuǎn)換成 DFA（最小子集法） ： - 閉包（ - c l o s u r e）是可由 轉(zhuǎn)換從某狀態(tài)或某些

7、狀態(tài)達(dá)到的所有狀態(tài)集合，它總是包含狀態(tài)本身子集構(gòu)造相關(guān)題目：2.1 ，2.12 ， 2.16四、提左因子和消除左遞歸1、在建立 LL(1) 語(yǔ)法分析器的時(shí)候，提左因子和消除左遞歸的目的、原因目的：提取左因子 -避免程序回溯；消除左遞歸 -消除無(wú)限循環(huán)原因：當(dāng)有公因子存在時(shí)，不能立即區(qū)分出文法規(guī)則右邊的選擇；當(dāng)有左遞歸時(shí)，將導(dǎo)致一個(gè)無(wú)限循環(huán)。2、提左因子和消除左遞歸的算法描述消除左遞歸 偽代碼P119for i:=1 to for j:=1 tomdoi -1doreplaceeachgrammerrule choice of theform Ai Aj by the ruleAi , wher

8、e Aj 1 |2 |.|k1|2|.| kisthecurrent rule for Ajremove,if necessary,immediateleft recursioninvolving Aia) 把直接左遞歸改寫(xiě)為右遞歸【簡(jiǎn)單直接左遞歸】設(shè)有文法產(chǎn)生式： AA| 。其中 非空， 不以A 打頭。可寫(xiě)為： A A'A' A'|一般情況下，假定關(guān)于 A 的產(chǎn)生式是 【普遍的直接左遞歸】 AA 1| A 2 | |A m| 1| 2 | | n其中， i (1 i m)均不為空，j (1 j n) 均不以A 打頭。則消除直接左遞歸后改寫(xiě)為：A1A'|2A&#

9、39;| nA'A' 1A'| 2A'| mA'| 例 4.12 ：有文法 G(E)：EE +T|TTT*F |FFi|(E)消除該文法的直接左遞歸。解：按轉(zhuǎn)換規(guī)則, 可得 :ETE'E' +TE'| TFT 'T' *FT'| Fi|(E)b) 消除間接左遞歸 【一般的左遞歸， 不帶有 產(chǎn)生式且不帶有循環(huán)的文法】對(duì)于間接左遞歸的消除需要先將間接左遞歸變?yōu)橹苯幼筮f歸，然后再按a) 清除左遞歸。例 4.13 ：以文法 G6為例消除左遞歸：(1)A aB(2)A Bb(3)B Ac(4)B d解：用產(chǎn)生式 (1

10、) ，(2) 的右部代替產(chǎn)生式(3) 中的非終結(jié)A 得到左部為B 的產(chǎn)生式：(1)B aBc(2)B Bbc(3)B d消除左遞歸后得到：BaBcB'|dB'B' bcB'| 再把原來(lái)其余的產(chǎn)生式AaB,ABb 加入，最終得到等價(jià)文法為 :(1)AaB(2)ABb(3)B(aBc|d)B'(4)B' bcB'| c) 消除文法中一切左遞歸的算法設(shè)非終結(jié)符按某種規(guī)則排序?yàn)?A1， A2， ， An。For i =1tondobeginFor j =1toi-1dobegin若 Aj 的所有產(chǎn)生式為：Aj 1| 2 | n替換形如 Ai Aj

11、的產(chǎn)生式為：Ai 1 | 2 | nend消除 Ai 中的一切直接左遞歸end提取左因子偽代碼P122當(dāng)兩個(gè)或更多文法規(guī)則選擇共享一個(gè)通用前綴時(shí)，需要提取左因子：A|按如下規(guī)則提取左因子：AAA|、集合follow集合 算法偽代碼P126 P1315 first具體看書(shū)上的例子First 集合求法：1. 直接收?。簩?duì)形如 U a 的產(chǎn)生式（其中 a 是終結(jié)符），把 a 收入到 First(U) 中2.反復(fù)傳送：對(duì)形入U(xiǎn) P 的產(chǎn)生式（其中P 是非終結(jié)符），應(yīng)把 First(P) 中的全部?jī)?nèi)容傳送到 First(U) 中。Follow 集合求法：1.直接收?。鹤⒁猱a(chǎn)生式右部的每一個(gè)形如“ Ua

12、”的組合，把a(bǔ) 直接收入到Follow(U) 中。2直接收?。簩?duì)形如“ Follow(U) 中。UP ” (P 是非終結(jié)符)的組合，把First(P) 除 直接收入到3反復(fù)傳送：對(duì)形如P U 的產(chǎn)生式（其中U 是非終結(jié)符），應(yīng)把 Follow(P) 中的全部?jī)?nèi)容傳送到 Follow(U) 中。 (或P UB 且 First(B) 包含 ，則把 First(B) 除 直接收入到Follow(U) 中，并把Follow(P) 中的全部?jī)?nèi)容傳送到Follow(U) 中 )6、寫(xiě)遞歸下降子程序偽代碼遞歸下降：將一個(gè)非終結(jié)符的文法規(guī)則看作將識(shí)別的一個(gè)過(guò)程的定義一個(gè) if 語(yǔ)句（簡(jiǎn)化了的）文法規(guī)則是：if

13、 -stmt if (exp) statement|if (exp) statementelsestatement偽代碼：procedureifstmt；beginmatch （if ）；match（）；exp；match （）；statement；iftoken=elsethenmatch（ else）；statement；endif ；end ifstmt ；給出基于 DFA 進(jìn)行詞法分析的表驅(qū)動(dòng)的實(shí)現(xiàn)算法p44state:=1;ch:=nextinput character;while not acceptstateand not error(state) donewstate:=Tst

14、ate,ch；if advancestate,chthen ch:=next input chracter;State：=newstate；end while;if acceptstatethen accpet;7、上下文無(wú)關(guān)文法 BNF EBNF最左最右推導(dǎo)1、定義 ：上下文無(wú)關(guān)文法G 是一個(gè)四元組G = (N， T ，P， S)，其中N 是非終結(jié)符的有限集合；T 是終結(jié)符或單詞的有限集合，它與N 不相交；P 是形如 A 的產(chǎn)生式的有限集合，其中A N, V ,V=T NS 是 N 中的區(qū)分符號(hào)，稱(chēng)為開(kāi)始符號(hào)或句子符號(hào)。V 中的符號(hào)稱(chēng)為文法符號(hào)，包括終結(jié)符和非終結(jié)符。2、 Backus-Na

15、ur 符號(hào)（就是眾所周知的 BNF 或 Backus-Naur Form ）是描述語(yǔ)言的形式化的數(shù)學(xué)方法 ，由 John Backus (也許是 Peter Naur)開(kāi)發(fā)，用于描述 Algol 60 編程語(yǔ)言的語(yǔ)法。3、 EBNF （擴(kuò)展的 BNF ）使用花括號(hào) 表示重復(fù)，方括號(hào) .表示可選EBNF中注意重復(fù)和可選的表示方法，語(yǔ)法圖【可視的表示EBNF規(guī)則的圖形表示法】上下文無(wú)關(guān)文法說(shuō)明程序設(shè)計(jì)語(yǔ)言的語(yǔ)法結(jié)構(gòu)，利用了與正則表達(dá)式中極為類(lèi)似的命名慣例和運(yùn)算。二者的主要區(qū)別在于上下文無(wú)關(guān)文法的規(guī)則是遞歸的（recursive）最左推導(dǎo)（leftmost derivation ）是指它的每一步中最

16、左的非終結(jié)符都要被替換的推導(dǎo)最右推導(dǎo)（rightmost derivation ）則是指它的每一步中最右的非終結(jié)符都要被替換的推導(dǎo)。最左推導(dǎo)和與其相關(guān)的分析樹(shù)的內(nèi)部節(jié)點(diǎn)的前序編號(hào)相對(duì)應(yīng)；最右推導(dǎo)則和后序編號(hào)相對(duì)應(yīng)最右推導(dǎo)的一個(gè)例子：文法規(guī)則： exp expop exp | ( e x p)| n u m b e rop +| -| *分析樹(shù)與抽象語(yǔ)法樹(shù)有什么不同？對(duì)一個(gè)串按照某種文法進(jìn)行推導(dǎo)的過(guò)程 ，可以用一顆樹(shù)表示出來(lái)，這棵樹(shù)就是分析樹(shù)。分析樹(shù)是表示記號(hào)串結(jié)構(gòu)的一種十分有用的方法。抽象語(yǔ)法樹(shù)是真正的源代碼記號(hào)序列的抽象表示 ，包含了轉(zhuǎn)換所需的所有信息，而且 比分析樹(shù)效率更高。分析程序可以通

17、過(guò)一個(gè)分析樹(shù)表示所有步驟，但卻通常只能構(gòu)造出一個(gè)抽象的語(yǔ)法樹(shù)（或與它等同的）。8、記號(hào)類(lèi)型1、保留字，如 IF 何 THEN ，它們表示字符串“ if”和“then”2、特殊符號(hào)，如算數(shù)符號(hào)加（ PLUS）和減（ MINUS ），它們表示“+”“”3、表示多字符串的記號(hào)，如 NUM 和 ，它們分別表示數(shù)字和標(biāo)識(shí)符9、語(yǔ)言、句子、句型【語(yǔ)言】由推導(dǎo)從 exp 中得到的所有記號(hào)符號(hào)的串集是被表達(dá)式的文法定義的語(yǔ)言【句型】從文法起始符號(hào)出發(fā)經(jīng)過(guò)任意有限次推導(dǎo)出來(lái)的串【句子】 -的只有終結(jié)符的串10、自頂向下（第 4 章） 自底向上（第 5 章）區(qū)別：自頂向下語(yǔ)法分析：從文法的開(kāi)始符號(hào)出發(fā)，從頂部開(kāi)始

18、構(gòu)造語(yǔ)法分析樹(shù)。自底向上語(yǔ)法分析：從構(gòu)成語(yǔ)法分析樹(shù)的葉子節(jié)點(diǎn)的終結(jié)符號(hào)串開(kāi)始，從底部開(kāi)始構(gòu)造語(yǔ)法分析樹(shù)。1、自頂向下的分析算法通過(guò)在最左推導(dǎo)中描述出各步驟來(lái)分析記號(hào)串輸入從文法的開(kāi)始符號(hào)出發(fā)，從頂部開(kāi)始構(gòu)造語(yǔ)法分析樹(shù)。自頂向下的分析程序有兩類(lèi)：回溯分析程序、預(yù)測(cè)分析程序。兩類(lèi)自頂向下分析的算法：遞歸下降分析、LL （ 1）分析。LL(1) ：第一個(gè) L 指的是由左向右的處理輸入，第2 個(gè) L 指的是為輸入串描繪一個(gè)最左推導(dǎo)，括號(hào)里的1 表示僅使用輸入中的一個(gè)符號(hào)來(lái)預(yù)測(cè)分析的方向。P106-112遞歸下降：將一個(gè)非終結(jié)符的文法規(guī)則看作將識(shí)別的一個(gè)過(guò)程的定義First 集合 follow 集合LL(1) 文法的判斷及分析表2、自底向上 語(yǔ)法分析：從構(gòu)成語(yǔ)法分析樹(shù)的葉子節(jié)點(diǎn)的終結(jié)符號(hào)串開(kāi)始，從底部開(kāi)始構(gòu)造語(yǔ)法分析樹(shù)。自底向上分析法 也稱(chēng)移進(jìn) -規(guī)約分析法。思想：對(duì)輸入串自左向右進(jìn)行掃描，并將輸入符逐個(gè)移入棧中，邊移入邊分析，一旦棧頂符號(hào)形成某個(gè)句型的句柄或可規(guī)約串時(shí)，就用產(chǎn)生式左部的非終結(jié)符代替之；這稱(chēng)為一步規(guī)約。最普通的自底向上算法稱(chēng)作LR(1) 分析： L 表示自左向右處理輸入，R 表示生成了最右推導(dǎo)SLR（ 1）分析是對(duì)LR（ 1）分析的改進(jìn)LALR （ 1）比 SLR （1）略微強(qiáng)大且 比一般的LR （ 1）簡(jiǎn)單P153