查看“︁格雷巴赫标准式”︁的源代码

在[[计算机科学]]中，声称一个[[上下文无关文法]]是'''Greibach 标准式（范式）'''(GNF)的意味着所有的产生规则都有如下形式：
:<math>A \to \alpha X</math> 
或
:<math>S \to \epsilon</math>
这里的 ''A'' 是[[非终结符]]，α 是[[终结符]]，''X'' 是不包括开始符号的非终结符的（可能为空）的序列，''S'' 是开始符号，而 ''ε'' 是空串。

可观察出这种文法没有左递归。

所有上下文无关文法口可以被转换成等价的 Greibach 范式的文法。（某些定义不认可第二种形式的规则，在这种情况下能生成空串的上下文无关文法不能被如此转换。）这可以被用来证明所有[[上下文无关语言]]可以被非确定[[下推自动机]]所接受。

给定 GNF 的一个文法和长度为 ''n'' 的符合这个文法的一个可导出的字符串，任何[[自顶向下分析|自顶向下分析器]]将在深度 ''n'' 停机。

'''Greibach 范式'''得名于 [[Sheila Greibach]]。

== 範例 ==
請寫出
:<math>S \to AA|0</math>
:<math>A \to SS|1</math>
的 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范式]]
* [[上下文有关文法]]
* [[形式文法]]
* [[分析表达式文法]]
* [[随机上下文无关文法]]

[[Category:形式语言|G]]
[[Category:编译原理]]