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.)
格雷巴赫标准式, 在计算机科学中, 声称一个上下文无关文法是greibach, 标准式, 范式, 的意味着所有的产生规则都有如下形式, displaystyle, alpha, displaystyle, epsilon, 这里的, 是非终结符, 是终结符, 是不包括开始符号的非终结符的, 可能为空, 的序列, 是开始符号, 是空串, 可观察出这种文法没有左递归, 所有上下文无关文法口可以被转换成等价的, greibach, 范式的文法, 某些定义不认可第二种形式的规则, 在这种情况下能生成空串的上下文无关文法不能. 在计算机科学中 声称一个上下文无关文法是Greibach 标准式 范式 GNF 的意味着所有的产生规则都有如下形式 A a X displaystyle A to alpha X 或 S ϵ displaystyle S to epsilon 这里的 A 是非终结符 a 是终结符 X 是不包括开始符号的非终结符的 可能为空 的序列 S 是开始符号 而 e 是空串 可观察出这种文法没有左递归 所有上下文无关文法口可以被转换成等价的 Greibach 范式的文法 某些定义不认可第二种形式的规则 在这种情况下能生成空串的上下文无关文法不能被如此转换 这可以被用来证明所有上下文无关语言可以被非确定下推自动机所接受 给定 GNF 的一个文法和长度为 n 的符合这个文法的一个可导出的字符串 任何自顶向下分析器将在深度 n 停机 Greibach 范式得名于 Sheila Greibach 範例 编辑請寫出 S A A 0 displaystyle S to AA 0 A S S 1 displaystyle A to SS 1 的 Greibach 標準式A A A 0 A A A 1A A A 0 A A A A 0A 1A 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范式 上下文有关文法 形式文法 分析表达式文法 随机上下文无关文法 取自 https zh wikipedia org w index php title 格雷巴赫标准式 amp oldid 55531377, 维基百科，wiki，书籍，书籍，图书馆，
