[科普中国]-随机上下文无关文法

随机上下文无关文法（英语：Stochastic context-free grammar），即在上下文无关文法中，为每一个产生式规则赋予一个概率，标示应用一个产生式规则的可能性。

上下文无关文法上下文无关文法（英语：context-free grammar，缩写为CFG），在计算机科学中，若一个形式文法G = (N, Σ, P, S) 的产生式规则都取如下的形式：V->w，则谓之。其中 V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的。

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

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

上下文有关文法上下文有关文法(CSG，英语：context-sensitive grammar)是一种形式文法，其中任何产生式规则的左手端和右手端都可以被终结符和非终结符构成的上下文所围绕。上下文有关文法比上下文无关文法更一般性，但仍足够有秩序得可以被线性有界自动机所解析。

上下文有关文法的概念是诺姆·乔姆斯基在1950年代介入的，被作为描述自然语言的语法的一种方式，在自然语言中一个单词是否可以出现在特定位置上，要依赖于上下文。可以被上下文有关文法描述的形式语言叫做上下文有关语言。1

形式文法在计算机科学中，形式语言是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。

形式文法描述形式语言的基本想法是，从一个特殊的初始符号出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。2

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学