基本介紹
- 中文名：確定上下文無關文法
- 學科：計算機
簡介,意義,形式文法,上下文無關文法,
簡介
意義
它們在計算機科學領域中特別重要，因為這些文法可以有效的識別，而非確定上下文無關文法需要回溯或其他複雜的技術；非確定步驟的每次出現，棧都必須被複製並接著被傳播(propagate)，消耗運行時間、記憶體或兩者。在實踐中，當你希望為非確定文法(比如用YACC)建立一個解析器的時候，你必須通過增加約束如優先權來改變分析器為確定的。
確定上下文無關語言是擁有無歧義上下文無關文法的語言的集合的真子集。例如，無歧義文法 S → 0S0 | 1S1 | ε，它定義了在字母 0 和 1 上的偶數長度的回文的語言，它能用確定下推自動機解析。
形式文法
形式文法描述形式語言的基本想法是，從一個特殊的初始符號出發，不斷的套用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。舉例來說，假設字母表只包含'a'和'b'兩個字元，初始符號是'S'，我們套用下述規則：
- 1. S -> aSb
- 2. S -> ba
於是我們可以通過把"S"重寫為"aSb"（規則1），我們還可以繼續套用這條規則把"aSb"重寫為"aaSbb"。這個重寫的過程不斷重複，直到結果中只包含字母表中的字母為止。在例子中，我們可以得到S -> aSb -> aaSbb -> aababb這樣的結果。由文法刻畫的語言，包含了所有可以這樣產生的字串，比如ba, abab, aababb, aaababbb等等。
上下文無關文法
形式文法描述形式語言的基本想法是，從一個特殊的初始符號出發，不斷的套用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。
