編譯原理分析樹

⑴ 編譯原理全部的名詞解釋

書上有別那麼懶!.
編譯過程的六個階段：詞法分析,語法分析,語義分析,中間代碼生成,代碼優化,目標代碼生成
解釋程序：把某種語言的源程序轉換成等價的另一種語言程序——目標語言程序,然後再執行目標程序.解釋方式是接受某高級語言的一個語句輸入,進行解釋並控制計算機執行,馬上得到這句的執行結果,然後再接受下一句.
編譯程序：就是指這樣一種程序,通過它能夠將用高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序(機器語言程序或匯編語言程序).
解釋程序和編譯程序的根本區別：是否生成目標代碼
句子的二義性（這里的二義性是指語法結構上的.）:文法G[S]的一個句子如果能找到兩種不同的最左推導(或最右推導),或者存在兩棵不同的語法樹,則稱這個句子是二義性的.
文法的二義性:一個文法如果包含二義性的句子,則這個文法是二義文法,否則是無二義文法.
LL(1)的含義：(LL(1)文法是無二義的； LL(1)文法不含左遞歸)
第1個L：從左到右掃描輸入串 第2個L：生成的是最左推導
1 ：向右看1個輸入符號便可決定選擇哪個產生式
某些非LL(1)文法到LL(1)文法的等價變換: 1. 提取公因子 2. 消除左遞歸
文法符號的屬性:單詞的含義,即與文法符號相關的一些信息.如,類型、值、存儲地址等.
一個屬性文法(attribute grammar)是一個三元組A=(G, V, F)
G：上下文無關文法.
V：屬性的有窮集.每個屬性與文法的一個終結符或非終結符相連.屬性與變數一樣,可以進行計算和傳遞.
F：關於屬性的斷言或謂詞(一組屬性的計算規則)的有窮集.斷言或語義規則與一個產生式相聯,只引用該產生式左端或右端的終結符或非終結符相聯的屬性.
綜合屬性:若產生式左部的單非終結符A的屬性值由右部各非終結符的屬性值決定,則A的屬性稱為綜合屬
繼承屬性:若產生式右部符號B的屬性值是根據左部非終結符的屬性值或者右部其它符號的屬性值決定的,則B的屬性為繼承屬性.
(1)非終結符既可有綜合屬性也可有繼承屬性,但文法開始符號沒有繼承屬性.
(2) 終結符只有綜合屬性,沒有繼承屬性,它們由詞法程序提供.
在計算時： 綜合屬性沿屬性語法樹向上傳遞；繼承屬性沿屬性語法樹向下傳遞.
語法制導翻譯：是指在語法分析過程中,完成附加在所使用的產生式上的語義規則描述的動作.
語法制導翻譯實現：對單詞符號串進行語法分析,構造語法分析樹,然後根據需要構造屬性依賴圖,遍歷語法樹並在語法樹的各結點處按語義規則進行計算.
中間代碼（中間語言）
1、是復雜性介於源程序語言和機器語言的一種表示形式.
2、一般,快速編譯程序直接生成目標代碼.
3、為了使編譯程序結構在邏輯上更為簡單明確,常採用中間代碼,這樣可以將與機器相關的某些實現細節置於代碼生成階段仔細處理,並且可以在中間代碼一級進行優化工作,使得代碼優化比較容易實現.
何謂中間代碼：源程序的一種內部表示,不依賴目標機的結構,易於代碼的機械生成.
為何要轉換成中間代碼:(1)邏輯結構清楚；利於不同目標機上實現同一種語言.
(2)便於移植,便於修改,便於進行與機器無關的優化.
中間代碼的幾種形式：逆波蘭記號 ,三元式和樹形表示 ,四元式
符號表的一般形式：一張符號表的的組成包括兩項,即名字欄和信息欄.
信息欄包含許多子欄和標志位,用來記錄相應名字和種種不同屬性,名字欄也稱主欄.主欄的內容稱為關鍵字（key word）.
符號表的功能：（1）收集符號屬性 (2) 上下文語義的合法性檢查的依據： 檢查標識符屬性在上下文中的一致性和合法性.(3)作為目標代碼生成階段地址分配的依據
符號的主要屬性及作用：
1. 符號名 2. 符號的類型 （整型、實型、字元串型等））3. 符號的存儲類別（公共、私有）
4. 符號的作用域及可視性 （全局、局部） 5. 符號變數的存儲分配信息 （靜態存儲區、動態存儲區）
存儲分配方案策略：靜態存儲分配；動態存儲分配：棧式、 堆式.
靜態存儲分配
1、基本策略
在編譯時就安排好目標程序運行時的全部數據空間,並能確定每個數據項的單元地址.
2、適用的分配對象：子程序的目標代碼段；全局數據目標（全局變數）
3、靜態存儲分配的要求：不允許遞歸調用,不含有可變數組.
FORTRAN程序是段結構,不允許遞歸,數據名大小、性質固定. 是典型的靜態分配
動態存儲分配
1、如果一個程序設計語言允許遞歸過程、可變數組或允許用戶自由申請和釋放空間,那麼,就需要採用動態存儲管理技術.
2、兩種動態存儲分配方式：棧式,堆式
棧式動態存儲分配
分配策略：將整個程序的數據空間設計為一個棧.
【例】在具有遞歸結構的語言程序中,每當調用一個過程時,它所需的數據空間就分配在棧頂,每當過程工作結束時就釋放這部分空間.
過程所需的數據空間包括兩部分
一部分是生存期在本過程這次活動中的數據對象.如局部變數、參數單元、臨時變數等；
另一部分則是用以管理過程活動的記錄信息(連接數據).
活動記錄（AR）
一個過程的一次執行所需要的信息使用一個連續的存儲區來管理,這個區 (塊)叫做一個活動記錄.
構成
1、臨時工作單元；2、局部變數；3、機器狀態信息；4、存取鏈；
5、控制鏈；6、實參；7、返回地址
什麼是代碼優化
所謂優化,就是對代碼進行等價變換,使得變換後的代碼運行結果與變換前代碼運行結果相同,而運行速度加快或佔用存儲空間減少.
優化原則：等價原則：經過優化後不應改變程序運行的結果.
有效原則：使優化後所產生的目標代碼運行時間較短,佔用的存儲空間較小.
合算原則：以盡可能低的代價取得較好的優化效果.
常見的優化技術
(1) 刪除多餘運算(刪除公共子表達式) (2) 代碼外提 +刪除歸納變數+ (3)強度削弱; (4)變換循環控制條件 (5)合並已知量與復寫傳播 (6)刪除無用賦值
基本塊定義
程序中只有一個入口和一個出口的一段順序執行的語句序列,稱為程序的一個基本塊.
給我分數啊.

