《編譯原理》復習要點

1、考試安排：7月13日（20周周三），15：00-17:00,20208填空10X1分、選擇10X2分、簡答4X5分、大題5X10分考試大題：循環(huán)優(yōu)化 LL(1).定義之類的 算符優(yōu)先算法 自下而上分析法（20分，選擇、填空、大題）第一章 引論一編譯程序(compiler):把某一種高級語言程序等價地轉換成另一種低級語言程序(如匯編語言或機器語言程序)的程序二編譯程序的工作的五個階段:詞法分析、語法分析、中間代碼產生、優(yōu)化、目標代碼產生1. 詞法分析Pascal語言任務: 輸入源程序，對構成源程序的字符串進行掃描和分解，識別出一個個單詞符號。依循的原則：構詞規(guī)則描述工具：有限自動機FOR I :

2、= 1 TO 100 DO保留字 標識符 等符 整常數 保留字 整常數 保留字2. 語法分析任務:在詞法分析的基礎上，根據語言的語法規(guī)則把單詞符號串分解成各類語法單位。依循的原則：語法規(guī)則述工具：上下文無關文法3. 語義分析與中間代碼產生任務:對各類不同語法范疇按語言的語義進行初步翻譯。（變量是否定義、類型是否正確等）依循的原則：語義規(guī)則中間代碼:三元式，四元式，逆波蘭記號，樹形結構等。是一種獨立于具體硬件的記號系統(tǒng)。例：將Z:=X + 0.618 * Y 翻譯成四元式為(1) * 0.618 Y T1(2) + X T1 T2(3) := T2 _ Z4. 優(yōu)化任務：對于前階段產生的中間代碼

3、進行加工變換，以期在最后階段產生更高效的目標代碼。依循的原則：程序的等價變換規(guī)則FOR K:=1 TO 100 DO BEGIN M := I + 10 * K; N := J + 10 * K; END4. 目標代碼產生任務: 把中間代碼變換成特定機器上的目標代碼。依賴于硬件系統(tǒng)結構和機器指令的含義目標代碼三種形式:a) 絕對指令代碼: 可直接運行 b) 可重新定位指令代碼: 需要連接裝配c) 匯編指令代碼: 需要進行匯編三. 編譯程序結構u 編譯程序總框 (簡答題5分)第二章 高級語言及其語法描述2.1.1語法詞法規(guī)則：單詞符號的形成規(guī)則。a) 單詞符號是語言中具有獨立意義的最基本結構。一

4、般包括：常數、標識符、基本字、算符、界符等。b) 描述工具：正規(guī)式和有限自動機語法規(guī)則：語法單位的形成規(guī)則。a) 語法單位通常包括：表達式、語句、分程序、過程、函數、程序等;c) 描述工具：上下文無關文法2.1.2語義語義：一組規(guī)則，用它可以定義一個程序的意義。描述方法：a) 自然語言描述：隱藏錯誤、二義性和不完整性b) 形式描述：F 無二義性F 完整性多數語言中，算符的優(yōu)先順序如下：u 乘冪（*或）優(yōu)先級由高自低u 一元負（-）u 乘、除u 加、減不同的語言對算符優(yōu)先級的規(guī)定有差異，甚至差異很大！u 關系符（<,=,>,<=,>=,<>）u 非（¬

5、;，not）u 與(，&，and )u 或(,|,or,)u 隱含( 或imp)u 等值（ 或epui，或 ）2.3 程序語言的語法描述1. 幾個概念:a) 考慮一個有窮 字母表 字符集b) 其中每一個元素稱為一個字符c) 上的字(也叫字符串) 是指由中的字符所構成的一個有窮序列d) 不包含任何字符的序列稱為空字，記為e) 用*表示上的所有字的全體,包含空字例如: 設 =a， b，則 *=,a,b,aa,ab,ba,bb,aaa,.f) *的子集U和V的連接（積）定義為UV ab | aÎU & bÎV 例如: 設：U a, aa ,V b, bb 那么：U

