上下文无关文法

维基百科，自由的百科全书

在计算机科学中，若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，則称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的（条目上下文无关语言）。

上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL 分析器。

BNF（巴克斯-诺尔范式）经常用来表达上下文无关文法。

[编辑] 形式定义

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

$G = (V\,, \Sigma\,, R\,, S\,)$ 这里的

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

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

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

4. $R\,$ 是从 $V\,$ 到 $(V\cup\Sigma)^{*}$ 的关系，使得 $\exist\, 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$ 是应用规则 $(α,β)$ 于 $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 | ε 。这个文法产生了语言 {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 的数目的所有字串。

[编辑] 推导与语法树

[编辑] 范式

每一个不生成空串的上下文无关文法都可以转化为等价的 Chomsky 范式或 Greibach 范式。这里两个文法等价的含义指它们生成相同的语言。

由于 Chomsky 范式在形式上非常简单，所以它在理论和实践上都有应用。比如，对每一个上下文无关语言，我们可以利用 Chomsky 范式构造一个多项式算法，用它来判断一个给定字串是否属于这个语言（CYK算法）。

[编辑] 参见

[编辑] 注释

[编辑] 引用

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

[编辑] 进一步阅读

Michael Sipser（1997）．Introduction to the Theory of Computation．PWS Publishing．ISBN 0-534-94728-X． 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.

自动机理论: 形式语言和形式文法
乔姆斯基层级	文法	语言	极小自动机
类型 0	无限制	递归可枚举	图灵机
n/a	(无公用名)	递归	判定器
类型 1	上下文有关	上下文有关	线性有界
n/a	附标	附标	嵌套堆栈
n/a	树-邻接	适度上下文有关	嵌入下推
类型 2	上下文无关	上下文无关	非确定下推
n/a	确定上下文无关	确定上下文无关	确定下推
类型 3	正则	正则	有限
每个语言或文法范畴都是其直接上面的范畴的真子集。