基本介紹
- 中文名：隨機上下文無關文法
- 外文名：Stochastic context-free grammar
- 領域：計算機
- 縮寫：CFG
- 相關：上下文無關文法
- 目的：標示套用一個產生式規則的可能性
上下文無關文法,上下文有關文法,形式文法,
上下文無關文法
上下文無關文法（英語：context-free grammar，縮寫為CFG），在計算機科學中，若一個形式文法G = (N, Σ, P, S) 的產生式規則都取如下的形式：V->w，則謂之。其中 V∈N ，w∈(N∪Σ)* 。上下文無關文法取名為“上下文無關”的原因就是因為字元 V 總可以被字串 w 自由替換，而無需考慮字元 V 出現的上下文。一個形式語言是上下文無關的，如果它是由上下文無關文法生成的。
上下文無關文法重要的原因在於它們擁有足夠強的表達力來表示大多數程式設計語言的語法；實際上，幾乎所有程式設計語言都是通過上下文無關文法來定義的。另一方面，上下文無關文法又足夠簡單，使得我們可以構造有效的分析算法來檢驗一個給定字串是否是由某個上下文無關文法產生的。例子可以參見LR 分析器和LL 分析器。
BNF（巴克斯-諾爾範式）經常用來表達上下文無關文法。
上下文有關文法
上下文有關文法(CSG，英語：context-sensitive grammar)是一種形式文法，其中任何產生式規則的左手端和右手端都可以被終結符和非終結符構成的上下文所圍繞。上下文有關文法比上下文無關文法更一般性，但仍足夠有秩序得可以被線性有界自動機所解析。
上下文有關文法的概念是諾姆·喬姆斯基在1950年代介入的，被作為描述自然語言的語法的一種方式，在自然語言中一個單詞是否可以出現在特定位置上，要依賴於上下文。可以被上下文有關文法描述的形式語言叫做上下文有關語言。
形式文法
形式文法描述形式語言的基本想法是，從一個特殊的初始符號出發，不斷的套用一些產生式規則，從而生成出一個字串的集合。產生式規則指定了某些符號組合如何被另外一些符號組合替換。
