編譯原理知識(shí)點(diǎn)

1、1. 解釋程序：不生成目標(biāo)代碼編譯程序：生成目標(biāo)代碼2. 編譯程序組成：8個(gè)分析< 前端 >：(詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序)綜合< 后端 >：（代碼優(yōu)化程序、目標(biāo)代碼生成程序）貫穿始末：表格管理程序、出錯(cuò)處理程序3. 文法四元組：終結(jié)符號(hào)集合Vt 、非終結(jié)符號(hào)集合Vn、 產(chǎn)生式集合P、識(shí)別符號(hào)(開始符號(hào))SVTVN文法 -> 語言 （推導(dǎo)、規(guī)約）唯一； 語言 -> 文法 （湊規(guī)則）不唯一。4. 文法分類：0型文法(短語結(jié)構(gòu)文法)：左側(cè)至少含有一個(gè)非終結(jié)符1型文法(上下文有關(guān)文法)：左側(cè)長度 <= 右側(cè)長度 S->除

2、外， S不能出現(xiàn)在右側(cè)2型文法(上下文無關(guān)文法)：左側(cè)只能有一個(gè)非終結(jié)符 ( 語法分析 ) 3型文法(正規(guī)文法)：A-> aB A->a 右線性； ( 詞法分析 ) A->Ba 或A->a 左線性（看非終結(jié)符位置） 5. A* A0 A+ A0 != 空集A+ AA* A*A 6. 句型：符號(hào)串x是從識(shí)別符號(hào)S推導(dǎo)出來的，x稱為一個(gè)句型句子：x僅由終結(jié)符號(hào)組成，僅含終結(jié)符號(hào)的句型是一個(gè)句子短語：子樹的末端（葉子）從左至右連成的串（包括整棵語法樹）簡單子樹：只含有單層分枝的子樹直接短語( 簡單短語 )：由簡單子樹的葉子組成 句柄：最左邊的直接短語（不一定含終結(jié)符）素短語：

3、至少含有一個(gè)終結(jié)符的短語，并且除它自身之外不再含任何更小的素短語最左素短語：最左邊的素短語短語：P（相對(duì)于T、E）、 P+T（相對(duì)于E）、i（相對(duì)于P、F）、P+T+i（相對(duì)于E）直接短語：P、i 句柄：P (最左邊的直接短語)素短語：P+T 、i （至少含有一個(gè)終結(jié)符的短語） 最左素短語：P+T7. 二義性文法：有兩個(gè)不同的最左推導(dǎo)或有兩個(gè)不同的最右推導(dǎo)或能產(chǎn)生兩棵語法樹8. 文法產(chǎn)生式 正規(guī)式 規(guī)則1 A®xB B®y A = xy 規(guī)則2 A®xA|y A = x*y 右線性A®Ax|y A = yx* 左線性 規(guī)則3 A®x A

4、4;y A = x|y9. DFA 初態(tài)唯一，轉(zhuǎn)換函數(shù)為單值映射表示方式：轉(zhuǎn)移矩陣、狀態(tài)轉(zhuǎn)換圖 狀態(tài)轉(zhuǎn)換圖上若存在一條從初態(tài)到某一終態(tài)的道路，且這條路上所有弧的標(biāo)記符連成的字符串為t，則稱t被DFA接受。10. NFA初態(tài)可為多個(gè)，轉(zhuǎn)換函數(shù)為多值映射確定化：與某一NFA等價(jià)的DFA不唯一1.狀態(tài)集合I的-閉包2.move函數(shù)最小化：消除多余狀態(tài)和合并等價(jià)狀態(tài)多余狀態(tài)：從自動(dòng)機(jī)的開始狀態(tài)出發(fā)，任何輸入串也不能到達(dá)的那個(gè)狀態(tài)；或者從這個(gè)狀態(tài)沒有通路到達(dá)終態(tài)。 11. 左公因子顯式左公因子提取若Aab1|ar，則將其改寫為： i. Aa(b1|r)ii. 或引入新非終結(jié)符 AaA Ab1|r隱式左公

5、因子:產(chǎn)生式右部以非終結(jié)符開始用該非終結(jié)符的右部以終結(jié)符開始的產(chǎn)生式去替換它，再提取SaSd|Ac AaS|b把A的產(chǎn)生式代入S中： SaSd|aSc|bcSaS S S d|c Sbc12. 左遞歸1.簡單左遞歸：消除左遞歸改寫為右遞歸 AAa|b AbA AaA|2.間接左遞歸非終結(jié)符號(hào)排序(出現(xiàn)頻率高的排后面)左部非終結(jié)符下標(biāo) > 右部時(shí)改寫（替換右部）消除直接左遞歸 13. 自頂向下：LL（1） FIRST：A® X1X2X3Xn 若X1 Þ X2 Þ X3 !Þ 后面不用管則FIRST（A）= First（X1）- U First（X2）

