編譯上下文無關文法

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

不嚴格地說：文法就是語法啦，用來說明語言的。上下文無關文法是文法規則的左部只能是一個文法符號的文法。

㈡ 如何定義上下文無關文法

程序設計語言的語法基本上都是上下文無關文法，應用十分廣泛。

在計算機科學中，若一個形式文法G = (N, Σ, P, S) 的產生式規則都取如下的形式：V -> w，則稱之為上下文無關的，其中 V∈N ，w∈(N∪Σ)* 。

上下文無關文法取名為「上下文無關」的原因就是因為字元 V 總可以被字串 w 自由替換，而無需考慮字元 V 出現的上下文。一個形式語言是上下文無關的，如果它是由上下文無關文法生成的﹙條目上下文無關語言﹚。

例子 1

一個簡單的上下文無關文法的例子是：S -> aSb | ε上下文無關文法。這個文法產生了語言 {anbn : n ≥ 0} 。不難證明這個語言不是正規的。

例子 2

這個例子可以產生變數 x,y,z 的算術表達式：

S -> T + S | T - S | T

T -> T * T | T / T | ( S ) | x | y | z

例如字串 "( x + y ) * x - z * y / ( x + x )" 就可以用這個文法來產生。

例子 3

字母表 {a,b} 上 a 和 b 數目不相等的所有字串可以由下上下文無關文法述文法產生：

S -> U | V

U -> TaU | TaT

V -> TbV | TbT

T -> aTbT | bTaT | ε

這里 T 可以產生 a 和 b 數目相等的所有字串，U 可以產生 a 的數目多於 b 的數目的所有字串， V 可以產生 a 的數目少於 b 的數目的所有字串。

㈢ 編譯原理：構造產生此語言的上下文無關文法G

對於文法G=(V, T, S, P)，如果產生式的形式如下：
A -> xB
A -> x
其中A, B屬於V，x屬於T*，則稱為右線性文法；相似的，如果產生式的形式如下：
A -> Bx
A -> x
則稱為左線性文法。右線性文法和左線性文法統稱為正則文法。
正則表達式的表達能力等價於正則文法，正則表達式的定義如下：
字母表中的任意字母是正則表達式，空串和空集也是正則表達式；
如果r, s是正則表達式，那麼r|s, rs, r*, (r)也是正則表達式。
正則表達式的擴展：
r+：一個或多個重復
. ：任意字元
[a-z]：字元范圍
[^abc]：不在給定集合中的任意字元
r?：可選
正則表達式只能使用終結符（字母表中的字元），因而很容易變得復雜又難懂，實際中，經常使用正則描述，正則描述允許使用非終結符定義表達式，很像EBNF，但是它限制在未完全定義之前，不能使用非終結符，也就是說不允許遞歸或自嵌套。
像正則表達式的表達能力等價於正則文法一樣，BNF範式的表達能力等價於上下文無關文法。BNF是「Backus Naur Form」的縮寫。John Backus和Peter Naur首次引入一種形式化符號來描述給定語言的語法。
BNF的元符號：
::= 表示「定義為 」，有的書上用-->
| 表示「或者」
< > 尖括弧用於括起非終結符。
BNF的擴展EBNF：
可選項被括在元符號「[」和「]」中
重復項（零個或者多個）被括在元符號「{」和「}」中
僅一個字元的終結符用引號（"）引起來，以和元符號區別開來
上述操作符不是嚴格限定的，有的人喜歡直接使用擴展正則表達式的操作符描述EBNF。除了方便表達以外，引入EBNF的另一個主要原因是為了更緊密地把文法映射到遞歸下降分析程序的真實代碼。當需要手動構造歸下降分析程序的時候，通常把上下文無關文法改寫為EBNF是必需的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
BNF的擴展EBNF：
可選項被括在元符號「[」和「]」中
重復項（零個或者多個）被括在元符號「{」和「}」中
僅一個字元的終結符用引號（"）引起來，以和元符號區別開來
上述操作符不是嚴格限定的，有的人喜歡直接使用擴展正則表達式的操作符描述EBNF。除了方便表達以外，引入EBNF的另一個主要原因是為了更緊密地把文法映射到遞歸下降分析程序的真實代碼。當需要手動構造歸下降分析程序的時候，通常把上下文無關文法改寫為EBNF是必需的。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。
如上所述，上下文無關文法的遞歸性，對其分析方法也有很大影響。首先，用作識別這些結構的演算法必須使用遞歸調用或顯式管理的分析棧。其次，用作表示語言語義結構的數據結構現在也必須是遞歸的（通常是一顆分析樹），而不再是線性的（如同用於詞法和記號中的一樣）了。
在程序設計語言中，通常用正則表達式描述詞法規則。但是正則表示式的表達能力有限，她無法表達括弧配對等語法形式，因而，需要引入表達能力更強的上下文無關文法。編譯程序中常用正則文法表示詞法，用上下文無關文法表示語法。那麼程序語言中那些屬於詞法哪些屬於語法呢？一個簡單的辦法，把所有能用正則文法表示的規則成為詞法，即我們用盡可能的使用正則文法表示更多的東西，那些無法用正則表示式表示的成為句法，如C語言中的{ statement; }語法形式。語言中有些規則使用上下文無關文法仍然無法描述，例如變數的定義在使用之前，類型匹配等等，這些通常稱為（靜態）語義，它們在編譯程序的靜態語義檢查階段進行檢測。
如果一個上下文無關文法G不是自嵌套或自遞歸的，即不存在如下推導：
U =>* xUy
那麼L(G)是正則語言。自嵌套的上下文無關文法不一定是正則語言。事實上，一個上下文無關文法是嚴格的，既不可能由正則文法產生，當且僅當該語言的一切文法都是自嵌套的。