⑵ 編譯原理-LL1文法詳細講解

我們知道2型文法( CFG )，它的每個產生式類型都是 α→β ,其中 α ∈ VN , β ∈ (VN∪VT)*。

例如, 一個表達式的文法:

最終推導出 id + (id + id) 的句子，那麼它的推導過程就會構成一顆樹，即 CFG 分析樹：

從分析樹可以看出，我們從文法開始符號起，不斷地利用產生式的右部替換產生式左部的非終結符，最終推導出我們想要的句子。這種方式我們稱為自頂向下分析法。

從文法開始符號起，不斷用非終結符的候選式(即產生式)替換當前句型中的非終結符，最終得到相應的句子。
在每一步推導過程中，我們需要做兩個選擇:

因為一個句型中，可能存在多個非終結符，我們就不確定選擇那一個非終結符進行替換。
對於這種情況，我們就需要做強制規定，每次都選擇句型中第一個非終結符進行替換(或者每次都選擇句型中最後一個非終結符進行替換)。

自頂向下的語法分析採用最左推導方式，即總是選擇每個句型的最左非終結符進行替換。

最終的結果是要推導出一個特定句子(例如 id + (id + id) )。
我們將特定句子看成一個輸入字元串，而每一個非終結符對應一個處理方法，這個處理方法用來匹配輸入字元串的部分，演算法如下:

方法解析:

這種方式稱為遞歸下降分析( Recursive-Descent Parsing )：

當選擇的候選式不正確，就需要回溯( backtracking )，重新選擇候選式，進行下一次嘗試匹配。因為要不斷的回溯，導致分析效率比較低。

這種方式叫做預測分析( Predictive Parsing )：

要實現預測分析，我們必須保證從文法開始符號起，每一個推導過程中，當前句型最左非終結符 A 對於當前輸入字元 a ,只能得到唯一的 A 候選式。

根據上面的解決方法，我們首先想到，如果非終結符 A 的候選式只有一個以終結符 a 開頭候選式不就行了么。
進而我們可以得出，如果一個非終結符 A ，它的候選式都是以終結符開頭，並且這些終結符都各不相同，那麼本身就符合預測分析了。

這就是S_文法，滿足下面兩個條件:

例子:

