问题

问题3.1:假设给定语法中的所有终结符是不同的。语法是否明确?

问题3.2:编写一个程序, 给定一个语法G和一个数字n, 计算G允许的不同的有n个叶子(终端)的解析树的数量。

问题3.3:如果您熟悉现有分析器 (生成器), 请标识其分析器组件, 如69页所述。

问题3.4:3.5.4 节中的迷宫预处理算法消除了所有具有三壁的房间;在确定性迷宫中有两面或四面墙的是可以接受的。那么没有墙或者只有一面墙的房间呢?它们如何影响算法和结果?消除掉它们是否可能/有用?

问题3.5:构造一个例子,使得一个确定性自底向上解析器,对于某个k,在位置k必须执行k次操作。

问题3.6项目:图 3.10*(b)*中的迷宫有几种可能的路径,因此一个迷宫定义了一组路径。很容易就可以看出这些路径形成了一个常规集合。这样一个迷宫等同于一个语法。深入挖掘一下这个类比,例如:1.从迷宫的某些描述中推到出语法规则。2.子集算法(5.3.1节)如何变化迷宫?3.是否有可能生成一组迷宫,它们一起可以定义一个给定的CG集合?

问题3.7项目: 研究 Greibach [389] 的 "平移和交叉匹配括号" 解析方法。

问题3.8:展示图3.14的一个版本,其中在顶部附近标记为2的节点联合了在输入中不支持的解析数。

问题3.9:实现3.7.3 中草绘的回溯算法的蓝图。

问题3.10:假设算法表达式用一个高度模糊的语法解析,其中对数字进行了适当的定义。设计一个条件可以帮助优化解析林,以获取服从运算符一般优先权的解析树。例如,4+5×6+8应该是((4+(5×6))+8)这样的。考虑到前四个运算符是左结合,但幂运算↑是右结合运算符:6/6/6可以写成((6/6)/6),但6 ↑ 6 ↑ 6却是(6 ↑ (6 ↑ 6))。

图1

问题3.11研究项目:一些解析问题包含了非常大的CF语法,有数百万的规则。这样的语法是由程序生成的,并且将会把有限的上下文条件合并到语法中。它通常是非常多余的,包含许多相似的规则,并且非常不精确。许多正则CF解析器在语法范围内是二次的,上千万的规则带来1014的因子。能找到一个解析技术可以在这样的语法上很好的工作吗?(另请参见问题4.5。)

问题3.12扩展项目

  1. 对于一个标记对(t1,t2)如果S中有#t1=#t2并且S的前缀都有#t1≥#t2,那么一个字符串S平衡的,其中#tS或其前缀中t出现的次数。一个标记对(t1,t2)对语法G来说是括号对,如果所有L(G)的字符串对于(t1,t2)来说都是平衡的。设计一种算法来检查标记对(t1,t2)是否是括号对,对于给定语法G:a)在简化但合理的假设下,括号对一起出现在规则的右侧(例如F $$\rightarrow$$ (E)),b)普通情况下。

  2. 在字符串中位置i的标记t1和位置j的标记t2相匹配,如果它们之间的字符串段i+1· · · j−1对于(t1,t2)是平衡的。一个括号对(t1,t2)和另一个括号对(u1,u2)是兼容的,如果L(G)字符串中每一个段对于一个t1以及其匹配的t2,对于(u1,u2)都是平衡的。证明如果(t1,t2)与(u1,u2)兼容,那么(u1,u2)与(t1,t2)兼容。

  3. 对于一个给定语法,设计一个算法来找到最大的兼容括号对集合。

  4. 使用括号对集合来构造*L(G)*中的句子,在线性时间内。

  5. 从G中获取有关*L(G)*中不以这种形式构造的字符串段的信息,例如正则表达式。

  6. 设计更进一步的技术来利用CF语言的括号对蓝图。