格雷巴赫正常形式

在形式语言理论中，如果所有生产规则的右侧以一个终端符号开始，后面可选择一些变量，那么一个无语境语法就处于格雷巴赫正常形式（GNF）。非严格形式允许这种格式限制的一个例外，即允许空词（ε，ε）成为描述语言的成员。正常形式是由SheilaGreibach建立的，它以她的名字命名。更确切地说，如果所有的生产规则都是这样的形式，那么一个无语境语法就属于格雷巴赫正常形式。{displaystyleA_{1}A_{2}A_{n}ldotsA_{n}}是一个（可能是空的）非终结符序列，不包括起始符，也不包括”A”。是一个（可能是空的）非终端符号的序列，不包括起始符号和S{displaystyleS}是起始符号。是起始符号。请注意，该语法没有左递归。每个上下文自由语法都可以转化为Greibach正常形式的等价语法。存在各种构造。有些不允许第二种形式的规则，并且不能转换可以产生空词的无语境语法。

对于这样一种构造，在一般情况下，构造的语法大小为O(n4)，如果原始语法的派生不包含一个非终端符号，则为O(n3)，其中n为原始语法的大小。这种转换可以用来证明每一种无语境语言都可以被实时（非确定性）推倒式自动机所接受，即自动机每一步都从其输入中读取一个字母。给定一个GNF中的语法和一个长度为n的语法中的可派生字符串，任何自上而下的解析器都会在深度为n时停止。