這就是一個典型的S_文法，它的每一個非終結符遇到任一終結符得到候選式是確定的。如 S -> aA | bAB , 只有遇到終結符 a 和 b 的時候，才能返回 S 的候選式，遇到其他終結符時，直接報錯，匹配不成功。

雖然S_文法可以實現預測分析，但是從它的定義上看，S_文法不支持空產生式(ε產生式)，極大地限制了它的應用。

什麼是空產生式(ε產生式)？

例子

這里 A 有了空產生式，那麼 S 的產生式組 S -> aA | bAB ，就可以是 a | bB ,這樣 a , bb , bc 就變成這個文法 G 的新句子了。

根據預測分析的定義，非終結符對於任一終結符得到的產生式是確定的，要麼能獲取唯一的產生式，要麼不匹配直接報錯。

那麼空產生式何時被選擇呢？

由此可以引入非終結符 A 的後繼符號集的概念:
定義: 由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符 a 的集合，就是這個非終結符 A 的後繼符號集，記為 FOLLOW(A) 。

因此對於 A -> ε 空產生式，只要遇到非終結符 A 的後繼符號集中的字元，可以選擇這個空產生式。
那麼對於 A -> a 這樣的產生式，只要遇到終結符 a 就可以選擇了。

由此我們引入的產生式可選集概念:
定義: 在進行推導時，選用非終結符 A 一個產生式 A→β 對應的輸入符號的集合，記為 SELECT(A→β)

因為預測分析要求非終結符 A 對於輸入字元 a ,只能得到唯一的 A 候選式。
那麼對於一個文法 G 的所有產生式組，要求有相同左部的產生式，它們的可選集不相交。

在 S_文法基礎上，我們允許有空產生式，但是要做限制:

將上面例子中的文法改造:

但是q_文法的產生式不能是非終結符打頭，這就限制了其應用，因此引入LL(1)文法。

LL(1)文法允許產生式的右部首字元是非終結符，那麼怎麼得到這個產生式可選集。
我們知道對於產生式:

定義: 給定一個文法符號串 α ， α 的 串首終結符集 FIRST(α) 被定義為可以從 α 推導出的所有串首終結符構成的集合。

定義已經了解清楚了，那麼該如何求呢？
例如一個文法符號串 BCDe , 其中 B C D 都是非終結符， e 是終結符。

因此對於一個文法符號串 X1X2 … Xn ，求解 串首終結符集 FIRST(X1X2 … Xn) 演算法:

但是這里有一個關鍵點，如何求非終結符的串首終結符集？

因此對於一個非終結符 A , 求解 串首終結符集 FIRST(A) 演算法:

這里大家可能有個疑惑，怎麼能將 FIRST(Bβ) 添加到 FIRST(A) 中，如果問文法符號串 Bβ 中包含非終結符 A ，就產生了循環調用的情況，該怎麼辦?

對於 串首終結符集 ，我想大家疑惑的點就是，串首終結符集到底是針對 文法符號串 的，還是針對 非終結符 的，這個容易弄混。
其實我們應該知道， 非終結符 本身就屬於一個特殊的 文法符號串 。
而求解 文法符號串 的串首終結符集，其實就是要知道文法符號串中每個字元的串首終結符集:

上面章節我們知道了，對於非終結符 A 的 後繼符號集 :
就是由文法 G 推導出來的所有句型，可以出現在非終結符 A 後邊的終結符的集合，記為 FOLLOW(A) 。

仔細想一下，什麼樣的終結符可以出現在非終結符 A 後面，應該是在產生式中就位於 A 後面的終結符。例如 S -> Aa ，那麼終結符 a 肯定屬於 FOLLOW(A) 。

因此求非終結符 A 的 後繼符號集 演算法：

如果非終結符 A 是產生式結尾，那麼說明這個產生式左部非終結符後面能出現的終結符，也都可以出現在非終結符 A 後面。

我們可以求出 LL(1) 文法中每個產生式可選集:

根據產生式可選集，我們可以構建一個預測分析表，表中的每一行都是一個非終結符，表中的每一列都是一個終結符，包括結束符號 $ ，而表中的值就是產生式。
這樣進行語法推導的時候，非終結符遇到當前輸入字元，就可以從預測分析表中獲取對應的產生式了。

有了預測分析表，我們就可以進行預測分析了，具體流程:

可以這么理解：

我們知道要實現預測分析，要求相同左部的產生式，它們的可選集是不相交。
但是有的文法結構不符合這個要求，要進行改造。