6、- First（X3） 若全能推出 則先求所有FIRIST（X）-并集 再并上FOLLOW： (a)設(shè)S為開始符號(hào)，則#FOLLOW(S) (b)若有產(chǎn)生式A® aBb， b !Þ* ，則FIRST() 加至FOLLOW(B) (c)若b Þ* (即eÎFIRST()），則FIRST(b)-和FOLLOW(A)加至FOLLOW(B) SELECT：A® a的可選集SELECT *a !Þ，則SELECT(A®a)= FIRST(a) *aÞ，則SELECT(A®a)= FIRST(a)- FOLLOW(A

7、) 一個(gè)上下文無關(guān)文法G是LL(1)文法的充要條件是：對(duì)于G的每個(gè)非終結(jié)符號(hào)A的任何兩個(gè)不同產(chǎn)生式 A，A滿足：§ SELECT(A)SELECT(A)=Ƨ 、不同時(shí)推導(dǎo)出LL（1）的含義：第一個(gè)L：從左到右掃描輸入串 第二個(gè)L：分析過程中用最左推導(dǎo) 1：只需向右看1個(gè)輸入符號(hào)（Look ahead)便可確定選用哪個(gè)產(chǎn)生式進(jìn)行推導(dǎo) LL(1)文法是無二義的。 LL(1)文法不含左遞歸。14. 自底向上：算符優(yōu)先、LR（0）、SLR（1）、LR（1）、LALR（1）15. 規(guī)范歸約：最右推導(dǎo)的逆過程(最左歸約） 最右推導(dǎo)是規(guī)范推導(dǎo) 右句型(最右推導(dǎo)可得的句型）是規(guī)

8、范句型 規(guī)范句型的特點(diǎn)：句柄后（右邊）不會(huì)出現(xiàn)非終結(jié)符 規(guī)范歸約的中心問題是：如何尋找或確定一個(gè)句型的句柄 。 可歸約串： 最左素短語(算符優(yōu)先分析法） 句柄(LR分析法)算符優(yōu)先分析法不是規(guī)范歸約方法。16. 若文法G中不存在右部含有相鄰非終結(jié)符的產(chǎn)生式，則G為算符文法算符優(yōu)先分析的可歸約串是句型的最左素短語。起決定作用的是相鄰兩個(gè)終結(jié)符的優(yōu)先關(guān)系ab 當(dāng)且僅當(dāng)G中存在產(chǎn)生式規(guī)則 Aàab，或AàaBba<×b 當(dāng)且僅當(dāng)G中存在產(chǎn)生式規(guī)則AàaB，且BÞ+b或 BÞ+Cb a×>b 當(dāng)且僅當(dāng)G中存在產(chǎn)

9、生式規(guī)則AàBb，且BÞ+a或 BÞ+aC不允許有a<·b、ab、a·>b中的兩種關(guān)系同時(shí)存在17. FIRSTVT計(jì)算如下：若有產(chǎn)生式A®a或A®Ba 則aÎFIRSTVT(A) A左側(cè)的終結(jié)符 < FIRSTVT(A) 若aÎFIRSTVT(B)且有產(chǎn)生式A®B(B后面沒有緊跟一個(gè)終結(jié)符)則aÎFIRSTVT(A) A->a.，即以終結(jié)符開頭，該終結(jié)符入FirstvtA->B.，即以非終結(jié)符開頭，該非終結(jié)符的Firstvt入A的FirstvtA->

10、;Ba.，即先以非終結(jié)符開頭，緊跟終結(jié)符，則終結(jié)符入FirstvtLASTVT計(jì)算如下：若有產(chǎn)生式A®a或A®aB則aÎLASTVT(A) A右側(cè)的終結(jié)符 < LASTVT (A) 若aÎLASTVT(B)且有產(chǎn)生式A®B則aÎLASTVT(A)A->.a，即以終結(jié)符結(jié)尾，該終結(jié)符入LastvtA->.B，即以非終結(jié)符結(jié)尾，該非終結(jié)符的Lastvt入A的LastvtA->.aB，即先以非終結(jié)符結(jié)尾，前面是終結(jié)符，則終結(jié)符入Lastvt18. LR分析法的歸約過程是規(guī)范推導(dǎo)的逆過程，所以LR分析過程是一種規(guī)范歸約

11、過程無回溯的“移進(jìn)-歸約”方法符號(hào)棧中的符號(hào)是規(guī)范句型的前綴，且不含句柄以后的任何符號(hào)(活前綴) ACTION 移進(jìn) 歸約 接受 出錯(cuò) ACTIONi,a=空白 出錯(cuò) ACTIONi,a=acc 符號(hào)棧中僅有#和文法開始符號(hào)S，輸入串僅為#，分析結(jié)束。19. 一個(gè)句型的某個(gè)前綴的后綴是該句型的句柄，則這個(gè)前綴稱為該句型的可歸前綴。一個(gè)規(guī)范句型的一個(gè)前綴，若不含句柄之后的任何符號(hào)，則稱它為該句型的一個(gè)活前綴。S -> a Ac. B e 項(xiàng)目中 .之前a Ac為活前綴20. A® a × ab,aÎVT 移進(jìn)項(xiàng)目A® a × Bb,B

12、06;VN 待歸約項(xiàng)目A® a × 歸約項(xiàng)目特別地：A®e 只有 A® ×S®S, S®S × 接受項(xiàng)目以上項(xiàng)目稱作LR(0)項(xiàng)目。21. LR(0) 項(xiàng)目集規(guī)范族（識(shí)別G的活前綴的DFA)如果不存在移進(jìn)-歸約沖突，歸約-歸約沖突，則稱它是LR(0)文法。拓展文法的目的：使文法只有一個(gè)以識(shí)別符號(hào)作為左部的產(chǎn)生式，從而使構(gòu)造出來的分析器有唯一的接受狀態(tài)。22. 對(duì)給定的文法，利用LR(0)方法判斷符號(hào)串是否為該文法的句子：1.擴(kuò)充文法為拓廣文法；2.構(gòu)造識(shí)別此文法的全部活前綴的DFA，即構(gòu)造LR(0)項(xiàng)目集規(guī)范族；3

13、.判斷是否為LR(0)文法；4.是 構(gòu)造LR(0)分析表 利用LR分析算法分析符號(hào)串。5.否，做其他處理。23. SLR（1）對(duì)所有非終結(jié)符都求出其FOLLOW集合發(fā)生沖突時(shí)，歸約項(xiàng)目左部終結(jié)符FOLLOW集與移進(jìn)項(xiàng)目 .后的終結(jié)符交集為空時(shí)，才能按此規(guī)約項(xiàng)目的產(chǎn)生式進(jìn)行歸約。 LR(0)分析對(duì)所有終結(jié)符均采用歸約動(dòng)作 SLR(1)分析參考FOLLOW集，以確定歸約動(dòng)作。24. Follow集無法解決 移進(jìn)-歸約沖突或歸約-歸約沖突，考慮后繼符25. 歸約動(dòng)作的選擇：a) LR(0)分析考慮所有終結(jié)符b) SLR(1)分析參考 FOLLOW 集，為了確定歸約c) LR(1)分析僅考慮 LR(1

14、)項(xiàng)目中的后繼符（歸約展望集，向前搜索符）拓展文法的后繼符為#，即 S->S , # 為初態(tài)集的初始項(xiàng)目，S后first(e，#) = #LR（1）項(xiàng)目集規(guī)范族中，每個(gè)狀態(tài)中添加新的產(chǎn)生式時(shí)，需求產(chǎn)生式左部字母后面的First集作為新產(chǎn)生式的后繼符;否則后繼符照抄前一個(gè)狀態(tài)的I : A->a.B B->.e ，需求出First（）作為B->.e的后繼符26. 任何二義文法決不是一個(gè)LR文法 LL(k)文法都是LR(k)文法。27. a=b*c+b*d 逆波蘭式：abc*bd*+= （算符優(yōu)先的一個(gè)應(yīng)用）無括號(hào); 運(yùn)算對(duì)象順序不變; 運(yùn)算符號(hào)的位置反映運(yùn)算順序。u 三元式

15、 運(yùn)算結(jié)果用三元式編號(hào)表示 b*c （*，b，c）u 四元式 運(yùn)算結(jié)果用臨時(shí)變量表示 b*c （*，b，c，t）a:=b*c+b*d的三元式表示 a:=b*c+b*d的四元式表示 注意最后一步寫法四元式直觀寫法：t1:=b*c t2:=b*d t3:=t1+t2 a:=t3中間代碼優(yōu)化處理時(shí)，四元式比三元式方便的多28. 終結(jié)符只有綜合屬性，由詞法程序提供；非終結(jié)符可有綜合也可有繼承屬性，但文法開始符號(hào)無繼承屬性。29. 按優(yōu)化所涉及的程序范圍可分為三種級(jí)別：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化。局部優(yōu)化指在只有一個(gè)入口一個(gè)出口的基本塊內(nèi)進(jìn)行的優(yōu)化。30. 判定入口語句的規(guī)則：(a)代碼序列的第1個(gè)語句。(b)條件或無條件轉(zhuǎn)移語句的轉(zhuǎn)移目標(biāo)語句。If goto Goto (c)緊跟在無條件轉(zhuǎn)移語句或條件轉(zhuǎn)移語句后面的語句。例： B1 -> (1) read x (2) read y B2