6、V= ab, abb, aab, aabb g) V自身的 n次積記為Vn=VVVh) 規(guī)定V0=e，令V*=V0V1V2V3 稱V*是V的閉包;記 VVV* ，稱V+是V的正規(guī)閉包。例如: 設：U a, aa 那么：U* = e , a, aa, aaa, aaaa, U = a, aa, aaa, aaaa, i) 0型(短語文法，圖靈機)： 產生式形如： a ® b 其中：aÎ (VT È VN)*且至少含有一個非終結符；bÎ (VT È VN)* 任何0型語言都是遞歸可枚舉的。j) 1型(上下文有關文法，線性界限自動機)： 產生式形如：

7、 a ® b 其中：|a| £ |b|，僅 S®e 例外。意味著對非終結符進行替換時務必考慮上下文，并且，一般不允許替換成空串e 。k) 2型(上下文無關文法，非確定下推自動機)： 產生式形如： A ® b 其中：AÎ VN；bÎ (VT È VN)*。非終結符的替換可以不必考慮上下文。l) 3型(正規(guī)文法，有限自動機)：右線性文法 產生式形如： A ® aB 或 A ® a 其中： aÎ VT*；A，BÎVN左線性文法 產生式形如： A ® Ba 或 A ® a

8、其中： aÎ VT*；A，BÎVN正規(guī)文法的能力要比上下文無關文法弱得多。四種類型描述能力比較 m) 上下文無關文法的定義： 一個上下文無關文法G是一個四元式 G=(VT，VN，S，P)，其中VT：終結符集合(非空)VN：非終結符集合(非空)，且VT Ç VN=ÆS：文法的開始符號，SÎVNP：產生式集合(有限)，每個產生式形式為P®a， PÎVN， a Î (VT È VN)*開始符S至少必須在某個產生式的左部出現一次。例：文法G1(A)： A ® c|AbG1(A)的語言?解：L(G1)=c

9、，cb，cbb，¼，以c開頭，后繼若干個bn) 定義：如果一個文法存在某個句子對應兩顆不同的語法樹，則說這個文法是二義的。G(E)： E ® i|E+E|E*E|(E) 是二義文法。o) 語言的二義性：一個語言是二義性的，如果對它不存在無二義性的文法?？赡艽嬖贕和G，一個為二義的，一個為無二義的。但L(G)=L(G) 2. 狀態(tài)轉換圖 a) 概念：狀態(tài)轉換圖是一張有限方向圖。b) 結點代表狀態(tài)，用圓圈表示。c) 狀態(tài)之間用箭弧連結，箭弧上的標記(字符)代表射出結狀態(tài)下可能出現的輸入字符或字符類。d) 一張轉換圖只包含有限個狀態(tài)，其中有一個為初態(tài)，至少要有一個終態(tài)3. 正規(guī)運

10、算符優(yōu)先順序在不致混淆時，括號可以省去，但規(guī)定算符的優(yōu)先順序為：*（閉包） .（連接） |（或）4. 3型文法-正規(guī)式 G的任何產生式為 A ® aB 或 A ® a 其中： aÎ VT*；A，BÎVN 3型文法等價于正規(guī)式，所以也稱正規(guī)文法。3.3.2 確定有限自動機(DFA)對狀態(tài)圖進行形式化，則可以下定義：自動機M是一個五元式M=(S, S, f, S0, F),其中：a) S: 有窮狀態(tài)集，b) S：輸入字母表(有窮)，c) f: 狀態(tài)轉換函數，為S´S®S的單值部分映射，f(s，a)=s表示：當現行狀態(tài)為s，輸入字符為a時，

11、將狀態(tài)轉換到下一狀態(tài)s。我們把s稱為s的一個后繼狀態(tài)。d) S0ÎS是唯一的一個初態(tài)； e) FÍS ：終態(tài)集(可空)。例如：DFA M=(0，1，2，3，a，b，f，0，3)， 其中：f定義如下：f(0，a)=1f(0，b)=2f(1，a)=3 f(1，b)=2f(2，a)=1f(2，b)=3f(3，a)=3 f(3，b)=3 3.3.3 非確定有限自動機(NFA)定義：一個非確定有限自動機(NFA) M是一個五元式M=(S, S, f, S0, F)，其中：1 S: 有窮狀態(tài)集；2 S ：輸入字母表(有窮)；3 f: 狀態(tài)轉換函數，為S´S*®2S的

