編譯原理0123型文法定義

1. 編譯原理中，形式語言里怎麼區分2型文法與3型文法

二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文無關文法，表現在產生式上就是產生式的左部只有一個非終結符；3型文法從廣義上講包括左線形文法、右線形文法和正規文法 。
B、左線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最左端。
C、右線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最右端 。
D、正規文法是右線形文法的一個子集，其產生式右部只有三種情況：
1）空串
2）只有一個終結符
3）只有一個終結符後接一個非終結符
E、所有的3型文法都是2型文法。

2. 文法的類型

文法形式
在計算機科學中，文法是編譯原理的基礎，是描述一門程序設計語言和實現其編譯器的方法。文法的描述多用BNF(巴克斯範式)，而另一個重要的概念:正則表達式，也是文法的另一種形式。
文法分類
自從喬姆斯基(Chomsky)於1956年建立形式語言的描述以來，形式語言的理論發展很快。這種理論對計算機科學有著深刻的影響，特別是對程序設計語言的設計、編譯方法和計算復雜性等方面更有重大的作用。
喬姆斯基把文法分成四種類型，即0型、1型、2型和3型。這幾類文法的差別在於對產生式施加不同的限制。
多數程序設計語言的單詞的語法都能用正規文法或3型文法來描述。
3型文法G=(VN，VT，P，S)的P中的規則有兩種形式：一種是前面定義的形式，即：A→aB或A→a其中A，B∈VN ，a∈VT*，另一種形式是：A→Ba或A→a，前者稱為右線性文仿升法，後者稱為左線性文法。正規文法所描述的是VT*上的正規集。
四個文法類的定義是逐漸增加限制的，因此每一種正規文法都是上下文無關的，每一種上下文無關文法都是上下文有關的，而每一種上下文有關文法都是0型文法。稱0型文法產生的語言為0型語言。上下文有關文法、上下文無關文法和正規文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規語言。
類型說明
設G=(VN，VT，P，S)，如果它的每個產清搜生式α→β是這樣一種結構：α∈( VN∪VT )*且至少含有一個非終結符，而β∈( VN∪VT )*，則G是一個0型文法。
0型文法也稱短語文法。一個非常重要的理論結果是，0型文法的能力相當於圖靈機(Turing)。或者說，任何0型語言都是遞歸可枚舉的；反之，遞歸可枚舉集必定是一個0型語言。
對0型文法產生式的形式作某些限制，以給出1，2和3型文法的定義。
設G=(VN，VT，P，S)為一文法，若P中的每一個產生式α→β均滿足|β|≥|α| ，僅僅S→ε除外，則文法G是1型或上下文有關的。
在有些文獻給的定義中，將上下文有關文法的產生式的形式描述為α1Aα2→α1βα2，其中α1、α2和β都在( VN∪VT
)*中(即在V*中)，β≠ε，A在VN中。這種定義與前邊的定義等價。但它更能體現上下文有關這一術語，因為只有A出現在α1和α2的上下文中，才允許用β取代A。
設G=(VN，VT，P，S)，若P中的每一個產生式α→β滿足：α是一非終結符，β∈( VN∪VT )*則此文法稱為2型的或上下文無關的。有時將2型文法的產生式表示為形如：A→β其中A∈VN，也就是說用β取代非終結符A時，與A所在的上下文無關，因此取名為上下文無關文法。
例4.1和例4.2中的文法都是上下文無關的，下面我們再給出一個例子(例4.4)，例中的文法G是上下文無關文法，G的語言是由相同個數的a和b所組成的{a，b}*上的串。
設G=(VN，VT，P，S)，若P中的每一個產生式的形式都是A→aB或A→a，其中A和B都是非終結符，a是終結符，則G是3型文法或正規文法。
文法G定義為四元組(VN，VT，P，S )其中
VN:非終結符號(或語法實體，或變數)集；
VT:終結符號集；
P: 規則的集合；
VN，VT和P是 非空有窮集。
S:稱作識別符號或開始符號的一個非終結符，它至少要在一條產生式中作為左部出現。
VN和VT不含公共的元素，即VN ∩ VT = φ
用V表示VN ∪ VT ，稱為文法G的字母表或字匯表
規則答大歷，也稱重寫規則、產生式或生成式，是形如→或 ∷=的( ，)有序對，其中是字母表V的正閉包V+中的一個符號，是V*中的一個符號。  稱為規則的左部，  稱作規則的右部。

