確定上下文無關文法

在形式文法理論中，確定上下文無關文法(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]