12、部分映射(非單值)；4 S0ÍS是非空的初態(tài)集；5 F ÍS ：終態(tài)集(可空)。從狀態(tài)圖中看NFA 和DFA的區(qū)別： 1 弧上的標記可以是S*中的一個字，而不一定是單個字符； 2 同一個字可能出現在同狀態(tài)射出的多條弧上。DFA是NFA的特例。定義：對于任何兩個有限自動機M和M，如果L(M)=L(M)，則稱M與M等價。自動機理論中一個重要的結論：判定兩個自動機等價性的算法是存在的。對于每個NFA M存在一個DFA M，使得 L(M)=L(M)。亦即DFA與NFA描述能力相同。把上述NFA確定化采用子集法.設I是M的狀態(tài)集的一個子集，定義I的e-閉包e-closure(I)為:

13、 i) 若sÎI，則sÎe-closure(I)； ii) 若sÎI，則從s出發(fā)經過任意條e弧而能到達的任何狀態(tài)s都屬于e-closure(I) 即 e-closure(I)=IÈs|從某個sÎI出發(fā)經過任意條e弧能到達s例：設a是S中的一個字符，定義 Ia= e-closure(J)其中，J為I中的某個狀態(tài)出發(fā)經過一條a弧而到達的狀態(tài)集合。 3.3.4 正規(guī)文法與有限自動機的等價性定理： 1.對每一個右線性正規(guī)文法G或左線性正規(guī)文法G，都存在一個有限自動機(FA) M，使得L(M)L(G)。2.對每一個FA M，都存在一個右線性正規(guī)文法GR和

14、左線性正規(guī)文法GL，使得L(M)L(GR)L(GL)。3.3.5 正規(guī)式與有限自動機的等價性定理： 1. 對任何FA M，都存在一個正規(guī)式r，使得L(r)=L(M)。 2. 對任何正規(guī)式r，都存在一個FA M，使得L(M)=L(r)。2 對轉換圖概念拓廣，令每條弧可用一個正規(guī)式作標記。(對一類輸入符號)3.3.6 確定有限自動機的化簡u 對DFA M的化簡:尋找一個狀態(tài)數比M少的DFA M，使得L(M)=L(M)u 假設s和t為M的兩個狀態(tài)，稱s和t等價:如果從狀態(tài)s出發(fā)能讀出某個字a而停止于終態(tài)，那么同樣，從t出發(fā)也能讀出a而停止于終態(tài)；反之亦然。u 兩個狀態(tài)不等價，則稱它們是可區(qū)別的。u

15、對一個DFA M最少化的基本思想: 把M的狀態(tài)集劃分為一些不相交的子集，使得任何兩個不同子集的狀態(tài)是可區(qū)別的，而同一子集的任何兩個狀態(tài)是等價的。最后，讓每個子集選出一個代表，同時消去其他狀態(tài)。I(1)=0, 1, 2 I(2)=3, 4, 5, 6 Ia(1) =1, 3 I(11) =0, 2 I(12) =1 I(2)=3, 4, 5, 6 I(11) =0, 2Ia(11) =1 Ib(11) =2, 5 I(111) =0 I(112) =2 I(12) =1 I(2)=3, 4, 5, 6 Ia(2) =3, 6 Ia(2) =4, 5 第四章 語法分析自上而下分析u 語法分析的方法

16、：u 自下而上分析法(Bottom-up)u 自上而下分析法(Top-down)u 基本思想：它從文法的開始符號出發(fā)，反復使用各種產生式，尋找"匹配"的推導。u 遞歸下降分析法：對每一語法變量(非終結符)構造一個相應的子程序，每個子程序識別一定的語法單位，通過子程序間的信息反饋和聯(lián)合作用實現對輸入串的識別。u 預測分析程序F 優(yōu)點：直觀、簡單和宜于手工實現。4.3 LL(1)分析法u 構造不帶回溯的自上而下分析算法u 要消除文法的左遞歸性u 克服回溯4.3.1 左遞歸的消除u 直接消除見諸于產生式中的左遞歸：假定關于非終結符P的規(guī)則為PPa | b 其中b不以P開頭。 我們

