格雷巴赫标准式

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

定义在计算机科学中，声称一个上下文无关文法是Greibach 标准式（范式）(GNF)的意味着所有的产生规则都有如下形式：

或

这里的A是非终结符，α 是终结符，X是不包括开始符号的非终结符的（可能为空）的序列，S是开始符号，而ε是空串。

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

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

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

Greibach 范式得名于Sheila Greibach。1

范例请写出S->AA|0 A->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²1→0A¹A¹|0A¹B²A¹|1B²A¹|0A¹A¹B²|0A¹B²A¹B²|1B²A¹B²|1A¹|1A¹B²

上下文无关文法在 计算机科学中，若一个形式文法G = (N, Σ, P, S) 的 产生式规则都取如下的形式：V -> w，则称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)* 。上下文无关文法取名为“上下文无关”的原因就是因为字符 V 总可以被字串 w 自由替换，而无需考虑字符 V 出现的上下文。一个形式语言是上下文无关的，如果它是由上下文无关文法生成的﹙条目上下文无关语言﹚。

上下文无关文法重要的原因在于它们拥有足够强的表达力来表示大多数程序设计语言的语法；实际上，几乎所有程序设计语言都是通 过上下文无关文法来定义的。另一方面，上下文无关文法又足够简单，使得我们可以构造有效的分析算法来检验一个给定字串是否是由某个上下文无关文法产生的。例子可以参见 LR 分析器和 LL 分析器。2

本词条内容贡献者为:

程鹏 - 副教授 - 西南大学