格雷巴赫标准式

在计算机科学中，声称一个上下文无关文法是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范式
• 上下文有关文法
• 形式文法
• 分析表达式文法
• 随机上下文无关文法