2.9.4 循环

上述定义使所有可以包含在一个句子生成过程中的规则是“非无用”的,但仍有一类规则并不是真的有用:类似A → A 形式的规则。这类规则被称为循环。循环也可以是间接的:A → B,B → C,C → A;而且它们可以被隐藏:A → PAQ,P ε, Q ε,所以生成过程A→PAQ→. . .A. . .→A也是可能的。

一个循环可以合理的而出现在句子的生成过程中,并且如果它确实出现了,依旧会有这个句子的另一个不包含循环的生成过程。循环不对语言最贡献,任何句子的生成过程包含一个循环的无限模糊的,意味着对它来说有无限多的生成树。4.1.2 节中给出了循环检测算法。

不同解析器对带有循环的语法的反应不一样。有些(大部分的普通解析器)诚实的试图去构建无限数量的推导树,另一些(例如,CYK解析器)如上文所述一样将循环折叠起来,还有一些(最具决定性的解析器)拒绝了这样的语法。而ε规则可以隐藏循环加剧了这个问题:一个循环只有当某些非终结符生成了ε时,才是可见的。

一个不含有无用非终结符和循环的语法,才被称为一个正确的语法。

results matching ""

    No results matching ""