如果相同左部的多個產生式有共同前綴，那麼它們的可選集必然相交。
例如:

那麼如何進行改造呢？
其實很簡單，進行如下轉換:

如此文法的相同左部的產生式，它們的可選集是不相交，符合現預測分析。

這種改造方法稱為 提取公因子演算法 。

當我們自頂向下的語法分析時，就需要採用最左推導方式。
而這個時候，如果產生式左部和產生式右部首字元一樣(即A→Aα)，那麼推導就可能陷入無限循環。
例如:

因此對於:

文法中不能包含這兩種形式，不然最左推導就沒辦法進行。

例如:

它能夠推導出如下:

你會驚奇的發現，它能推導出 b 和 (a)* (即由 0 個 a 或者無數個 a 生成的文法符號串)。其實就可以改造成:

因此消除 直接左遞歸 演算法的一般形式：

例如:

消除間接左遞歸的方法就是直接帶入消除，即

消除間接左遞歸演算法：

這個演算法看起來描述很多，其實理解起來很簡單：

思考 : 我們通過 Ai -> Ajβ 來判斷是不是間接左遞歸，那如果有產生式 Ai -> BAjβ 且 B -> ε ,那麼它是不是間接左遞歸呢？
間接地我們可以推出如果一個產生式 Ai -> αAjβ 且 FIRST(α) 包括空串ε，那麼這個產生式是不是間接左遞歸。

⑶ 編譯原理-句型、句子、短語、直接短語、句柄、素短語、最左素短語

在進行語法分析的時候，有時候會對這些詞語的概念不清晰，這里我們就詳細歸納總結一下。

可以看出這個裡面，最需要理解的概念就是短語，其他大部分概念都是在短語基礎上延伸的，從概念上可以看出：

假設有一個文法

針對文法的一個特定句型 (Sd(T)db) , 其推導過程如下:

這個句型 (Sd(T)db) 對應的 CFG 分析樹如下：

那個這個句型 (Sd(T)db) 有多少個短語呢？

還記得短語的定義么， S ⇒* αβδ ， αβδ 代表句型就是這里的 (Sd(T)db) 。

因此這個句型 (Sd(T)db) :

演算法非常簡單，就是通過分析樹的後序遍歷，先將子樹的葉節點從左到右排合並成字元串(即一個短語)，然後用它代表子樹的根節點的值，再和與子樹根節點同一層節點值合並，得到新的短語。就這樣從分析樹的最底層，一路合並到分析樹的根節點，就能得到所有的短語了。

通過遞歸的方法，獲取短語列表 phraseList , 直接短語列表 directPhraseList 和 素短語列表 plainPhraseList 。

運行結果:

⑷ 【編譯原理】第二章：語言和文法

上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。

約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：

產生式

可以簡寫為：

如上例中，

可以簡寫為：

給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。

如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。

推導的反過程稱為 歸約 。

如果 ，則稱 是 的一個 句型（sentential form ）。

由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：

例
文法

表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。

並、連接、冪、克林閉包、正閉包。
如上例表示為：

中必須包含一個 非終結符 。

產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。

上下文有關文法不包含空產生式（ ）。

產生式的一般形式：
即產生式左邊都是非終結符。

右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。

例：（右線性文法）

以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：

正則文法能描述程序設計語言中的多數單詞。

正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。

根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。

給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。

直接短語一定是某產生式的右部，但反之不一定。

如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。

二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。

⑸ 【編譯原理】第四章：語法分析

從分析樹的根節點到葉節點方向構造分析樹。
即從開始符號S推導出詞串w的過程。

例：

總是選擇每個句型的 最左非終結符 進行替換。

總是選擇每個句型的 最右非終結符 進行替換。

在自底向上的分析中，總是採用 最左規約 的方式，因此把 最左規約 稱為 規范規約 ，對應的 最右推導 稱為 規范推導 。

最左推導、最右推導具有唯一性。

自頂向下的語法分析採用最左推導方試，總是選擇每個句型的 最左非終結符 進行替換。

由一組 過程 組成，每一個過程對應一個 非終結符 。
從文法開始符號S開始，遞歸調用文法中的其他非終結符，最終掃描整個輸入串，完成分析。

如果其間有不唯一的產生式，就可能需要退回上一步重新嘗試的情況，稱為 回溯 。

預測分析 是 遞歸下降分析 技術的一個特例，通過輸入中向前看固定個數的符號選擇正確的產生式。
如果一個文法可以構造出向前看k個符號的預測分析器，稱為LL(k)文法 。