17、可以把P的規(guī)則等價地改寫為如下的非直接左遞歸形式：PbP¢左遞歸變右遞歸P¢aP¢|eu 一般而言，假定P關于的全部產生式是 PPa1 | Pa2 | | Pam | b1 | b2|bn其中，每個a都不等于e，每個b都不以P開頭 那么，消除P的直接左遞歸性就是把這些規(guī)則改寫成： Pb1P¢ | b2P¢ | | bnP¢ P¢a1P¢ | a2P¢ | | amP¢ | eu 提取公共左因子: 假定關于A的規(guī)則是 Adb 1 | db 2 | | db n | g 1 | g 2 | | gm

18、 (其中，每個g 不以d開頭) 那么，可以把這些規(guī)則改寫成AdA¢ | g 1 | g 2 | | g mA¢b 1 | b 2 | | b nu 經過反復提取左因子，就能夠把每個非終結符(包括新引進者)的所有候選首符集變成為兩兩不相交。4.3.3 LL(1)分析條件u 假定S是文法G的開始符號，對于G的任何非終結符A，我們定義特別是，若，則規(guī)定ÎFOLLOW(A)n 構造不帶回溯的自上而下分析的文法條件1. 文法不含左遞歸，2. 對于文法中每一個非終結符A的各個產生式的候選首符集兩兩不相交。即，若 Aa 1|a 2|a n 則 FIRST(a i)FIRST(a

19、 j)f (i¹j) i=1,2,.,n3. 對文法中的每個非終結符A，若它存在某個候選首符集包含e，則FIRST(A)FOLLOW(A)=f如果一個文法G滿足以上條件，則稱該文法G為LL(1)文法。第五章 語法分析自下而上分析語法分析的方法：自下而上分析法(Bottom-up)u 基本思想：從輸入串開始，逐步進行“歸約”，直到文法的開始符號。即從樹末端開始，構造語法樹。所謂歸約，是指根據文法的產生式規(guī)則，把產生式的右部替換成左部符號。u 算符優(yōu)先分析法：按照算符的優(yōu)先關系和結合性質進行語法分析。適合分析表達式。u LR分析法：規(guī)范歸約5.1.2 規(guī)范歸約1.定義：令G是一個文法，S

20、是文法的開始符號，假定abd是文法G的一個句型，如果有 且 ，則稱b是句型abd相對于非終結符A的短語。特別是，如果有AÞb,則稱b是句型abd相對于規(guī)則A® b的直接短語。一個句型的最左直接短語稱為該句型的句柄。2.歸約采用“移進歸約”思想進行自下而上分析?；舅枷耄河靡粋€寄存符號的先進后出棧，把輸入符號一個一個地移進到棧里，當棧頂形成某個產生式的候選式時，即把棧頂的這一部分替換成(歸約為)該產生式的左部符號。5.2 算符優(yōu)先分析u 四則運算的優(yōu)先規(guī)則： 先乘除后加減，同級從左到右u 考慮二義文法文法G(E)：G(E)： E ® i| E+E|E-E|E*E|E

21、/E|(E)u 它的句子有幾種不同的規(guī)范規(guī)約。u 歸約即計算表達式的值。歸約順序不同，則計算的順序也不同，結果也不一樣。u 如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進行歸約，則歸約過程是唯一的。u 起決定作用的是相鄰的兩個算符之間的優(yōu)先關系。u 所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關系，借助于這種關系尋找“可歸約串”和進行歸約。5.2.1 算符優(yōu)先文法及優(yōu)先表構造u 一個文法，如果它的任一產生式的右部都不含兩個相繼(并列)的非終結符，即不含如下形式的產生式右部：QR 則我們稱該文法為算符文法。u 約定：u a、b代表任意終結符；u P、Q、R代表任意非終結符；u 代表由終結符和非終結符組成

