上下文無關文法

上下文無關文法（英語：context-free grammar，縮寫為CFG），在計算機科學中，若一個形式文法 G = (V, Σ, P, S) 的產生式規則都取如下的形式：A -> α，則謂之。其中 A∈V ，α∈(V∪Σ)* 。上下文無關文法取名為「上下文無關」的原因就是因為字符 A 總可以被字串 α 自由替換，而無需考慮字符 A 出現的上下文。如果一個形式語言是由上下文無關文法生成的，那麼可以說這個形式語言是上下文無關的。（條目上下文無關語言）。

上下文無關文法重要的原因在於它們擁有足夠強的表達力來表示大多數程序設計語言的語法；實際上，幾乎所有程序設計語言都是通過上下文無關文法來定義的。另一方面，上下文無關文法又足夠簡單，使得我們可以構造有效的分析算法來檢驗一個給定字串是否是由某個上下文無關文法產生的。例子可以參見LR分析器和LL分析器。

BNF（巴克斯-諾爾範式）經常用來表達上下文無關文法。

形式定義

上下文無關文法 G 是 4-元組：

G=(V,\Sigma ,R,S)

這裡的

$V$ 是「非終結」符號或變量的有限集合。它們表示在句子中不同類型的短語或子句。
$\Sigma$ 是「終結符」的有限集合，無交集於 $V$ ，它們構成了句子的實際內容。
$S$ 是開始變量，用來表示整個句子（或程序）。它必須是 $V$ 的元素。
$R$ 是從 $V$ 到 $(V\cup \Sigma )^{*}$ 的關係，使得 $\exists w\in (V\cup \Sigma )^{*}:(S,w)\in R$ 。

此外， $R$ 是有限集合。 $R$ 的成員叫做文法的「規則」或「產生式」。星號表示Kleene星號運算。

補充定義 1

對於任何字符串 $u,v\in (V\cup \Sigma )^{*}$ ，我們稱 $u$ 生成 $v$ ，寫為 $u\Rightarrow v$ ，如果 $\exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}$ 使得 $u=u_{1}\alpha u_{2}$ 且 $v=u_{1}\beta u_{2}$ 。因此 $v$ 是應用規則 $(\alpha ,\beta )$ 於 $u$ 的結果。

補充定義 2

對於任何 $u,v\in (V\cup \Sigma )^{*},u{\stackrel {*}{\Rightarrow }}v$ （或 $u\Rightarrow \Rightarrow v$ 在某些教科書中），如果 $\exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0$ 使得 $u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v$ 。

補充定義 3

文法 $G=(V,\Sigma ,R,S)$ 的語言是集合

L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}

補充定義 4

語言 $L$ 被稱為是上下文無關語言（CFL），如果存在一個 CFG $G$ 使得 $L=L(G)$ 。

例子

例子 1

一個簡單的上下文無關文法的例子是：S -> aSb | ab 。這個文法產生了語言 {aⁿbⁿ : n ≥ 1} 。不難證明這個語言不是正則的。

例子 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 的數目的所有字串。

推導與語法樹

最左推導

在推導的任何一步α=> β中，都是對α中的最左邊非終結符進行替換。如文法:

S -> AB

A -> a|t

B -> +CD

C -> a

D -> a

那麼最左推導為:

S => AB => aB => a+CD => a+aD => a+aa

範式

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

由於Chomsky範式在形式上非常簡單，所以它在理論和實踐上都有應用。比如，對每一個上下文無關語言，我們可以利用Chomsky範式構造一個多項式算法，用它來判斷一個給定字串是否屬於這個語言（CYK算法）。

參見

引用

Chomsky, Noam (Sept. 1956). "Three models for the description of language". Information Theory, IEEE Transactions 2 (3).

延伸閱讀

Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6. Section 2.1: Context-Free Grammars, pp.91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp.156–159. Section 5.1.1: Reductions via computation histories: pp.176–183.