預測分析不需要回溯，具有確定性。

含有 形式產生式的文法稱為是 直接左遞歸 的。
如果一個文法中有一個非終結符A使得對某個串存在推導 ，那麼這個文法是 左遞歸 的。其中，經過兩步或以上推導產生的左遞歸，稱為 間接左遞歸 的。
左遞歸會使遞歸下降分析器陷入無限循環。

文法
即
該文法是直接左遞歸的，會陷入無限循環。

將以上文法轉換為：


即可消除左遞歸。事實上，這個過程把左遞歸轉換成了右遞歸。

消除直接左遞歸的一般形式

使用代入法。

對於一個文法，通過改寫產生式來 推遲決定 ，等獲得足夠多的輸入信息再做正確的決定。

例：文法：

可以改寫為：

從文法的開始符號S開始，每一步推導根據當前句型的最左非終結符A和當前輸入符號α，選擇正確的A-產生式。為保證分析的確定性，選出的候選式必須是唯一的。

S_文法（簡單的確定型文法）

可能在某個舉行中緊跟在A後面的終結符a的集合，記為 FOLLOW(A) 。
如果A是某個句型的最右符號，則將結束符「 $ 」添加到FOLLOW(A)中。

例：文法：






中，FOLLOW(B) = {a, c}

產生式 的可選集是指可以選用該產生式進行推導時對應的輸入符號的集合，記為 SELECT(A->β) 。
例如
SELECT(A -> aβ)={a}
SELECT(A -> aβ | bγ)={a, b}
SELECT(A -> ε)=FOLLOW(A)

q_文法

文法符號串α串首終結符的集合，記作 FIRST(A) 。

⑹ 如何由文法推導語法樹(編譯原理)

語法樹，是針對上下文無關文法，用來表示一個句型的生成過程的一種描述手段。

對於給定的句型，依據文法構造它的語法樹，是語法分析的任務。
編譯原理課程中重點學習的各種語法分析方法，都是解決語法樹的構造的具體分析方法。

在學習並掌握各種語法分析方法之前，一般只能依據直覺印象，通過猜測、拼湊等手段，去試著推演，湊出符合要求的句型的語法樹。所以這個階段練慣用的題目一般也不很復雜，通過多多練習也能找到一些技巧（其實主要是後面將要學習的自頂向下語法分析中的一些原則）。

對於給定的文法，有一些句型可能能構建出兩棵甚至多棵結構不同的語法樹，結果不一定是唯一的。這樣的文法就是所謂的二義性文法。
對於非二義性文法而言，任意一個句型的語法樹都是唯一的。

⑺ 編譯原理筆記9：語法分析樹、語法樹、二義性的消除

語法分析樹和語法樹不是一種東西 。習慣上，我們把前者叫做「具體語法樹」，其能夠體現推導的過程；後者叫做「抽象語法樹」，其不體現過程，只關心最後的結果。

語法分析樹是語言推導過程的圖形化表示方法。這種表示方法反映了語言的實質以及語言的推導過程。

定義：對於 CFG G 的句型，分析樹被定義為具有下述性質的一棵樹：

推導，有最左推導和最右推導，這兩種推導方式在推導過程中的分析樹可能不同，但因最終得到的句子是相同的，所以最終的分析樹是一樣的。

分析樹能反映句型的推導過程，也能反映句型的結構。然而實際上，我們往往不關心推導的過程，而只關心推導的結果。因此，我們要對 分析樹 進行改造，得到 語法樹 。語法樹中全是終結符，沒有非終結符。而且語法樹中沒有括弧

定義：

說白了，語法樹這玩意，就一句話： 葉子全是操作數，內部全是操作符 ，樹里沒有非終結符也不能有括弧。

語法樹要表達的東西，是操作符（運算）作用於操作數（運算對象）

舉倆例子吧：

【例】： -(id+id) 的語法樹：

【例】：-id+id 的語法樹：

顯然，我們從上面這兩個語法樹中，直接就能觀察出來它們的運算順序。

【例】：句型 if C then s1 else s2

二義性問題：一個句子可能對應多於一棵語法樹。

【例】： 設文法 G： E → E+E | E*E | (E) | -E | id

則，句子 id+id*id、id+id+id 可能的分析樹有：

在該例中，雖然 id+id+id 的 「+」 的結合性無論左右都不會影響結果。但萬一，萬一「+」的含義變成了「減法」，那麼左結合和右結合就會引起很大的問題了。

我們在這里講的「二義性」的「義」並非語義——我們現在在學習的內容是「語法分析器」，尚未到需要研究語言背後含義的階段。