3. 編譯原理-文法定義

文法定義公式如下:

Chomsky 文法分類將文法分為四種，0型文法( PSG )、1型文法( CSG )、2型文法( CFG )和3型文法( RG )。

又被稱為無限制文法(Unrestricted Grammar), 或者短語結構文法（Phrase Structure Grammar）
定義: 對於產生式 α→β ， α 至少包含一個非終結符。

為什麼要叫無限制文法，明明它要求產生式的左部必須包含一個非終結符。

又被稱為上下文有關文法(Context-Sensitive Grammar)
定義：對於產生式 α→β , |α| <= |β| , 僅僅 S→ε 除外

為什麼叫做上下文有關文法？

一般情況下，這種產生式的形式為 α1Aα2→α1βα2

又被稱為上下文無關文法(Context-Free Grammar)
定義：對任一產生式 α→β ，都有 α∈VN，β∈(VN∪VT)*

為什麼叫上下文無關文法？

又被稱為正則文法（Regular Grammar，RG），分為右線性（Right Linear）文法和左線性（Left Linear）文法。

定義: 對任一產生式 α→β ，都有 α∈VN，β最多兩個字元元素，如果有二個字元必須是（終結符+非終結符）的格式，如果是一個字元，那麼必須是終結符。

根據產生式右部非終結符位置不同，分為右線性文法和左線性文法。

可以看出，不同文法就是對產生式進行逐層的限制，所以各個文法是包含關系，即0型文法包含1型文法；1型文法又包含2型文法；2型文法最後包含3型文法。

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

5. 四種文法的類型(編譯原理)

喬姆斯基（Chomsky）按產生式的類型把文法分為四種類型：0、1、2、3型文法。

*在下文中的產生式中，箭頭左邊的大寫字母為嚴格的非終結符，而其左邊的小寫字母不嚴格要求為非終結符，如[0型文法]中的第2條產生式。

【0型文法】

產生式形式：α→β

要求：箭頭左邊的α 至少 含有 一個非終結符 ， 其餘 不加任何限制

    例如，G：C→AaB

                     aA→a

                     B→b|Bb

【1型文法】

產生式形式：α→β

要求： |α|≤|β| (產生式左端的長度<=右端的長度)，S→ε除外。

例如G： C→aAB

               aA→aBa

               B→b|Bb 

【2型文法】(上下文無關文法)

產生式形式：A→β，A∈VN(終結符) ，β∈V *(VN∪VT，即可為終結符也可為非終結符) 

說明：當以β替換A時，與A的上下文環境無關；

          大部分程序設計語言近似於2型文法。

【3型文法】(正規文法 / 右線性文法)

產生式形式：A→a，A→aB，

說明：a∈VT(終結符) ，  A，B∈VN(非終結符)，即產生式右端的第一個符號必須為 終結符

例如 G：A→aB

              B→b|bB

【其他說明】對於這四種類型的文法：

*包含關系：0 > 1 > 2 > 3 (以'>'代替包含符，'A>B'譯為A包含B)

*嚴格程度：3 > 2 > 1 > 0

*判斷文法所屬類型的順序：3 → 2 → 1 → 0

6. 什麼是文法(編譯原理)

【定義】

文法G定義為四元組（VN，VT，P，S）

其中 VN   ：非終結符號(即語法變數)集

        VT   ： 終結符號集

                   VN∩VT =Φ，令V= VN∪VT，V稱為文法G的字母表或字匯表。

        P  ：產生式(α→β)集

        S ：開始符號，且S∈VN ，S至少要在一條規則的左部出現。

