上下文无关文法
维基百科，自由的百科全书
在计算机科学中，若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，則称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的﹙条目上下文无关语言﹚。
上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL 分析器。
BNF ﹙巴克斯-诺尔范式﹚经常用来表达上下文无关文法。
目录 |
[编辑] 例子
[编辑] 例子 1
一个简单的上下文无关文法的例子是：S -> aSb | ε 。这个文法产生了语言 {anbn : n ≥ 0} 。不难证明这个语言不是正规的。
[编辑] 例子 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 算法﹚。