我們現在講的「二義性」指的是一個句子對應多種分析樹。

二義性的體現，是文法對同一句子有不止一棵分析樹。這種問題由【句子產生過程中的某些推導有多於一種選擇】引起。懸空 else 問題就可以很好地體現這種【超過一種選擇】帶來的二義性問題，示例如下。

看下面這么個例子。。

（其實，我感覺這個其實比較像是「說話大喘氣」帶來的理解歧義問題。。。）上面的產生式中並沒體現出來該咋算分一塊，所以兩種完全不同的句子結構都是合法的。

二義性問題是有救的，大概有以下這三種辦法：

這些辦法的核心，其實都是將優先順序和結合性說明白。

核心：把優先順序和結合性說明白

既然要說明白，那就不能讓一個非終結符可以直接在當次推導中能推出會帶來優先順序和結合性歧義的東西。（對分析樹的一個內部節點，不會有出現在其下面的分支是相同的非終結符的情況。如果有得選，那就有得歧義了。沒得選才能確定地一路走到黑）

改寫為非二義文法的二義文法大概有下面這幾個特點：

改寫的關鍵步驟：

【例】改寫下面的二義文法為非二義文法。圖右側是要達成的優先順序和結合性

改寫的核心其實就兩句話：

所以能夠得到非終結符與運算的對應關系（因為不同的運算有不同的優先順序，我們想要引入多個優先順序就要引入多個新的非終結符。這樣每個非終結符就可以負責一個優先順序的運算符號，也就是說新的非終結符是與運算有關系的了。因此這里搞出來了「對應關系」四個字）如下：

優先順序由低到高分別是 +、 、-，而距離開始符號越近，優先順序越低。因此在這里的排序也可以+ -順序。每個符號對應一層的非終結符。根據所需要的結合性，則可確定是左遞歸還是右遞歸，以確定新的產生式長什麼樣子

【例】：規定優先順序和結合性，寫出改寫的非二義文法

我們已經掌握了一種叫做【改寫】的工具，能讓我們消除二義性。接下來我們就要用這個工具來嘗試搞搞懸空 else 問題！

懸空 else 問題出現的原因是 then 數量多於 else，讓 else 有多個可以結合的 then。在二義文法中，由於選哪兩個 then、else 配對都可以，故會引起出現二義的情況。在這里，我們規定 else 右結合，即與左邊最靠近的 then 結合。

為改寫此文法，可以將 S 分為完全匹配（MS）和不完全匹配（UMS）兩類。在 MS 中體現 then、else 個數相等即匹配且右結合；在UMS 中 then、else 不匹配，體現 else 右結合。

【例】：用改寫後的文法寫一個條件語句

經過檢查，無法再根據文法寫出其他分析樹，故已經消除了二義性

雖然二義文法會導致二義性，但是其並非一無是處。其有兩個顯著的優點：

在 Yacc 中，我們可以直接指定優先順序、結合性而無需自己重寫文法。

left 表示左結合，right 表示右結合。越往下的算符優先順序越高。

嗯就這么簡單。。。

我們其實可以把語言本身定義成沒有優先順序和結合性的。。然後所有的優先、結合都交由括弧進行控制，哪個先算就加括弧。把一個過程的結束用明確的標志標記出來。

比如在 Ada 中：

在 Pascal 中，給表達式加括弧：

⑻ 一個編譯原理問題

首先寫出指定句型的規范推導：

S→(L)→(L,S)→(L,(L))→(L,(S))→(L,(a))→(S,(a))

然後畫出分析樹如下圖

根據分析樹的葉子結點可以找出該句型的所有短語：

aS(a)S,(a)(S,(a))

直接短語，就是經過一次非終結符替換得到的短語：

aS沒了

句柄就是最左直接短語，要進行規約的部分，根據分析樹我們找到最左直接短語為：

S

⑼ 分析樹和語法樹的區別 編譯原理

如果給出短語等名詞的形式化的定義，便較難理解，不好求。我們通過構造語法樹來求解。首先你應該會根據文法將所給句型構造成語法樹的形式，即根據文法怎樣推導出句型E+T*F。如果你有數據結構二叉樹基礎的話這很簡單就構造出來了。構造出語法樹後，求短語看根節點，有T，和E。則短語為：E+T*F,T*F，而直接短語是指能直接推出葉子節點的根所對應的短語，可知該節點為T，直接短語為：T*F。句柄是最左直接短語，可知為：T*F。