㈣ 編譯原理-文法定義

文法定義公式如下:

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

㈤ 編譯原理文法

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

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

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

㈥ 形式語言總結（上下文無關文法與正則文法）

形式語言理論是用數學方法研究自然語言和人工語言如程序設計語言的語法的理論。它只 研究語言的組成規則，不研究語言的含義 。形式語言理論在自然語言的理解和翻譯、 計算機語言 的描述和編譯、社會和自然現象的模擬、語法制導的 模式識別 等方面有廣泛的應用。

形式文法被嚴格地定義為四元組G=（N，T，P，S），

根據P中生成式a→β的特點，可以將 形式文法 及其產生的 形式語言 分類，構成所謂的形式語言譜系。形式語言理論中重點研究四類 文法 和語言：

上述定義的4種語言類具有依次包含關系，即對於i=0，1，2，在不考慮 空字元串 時，i型語言都真包含i+1型語言。

每一個不生成空串的上下文無關文法都可以轉化為等價的Chomsky 範式或Greibach 範式。這里兩個文法等價的含義指它們生成相同的語言。

由於 Chomsky 範式在形式上非常簡單，所以它在理論和實踐上都有應用。比如，對每一個上下文無關語言，我們可以利用 Chomsky 範式構造一個多項式演算法，用它來判斷一個給定字串是否屬於這個語言（ CKY演算法 [限制：P滿足Chomsky範式]，chart演算法[Generalize the CKY algorithm for all CFG]）。

正則定義與上下文無關文法的重要區別在於，在正則定義中是不允許遞歸定義的，例如A → aA|b不是一個正則定義，為其左邊的A必須是一個新的符號，也就是說不能在其他地方定義過，但是其右邊要求每一個符號都是定義過的，因此這個定義無法滿足。而上下文無關文法則沒有這個約束，因此A → aA|b是一個上下文無關文法的產生式，但不是正則定義的定義式。

正則表達式在編譯器構建中一般用來進行詞法分析，通過NFA、DFA就可以識別，而更復雜的文法就需要以來其他演算法了。

PPT1
PPT2

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

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

㈧ 編譯原理中的語法和文法一樣嗎

編譯原理中的語法和文法是不一樣的，但卻融會貫通。
在計算機科學中，文法是編譯原理的基礎，是描述一門程序設計語言和實現其編譯器的方法。
文法分成四種類型，即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型語言。上下文有關文法、上下文無關文法和正規文法產生的語言分別稱為上下文有關語言、上下文無關語言和正規語言。

㈨ 上下文無關文法適合描述什麼規則....很急（編譯原理的）

上下無關文法，適合用來描述程序設計的語言。c語言，php，java的語法規則都涉及到上下無關文法。
正規文法用來識別單詞。

㈩ 編譯原理 文法類型

    0型文法(Type-0 Grammar)

    1型文法(Type-1 Grammar)

    2型文法(Type-2 Grammar)

    3型文法(Type-3 Grammar)

無限制文法(Unrestricted Grammar) /短語結構文法(Phrase Structure Grammar, PSG )

∀α → β∈P， α中至少包含1個非終結符

0型語言

由0型文法G生成的語言L(G )

上下文有關文法(Context-Sensitive Grammar , CSG )

∀α → β∈P，｜α｜≤｜β｜

產生式的一般形式： α1Aα2 → α1βα2 ( β≠ε )

上下文有關語言（1型語言）

由上下文有關文法(1型文法) G生成的語言L(G )

上下文無關文法(Context-Free Grammar, CFG )

∀α → β∈P，α ∈ VN

產生式的一般形式：A→β

上下文無關語言（2型語言）

由上下文無關文法(2型文法) G生成的語言L(G )

正則文法(Regular Grammar, RG )

右線性(Right Linear)文法： A→wB 或 A→w

左線性(Left Linear) 文法： A→Bw 或 A→w

左線性文法和右線性文法都稱為正則文法

0型文法：α中至少包含1個非終結符

1型文法（CSG） ：｜α｜≤｜β｜

2型文法（CFG） ：α ∈ VN

3型文法（RG）：A→wB 或 A→w (A→Bw 或A→w)

0型文法包含1型文法，1型文法包含2型文法，2型文法包含3型文法