[科普中國]-黑田范式

所有 Kuroda 范式的文法都是單調(diào)的，因此生成上下文有關(guān)語言。反過來說，所有不生成空串的上下文有關(guān)語言都可以被 Kuroda 范式的文法所生成。

簡介在計算機(jī)科學(xué)中，形式文法是Kuroda 范式的，當(dāng)且僅當(dāng)所有產(chǎn)生規(guī)則都有如下形式:1

AB → CD

A → BC

A → B

A → α

這里的 A, B, C 和 D 是非終結(jié)符而 α 是終結(jié)符。

所有 Kuroda 范式的文法都是單調(diào)的，因此生成上下文有關(guān)語言。反過來說，所有不生成空串的上下文有關(guān)語言都可以被 Kuroda 范式的文法所生成。

參見巴科斯范式巴科斯范式（英語：Backus Normal Form，縮寫為BNF），又稱為巴科斯-諾爾范式（英語：Backus-Naur Form，縮寫同樣為BNF，也譯為巴科斯-瑙爾范式、巴克斯-諾爾范式），是一種用于表示上下文無關(guān)文法的語言，上下文無關(guān)文法描述了一類形式語言。它是由約翰·巴科斯（John Backus）和彼得·諾爾（Peter Naur）首先引入的用來描述計算機(jī)語言語法的符號集。

盡管巴科斯范式也能表示一部分自然語言的語法，它還是更廣泛地使用于程序設(shè)計語言、指令集、通信協(xié)議的語法表示中。大多數(shù)程序設(shè)計語言或者形式語義方面的教科書都采用巴科斯范式。在各種文獻(xiàn)中還存在巴科斯范式的一些變體，如擴(kuò)展巴科斯范式EBNF 或擴(kuò)充巴科斯范式ABNF。

喬姆斯基范式在計算機(jī)科學(xué)中，一個形式文法是Chomsky 范式的，當(dāng)且僅當(dāng)所有產(chǎn)生規(guī)則都有如下形式：

A→BC

A→ α

S→ ε

這里的A,B和C是非終結(jié)符，α 是終結(jié)符（表示常量值的符號），S是開始符號，而 ε 是空串。還有，B和C都不可以是開始符號。

所有的 Chomsky 范式的文法都是上下文無關(guān)，反過來，所有上下文無關(guān)文法都可以有效的變換成等價的 Chomsky 范式的文法。

除了（在文法可能生成空串的時候包括的）可選規(guī)則S→ ε 是例外，Chomsky 范式的文法的所有規(guī)則都是擴(kuò)張的，就是說在字符串的整個導(dǎo)出過程中，每個終結(jié)符和非終結(jié)符的字符串比起前面導(dǎo)出的字符串要么同樣長度要么多出一個元素。長度 n 的字符串的導(dǎo)出總是精確的 2n-1 步長。

Chomsky 范式得名于諾姆·喬姆斯基，他是發(fā)明喬姆斯基層級的美國語言學(xué)家。

格雷巴赫標(biāo)準(zhǔn)式在計算機(jī)科學(xué)中，聲稱一個上下文無關(guān)文法是Greibach 標(biāo)準(zhǔn)式（范式）(GNF)的意味著所有的產(chǎn)生規(guī)則都有如下形式：

或

這里的A是非終結(jié)符，α 是終結(jié)符，X是不包括開始符號的非終結(jié)符的（可能為空）的序列，S是開始符號，而ε是空串。可觀察出這種文法沒有左遞歸。所有上下文無關(guān)文法口可以被轉(zhuǎn)換成等價的 Greibach 范式的文法。（某些定義不認(rèn)可第二種形式的規(guī)則，在這種情況下能生成空串的上下文無關(guān)文法不能被如此轉(zhuǎn)換。）這可以被用來證明所有上下文無關(guān)語言可以被非確定下推自動機(jī)所接受。給定 GNF 的一個文法和長度為n的符合這個文法的一個可導(dǎo)出的字符串，任何自頂向下分析器將在深度n停機(jī)。Greibach 范式得名于Sheila Greibach。

本詞條內(nèi)容貢獻(xiàn)者為:

楊明 - 副教授 - 西南大學(xué)