4.2.8 从CYK解析获取解析林语法

与Unger解析器一样,在CYK解析过程中获取一个解析林语法非常简单:每当识别表Ri,1中新增一个非终结符A的时候(因为有A→BC规则,并且B包含于Ri,kC包含于Ri+k,l−k),规则

A_i_l ---> B_i_k C_m_n

将被添加至解析林语法,当m = i+kn = i+l−k时。

有两点需要注意。第一点,这个算法永远不会引入未定义的非终结符:只有在规则B_i_kC_m_n都存在之后,才会引入规则A_i_l--->B_i_k C_m_n。另一方面,在添加此类规则时不考虑其可及性:从起始符号起,非终结符A_i_l可能可及也可能不可及;其实讨论是否可及还太早了。可以看到,CYK解析作为一个自底向上算法,它产生了太多不可及的非终结符;这表示自底向上的这些过程没有意义。

第二点,解析林语法包含的信息比识别表要多,因为它不仅包含给定句子的非终结符,还包含了每个非终结符被记录的原因。解析林语法包含了CYK解析过程的识别阶段(4.2.2节)和解析阶段(4.2.5节)。

从图Fig4.17获得的解析林语法以及从图Fig4.6获得的语法非常简单;结论见图Fig4.18。可以看到,包含非常多的不可及的非终结符,例如Number_2_6,Scale_5_0等。删除掉这些就得到了图Fig4.19的样子;很容易看出它相当于4.2.6节结尾处得到的结果。