上下文无关文法
维基百科,自由的 encyclopedia
上下文无关文法(英语:context-free grammar,缩写为CFG),在电脑科学中,若一个形式文法 G = (V, Σ, P, S) 的产生式规则都取如下的形式:A -> α,则谓之。其中 A∈V ,α∈(V∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 A 总可以被字符串 α 自由替换,而无需考虑字符 A 出现的上下文。如果一个形式语言是由上下文无关文法生成的,那么可以说这个形式语言是上下文无关的。(条目上下文无关语言)。
上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程式设计语言的语法;实际上,几乎所有程式设计语言都是通过上下文无关文法来定义的。另一方面,上下文无关文法又足够简单,使得我们可以构造有效的分析算法来检验一个给定字符串是否是由某个上下文无关文法产生的。例子可以参见LR分析器和LL分析器。
BNF(巴克斯-诺尔范式)经常用来表达上下文无关文法。