編譯原理表達式文法

㈠ 什麼是文法(編譯原理)

【定義】

文法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是開始符號

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

喬姆斯基（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

㈢ 編譯原理 將算術運算表達式寫成算符優先文法

算符優先分析法比LR分析（規范歸約）法的歸約速度快。在LR分析一章的語法分析器自動生成工具Yacc中，對算數表達式的歸約往往會用到算符優先關系的概念。算符優先分析的缺點是對文法有一定的限制，在實際應用中往往只用於算數表達式的歸約。由於算符優先分析不是規范歸約，所以可能把不是文法的句子錯誤的歸約成功

㈣ 編譯原理-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——>SS+|SS*|a能產生什麼語言，並驗證！ 求高人指導！

為了使問題簡化，我們考慮文法S->ss+|a，考慮s->ss*時，只要把+換成*即可。
0層遞歸是，s->a,文法的語言是{a}。是後綴表達式。
1層以內遞歸時，文法語言是{a,aa+}。是後綴表達式。
2層以內遞歸時，文法語言是{a,aa+}.{a,aa+}.{+}。其中.表示連接，是後綴表達式。
依此類推，多少層的遞歸都是後綴表達式。
把表達式的+換成*後依然為後綴表達式。
下面證明文法產生的語言是所有的以a為變數，以+和*為運算符的後綴表達式。
因為每個表達式都對應一個常規的表達式（如1*2+3就是常規表達式），下面只需證明語言能產生的後綴表達式對應所有的常規表達式。當常規表達式只有一個運算符，對應aa+或aa*。當常規表達式有兩個運算符，可寫成(表達式1）.{+|*}.(表達式2），因為表達式1和2都只含一個運算符，所以可以用語言表示，上述常規表達式可用後綴表達式（表達式1）.（表達式2）.{+l*}表示。所以不管常規表達式有多少個運算符，都可以由語言的後綴表達式對應。

㈥ 編譯原理

編譯原理)：利用編譯程序從源語言編寫的源程序產生目標程序的過程； 用編譯程序產生目標程序的動作。 編譯就是把高級語言變成計算機可以識別的2進制語言，計算機只認識1和0，編譯程序把人們熟悉的語言換成2進制的。

編譯程序把一個源程序翻譯成目標程序的工作過程分為五個階段：詞法分析；語法分析；語義檢查和中間代碼生成

(6)編譯原理表達式文法擴展閱讀：

編譯程序的語法分析器以單詞符號作為輸入，分析單詞符號串是否形成符合語法規則的語法單位，如表達式、賦值、循環等，最後看是否構成一個符合要求的程序，按該語言使用的語法規則分析檢查每條語句是否有正確的邏輯結構，程序是最終的一個語法單位。

編譯程序的語法規則可用上下文無關文法來刻畫。語法分析的方法分為兩種：自上而下分析法和自下而上分析法。自上而下就是從文法的開始符號出發，向下推導，推出句子。

而自下而上分析法採用的是移進歸約法，基本思想是：用一個寄存符號的先進後出棧，把輸入符號一個一個地移進棧里，當棧頂形成某個產生式的一個候選式時，即把棧頂的這一部分歸約成該產生式的左鄰符號。

㈦ 編譯原理-文法定義

文法定義公式如下:

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型文法。

㈧ 編譯原理考試問題:已知表達式文法G(Exp)

簡單起見，用E代表Exp，用T代表Term，用F代表Factor。下面是所求屬性文法

（1）E→ E1 + T E.val:=E1.val+T.val /* 為了區別→兩側的E, →右側的E用E1表示 */

（2）E→
T E.val:=T.val

（3）T→ T1 * F T.val:=T1.val*F.val

（4）T→
F T.val:=F.val

（5）F→（E） F.val:=E.val

（6）F→num F.val:=num.val

㈨ 【編譯原理】第二章：語言和文法

上述文法 表示，該文法由終結符集合 ，非終結符集合 ，產生式集合 ，以及開始符號 構成。
而產生式 表示，一個表達式（Expression） ，可以由一個標識符（Identifier） 、或者兩個表達式由加號 或乘號 連接、或者另一個表達式用括弧包裹（ ）構成。

約定 ：在不引起歧義的情況下，可以只寫產生式。如以上文法可以簡寫為：

產生式

可以簡寫為：

如上例中，

可以簡寫為：

給定文法 ，如果有 ，那麼可以將符號串 重寫 為 ，記作 ，這個過程稱為 推導 。
如上例中， 可以推導出 或 或 等等。

如果 ，
可以記作 ，則稱為 經過n步推導出 ，記作 。

推導的反過程稱為 歸約 。

如果 ，則稱 是 的一個 句型（sentential form ）。

由文法 的開始符號 推導出的所有句子構成的集合稱為 文法G生成的語言 ，記作 。
即：

例
文法

表示什麼呢？
代表小寫字母；
代表數字；
表示若干個字母和數字構成的字元串；
說明 是一個字母、或者是字母開頭的字元串。
那麼這個文法表示的即是，以字母開頭的、非空的字元串，即標識符的構成方式。

並、連接、冪、克林閉包、正閉包。
如上例表示為：

中必須包含一個 非終結符 。

產生式一般形式：
即上式中只有當上下文滿足 與 時，才能進行從 到 的推導。

上下文有關文法不包含空產生式（ ）。

產生式的一般形式：
即產生式左邊都是非終結符。

右線性文法 ：
左線性文法 ：
以上都成為正則文法。
即產生式的右側只能有一個終結符，且所有終結符只能在同一側。

例：（右線性文法）

以上文法滿足右線性文法。
以上文法生成一個以字母開頭的字母數字串（標識符）。
以上文法等價於 上下文無關文法 ：

正則文法能描述程序設計語言中的多數單詞。

正則文法能描述程序設計語言中的多數單詞，但不能表示句子構造，所以用到最多的是CFG。

根節點 表示文法開始符號S；
內部節點 表示對產生式 的應用；該節點的標號是產生式左部，子節點從左到右表示了產生式的右部；
葉節點 （又稱邊緣）既可以是非終結符也可以是終結符。

給定一個句型，其分析樹的每一棵子樹的邊緣稱為該句型的一個 短語 。
如果子樹高度為2，那麼這棵子樹的邊緣稱為該句型的一個 直接短語 。

直接短語一定是某產生式的右部，但反之不一定。

如果一個文法可以為某個句子生成 多棵分析樹 ，則稱這個文法是 二義性的 。

二義性原因：多個if只有一個else；
消岐規則：每個else只與最近的if匹配。

㈩ 編譯原理 while 語句文法

while(條件)
{
.......；//語句
X++或者X--；//做自增或自減運算來達到循環的過程
}
while後面跟一堆小括弧，裡面的條件判斷，類似IF語句，當條件滿足時做以下語句的循環，條件不滿足後直接跳出循環；
例題：
int i=0;//初始化i=0
while(i<5)//i=0滿足判斷的條件，進入循環語句
{
i++;//做自增運算，當i+到5時跳出循環，因為i不小於5了
}
printf("%d",i);//此時i的值為5