编译原理 【国防科技大学网课】【笔记】【 陈火旺】 ——用于期末考试 【持续更新ing】
編譯原理 陳火旺
- 期末考試復習試題
- 第一章：緒論
- 第二章：高級語言及其語法描述
- 2.1 基本符號概念
- 2.2 上下文無關文法G是一個四元式
- 2.3 推導和規約、語法樹（子樹、直接子樹）
- 2.4 二義性文法判斷
- 2.5 短語、直接短語、句柄、素短語
- 2.6 化簡文法
- 第三章：詞法分析
- 基礎知識
- **3.1 右線性文法、狀態轉換圖**
- 3.2 NFA的確定化和最小化
- 考點：DFA與NFA的區別（老師強調）
- 第四章： 語法分析——自上而下分析
- 4.1 求First（α）首符號集 、Follow（B）后跟符號集
- 4.2 LL（1）文法（自頂向下的分析）
- 4.2.1非LL1文法到LL1文法的等價轉換（不一定都能轉換）
- 方法一：提取左公因子
- 方法二、消除直接左遞歸——背公式【注意空串e】
- 4.2.2 判斷LL（1）文法---求相同左步產生式的Select集的交集
- 4.2.3 LL（1）分析的實現
- 遞歸下降的分析（一種寫代碼的思想）
- 表驅動的
- 第五章： 語法分析——自底向上的分析
- 5.1 自下而上分析法基本問題——確定可規約串
- 求短語、直接短語和句柄的快速方法——畫出語法樹，從下向上找
- 規范規約、規范推導、規范句型
- 5.2 算符優先分析法（不是規范規約）——根據最左素短語找可規約串
- **計算FIRSTVT 和 LASTVT集合**
- **優先關系表的構造**
- 算符優先分析——根據最左素短語找可規約串
- 算符優先分析算法
- 優先函數——優化
- 5.3 LR分析法（規范規約）——根據句柄，怎么找句柄，即保證棧里是活前綴？
- LR分析器的工作原理—— 三元組表示
- ① LR（0）分析表的構造——0 代表不看后面那個
- 方法一：LR（0）項目 -》NFA-》DFA=》LR（0）分析表
- 方法二：拓展文法=》做閉包 =》GO函數=》DFA =》LR（0）分析表
- ② SLR分析表的構造——Follow集解決沖突，Simple 簡單解決
- ③ 規范LR分析表的構造——LR（1）分析表的構造
- ④ LALR——壓縮相同展望串的LR(1)項目
- 小結
- 第六章：屬性文法和語法制導翻譯
- 屬性文法
- 基于屬性文法的處理方法
- 1.依賴圖（有向圖）
- 2.樹遍歷方法（從上到下，從左到右）
- 3.一遍掃描
- 3.1 S屬性文法自下而上的計算 S綜合屬性
- 3.2 L屬性文法和自頂向下的翻譯 L聯系成方向
- 翻譯模式（進一步說明每一個規則在什么地方算，語義規則說明怎么算）
- 自頂向下翻譯
- 第七章 語義分析和中間代碼產生
- 中間語言
- 后綴式
- 無循環有向圖DAG
- 三地址代碼
- 賦值語句的翻譯
- 布爾表達式的翻譯
電子書鏈接：
期末考試復習試題
第一章：緒論
編譯器的五個工作步驟、功能、五個核心的模塊、出錯管理
第二章：高級語言及其語法描述
2.1 基本符號概念
注意：
1 . AB就是笛卡爾
2 . 自反傳遞閉包* 是有空串的 A^0 就是空串
本題注意 自反傳遞閉包 是有空串的 A^0 就是空串
2.2 上下文無關文法G是一個四元式
構造文法時，先寫產生式S->ab| ? 然后寫出四元式
? 不是非終結符集里的
非終結符一般大寫A，終結符小寫a
右部叫做候選式
2.3 推導和規約、語法樹（子樹、直接子樹）
2問 第一個產生式不能推出d，第二個雖然有d但是S一直存在，死循環，因此不是文法的句子
2.4 二義性文法判斷
二義性文法：某一句子可以由兩顆語法樹推出
2.5 短語、直接短語、句柄、素短語
做題方法：先畫出語法樹，然后根據語法樹寫出最右推到，再自下而上找出每一步的句柄（采用剪枝法），注意題目中是求每一步推導的句柄還是整棵語法樹的句柄？
求句柄時：是求每一步推導的句柄還是整棵語法樹的句柄；
注意這里求的是每一步推導的句柄，而我們分析用的是自下而上，最后要倒過來寫才與推導順序一致
2.6 化簡文法
就是刪掉死循環、沒用到的產生式
刪空串產生式
刪A->B單產生式
第三章：詞法分析
用戶的詞是不是合法的詞
基礎知識
3.1 右線性文法、狀態轉換圖
3型文法就是正規文法、右線性文法A->aB 以及A-〉a
例題
解題步驟：
根據語法樹知道文法結果，然后根據語法結果畫出等價的狀態圖，然后由狀態轉換圖寫出最右線性文法（一系列產生式），注意有兩種寫法
注意這里C->0A|1F|1 1F是F作為中間狀態，1是F為終態
輸入串的特征是，任意以b開頭，中間任意個a，后面跟一個b，然后由a或b結尾的字符串
3.2 NFA的確定化和最小化
一、先將正規式轉換成NFA
二、再將NFA轉成DFA（子集法）
三、DFA的最小化
什么是最小化，為什么要最小化？
怎么做？用一個例題來講解 這篇講的很好
什么叫不同？不屬于同一個狀態集合，需要再次劃分；相同就是屬于同一個狀態集合，無需劃分，最后需要合并成一個狀態表示。
注意：最后還要刪除多余狀態
例題：考前做幾道理解一下
考點：DFA與NFA的區別（老師強調）
第四章： 語法分析——自上而下分析
期末復習建議直接看這里：
有一定基礎看這個視頻！理解兩種推到方式
4.1 求First（α）首符號集 、Follow（B）后跟符號集
定義
First（E）表示所有能表示為E的終結符串的開頭符號的集合
找最左邊可能出現的終結符
規則如下：
以例題講解
求Follow（B）后跟符號集
定義
即找所有可能跟在B后面所能跟的所有終結符或結束符#，口訣 看右邊
規則
上面講得可能還是有點亂，多讀幾遍，直接記憶下面這個方法！看右邊！
總結：看右邊，就是我們看文法右邊，找我們要求的非終結符B的Follow，哪里出現了B，看B后面跟的是哪個符號？A->αBβ
- 如果是跟的β是終結符，直接β放入Follow(B)集（僅放入一個 如 S-》Abc follow A ={b} ）；
- 如果是跟的β是非終結符，看Firstβ集是什么樣的，如果里面有空串e（β可以推出e），一要把First β中的空串e去掉之后放入Follow(B)（如 A-》αBβ ,β->C|e 求Follow（B））；二是要左步的的followA 放進Follow（B）
下面的圖示也比較清晰，只是A B 翻過來了，上面的是根據我的理解容易記憶的寫法
例題：
4.2 LL（1）文法（自頂向下的分析）
首先LL1文法的判定只針對有兩條產生式的非終結符如A->α A->β
先明確select(A->α)t選擇符號集的定義
當我們拿到一個非終結符時候，遇到哪些輸入符號時候可以進行推導，將這些符號成為一個產生式的select集，意為遇到這些符號時選擇這一產生式！
例題：同上
如果=》右側不能廣義推導出空串e，就=右部的First集
如果=》右側可以廣義推到出空串e，就=右部的First集-{e} 并上 Follow A
總結select求法：
下面是LL1型文法的定義
L表明自頂向下分析是從左向右掃描輸入串
第2個L表明分析過程中將用最左到推倒,
1表明只需向右看一個符號便可決定如何推倒即選擇哪個產生式(規則)進行推導,類似也可以有LL(k)文法,也就是需要向前查看k個符號才能確定選用哪個產生式
LL1型文法的判定
首先文法無左遞歸
只看含相同左部的產生式（如 E->+E|e），可選集合select的交集 ，均為空集合（拆成E->+E 和 E->e），則文法為LL1文法
4.2.1非LL1文法到LL1文法的等價轉換（不一定都能轉換）
方法一：提取左公因子
方法二、消除直接左遞歸——背公式【注意空串e】
我們只學消除直接左遞歸；注意空串
例題
4.2.2 判斷LL（1）文法—求相同左步產生式的Select集的交集
下面還有一種判斷方法，其實就是同一個意思，用select方法方便理解，雖然挺浪費時間。。。。建議掌握下面的
4.2.3 LL（1）分析的實現
遞歸下降的分析（一種寫代碼的思想）
舉例分析41.55秒
注意如果能推出空串e的，不會有報錯處理，因為如果不匹配指針后移1個，可以為空e，可能下一個就匹配了呀比如+
偽代碼如下
表驅動的
表中一項沒有兩個，沒有沖突項，也可以說明是LL 1文法
寫到這里突然發現自己對基本知識還不夠理解，于是又去惡補了視頻，從基礎開始寫
第五章： 語法分析——自底向上的分析
5.1 自下而上分析法基本問題——確定可規約串
基本思想
移進——規約
關鍵問題是識別可規約串，有好幾種選擇選哪個規約？——用句柄來規約
基本概念：
短語、直接短語、句柄
短語：=》是某個非終結符一步或多部推到出的句子
β能夠規約成非終結符A，一步獲多步規約為A，構成一個語法單位
而且這個語法的單位能和上文和下文規約為S，即拼起來是一棵樹
直接短語：是某個非終結符一步推到出的句子
β一步規約為A，
短語是可能的 要規約的目標
直接短語是可能的 馬上要規約的目標，一步就到非終結符
句柄：
最左的直接短語，規約的抓手！
就是那個馬上要規約的對象，因為我們是從左到右分析，
句柄可能是非終結符、終結符，因為短語只說了是葉子！！
求短語、直接短語和句柄的快速方法——畫出語法樹，從下向上找
這篇
所有子樹的末端，保證了A=》+ β
而短語的第一個條件要求S=》αAβ，即把這子樹切掉還是一顆樹
此時利用句柄進行規約就不會出現剛才有好幾種選擇的情況了
規范規約、規范推導、規范句型
每次都是用句柄進行規約，是規范規約，因此得到的分析樹跟語法樹一定是一致的
符號棧的使用
這中間的每一步，棧內的內容和輸入串剩下的內容拼起來一定是一個句型，一定是一個規范句型，可以畫出拼成的語法樹來理解，一但棧頂出現句柄就進行規約！
那么具體怎么確定可規約串，肯定不能畫出語法樹找句柄，下面講找。。。。。。。。。
5.2 算符優先分析法（不是規范規約）——根據最左素短語找可規約串
優先關系定義
算符文法（沒有+*這種形式）
算符優先文法
計算FIRSTVT 和 LASTVT集合
先介紹FIRSTVT集和LASTVT集
構造FISTVT、LASTVT集合的算法——利用二維bool矩陣 手算也推薦
優先關系表的構造
現在已經求出FISTVT 和LASTVT集合，構造優先關系表
如果考慮# 符號，只用考慮#S# 句型
構造優先關系表的算法
解釋：
在構造優先關系表時每個產生式只從左到右掃描1遍，但每次掃描，都要檢查所有可能的模式= 《 》！
如果 出現兩個連續的終結符 ± ，關系為 =
如果 兩個終結符中間只有一個非終結符 +E- ，說明兩邊的終結符的優先級是相等的，關系為 =
如果 +E形式，對于FIRSTVT E 中每一個a 都有 + 《a a要先規約
如果 E+ 形式，對于LASTVT E 中每一個a 都有 a》+ a要先規約
例題：
算符優先分析——根據最左素短語找可規約串
概念回顧：
可歸約串：自底向下分析的核心就是找可規約串
句型：文法開始符號所能推出的某種串
短語：語法樹末端
直接短語、句柄： 短語的特例
規范規約：每次都對句柄進行規約，這個規約就是規范規約，規范規約的結果一定是語法樹
素短語：在算法分析方法中要規約的對象
首先是短語，然后至少有一個終結符，但內部不能再有包含終結符的短語，即不含有更小的素短語
最左素短語：在句型最左邊的那個素短語，之所以找最左，因為我們規約就是從左向右的，最左素短語就是我們要規約的
例題：
怎么找最短素短語？找滿足如下條件的子串
中間部分即是最左素短語
算符優先分析算法
算符優先分析算法解釋：
Q是上面的終結符，s【j】是下面的終結符，直到上面大下面小就退出；說明找到了
體現在分析樹上就是比語法樹短了好幾節，直接對應上去的。跳過了一些簡單的規約
發現非終結符好像沒有影響，可以不進棧，但有時候會錯
優缺點
算符優先分析一般不是規范規約，跳過了一些簡單的規約，速度更快了
優先函數——優化
優先函數不一定存在
優先函數如果存在，是無窮多的，可以加減常數
如果優先函數存在，三步構造優先函數
檢查很重要！檢查f g值關系和符號表的對應關系是否一致
例題
5.3 LR分析法（規范規約）——根據句柄，怎么找句柄，即保證棧里是活前綴？
問題：
我們要用句柄來確定可規約串，但語法分析的目的就是為了得到語法樹，語法分析沒有完哪來的句柄？——LR分析器
思想：
LR分析表
LR分析器的工作原理—— 三元組表示
LR分析器工作原理例題：講得很棒理解過程44：00
LR文法、 LR（k）文法
LR文法不是二義文法
因此文法是LR文法是文法無二義性的充分條件
① LR（0）分析表的構造——0 代表不看后面那個
基本概念：字的前綴、活前綴
解釋
活前綴保證不會出現句柄+句柄之后的符號 出現在棧中，只會有三種情況，句柄在棧頂，句柄一部分在棧頂一部分在棧外，句柄全在棧外
問題是：怎么樣構造DFA識別活前綴
方法一：LR（0）項目 -》NFA-》DFA=》LR（0）分析表
LR（0）項目
解釋
移進項目：現在α已經在棧中，我希望見到終結符a，將來把β移進，最后規約到A
待約項目：等待著把B先歸約
其實這里的。可以理解為當前用戶輸入到哪了？
構成識別活前綴的NFA方法
解釋
2. 等待A形成，到了狀態A直接跳到A->γ上去，希望下面的輸入符號能沿向右移動，形成γ最后形成A，回到狀態i
終結態是*在最后的狀態，也是句柄識別態，是規約項目
子集法確定化DFA
任何一個狀態都是活前綴的識別態
LR分析表實際上把DFA識別活前綴的能力轉換到表里了，前進后退
圖里所有項目集合構成了LR（0）項目集規范族
方法二：拓展文法=》做閉包 =》GO函數=》DFA =》LR（0）分析表
有效項目
也就是說識別了αβ1后，A的前部分已經識別，后一部分β2等待著識別，*后是我們希望識別的部分
一個結論
項目對于活前綴是有效的 例子理解：
定義幾個概念：拓廣文法、閉包運算、GO函數
解釋：
這里求閉包與之前類似：
GO函數
解釋：
例題理解：
LR（0）項目集規范族的算法
構造過程舉例：
LR（0）分析表的構造
LR（0）文法定義
把DFA 識別活前綴的能力轉換到LR分析表中去
LR（0）分析表的ACTION和GOTT子表的構造方法
例子：
文法
識別活前綴的DFA 、項目集規范族
轉變為分析表
檢查：
對應到DFA識別活前綴的過程，接收、退出
② SLR分析表的構造——Follow集解決沖突，Simple 簡單解決
LR文法會有沖突: 移進歸約沖突、歸約歸約沖突，（沒有移進移進沖突！！！）
檢查非終結符的Follow集合，有選擇地把歸約動作放在某些列中去，而不是每一列
推廣
藍色是所有移進項目，綠色是歸約項目
S small 有一點點展望 FollowA 告訴我們非終結符A后面可能跟哪些符號
1 代表向前看1個
SLR（1）分析表的ACTION和GOTO子表構造
與LR0區別在:放的時候看終結符是不是FollowA里可能的后跟符號
又是一個判斷無二義文法的充分條件
例題理解：
項目集規范族，通過GO函數連成DFA
其中1 2 9 都有沖突
SLR沖突消解存在的問題
我們應該要在某種特定狀態才能follow！
舉例解釋：
③ 規范LR分析表的構造——LR（1）分析表的構造
展望信息關聯到每一個具體的狀態上，不再關聯到follow集合上了
LR（k）項目、展望串 新定義
對比：
第二分量代表是只有遇到這種情況，才進行前面的動作
LR（1）項目集規范族的構造
做項目集閉包的方法
其中：與前面LR（0）項目求閉包不同之處
理解：
b是怎么來的？
說明α已經有了，下面希望形成B再形成β，當β出現的時候我希望碰到a，然后一起歸約成A，因此格局應該轉到B的識別
希望通過識別kesi來歸約為B，但是有一個上下文條件！
B的下文是β，如果β不空，把kesi歸約成B面臨的終結符即展望的單詞要是β的開頭！
如果β為空，展望的單詞就是a（比如a是# 如果β為空，說明是空串，后面只會跟#）
=》合起來就是b屬于FIRST（βa）
=》展望串分量的寫法，其實就是看從哪過來的！ 在求的時候不用這么麻煩
項目集轉換函數GO新定義
LR（1）項目集規范族構造算法（與LR（0）類似）
LR（1）分析表的ACTION和GOTO子表的構造
差別就在2，把歸約動作都放在展望串那一列中
LR（0） SLR呢？
LR（1）文法
又是一個判斷無二義文法的充分條件
舉例理解：
文法
LR（1）項目集構造
注意圖中S->.BB狀態I0 延伸出來的I2的展望串的寫法，到底是哪個B？
LR（1）分析表為
觀察：狀態7的歸約動作只放在了#中，8的歸約動作只放在了ab中，都是狀態的展望串對應的終結符
利用表對輸入串進行分析
④ LALR——壓縮相同展望串的LR(1)項目
注意：可能導致一種新的沖突 歸約——歸約 沖突！因為第一分量是一樣的，只有第二分量展望串可能會沖突
小結
LR分析法就是根據句柄分析，怎么找句柄，怎么樣保持棧里的是活前綴？
通過構造LR（1）、SLR、LR（0）項目集規范族=》識別活前綴的DFA=》LR分析表=》安裝LR分析表去正確的移進歸約！！！
第六章：屬性文法和語法制導翻譯
屬性文法
兩種屬性
- 綜合屬性
- 繼承屬性-可以來自兄弟節點 or 父節點
說明：
例：
基于屬性文法的處理方法
1.依賴圖（有向圖）
語義規則中沒有返回值，需要添加一個虛擬的綜合屬性節點
構造依賴圖的算法：
舉例
良定義的屬性文法
屬性的計算次序
例子：需要多遍掃描
2.樹遍歷方法（從上到下，從左到右）
算法理解：
從上到下，從左到右，能算的繼承屬性先算出來，不斷VisitNode，掃過一遍，算一下根節點N的綜合屬性
例子：
3.一遍掃描
AST 抽象語法樹 中間代碼
建立抽象語法樹
例子：構造抽象語法樹，從左到右，從上到下，一遍
起主導的是語法分析，所以叫語法制導
3.1 S屬性文法自下而上的計算 S綜合屬性
概念介紹：
把棧變成三元組
每個規則有相應的代碼段
例子：
3.2 L屬性文法和自頂向下的翻譯 L聯系成方向
L屬性文法
區分：下面的Q依賴于右兄弟1節點的綜合屬性，不屬于L屬性文法
翻譯模式（進一步說明每一個規則在什么地方算，語義規則說明怎么算）
把產生式對應的語義規則打上{} ，變成語義動作，放到正確的位置上，保證用一個屬性時，他有定義有值
例子：把中綴表達式翻譯為后綴表達式
打印出 9 5 - 2 +
建立翻譯模式=》保證在用到一個屬性時候已經計算好了
只有綜合屬性，當所有子節點都匹配成功，自動執行他，L屬性保證了這點
要放在非終結符前面，當碰到非終結符要往下擴展時候，因為子節點要引用非終結符的繼承屬性，如果{}放在后面，在擴展時候可能會用到！
改進，把所有的{}都放在后面，改寫加e，第七章會詳細講
自頂向下翻譯
首先自頂向下翻譯會遇到左遞歸，先要消除左遞歸，要進行文法、屬性計算的改造
消除左遞歸，構建新的翻譯模式（學完第七章再來重新理解）
例子：
推廣：帶左遞歸的翻譯模式的改造方法
A推出的是X開頭YYYY串，消除左遞歸，用R來產生YYYY串，注意e空串結束
牢記：用之前必須有值
例子
例2
構造抽象語法樹
第七章 語義分析和中間代碼產生
靜態語言檢查
中間語言
常用的中間語言：
后綴式
定義: 比較復雜，看書，或者不看
優點：
以后綴式為中間語言構造翻譯模式來分析和翻譯輸入串
無循環有向圖DAG
定義：
DAG與抽象語法樹對比（省略箭頭，其實有向，DAG是壓縮過的、優化）
三地址代碼
種類：
**四元式：**容易優化，刪除調整順序方便
**三元式：**不去顯示運算的單元，引用計算該值的位置來引用結果
其他情況
間接三元式：方便優化，節省空間存儲效率高
間接碼表表示計算的順序，要調整順序、刪除就去操作間接碼表
賦值語句的翻譯
產生賦值語句的三地址代碼的S屬性文法（先用屬性文法描述語義）
產生賦值語句的三地址代碼翻譯模式（語義規則在什么時候計算，構造翻譯模式，語義動作）
把屬性文法和分析過程結合起來，得到語義動作，得到翻譯模式
說明：
lookup是查看一下標志符是否有定義，返回其在符號表中的入口地址
emit是發送到輸出文件中去，與gen差不多
這個翻譯模式適合和自下而上的分析器結合在一起，當用某個產生式規約時，就執行其后面的語義動作
數組元素地址的計算
程序每翻譯一個賦值語句，當碰到一個數組元素時候，我們只要去生成紅色可變部分的代碼，與不變部分藍色相加即可得到數組元素的地址
方便計算地址，改寫文法
帶數組元素引用的賦值語句翻譯模式
帶類型轉換的賦值語句
布爾表達式的翻譯
太復雜了，考試不考
總結
以上是生活随笔為你收集整理的编译原理 【国防科技大学网课】【笔记】【 陈火旺】 ——用于期末考试 【持续更新ing】的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 软考高级 真题 2011年上半年 信息系
- 下一篇： 京东商品详情API接口-（item_ge