22、的任意序列，包括空字。u 假定G是一個不含e-產生式的算符文法。對于任何一對終結符a、b，我們說：1. a=b當且僅當文法G中含有形如Pab或PaQb的產生式；2. a<b當且僅當G中含有形如PaR的產生式， 而Rb或RQb；3. a>b 當且僅當G中含有形如PRb的產生式，而 Ra或RaQ。n 如果一個算符文法G中的任何終結符對(a，b)至多只滿足下述三關系之一：a=b，a<b， a>b。 則稱G是一個算符優(yōu)先文法。u 從算符優(yōu)先文法G構造優(yōu)先關系表的算法。u 通過檢查G的每個產生式的每個候選式，可找出所有滿足a=b的終結符對。u 確定滿足關系<和>的所有

23、終結符對：u 首先需要對G的每個非終結符P構造兩個集合FIRSTVT(P)和LASTVT(P)：a<b當且僅當G中含有形如PaR的產生式， 而Rb或RQb；a>b 當且僅當G中含有形如PRb的產生式，而 Ra或RaQ。q 有了這兩個集合之后，就可以通過檢查每個產生式的候選式確定滿足關系<和>的所有終結符對。Ø 假定有個產生式的一個候選形為aP 那么，對任何bÎFIRSTVT(P)，有 a<b。Ø 假定有個產生式的一個候選形為Pb 那么，對任何aÎLASTVT(P)，有 a>b。u 按其定義，可用下面兩條規(guī)則來構造集合F

24、IRSTVT(P)：1. 若有產生式Pa或PQa，則aÎFIRSTVT(P)；2. 若aÎFIRSTVT(Q)，且有產生式PQ，則aÎFIRSTVT(P)。練習：P133-2 計算它的FIRSTVT和LASTVT； 計算G的優(yōu)先關系 。并確定G是否是一個算符優(yōu)先文法？u LR分析方法：把"歷史"及"展望"綜合抽象成狀態(tài)；由棧頂的狀態(tài)和現行的輸入符號唯一確定每一步工作u LR分析器的核心是一張分析表：u ACTIONs，a：當狀態(tài)s面臨輸入符號a時，應采取什么動作.u GOTOs，X：狀態(tài)s面對文法符號X時，下一狀態(tài)是什么u

25、文法G的每個產生式的右部添加一個圓點稱為G的LR(0)項目例：如:A®XYZ有四個項目：A®.XYZ A®X.YZ A®XY.Z A®XYZ. F A®a . 稱為"歸約項目"F 歸約項目 S®a . 稱為"接受項目"F A®a .ab (aÎVT) 稱為"移進項目"F A®a .Bb (BÎVN) 稱為"待約項目".例：文法G(S¢) S¢E EaA|bB AcA|d BcB|d 該文

26、法的項目有：1.S¢·E 2.S¢E· 3.E·aA 4.Ea·A 5.EaA· 6.A·cA 7.Ac·A 8.AcA· 9.A·d 10.Ad· 11.E·bB 12.Eb·B 13.EbB· 14.B·cB 15.Bc·B 16.BcB· 17.B·d 18.Bd·u 構造識別文法所有活前綴的NFA方法 1. 若狀態(tài)i為X®X1 Xi-1.Xi Xn ，狀態(tài)j為X®X1

27、Xi-1Xi .Xi+1 Xn ，則從狀態(tài)i畫一條標志為Xi的有向邊到狀態(tài)j； 2. 若狀態(tài)i為X®a .Ab ，A為非終結符，則從狀態(tài)i畫一條e邊到所有狀態(tài)A®.g。u 把識別文法所有活前綴的NFA確定化。u 構成識別一個文法活前綴的DFA的項目集(狀態(tài))的全體稱為文法的LR(0)項目集規(guī)范族。LR(0)分析表的構造u 假若一個文法G的拓廣文法G¢的活前綴識別自動機中的每個狀態(tài)(項目集)不存在下述情況： 1) 既含移進項目又含歸約項目， 2) 含有多個歸約項目 則稱G是一個LR(0)文法。u 分析表的ACTION和GOTO子表構造方法：1. 若項目Aa·

