編譯原理句型
『壹』 編譯原理什麼是素短語
編譯原理中，素短語是至少含義一個終結符，並且自身不包含任何更小素短語的一種短語。
素短語是一種特殊的短語，它是一個遞歸的定義，至少含有一個終結符，並且除它自身之外不再含任何更小的素短語，所謂最左素短語就是處於句型最左邊的素短語的短語。
一個算符優先文法G的任何句型的最左素短語是滿足以下條件的最左子串NaNb…NcNdN(N是非終結符，a,b,c,d是終結符)。例如：句型T+T*F+id，T*F是最左素短語，id是素短語。
(1)編譯原理句型擴展閱讀：
通過語法樹可以得知素短語：
1、每個句型對應一棵語法樹
2、每棵語法樹的葉子結點從左到右排列構成一個句型
3、每棵語法樹的子樹的葉子結點從左到右排列構成一個短語
4、每棵語法樹的簡單子樹（只有父子兩層結點）的葉子結點從左到右排列構成一個簡單(直接)短語。
5、素短語是至少包含一個終結符的短語，但它不能包含其它素短語。
『貳』 編譯原理實現判斷是不是一個文法的句子
構造LL(1)語法分析程序，任意輸入一個文法符號串，並判斷它是否為文法的一個句子。程序要求為該文法構造預測分析表，並按照預測分析演算法對輸入串進行語法分析，判別程序是否符合已知的語法規則，如果不符合（編譯出錯），則輸出錯誤信息。
『叄』 編譯原理筆記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 中，給表達式加括弧：
『肆』 有關編譯原理
⑴拓廣文法 1 分
G[S ′ ]: S ′→ S ⑴
S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA ：
⑵ 該文法的 LR(0) 分析表：
狀態 ACTION GOTO
a b # S A
0 S 2 1
1 S 3 acc
2 r 3 r 3 r 3
3 S 5 4
4 r 2 r 2 /S 6 r 2
5 r 5 r 5 r 5
6 S 2 7
7 r 4 /S 3 r 4 r 4
⑶ LR(0) 文法：該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中沒有沖突狀態。
該文法不是 LR(0) 文法
因為存在沖突狀態： I 4 和 I 7
⑷ SLR(1) 文法：該文法的以 LR(0) 項目集為狀態的識別規范句型活前綴的 DFA 中有沖突狀態，沖突可用 FOLLOW 集解決。
該文法不是 SLR(1) 文法。
因為 FOLLOW(S)={a,b,#} ，所以無法解決沖突
『伍』 編譯原理中文法二義性問題
二義性文法
【定義】 若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法。
二義性文法會引起歧義，應盡量避免之！
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(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
所以;文法具有二義性。
『柒』 句柄的編譯原理
一個句型的最左直接短語稱為該句型的句柄，句型的句柄是和某產生式右部匹配的子串，並且，把它規約成該產生式左部的非終結符，代表了最右推導過程的逆過程的一步。
如右圖，在推導過程中，S→aABe→aAde→aAbcde→abbcde，此四步的句柄分別為aABe,d,Abc,b
句柄的特徵：
1. 它是直接短語，即某規則右部。
2. 它具有最左性。
注意：短語、直接短語和句柄都是針對某一句型的，特指句型中的哪些符號子串能構成短語和直接短語，離開具體的句型來談短語、直接短語和句柄是無意義的。另外句柄的右邊僅含終結符如果文法二義，那麼句柄可能不唯一。
『捌』 【編譯原理】第四章：語法分析
從分析樹的根節點到葉節點方向構造分析樹。
即從開始符號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) 。
『玖』 編譯原理 句型的句柄怎麼求
句型aabbAb的句柄是D: bA;
S->aB->aaBB->aabSB->aabbAB->aabbAb
按照最左推導，其中的S->bA這步是最後的直接推導（即它推出的bA不再被繼續往下推導），雖然B->b也是這樣的，但不是最左的。
其實你根據句型畫個語法樹就一目瞭然了，句柄即是最左直接短語，首先要是直接短語（直接推導），再就是最左（按最左的話最先推出的）。