形式定义

上下文无关文法 G 是 4-元组：

G = ( V , Σ Σ --> , R , S ) {\displaystyle G=(V\,,\Sigma \,,R\,,S\,)} 这里的

1. V {\displaystyle V\,} 是“非终结”符号或变量的有限集合。它们表示在句子中不同类型的短语或子句。

2. Σ Σ --> {\displaystyle \Sigma \,} 是“终结符”的有限集合，无交集于 V {\displaystyle V\,} ，它们构成了句子的实际内容。

3. S {\displaystyle S\,} 是开始变量，用来表示整个句子（或程序）。它必须是 V {\displaystyle V\,} 的元素。

4. R {\displaystyle R\,} 是从 V {\displaystyle V\,} 到 ( V ∪ ∪ --> Σ Σ --> ) ∗ ∗ --> {\displaystyle (V\cup \Sigma )^{*}} 的关系，使得 ∃ ∃ --> w ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ∗ ∗ --> : ( S , w ) ∈ ∈ --> R {\displaystyle \exists \,w\in (V\cup \Sigma )^{*}:(S,w)\in R} 。

此外， R {\displaystyle R\,} 是有限集合。 R {\displaystyle R\,} 的成员叫做文法的“规则”或“产生式”。星号表示Kleene星号运算。

补充定义 1

对于任何字符串 u , v ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ∗ ∗ --> {\displaystyle u,v\in (V\cup \Sigma )^{*}} ，我们称 u {\displaystyle u\,} 生成 v {\displaystyle v\,} ，写为 u ⇒ ⇒ --> v {\displaystyle u\Rightarrow v\,} ，如果 ∃ ∃ --> ( α α --> , β β --> ) ∈ ∈ --> R , u 1 , u 2 ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ∗ ∗ --> {\displaystyle \exists (\alpha ,\beta )\in R,u_{1},u_{2}\in (V\cup \Sigma )^{*}} 使得 u = u 1 α α --> u 2 {\displaystyle u\,=u_{1}\alpha u_{2}} 且 v = u 1 β β --> u 2 {\displaystyle v\,=u_{1}\beta u_{2}} 。因此 v {\displaystyle v} 是应用规则 ( α α --> , β β --> ) {\displaystyle (\alpha ,\beta )} 于 u {\displaystyle u} 的结果。

补充定义 2

对于任何 u , v ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ∗ ∗ --> , u ⇒ ⇒ --> ∗ ∗ --> v {\displaystyle u,v\in (V\cup \Sigma )^{*},u{\stackrel {*}{\Rightarrow }}v} （或 u ⇒ ⇒ -->⇒ ⇒ --> v {\displaystyle u\Rightarrow \Rightarrow v\,} 在某些教科书中），如果 ∃ ∃ --> u 1 , u 2 , ⋯ ⋯ --> u k ∈ ∈ --> ( V ∪ ∪ --> Σ Σ --> ) ∗ ∗ --> , k ≥ ≥ --> 0 {\displaystyle \exists u_{1},u_{2},\cdots u_{k}\in (V\cup \Sigma )^{*},k\geq 0} 使得 u ⇒ ⇒ --> u 1 ⇒ ⇒ --> u 2 ⋯ ⋯ --> ⇒ ⇒ --> u k ⇒ ⇒ --> v {\displaystyle u\Rightarrow u_{1}\Rightarrow u_{2}\cdots \Rightarrow u_{k}\Rightarrow v} 。

补充定义 3

文法 G = ( V , Σ Σ --> , R , S ) {\displaystyle G=(V\,,\Sigma \,,R\,,S\,)} 的语言是集合

补充定义 4

语言 L {\displaystyle L\,} 被称为是上下文无关语言（CFL），如果存在一个 CFG G {\displaystyle G\,} 使得 L = L ( G ) {\displaystyle L\,=\,L(G)} 。

例子

例子 1

一个简单的上下文无关文法的例子是：S -> aSb | ab 。这个文法产生了语言 {a b : n ≥ 1} 。不难证明这个语言不是正则的。

例子 2

这个例子可以产生变量 x,y,z 的算术表达式：

例如字串 "( x + y ) * x - z * y / ( x + x )" 就可以用这个文法来产生。

例子 3

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

这里 T 可以产生 a 和 b 数目相等的所有字串，U 可以产生 a 的数目多于 b 的数目的所有字串， V 可以产生 a 的数目少于 b 的数目的所有字串。

推导与语法树

范式

每一个不生成空串的上下文无关文法都可以转化为等价的 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.

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。