上下文无关文法
上下文无关文法
上下文无关文法（，缩写为CFG），在计算机科学中，若一个形式文法 G = (V, Σ, P, S) 的产生式规则都取如下的形式：A -> "α"，则谓之。其中 A∈V ，"α"∈(V∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 A 总可以被字串 α 自由替换，而无需考虑字符 A 出现的上下文。如果一个形式语言是由上下文无关文法生成的，那么可以说这个形式语言是上下文无关的。（条目上下文无关语言）。
上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见LR分析器和LL分析器。
BNF（巴克斯-诺尔范式）经常用来表达上下文无关文法。
形式定义.
上下文无关文法 "G" 是 4-元组：
formula_1
这里的
此外，formula_7 是有限集合。formula_7 的成员叫做文法的“规则”或“产生式”。星号表示Kleene星号运算。
补充定义 1
对于任何字符串 formula_13，我们称 formula_14 生成 formula_15，写为 formula_16，如果 formula_17 使得 formula_18 且 formula_19。因此 formula_15 是应用规则 formula_21 于 formula_14 的结果。
补充定义 2
对于任何 formula_23（或 formula_24 在某些教科书中），如果 formula_25 使得 formula_26。
补充定义 3
文法 formula_1 的语言是集合
formula_28
补充定义 4
语言 formula_29 被称为是上下文无关语言（CFL），如果存在一个 CFG formula_30 使得 formula_31。
例子.
例子 1.
一个简单的上下文无关文法的例子是：S -> aSb | ab 。这个文法产生了语言 {anbn : 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算法）。
引用.
延伸阅读.
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.
