问题

问题4.1：如果可以通过在S中的任意位置插入语言中的0个或多个令牌来生成U，那么字符串U称为字符串S的一个超级序列（supersequence）。（见12.4节）

• a) 为语法G设计一个Unger解析器，且G生成的语言中的一个字符串可以被识别为G的一个超级序列。

• b) 设计一个CYK解析器，要求同上。

问题4.2：如果可以通过删除S中任意位置的零个或多个token来生成U，那么字符串U称为字符串S的一个子序列（subsequence）。（见12.4节）

• a) 为语法G设计一个Unger解析器，该解析器可以识别G生成的语言中的字符串的子序列。

• b) 设计一个CYK解析器，要求同上。

问题4.3：从语法中去掉ε规则将会很大程度的改变语法，在解析过程中必须要花大力气来恢复这种破坏。通过将删除的ε规则合并到修改后的语法中可以省掉一些麻烦，如下所示。给定一个语法S--->aBc, B--->b|ε，我们先将其转换为“AND-OR”形式，将原本的右侧记为非终结符。（只有AND规则和OR规则两种的语法即属于AND-OR形式，AND规则即语法符号是并列关系，OR规则即非终结符是择其一关系，并且对于每一个非终结符而言，同时只有一个规则存在。）上面的语法就成为了S--->aBc, B--->B_b |B_ε , B_b --->b, B_ε --->ε。接下来替换所有为空的OR规则（举例中B的规则）：S--->$$S_{aB_{b}c}$$|$$S_{aB_{\xi }c}$$, $$S_{aB_{b}c}$$--->aB_bc, $$S_{aB_{\xi }c}$$--->aB_εc, B_b--->b, B_ε--->ε。接下里替换A → ε形式的规则：S--->$$S_{aB_{b}c}$$|$$S_{aB_{\xi }c}$$, $$S_{aB_{b}c}$$--->aB_bc, $$S_{aB_{\xi }c}$$--->ac, B_b--->b。在我们解析**$$S_{aB_{\xi }c}$$--->ac**时，S的角标就是真正的右侧。用解析器将这个想法细化为一个完整的算法。

问题4.4：从下面的语法中删除单元规则：

问题4.5：拓展题：CYK，尤其是图标解析形式，长久以来一直是自然语言解析的最爱方式，即便我们已经知道时间成本是O(|G||P_av|n³)。当遇到一些非常大的自然语言语法时（拥有数百万规则），更甚至是它所生成的语言，那么仅仅O(|G|)就已经很成问题了，勿论O(|P_av|)。请设计一个CYK/图表形式的优化版本（比*O(|G|)更优）。不要指望|ADJ|比|G|²*更小，ADJ是任意右侧会出现的非终结符对的集合。（见问题3.11）

问题4.6：在编辑器中查看源代码时，成对出现的命令（tokens）可以让语法结构一目了然。这就去掉了CYK坚持的很多自底向上的假设。这个方法可以自动去掉大部分的表输入，只留下很少的一部分。这使得它几乎成为一个时间要求为线性的解析器，而这对于解析旧代码可能很重要，因为旧代码通常语法非常难搞。

先检查A生成的非终结符之前、开头、中间、结尾、之后的命令，然后在尝试减少A → α形式的假设。

问题4.7：将4.3节中计算*T_i,A*的推理规则格式化。

问题4.8：使用识别段的结束位置作为第二个索引绘制图Fig4.8和Fig4.16。

问题4.9：Rus算法适用的确定性的语法类型有哪些。

问题4.10：形式语言：设计一个算法，将给定语法转换为一个非终结符数量尽可能少的语法。这一点很重要，因为很多解析算法的时间成本取决于语法的大小。