当将上下文无关的语法转换为乔姆斯基范式时,我们首先按此顺序删除空产物,然后是单元产物,然后是无用产物。我知道去掉零产生可能会引起单位产生,这就是为什么在去掉零产生后去掉单位。然而,我不明白如果我们先删除无用的产品,然后再删除单位,会出现什么问题?
如果您删除了单元生产A → B
,并且这是语法中唯一引用B
的地方,那么由于单元生产消除,B
将变得不可访问,并且需要与其生产一起删除。
该条件要求B
是非递归的(因为递归的非终端指的是自身,并且可能不是单位生产),并且在B
的生产中引用的任何非终端仍将被引用,已被吸收到A
的生产中。
如果语法没有允许A →* A
的单元生成循环,则可以对单元生成进行拓扑排序,并以反向拓扑顺序删除,这保证了单元生成消除不会创建新的单元生成。这使得在进行单位生产消除时可以删除新的不可访问的非终端。但我认为教科书上的算法可能不会这样做,这大概就是为什么教科书希望你在语法转换为CNF后删除无用的产物。(当然,没有什么能阻止语法有一个循环的单位生成。这样的语法是不明确的,因此很难在解析器中使用,但是本练习并不要求语法在解析器中有用。
同样,如果非终结符的唯一产物是ε-产物,则该非终结符在删除null-产物后将最终没有产物(并且它也将不可达)。同样,这可以用一种不需要延迟可达性分析的方式来处理,但教科书上的算法可能不会这样做。