问题

问题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))。

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

问题3.12：扩展项目：

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

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

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

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

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

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