-
上下文無關文法
鎖定
形式文法描述形式語言的基本想法是,從一個特殊的初始符號出發,不斷的應用一些產生式規則,從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。
- 中文名
- 上下文無關文法
- 外文名
- context-free grammar
- 縮 寫
- CFG
上下文無關文法簡介
上下文無關文法(英語:context-free grammar,縮寫為CFG),在計算機科學中,若一個形式文法G = (N, Σ, P, S) 的產生式規則都取如下的形式:V->w,則謂之。其中 V∈N ,w∈(N∪Σ)* 。上下文無關文法取名為“上下文無關”的原因就是因為字符 V 總可以被字串 w 自由替換,而無需考慮字符 V 出現的上下文。一個形式語言是上下文無關的,如果它是由上下文無關文法生成的(條目上下文無關語言)。
上下文無關文法重要的原因在於它們擁有足夠強的表達力來表示大多數程序設計語言的語法;實際上,幾乎所有程序設計語言都是通過上下文無關文法來定義的。另一方面,上下文無關文法又足夠簡單,使得我們可以構造有效的分析算法來檢驗一個給定字串是否是由某個上下文無關文法產生的。例子可以參見LR 分析器和LL 分析器。
上下文無關文法形式定義
上下文無關文法G是 4-元組:
1.
是“非終結”符號或變量的有限集合。它們表示在句子中不同類型的短語或子句。
2.
是“終結符”的有限集合,無交集於
,它們構成了句子的實際內容。
3.
是開始變量,用來表示整個句子(或程序)。它必須是
的元素。
4.
是從
到
的關係,使得
。
補充定義 1
對於任何字符串
,我們稱
生成
,寫為
,如果
使得
且
。因此v是應用規則
於
的結果。
補充定義 2
對於任何
(或
在某些教科書中),如果
使得
。
補充定義 3
文法
的語言是集合
補充定義 4
上下文無關文法範式
每一個不生成空串的上下文無關文法都可以轉化為等價的Chomsky 範式或Greibach 範式。這裏兩個文法等價的含義指它們生成相同的語言。
由於 Chomsky 範式在形式上非常簡單,所以它在理論和實踐上都有應用。比如,對每一個上下文無關語言,我們可以利用 Chomsky 範式構造一個多項式算法,用它來判斷一個給定字串是否屬於這個語言(CYK算法)。
[2]
上下文無關文法參見
- 分析表達式文法
- 參考資料
-
- 1. Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6. Section 2.1: Context-Free Grammars, pp.91–101. Section 4.1.2: Decidable problems concerning context-free languages, pp.156–159. Section 5.1.1: Reductions via computation histories: pp.176–183.
- 2. Chomsky, Noam (Sept. 1956). "Three models for the description of language". Information Theory, IEEE Transactions 2 (3).