问题

问题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--->Bb |Bε , Bb --->b, Bε --->ε。接下来替换所有为空的OR规则(举例中B的规则):S--->|, --->aBbc, --->aBεc, Bb--->b, Bε--->ε。接下里替换A → ε形式的规则:S--->|, --->aBbc, --->ac, Bb--->b。在我们解析--->ac时,S的角标就是真正的右侧。用解析器将这个想法细化为一个完整的算法。

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

SS ---> T

T ---> U

U ---> T

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

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

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

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

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

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

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

results matching ""

    No results matching ""