在形式文法理論中，確定上下文無關(guān)文法(DCFG)是上下文無關(guān)文法的真子集。確定上下文無關(guān)文法是確定下推自動機(jī)可識別的文法。確定上下文無關(guān)語言是確定上下文無關(guān)文法所定義的形式語言。
它們在計(jì)算機(jī)科學(xué)領(lǐng)域中特別重要，因?yàn)檫@些文法可以有效的識別，而非確定上下文無關(guān)文法需要回溯或其他復(fù)雜的技術(shù)；非確定步驟的每次出現(xiàn)，棧都必須被復(fù)制并接著被傳播(propagate)，消耗運(yùn)行時(shí)間、內(nèi)存或兩者。在實(shí)踐中，當(dāng)你希望為非確定文法(比如用 YACC)建立一個(gè)解析器的時(shí)候，你必須通過增加約束如優(yōu)先級來改變分析器為確定的。
確定上下文無關(guān)語言是擁有無歧義上下文無關(guān)文法的語言的集合的真子集。例如，無歧義文法 S → 0S0 | 1S1 | ε，它定義了在字母 0 和 1 上的偶數(shù)長度的回文的語言，它不能用確定下推自動機(jī)解析。[1]
[編輯] 參見
[編輯] 引用
1. ^ Hopcroft, John，Rajeev Motwani & Jeffrey Ullman（2001）．Introduction to automata theory, languages, and computation 2nd edition．Addison-Wesley，246-253．
這是與邏輯學(xué)相關(guān)的小作品。你可以通過編輯或修訂擴(kuò)充其內(nèi)容。
來自“http://zh.wikipedia.org/wiki/%E7%A1%AE%E5%AE%9A%E4%B8%8A%E4%B8%8B%E6%96%87%E6%97%A0%E5%85%B3%E6%96%87%E6%B3%95”
分類: 形式語言
1個(gè)隱藏分類: 邏輯學(xué)小作品