【約定】

一般地，文法G的 四元組 不用全部給出 ，而只將產生式寫出。

約定：

    （1）第一條產生式的左部是開始符號

    （2）用尖括弧括起來的（或 大寫字母 ）是非終結符號

    （3）不用尖括弧括起來（或 小寫字母 ）是終結符號

    （4）還有一種習慣寫法，即 G[S] ，其中 S 是 開始符號 。

【舉例】

    例: G=（VN，VT，P，S）

           其中  VN={S}，

           VT ={0，1}，

           P={S→0S1，S→01}

           S是開始符號

7. 編譯原理中的一概念：什麼是左線性正規文法

正規文法是左線性文法和右線性文法的統稱.它們都是Chomsky分類下的3型文法.由正規文法產生的語言稱為正規集.下面我們將會看到,這里之所以用「正規」二字為一種語言命名,是因為這種語言的結構可以用所謂正規式來描述.
1．右線性文法
設G[S]=(VN,VT,P,S)為CFG,若P中的產生或均有如下的形式：
A→aB或A→a（A∈VN,a∈VT）
則稱G為右線性文法.例如,文法
G1[S]=({S,A,B},{a,b},P1,S)
其中
P1={S→aA,A→aA,A→bB,A→b,B→bB,B→b}
為一右線性文法,G1所產生的正規集為
L(G1)={aibj |i,j≥1}
2．左線性文法
若一個文法G[S]=(VN,VT,P,S)中的產生式均有如下的形式：
A→Ba或A→a（A,B∈VN,a∈VT）
則稱G為左線性文法.例如,文法
G2[S]=({S,A},{a,b},P2,S)
其中
P2={S→Sb,S→Ab,A→Aa,A→a}
為一左線性文法,且有
L(G2)=L(G1)={aibj |i,j≥1}
請注意,雖然文法
G3[S]=({S,A,B},{a,b},P3,S)
其中
P3={S→aA,A→aA,A→Bb,A→b,B→Bb,B→b}
也同樣產生語言{aibj |i,j≥1},但由於G3中同時含有左線性產生式和右線性產生式,故G3不是正規文法.
另外
P4={S-->aA,A-->ab},
也不是正規文法

8. 編譯原理的文法是什麼

文法是描述語言規則的形式規則。實際上就是用一個四元組G=(VT,VN,S,P)定義的一個推理方式。其中VT是終結符，VN是非終結符，S是開始符號，P是一組產生規則。

9. 編譯原理文法

編譯原理文法的概念為：每一種自然語言或者是編程語言都需要文法來描述，文法相當於語言學的語義分析，即分析每一句話所表示的含義，編譯器需要利用文法來完成其語法分析和語義分析。

字母表是元素的非空有窮集合，字母表中的元素稱之為符號，因此，字母表也稱之為符號集。例如C語言中的字母表由字母、數字、關鍵字等組成。

符號串，就是由符號集中的元素組成的序列。例如，給定符號集a、b、c，那麼abc、abb、ac就是由該符號集組成的符號串。一個文法中，含有一個，或多個產生式，產生式，描述了將終結符集合和非終結符集合組合成串的方法。

10. 在編譯原理中，什麼是上下文無關文法什麼是語言

二型文法如下:S->AcS->ScA->abA->aAb三型文法如下:S->aSA->bAB->cBB->cA->BbA、2型文法是上下文無關文法，表現在產生式上就是產生式的左部只有一個非終結符；3型文法從廣義上講包括左線形文法、右線形文法和正規文法。B、左線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最左端。C、右線形文法產生式的右部要麼沒有非終結符，如果有非終結符也只能有一個，且必須位於產生式右部的最右端。D、正規文法是右線形文法的一個子集，其產生式右部只有三種情況：1）空串2）只有一個終結符3）只有一個終結符後接一個非終結符E、所有的3型文法都是2型文法。