上下文無關文法

在計算機科學中，若一個形式文法?G = (N, Σ, P, S) 的產生式規則都取如下的形式：V?->?w，則稱之為上下文無關文法（英語：context-free grammar，縮寫為CFG），其中 V∈N ，w∈(N∪Σ)* 。上下文無關文法取名為“上下文無關”的原因就是因為字符 V 總可以被字串 w 自由替換，而無需考慮字符 V 出現的上下文。一個形式語言是上下文無關的，如果它是由上下文無關文法生成的（條目上下文無關語言）。

上下文無關文法重要的原因在于它們擁有足夠強的表達力來表示大多數程序設計語言的語法；實際上，幾乎所有程序設計語言都是通過上下文無關文法來定義的。另一方面，上下文無關文法又足夠簡單，使得我們可以構造有效的分析算法來檢驗一個給定字串是否是由某個上下文無關文法產生的。例子可以參見?LR 分析器和?LL 分析器。

BNF（巴克斯-諾爾范式）經常用來表達上下文無關文法。

形式定義

上下文無關文法?G?是 4-元組：

$G = (V\,, \Sigma\,, R\,, S\,)$ ?這里的

1.? $V\,$ ?是“非終結”符號或變量的有限集合。它們表示在句子中不同類型的短語或子句。

2.? $\Sigma\,$ ?是“終結符”的有限集合，無交集于? $V\,$ ，它們構成了句子的實際內容。

3.? $S\,$ ?是開始變量，用來表示整個句子（或程序）。它必須是? $V\,$ ?的元素。

4.? $R\,$ ?是從? $V\,$ ?到? $(V\cup\Sigma)^{*}$ ?的關系，使得? $\exist\, w\in (V\cup\Sigma)^{*}: (S,w)\in R$ 。

此外， $R\,$ ?是有限集合。 $R\,$ ?的成員叫做文法的“規則”或“產生式”。星號表示Kleene星號運算。

補充定義 1

對于任何字符串? $u, v\in (V\cup\Sigma)^{*}$ ，我們稱? $u\,$ ?生成? $v\,$ ，寫為? $u\Rightarrow v\,$ ，如果? $\exists (\alpha, \beta)\in R, u_{1}, u_{2}\in (V\cup\Sigma)^{*}$ ?使得? $u\,=u_{1}\alpha u_{2}$ ?且? $v\,=u_{1}\beta u_{2}$ 。因此? $v$ ?是應用規則? $(\alpha, \beta)$ ?于? $u$ ?的結果。

補充定義 2

對于任何? $u, v\in (V\cup\Sigma)^{*}, u\stackrel{*}{\Rightarrow} v$ （或? $u\Rightarrow\Rightarrow v\,$ ?在某些教科書中），如果? $\exists u_{1}, u_{2}, \cdots u_{k}\in (V\cup\Sigma)^{*}, k\geq 0$ ?使得? $u\Rightarrow u_{1}\Rightarrow u_{2}\cdots\Rightarrow u_{k}\Rightarrow v$ 。

補充定義 3

文法? $G = (V\,, \Sigma\,, R\,, S\,)$ ?的語言是集合

L(G) = \{ w\in\Sigma^{*} : S\stackrel{*}{\Rightarrow} w\}

補充定義 4

語言? $L\,$ ?被稱為是上下文無關語言（CFL），如果存在一個 CFG? $G\,$ ?使得? $L\,=\,L(G)$ 。

范式

每一個不生成空串的上下文無關文法都可以轉化為等價的?Chomsky 范式或?Greibach 范式。這里兩個文法等價的含義指它們生成相同的語言。

由于 Chomsky 范式在形式上非常簡單，所以它在理論和實踐上都有應用。比如，對每一個上下文無關語言，我們可以利用 Chomsky 范式構造一個多項式算法，用它來判斷一個給定字串是否屬于這個語言（CYK算法）。

轉載于:https://www.cnblogs.com/javaleon/p/4103811.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/257987.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/257987.shtml
英文地址，請注明出處：http://en.pswp.cn/news/257987.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！