1．★已知文法g[s]：
s→saa|a
a→abb|b
b→csd|e
請證實aacabcbaadbed是文法的乙個句型，並寫出該句型的所有短語、素短語以及控制代碼。
解：本題考查「句型」、「短語」、「控制代碼」、「素短語」等概念。
因為存在從文法開始符號s到符號串aacabcbaadbed的推導過程（如圖6.1中的語法樹所示），所以符號串aacabcbaadbed是文法的句型。
從圖6.1中句型a1a1c1 a2b1c2ba2 a3d1b2ed2的語法樹可知，該句型的短語有：a1、b、
ba2 a3、c2ba2 a3d1、a2b1c2ba2 a3d1、e、a2b1c2ba2 a3d1b2e、c1 a2b1c2ba2 a3d1b2ed2、
a1a1c1 a2b1c2ba2 a3d1b2ed2
該句型的素短語有：ba2 a3、e
該句型的控制代碼為：b
2．★已知文法g[s]：
s→*a
a→0a1|*
（1） 求文法g的各非終結符號的firstvt集和lastvt集;
（2） 構造文法g的優先關係矩陣，並判斷該文法是否是算符優先文法；
（3） 分析句子*0*1，並寫出分析過程。
解：本題考查算符優先分析法中的有關知識：非終結符號的firstvt集和lastvt集的求法、算符優先關係的構造、算符優先文法的定義、算符優先分析過程等。
（1） 求文法g的各非終結符號的firstvt集和lastvt集。
根據非終結符號的firstvt集定義得到
firstvt（s）＝｛*｝
firstvt（s）＝｛0，*｝
根據非終結符號的lastvt集定義得到
lastvt（s）＝｛*，1｝
lastvt（s）＝｛1，*｝
ss a1 a
a1bc1 s d2
aa b2 b
a2 b1 b e
c2 s d1
s a2 a3ab
圖6.1句型aacabcbaadbed的語法樹
（2） 構造文法g的優先關係矩陣。
根據（1）中的firstvt集和lastvt集及算符優先關係構造演算法
對s→*a，按演算法第3種情形有：（*<0），（*<*）
對a→0a1，按演算法第1種情形有：（0|＝1）
按演算法第3種情形有：（0|<0）,(0|<*)
按演算法第4種情形有：（1|>1），(*|>1),
根據上述算符優先關係得到算符優先關係矩陣如表6.1所示。表中空白元素表示相應終結符號對之間沒有算符優先關係，即它們不會在任何句型中相繼出現。
表6.1文法的算符優先關係矩陣
(3)對句子「*0*1#」分析過程如表6.2所示。
表6.2分析輸入符號串「*0*1#」的過程
3．試為下列優先矩陣構造優先函式。
（1）(2)
解：本題考查優先函式的構造方法。
（1） 採用迭代法求優先函式，過程如下。
（2） 初始狀態：
第1次迭代：
第2次迭代：
第2次迭代沒有變化，所以第2次迭代結果便是優先函式。
（3） 採用bell有向圖法構造優先函式(省略)。
因為fs1可以到達的結點：gs3，gs4，fs4，gs3，gs2
fs2可以到達的結點：gs3，fs3，gs2，fs4，gs1
fs3可以到達的結點：gs2，fs3
fs4可以到達的結點：gs1，gs3，fs3，gs2，fs4
gs1可以到達的結點：fs3，fs4，gs2，gs1，gs3
gs2可以到達的結點：fs3，gs2
gs3可以到達的結點：fs4，fs3，gs1，gs3，gs2
gs4可以到達的結點：無
於是得到優先函式如表6.3所示。
4.試為文法g[z]：
z→a( )
a→(|ai|b)
b→i構造算符優先關係和優先函式。
解：本題考查算符優先關係的構造方法和優先函式的構造方法。
（1） 構造算符優先關係。
首先構造firstvt集和lastvt集，根據定義有：
firstvt（z）＝｛（， i， ）｝
firstvt（a）＝｛（， i， ）｝
firstvt（b）＝｛i｝
和 lastvt（z）＝｛｝｝
lastvt（a）＝｛（， ）， i｝
lastvt（b）＝｛i｝
按照構造算符優先關係的演算法得到如下算符優先關係：
「＝」的構造
∵有產生式z→a按演算法第1種情形有
「<」的構造
文法沒有滿足「<」的相鄰符號
「>」的構造
∵有產生式z→a按演算法第4種情形有： （ (>（） ，（）>（），（i>（）
∵有產生式a→ai按演算法第4種情形有： （ （>i）, ( )>i） ，（i>i）
∵有產生式a→b按演算法第4種情形有： (i>) )
綜合上述算符優先關係得到該文法的算符優先關係矩陣如表6.4所示。
(2)構造優先函式。
1 採用迭代法（先考慮所有的大於關係，再考慮所有的等於關係）。
初始狀態：
第1次迭代：
第2次迭代：
第3次迭代：
第3次迭代沒有變化，所以第3次迭代的的結果便是優先函式。
2 採用bell有向圖法構造優先函式，其過程如圖6.2所示。
圖6.2構造優先函式
因為f（可以到達的節點：g（，g），gi，f（
f）可以到達的節點：g（，gi
fi 可以到達的節點：g（，g），gi，f（
g（可以到達的節點：無
g）可以到達的節點：g（，g），gi，f（
gi 可以到達的節點：無
於是得到優先函式如表6.5所示。
表6.5文法的優先函式
5.給出文法g2：
s→sas|sbs|csd|es|f
（1）請證實這是乙個二義文法；
（2）給出什麼樣的約束條件，可構造出無衝突的lr分析表？請證實你的論點。
解：本題考查「二義文法」及二義文法的lr分析法。
（1）該文法是二義文法，因為它存在句子：
fafbf
該句子有兩棵不同的語法樹，如圖6.3中的（a），（b）所示。
（2）構造文法的無衝突的lr分析表。
首先對文法進行拓廣得到
s』→s 0
s→sas 1
s→sbs 2
s→csd 3
s→es 4
s→f 5
在此基礎上構造文法的識別活字首的有窮自動機(省略)。
因為：follow(s)=
構造文法的slr(1)分析表如表6.6所示。
6.已知文法：
g[a]：a→aa|(a)|ε
（1）該文法是lr(0)文法嗎？為什麼？
（2）請構造該文法的以lr(0)專案集為狀態的識別活字首的dfa。
（3）規定：出現「移進-歸約」衝突時，移進優先；出現「歸約-歸約」衝突時，優先採用文法中出現在前的產生式進行歸約。構造該文法的lr分析表。
解：本題考查對二義性文法進行lr分析的方法。
先構造出識別活字首的有窮自動機，然後根據其中出現的衝突情況確定無二義規則的使用。
首先構造拓廣文法如下：
1 a』→a
2 a→aa
3 a→(a)
4 a→ε
（1）該文法不是lr(0)文法。因為文法存在有相同左部的產生式
a→aa 和 a→ε
產生式a→ε在任何時候都只產生歸約專案。當由專案a』→.a派生出新專案時，同時得到
a→.(a) 和 a→.
將出現「移進→歸約」衝突。所以該文法不是lr(0)文法。
（2）構造該文法的以lr(0)專案集為狀態的識別活字首的dfa如圖6.4所示。
（3）因為出現「移進－規約」衝突時，移進優先；出現「規約－規約」衝突時，優先採用文法中出現在前的產生式進行規約，所以得到該文法的lr分析表如表6.7所示。
圖6.4 文法的以lr(0)專案集為狀態的識別活字首的dfa
7．★「算符優先分析採用「移進－歸約」技術，其規約過程是規範的。」這種說法是否正確？
解：本題考查算符優先分析法中句型的規約過程。
在算符優先分析法中，每步自下而上分析、識別和歸約的是當前句型的最左素短語，而不是嚴格地從左到右歸約控制代碼。
算符優先分析法只對算符優先文法進行，利用的是算符優先關係矩陣，該矩陣中只有終結符號間的優先關係，在歸約過程中，利用算符優先關係矩陣無法找到句型中相應於產生式的控制代碼。因此，在算符優先分析法中，每次歸約時，歸約的是當前句型的最左素短語——所以產生式對歸約沒有起作用，因而算符優先分析不是規範規約。
編譯原理個人知識點總結
詞法分析的基本功能 將字串行轉化為計算機內部表示 單詞 是指語言中具有獨立含義的最小的語義單位。乙個單詞你不可以繼續進行劃分，再劃分就失去了他原有的語義含義 單詞的種類 保留字，識別符號，特殊符號，常量 要對源程式語言進行分析，分析我們的單詞中應該有哪些型別 寫程式中對於描述清晰的問題，和單詞的形式...
化工原理知識點
第一章知識點 一 流體靜力學基本方程式 或注意 1 應用條件 靜止的連通著的同一種連續的流體。2 壓強的表示方法 絕壓 大氣壓 表壓表壓常由壓強表來測量 大氣壓 絕壓 真空度真空度常由真空表來測量。3 壓強單位的換算 1atm 760mmhg 10.33mh2o 101.33kpa 1.033kgf...
通訊原理知識點
通訊 利用電 或光 訊號將訊息中所包含的資訊從信源傳送到乙個或多個目的地。通訊的目的是傳遞訊息中所包含的資訊。訊息 資訊的物理表形形式，資訊 訊息的內涵，機訊息中索包含的受信者原來不知道而待知的有效內容。訊號 訊息的載體 數字通訊系統是利用數碼訊號來傳遞資訊的通訊系統。信源與信宿 可以是模擬的，也可...