[科普中国]-确定上下文无关文法

在形式文法理论中，确定上下文无关文法(DCFG)是上下文无关文法的真子集。

简介确定上下文无关文法是确定下推自动机可识别的文法。确定上下文无关语言是确定上下文无关文法所定义的形式语言。1

意义它们在计算机科学领域中特别重要，因为这些文法可以有效的识别，而非确定上下文无关文法需要回溯或其他复杂的技术；非确定步骤的每次出现，栈都必须被复制并接着被传播(propagate)，消耗运行时间、内存或两者。在实践中，当你希望为非确定文法(比如用YACC)建立一个解析器的时候，你必须通过增加约束如优先级来改变分析器为确定的。

确定上下文无关语言是拥有无歧义上下文无关文法的语言的集合的真子集。例如，无歧义文法 S → 0S0 | 1S1 | ε，它定义了在字母 0 和 1 上的偶数长度的回文的语言，它能用确定下推自动机解析。2

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

形式文法描述形式语言的基本想法是，从一个特殊的初始符号出发，不断的应用一些产生式规则，从而生成出一个字串的集合。产生式规则指定了某些符号组合如何被另外一些符号组合替换。举例来说，假设字母表只包含'a'和'b'两个字符，初始符号是'S'，我们应用下述规则：

1. S -> aSb

2. S -> ba

于是我们可以通过把"S"重写为"aSb"（规则1），我们还可以继续应用这条规则把"aSb"重写为"aaSbb"。这个重写的过程不断重复，直到结果中只包含字母表中的字母为止。在例子中，我们可以得到S -> aSb -> aaSbb -> aababb这样的结果。由文法刻画的语言，包含了所有可以这样产生的字串，比如ba, abab, aababb, aaababbb等等。1

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

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

最常见的文法的分类系统是诺姆·乔姆斯基于1956年发展的乔姆斯基谱系，这个分类谱系把所有的文法分成四种类型：无限制文法、上下文相关文法、上下文无关文法和正规文法。四类文法对应的语言类分别是递归可枚举语言、上下文相关语言、上下文无关语言和正规语言。2

本词条内容贡献者为:

程鹏 - 副教授 - 西南大学