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

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

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

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

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

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

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

7、狀態(tài)達到的所有狀態(tài)集合，它總是包含狀態(tài)本身子集構(gòu)造相關(guān)題目：2.1 ，2.12 ， 2.16四、提左因子和消除左遞歸1、在建立 LL(1) 語法分析器的時候，提左因子和消除左遞歸的目的、原因目的：提取左因子 -避免程序回溯；消除左遞歸 -消除無限循環(huán)原因：當有公因子存在時，不能立即區(qū)分出文法規(guī)則右邊的選擇；當有左遞歸時，將導(dǎo)致一個無限循環(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) 把直接左遞歸改寫為右遞歸【簡單直接左遞歸】設(shè)有文法產(chǎn)生式： AA| 。其中 非空， 不以A 打頭?？蓪憺椋?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 打頭。則消除直接左遞歸后改寫為：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)的文法】對于間接左遞歸的消除需要先將間接左遞歸變?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'| 再把原來其余的產(chǎn)生式AaB,ABb 加入，最終得到等價文法為 :(1)AaB(2)ABb(3)B(aBc|d)B'(4)B' bcB'| c) 消除文法中一切左遞歸的算法設(shè)非終結(jié)符按某種規(guī)則排序為 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當兩個或更多文法規(guī)則選擇共享一個通用前綴時，需要提取左因子：A|按如下規(guī)則提取左因子：AAA|、集合follow集合 算法偽代碼P126 P1315 first具體看書上的例子First 集合求法：1. 直接收取：對形如 U a 的產(chǎn)生式（其中 a 是終結(jié)符），把 a 收入到 First(U) 中2.反復(fù)傳送：對形入U P 的產(chǎn)生式（其中P 是非終結(jié)符），應(yīng)把 First(P) 中的全部內(nèi)容傳送到 First(U) 中。Follow 集合求法：1.直接收?。鹤⒁猱a(chǎn)生式右部的每一個形如“ Ua

12、”的組合，把a 直接收入到Follow(U) 中。2直接收?。簩π稳纭?Follow(U) 中。UP ” (P 是非終結(jié)符)的組合，把First(P) 除 直接收入到3反復(fù)傳送：對形如P U 的產(chǎn)生式（其中U 是非終結(jié)符），應(yīng)把 Follow(P) 中的全部內(nèi)容傳送到 Follow(U) 中。 (或P UB 且 First(B) 包含 ，則把 First(B) 除 直接收入到Follow(U) 中，并把Follow(P) 中的全部內(nèi)容傳送到Follow(U) 中 )6、寫遞歸下降子程序偽代碼遞歸下降：將一個非終結(jié)符的文法規(guī)則看作將識別的一個過程的定義一個 if 語句（簡化了的）文法規(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 進行詞法分析的表驅(qū)動的實現(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、上下文無關(guān)文法 BNF EBNF最左最右推導(dǎo)1、定義 ：上下文無關(guān)文法G 是一個四元組G = (N， T ，P， S)，其中N 是非終結(jié)符的有限集合；T 是終結(jié)符或單詞的有限集合，它與N 不相交；P 是形如 A 的產(chǎn)生式的有限集合，其中A N, V ,V=T NS 是 N 中的區(qū)分符號，稱為開始符號或句子符號。V 中的符號稱為文法符號，包括終結(jié)符和非終結(jié)符。2、 Backus-Na

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

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

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

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