㈠ 編譯原理實驗二 LL(1)分析法
通過完成預測分析法的語法分析程序，了解預測分析法和遞歸子程序法的區別和聯系。使學生了解語法分析的功能，掌握語法分析程序設計的原理和構造方法，訓練學生掌握開發應用程序的基本方法。有利於提高學生的專業素質，為培養適應社會多方面需要的能力。
根據某一文法編制調試 LL(1)分析程序，以便對任意輸入的符號串進行分析。
構造預測分析表，並利用分析表和一個棧來實現對上述程序設計語言的分析程序。
分析法的功能是利用LL(1)控製程序根據顯示棧棧頂內容、向前看符號以及LL(1)分析表，對輸入符號串自上而下的分析過程。
對文法 的句子進行不含回溯的自上向下語法分析的充分必要條件是：
（1）文法不含左遞歸；
（2）對於文法中的每一個非終結符 的各個產生式的候選首符集兩兩不相交，即，若
Follow集合構造：
對於文法 的每個非終結符 構造 的演算法是，連續使用下面的規則，直至每個 不再增大為止：
僅給出核心部分
(1) GrammerSymbol.java
(2) GrammerSymbols.java
(3) Grammer.java
(4) LL1Grammer.java
㈡ 編譯原理的LL(1)文法是什麼意思
LL(1)的含義：第1個L表明自頂向下分析是從左向右掃描輸入串，第2個L表明分析過程中將用最左到推倒，1表明只需向右看一個符號便可決定如何推倒即選擇哪個產生式（規則）進行推導，類似也可以有LL（k）文法，也就是需要向前查看k個符號才能確定選用哪個產生式。
這是從我們編譯原理課本上抄來的，希望對你有幫助
㈢ 編譯原理實現判斷是不是一個文法的句子
構造LL(1)語法分析程序，任意輸入一個文法符號串，並判斷它是否為文法的一個句子。程序要求為該文法構造預測分析表，並按照預測分析演算法對輸入串進行語法分析，判別程序是否符合已知的語法規則，如果不符合（編譯出錯），則輸出錯誤信息。
㈣ 編譯原理-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(α) 包括空串ε，那麼這個產生式是不是間接左遞歸。
㈤ 編譯原理題目關於判斷LL(1)文法的
A 不是，因為含有左公共引子a
B 和D不是，因為含有左遞歸
C是，因為SELECT(S→aS) 與SELECT(S→b)的交集為空，符合LL(1)文法的定義。
㈥ 編譯原理的LL（1）文法是什麼意思
1.文法不含左遞歸，沒有公共左因子
2.對於文法中的每個非終結符A的產生式的候選首符集兩兩不相交。
3.對於文法中的每個非終結符A，它存在某個候選首符集包括ε，則FIRST（A）∩FOLLOW（A）=空
滿足以上條件的文法為LL（1）文法
㈦ 關於LL(1)文法的編譯原理題目
判斷是不是LL(1)，首先看候選式的首字元有沒有相同的，第二判斷首字元迭代進去是否會構成左遞歸。
如果首字元不相同，也沒用左遞歸就說明此文法是LL(1)
M→MaH｜H
H→(M)｜b(M)｜b
第一個產生式中存在左遞歸:M->MaH
第二個產生式中存在首字元相同:H->b(M) ,
H->b
怎麼改呢？
對第一個產生式，消除左遞歸就是要變成右遞歸，把右邊剩下的符號提到前面:
M->aHM'
M'->aHM'
對第二個產生式，提出公共因子
H->b( (M)|ε)
=>
H->bH'
H'->(M)|ε
㈧ 如何判斷一個文法是LL文法
1.
對文法G的句子進行確定的自頂向下語法分析的充分必要條件是，G的任意兩個具有相同左部的產生式A->α|β
滿足下列條件:
(1)如果α、β均不能推導出ε，則
FIRST(α)
∩
FIRST(β)
=
Φ。
(2)α
和
β
至多有一個能推導出
ε。
(3)如果
β
*═>
ε，則
FIRST(α)
∩
FOLLOW(A)
=
Φ。
將滿足上述條件的文法稱為LL(1)文法。
2.
第一個L代表從左向右掃描輸入符號串，第二個L代表產生最左推導，1代表在分析過程中執行每一步推導都要向前查看一個輸入符號——當前正在處理的輸入符號。
3.
LL(1)文法既不是二義性的，也不含左遞歸，對LL(1)文法的所有句子均可進行確定的自頂向下語法分析。
4.
並不是所有的語言都可以用LL(1)文法來描述，而且不存在判定某語言是否是LL(1)文法的演算法。也就是說，確定的自頂向下分析只能實現一部分上下文無關語言的分析，這就是LL(1)文法所產生的語言。另外，在上述LL(1)文法的條件中，要求：ε
∈
FIRST(α1)，ε
∈
FIRST(α2)，…ε
∈
FIRST(αn)
中至多有一個成立。
㈨ 編譯原理怎麼判斷是否為slr文法
LL(1)就是向前只搜索1個符號,即與FIRST()匹配,如果FIRST為空則還要考慮FELLOW.
LR需要構造一張LR分析表,此表用於當面臨輸入字元時,將它移進,規約（即自下而上分析思想）,接受還是出錯.
LR(0)找出句柄前綴,構造分析表,然後根據輸入符號進行規約.
SLR(1)使用LR(0)時若有沖突,不知道規約,移進,活移進哪一個,所以需要向前搜索,則只把有問題的地方向前搜索一次.
LR(1)1.在每個項目中增加搜索符.2.舉個列子如有A->α.Bβ,則還需將B的規則也加入.
LALR(1)就是假如兩個產生式集相同則將它們合並為一個,幾合並同心集.
㈩ 編譯原理 對一個文法進行改寫，然後判斷改寫後的文法是不是LL(1)文法，請問改寫方式的不同是否影響結果
樓上的答案是錯誤的。對同一種文法，可能同時存在兩種改寫方法，其中一種使改寫後的新文法為LL(1)文法，而另外一種使改寫後的新文法不為LL(1)文法。