解释 Greibach 范式 (GNF)
令G=(V,T,P,S)为CFL。如果P中的每个产生式都具有以下形式
A->aa
如果A在V中，a在T中，a在V*中，则称G为Greibach范式(GNF)。
示例
S->aAB|bBA->aA|一种
B->bB|C
定理-让L是不包含{s}的CFL。那么存在一个GNF文法G使得L=L(G)。
引理1-让L成为CFL。那么存在一个PDAM使得L=LE(M)。
证明-不失一般性地假设s不在L中。该构造可以修改为稍后包含。
设G=(V,T,P,S)是一个CFG，并且不失一般性地假设G在GNF中。
构造M=(Q,E,r,5,q,z,0)其中-
Q={q}
E=T
r=V
z=S
5：对于E中的所有a和r中的A，
5(q,a,A)包含(q,y)如果A->ay在P中或更确切地说-
5(q,a,A)={(q,y)|A->ay在P中，y在r*}中，因为E中的所有a和r中的A
对于E*中的给定字符串x，M将尝试用G模拟x的最左推导。
示例
考虑以下GNF中的CFG。
S^aSa
构造M如下-
Q={q}
E=T={a}r=V={S}
z=S
5(TaS)={(TS)(Ts)}
5(q,s,S)=0