确定上下文无关文法

在形式文法理论中，确定上下文无关文法(DCFG)是上下文无关文法的真子集。确定上下文无关文法是确定下推自动机可识别的文法。确定上下文无关语言是确定上下文无关文法所定义的形式语言。

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

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

参见

引用

^ Hopcroft, John; Rajeev Motwani & Jeffrey Ullman. Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. 2001: 246–253.

这是一篇与逻辑学相关的小作品。您可以通过编辑或修订扩充其内容。

[1] Hopcroft, John; Rajeev Motwani & Jeffrey Ullman. Introduction to automata theory, languages, and computation 2nd edition. Addison-Wesley. 2001: 246–253.

[1]