編譯原理規范句型是什麼

『壹』 編譯原理，設文法G[E]如下，句型T＋T * F＋a的素短語是__

試給出句型T－T／F＋a和T＋T＊F－F↑a的短語、句柄、素短語：

句型1：短語TT／F＋a， T－T／F， T， T／F， a

句型T

素短語： T／F，a

句型2：短語E＋T＊F＿F↑a， E＋T＊F， T＊F，F↑a， a

句型T＊F

素短語： T＊F，a

(1)編譯原理規范句型是什麼擴展閱讀

文法：以有窮的集合描述無窮的計劃的工具。

字母表：元素的非空有窮集合，其中的元素稱為符號，因此也叫符號集。

符號串：由字母表中的元素組成的任何有窮序列，串中的元素個數叫做符號串的長度，空符號串ε，長度為0。

符號串的運算：

連接－符號串x ＝ ab，y＝cd， xy ＝ abcd

方冪－z＝xn，當n ＝ 0， z ＝ ε，當 n ＝ 2， z ＝ xx

集合的閉包－∑＊ ＝ ∑0 ∪∑1 ∪∑2 ∪?∪∑n

∑＋ 為正閉包 ＝ ∑1 ∪∑2 ∪?∪∑n

『貳』 編譯原理 題目,誰會的,幫忙看看,頭都大了!

1D 2C 3B 4D 5 A 6D 7D 8B 9C 10 B
11C 12D 13 C 14A 15C 16C 17C 18B 19B 20C
21A 22B

『叄』 編譯原理-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(α) 包括空串ε，那麼這個產生式是不是間接左遞歸。

『肆』 一個編譯原理問題

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

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

然後畫出分析樹如下圖

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

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

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

aS沒了

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

S

『伍』 【編譯原理】第四章：語法分析

從分析樹的根節點到葉節點方向構造分析樹。
即從開始符號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) 。

『陸』 什麼是(文法的)規范推導(編譯原理))

規范推導：最右推導

最右推導、最左推導、規范推導、規范句型

對於文法：G[S]：S → aAS | a

                             A → SbA | SS | ba

最右推導：S＝> aA S ＝>a A a＝>aSb A a

                    ＝>a S bbaa＝>aabbaa(每次只推導 最右邊 的非終結符，直到推導完畢)

                    (得到的句型為 規范句型 )

最左推導： S＝>a A S＝>a S bAS＝>aab A S

                     ＝>aabba S ＝>aabbaa(與最右推導類比理解)

『柒』 編譯原理中的短語、直接短語、句柄

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

『捌』 有關編譯原理

⑴拓廣文法 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,#} ，所以無法解決沖突