网站首页  英汉词典

请输入您要查询的英文单词:

 

单词 Greibach normal form
释义

Greibach normal form

中文百科

格雷巴赫标准式

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

这里的 A 是非终结符,α 是终结符,X 是不包括开始符号的非终结符的(可能为空)的串行,S 是开始符号,而 ε 是空串。

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

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

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

英语百科

Greibach normal form 格雷巴赫标准式

In formal language theory, a context-free grammar is in Greibach normal form (GNF) if the right-hand sides of all production rules start with a terminal symbol, optionally followed by some variables. A non-strict form allows one exception to this format restriction for allowing the empty word (epsilon, ε) to be a member of the described language. The normal form was established by Sheila Greibach and it bears her name.

随便看

 

英汉网英语在线翻译词典收录了3779314条英语词汇在线翻译词条,基本涵盖了全部常用英语词汇的中英文双语翻译及用法,是英语学习的有利工具。

 

Copyright © 2004-2024 encnc.com All Rights Reserved
更新时间:2025/6/23 7:50:25