編譯原理無二義文法

『壹』 編譯原理中文法二義性問題

二義性文法

【定義】 若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法。

二義性文法會引起歧義，應盡量避免之！

E E

E + E E * E

i E * E E + E i

i i i i

都可以表示i+i*i

所以G(E)：E -> E+E | E*E | (E) | i ;文法具有二義性。

文法二義性的消除：

【方法1】不改變文法的原有規則,加進一些非形式規定。

加進運算符的優先順序和結合規則對G(E)，規定*優於+，*和+服從左結合

【方法2】構造一個等價的無二義性文法，將排除 二義性的規則合並到文法中

G(E) -> G´(E) : E -> E+T | T T -> T*F | F F -> (E) | i ;

『貳』 編譯原理，證明下面文法G（s）是二義性的。

證明：

若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法，二義性文法會引起歧義，應盡量避免。

（S + S）和（S * S）以及（i S * S）和（S + S i）都可以表示i+i*i，所以G(S)：S -> S+S| S*S | (S) | i ；文法具有二義性。

『叄』 編譯原理題目：下列文法能否轉換為等價的非二義文法

二義性文法【定義】 若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法。二義性文法會引起歧義，應盡量避免之！ E E E + E E * E i E * E E + E i i i i i 都可以表示i+i*i 所以G(E)：E -> E+E | E*E | (E) | i ;文法具有二義性。文法二義性的消除：【方法1】不改變文法的原有規則,加進一些非形式規定。加進運算符的優先順序和結合規則對G(E)，規定*優於+，*和+服從左結合【方法2】構造一個等價的無二義性文法，將排除 二義性的規則合並到文法中 G(E) -> G′(E) : E -> E+T | T T -> T*F | F F -> (E) | i ;

『肆』 編譯原理全部的名詞解釋

書上有別那麼懶！。。。。
編譯過程的六個階段：詞法分析，語法分析，語義分析，中間代碼生成，代碼優化，目標代碼生成
解釋程序：把某種語言的源程序轉換成等價的另一種語言程序——目標語言程序，然後再執行目標程序。解釋方式是接受某高級語言的一個語句輸入，進行解釋並控制計算機執行，馬上得到這句的執行結果，然後再接受下一句。
編譯程序：就是指這樣一種程序，通過它能夠將用高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序(機器語言程序或匯編語言程序)。
解釋程序和編譯程序的根本區別：是否生成目標代碼
句子的二義性（這里的二義性是指語法結構上的。）:文法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)刪除無用賦值
基本塊定義
程序中只有一個入口和一個出口的一段順序執行的語句序列，稱為程序的一個基本塊。

給我分數啊。。。

『伍』 怎樣為「逗號分隔的左結合的標志符列表」構建無二義性的上下文無關文法

這段話時龍書上的原話:

依照慣例，9+5+2等價於(9+5)+2,9-5-2等價於（9-5）-2.當一個運算分量（比如上式中的5）的左右兩側都優於氨酸時，我們需要一些規則來決定哪個運算符被應用於該運算分量。我們說運算符」+「是左結合（associate）的，因為當一個運算分量左右兩側都有」+「號時，它屬於其左邊的運算符。在大多數程序設計語言中，加減乘除四種算術運算符都是左結合的。

某些常用的運算符是右結合偶的，比如指數運算符。作為另一個例子，C語言中的賦值運算符」=「及其後裔（即+=，-=等譯者注)也是右結合的。對表達式a=b=c的處理和對表達式a=(b=c)的處理相同。帶有右結合運算符的串，比如a=b=c，可以由如下文法產生;

right=letter=right|letter

letter=a|...........|z

這是右結合的分析樹，它向右下方延伸。

所以你的答案為 list——>list,a|a.

『陸』 如何消除二義性 編譯原理

1、需要在語法設計時就要考慮了，即使是C/C++也存在二義性、不確定性的語法，對於這種情況，各編譯器考慮的不同的方案，主要還是看你如何進行文法分析，可以選一種方便分析的一種去做。
2、要判斷二義性的存在，可以嘗試使用不同的優先順序解釋
假如解釋出現歧義，那麼一定存在二義性的語法（如經典的++運算）
3、要消除二義性，最簡單可行的就是定義優先順序，不過不一定適合所有情況。

『柒』 如何把文法改寫為無二義性，請舉例讓我明白，還有原理是什麼舉個簡單的文法就行了，謝謝

設置一個規則，該規則可在每個二義性情況下指出哪一個分析樹（或語法樹）是正確的。這樣的規則稱作消除二義性規則（disambiguating rule）。這樣的規則的用處在於：它無需修改文法（可能會很復雜）就可消除二義性；

文法舉例

(7)編譯原理無二義文法擴展閱讀

如果文法G中的某個句子存在不只一棵語法樹，則稱該句子是二義性的。如果文法含有二義性的句子，則稱該文法是二義性的。

二義性文法認為是一種語言語法的不完善說明，而且也應避免它。幸運的是，二義性文法在後面將介紹到的標准分析演算法的測試中總是失敗的，而且也開發出了標准技術體系來解決在程序設計語言中遇到的典型二義性。

『捌』 編譯原理：證明下面文法G【s】是二義性的

證明：

若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法，二義性文法會引起歧義，應盡量避免。

（S + S）和（S * S）以及（i S * S）和（S + S i）都可以表示i+i*i，所以G(S)：S -> S+S| S*S | (S) | i ；文法具有二義性。

『玖』 編譯原理 正則語言 二義文法 急~

這個沒有一個好老師，自己咬文嚼字看懂是很累的
二義性文法

【定義】 若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法。

二義性文法會引起歧義，應盡量避免之！
G(E)：E -> E+E | E*E | (E) | i
這兩種展開
E E
E + E E * E
i E * E E + E i
i i i i

都可以表示i+i*i

所以;文法具有二義性。