格雷巴赫標準式

在計算機科學中，聲稱一個上下文無關文法是Greibach 標準式（範式）(GNF)的意味着所有的產生規則都有如下形式：

$A\to \alpha X$

或

$S\to \epsilon$

這裡的 A 是非終結符，α 是終結符，X 是不包括開始符號的非終結符的（可能為空）的序列，S 是開始符號，而 ε 是空串。

可觀察出這種文法沒有左遞歸。

所有上下文無關文法口可以被轉換成等價的 Greibach 範式的文法。（某些定義不認可第二種形式的規則，在這種情況下能生成空串的上下文無關文法不能被如此轉換。）這可以被用來證明所有上下文無關語言可以被非確定下推自動機所接受。

給定 GNF 的一個文法和長度為 n 的符合這個文法的一個可導出的字符串，任何自頂向下分析器將在深度 n 停機。

Greibach 範式得名於 Sheila Greibach。

範例

請寫出

$S\to AA|0$

$A\to SS|1$

的 Greibach 標準式

A¹→A²A²|0 A²→A¹A¹|1

A¹→A²A²|0 A²→A²A²A¹|0A¹|1

A¹→A²A²|0 A²→0A¹|1|0A¹B²|1B² B²→A²A¹|A²A¹B²

A¹→0A¹A²|1A²|0A¹B²A²|1B²A²|0 A²→0A¹|1|0A¹B²|1B² B²→A²A¹|A²A¹B²

A¹→0A¹A²|1A²|0A¹B²A²|1B²A²|0 A²→0A¹|1|0A¹B²1B² B²→0A¹A¹|0A¹B²A¹|1B²A¹|0A¹A¹B²|0A¹B²A¹B²|1B²A¹B²|1A¹|1A¹B²

引用

• John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley Publishing, Reading Massachusetts, 1979. ISBN 0-201-02988-X. (See chapter 4.)

參見

• 喬姆斯基範式
• 巴科斯範式
• Kuroda範式
• 上下文有關文法
• 形式文法
• 分析表達式文法
• 隨機上下文無關文法