查看“上下文无关文法”的源代码

{{NoteTA
|G1 = IT
}}
'''上下文无关文法'''（{{lang-en|context-free grammar}}，縮寫為CFG），在[[计算机科学]]中，若一个[[形式文法]] G = (N, Σ, P, S) 的产生式规则都取如下的形式：V <tt>-></tt> ''w''，則謂之。其中 V∈N ，''w''∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的（条目[[上下文无关语言]]）。

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

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

== 形式定义 ==
上下文无关文法 ''G'' 是 4-[[元组]]：
:<math>G = (V, \Sigma, R, S)</math>

这里的
# <math>V</math> 是“非终结”符号或变量的有限集合。它们表示在句子中不同类型的短语或子句。
# <math>\Sigma</math> 是“终结符”的有限集合，无交集于 <math>V</math>，它们构成了句子的实际内容。
# <math>S</math> 是开始变量，用来表示整个句子（或程序）。它必须是 <math>V</math> 的元素。
# <math>R</math> 是从 <math>V</math> 到 <math>(V\cup\Sigma)^{*}</math> 的关系，使得 <math>\exist w\in (V\cup\Sigma)^{*}: (S,w)\in R</math>。

此外，<math>R</math> 是有限集合。<math>R</math> 的成员叫做文法的“规则”或“产生式”。星号表示[[Kleene星号]]运算。

'''补充定义 1'''

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

'''补充定义 2'''

对于任何 <math>u, v\in (V\cup\Sigma)^{*}, u\stackrel{*}{\Rightarrow} v</math>（或 <math>u\Rightarrow\Rightarrow v</math> 在某些教科书中），如果 <math>\exists u_{1}, u_{2}, \cdots u_{k}\in (V\cup\Sigma)^{*}, k\geq 0</math> 使得 <math>u\Rightarrow u_{1}\Rightarrow u_{2}\cdots\Rightarrow u_{k}\Rightarrow v</math>。

'''补充定义 3'''

文法 <math>G = (V, \Sigma, R, S)</math> 的语言是集合

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

'''补充定义 4'''

语言 <math>L</math> 被称为是上下文无关语言（CFL），如果存在一个 CFG <math>G</math> 使得 <math>L=L(G)</math>。

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

=== 例子 2 ===
这个例子可以产生变量 x,y,z 的算术表达式：
:S <tt>-></tt> T + S | T - S | T
:T <tt>-></tt> T * T | T / T | ( S ) | x | y | z
例如字串 "( x + y ) * x - z * y / ( x + x )" 就可以用这个文法来产生。

=== 例子 3 ===

字母表 {a,b} 上 a 和 b 数目不相等的所有字串可以由下述文法产生：
:S <tt>-></tt> U | V
:U <tt>-></tt> TaU | TaT
:V <tt>-></tt> TbV | TbT
:T <tt>-></tt> 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算法]]）。

== 参见 ==
* [[上下文有关文法]]
* [[形式文法]]
* [[分析表达式文法]]
* [[随机上下文无关文法]]
*[[巴科斯范式]]
*[[乔姆斯基范式]]
*[[Greibach范式]]

== 引用 ==
{{refbegin}}
* Chomsky, Noam (Sept. 1956). "Three models for the description of language". Information Theory, IEEE Transactions 2 (3).
{{refend}}

== 延伸阅读 ==
{{refbegin}}
* {{cite book|author = [[Michael Sipser]] | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | id = 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.
{{refend}}

{{形式语言与形式文法}}

[[Category:编译原理]]
[[Category:形式语言|S]]