28、;ab屬于Ik且GO(Ik, a)Ij，a為終結符，則置ACTIONk,a 為“sj”。2. 若項目Aa·屬于Ik，那么，對任何終結符a(或結束符#)，置ACTIONk,a為 “rj”(假定產生式Aa是文法G¢的第j個產生式)。3. 若項目S¢S·屬于Ik，則置ACTIONk,#為 “acc”。4. 若GO(Ik,A)Ij，A為非終結符，則置GOTOk,A=j。5. 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“報錯標志”。u 按上述方法構造出的ACTION與GOTO表如果不含多重入口，則稱該文法為SLR(1)文法。u 使用SLR表的分析器叫做一個S

29、LR分析器。u 每個SLR(1)文法都是無二義的。但也存在許多無二義文法不是SLR(1)的.I1、I2和I9都含有“移進歸約”沖突。FOLLOW(E)#, ), +，5.3.4 規(guī)范LR分析表的構造u 我們需要重新定義項目，使得每個項目都附帶有k個終結符。每個項目的一般形式是Aa·b, a1a2ak ，這樣的一個項目稱為一個LR(k)項目。項目中的 a1a2ak 稱為它的向前搜索符串(或展望串)。u 向前搜索符串僅對歸約項目Aa·，a1a2ak有意義。對于任何移進或待約項目Aa·b, a1a2ak, b¹e，搜索符串 a1a2ak 沒有作用。按上述算法構

30、造的分析表，若不存在多重定義的入口(即，動作沖突)的情形，則稱它是文法G的一張規(guī)范的LR(1)分析表。使用這種分析表的分析器叫做一個規(guī)范的LR分析器。具有規(guī)范的LR(1)分析表的文法稱為一個LR(1)文法。LR(1)狀態(tài)比SLR多，LR(0)ÌSLR Ì LR(1) Ì無二義文法。第六章 屬性文法和語法制導翻譯6.1 屬性文法u 屬性文法（也稱屬性翻譯文法）u 在上下文無關文法的基礎上，為每個文法符號（終結符或非終結符）配備若干相關的“值”（稱為屬性）。u 屬性代表與文法符號相關信息，如類型、值、代碼序列、符號表內容等u 屬性可以進行計算和傳遞u 語義規(guī)則：對于文

31、法的每個產生式都配備了一組屬性的計算規(guī)則u 屬性u 綜合屬性：“自下而上”傳遞信息u 繼承屬性：“自上而下”傳遞信息u 綜合屬性u 在語法樹中，一個結點的綜合屬性的值由其子結點的屬性值確定。u 使用自底向上的方法在每一個結點處使用語義規(guī)則計算綜合屬性的值u 僅僅使用綜合屬性的屬性文法稱S屬性文法u 繼承屬性u 在語法樹中，一個結點的繼承屬性由此結點的父結點和/或兄弟結點的某些屬性確定u 用繼承屬性來表示程序設計語言結構中的上下文依賴關系很方便6.2.3 一遍掃描的處理方法u 一遍掃描的處理方法是在語法分析的同時計算屬性值 u 所采用的語法分析方法u 屬性的計算次序u L屬性文法適合于一遍掃描的

32、自上而下分析u S屬性文法適合于一遍掃描的自下而上分析 6.4 L-屬性文法和自頂向下翻譯u 通過深度優(yōu)先的方法對語法樹進行遍歷，計算屬性文法的所有屬性值u LL(1)：自上而下分析方法，深度優(yōu)先建立語法樹第七章 語義分析和中間代碼產生u 靜態(tài)語義檢查u 類型檢查u 控制流檢查u 一致性檢查 u 相關名字檢查u 名字的作用域分析 7.1 中間語言u 常用的中間語言：u 后綴式，逆波蘭表示u 圖表示： DAG、抽象語法樹u 三地址代碼u 三元式u 四元式u 間接三元式u 逆波蘭表示法不用括號。只要知道每個算符的目數，對于后綴式，不論從哪一端進行掃描，都能對它進行唯一分解。u 后綴式的計算u 用一個棧實現。u 一般的計算過程是：自左至右掃描后綴式，每碰到運算量就把它推進棧。每碰到k目運算符就把它作用于棧頂的k個項，并用運算結果代替這k個項。7.4 布爾表達式的翻譯u 布爾表達式的兩個基本作用:u 用于邏輯演算,計算邏輯值;u 用于控制語句的條件式.u 產生布爾表達式的文法: EE or E | E andE | Ø E | (E) | i rop i | i第十章 優(yōu)化u 優(yōu)