上下文无关文法

上下文无关文法（英语：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.