algorithm - 来自“编译器 - 原理、技术和工具”（又名 Dragon Book）的练习 4.2.8

Question

一段时间以来，我一直在努力解决这个问题。

这是练习的文本：

图 4.7 中的语法为单个数字标识符生成声明；这些声明涉及数字的四个不同的、独立的属性。

stmt -> declare id optionList
optionList -> optionList option | ε
option -> mode | scale | precision | base
mode -> real | complex
scale -> fixed | floating
precision -> single | double
base -> binary | decimal

1) 通过允许 n 个选项 Ai 来概括图 4.7 的语法，对于一些固定的 n 和 i = 1,2... ,n，其中 Ai 可以是 ai 或 bi·你的语法应该只使用 0(n)语法符号，产生式的总长度为 O(n)。2) 图 4.7 的语法及其在 (a) 部分的概括允许声明是矛盾的和/或冗余的，例如

declare foo real fixed real floating

我们可以坚持语言的语法禁止这样的声明；也就是说，语法生成的每个声明对于 n 个选项中的每一个都只有一个值。如果我们这样做，那么对于任何固定的 n，只有有限数量的合法声明。因此，法律声明的语言具有语法（以及正则表达式），就像任何有限语言一样。显而易见的语法，其中开始符号对每个合法声明都有一个产生式有 n! 生产和总生产长度为 O(nxn!)。你必须做得更好：总产生式长度为 O(n2^n) 表明任何部分 (b) 的语法必须具有至少 2^n 的总产生式长度。

特别是，我被困在第 2 部分。我知道给定 n 个二元选项，将选项设置为 a_n 或 b_n 会导致 2^n 组合。我不知道的是如何在不提及每个选项的位置的情况下表达这一点。

即，我如何想出一个可以指定任何 A1...AN 选项而不表达所有 N 的语法！组合（例如，对于 A1、A2 和 A3：A1 A2 A3、A1 A3A 2、A2 A1 A3、A2 A3 A1、A3 A1 A2、A3 A2 A1）？

谢谢

标签： algorithmgrammarcompiler-theory

Answer 1

我们可以创建一个有限状态机（正如我们所知，它等效于常规语法），而不是尝试编写语法。应该清楚的是，在这个有限状态机中，每个状态都将对应于n 个属性类型的某个子集，并且它的所有有效转换都将指向代表具有恰好多一个属性类型的子集的状态。（所有状态都在接受，因为没有属性的最小数量。）所以对于具有四种属性类型的文法（原始文法），我们最终得到 16 个状态：

要将其转换为语法，我们只需要将每个状态设为非终结符，并将每条边设为产生式。由于来自任何节点的转换永远不会超过n，因此边（以及由此产生的产品）的总数小于 n·2 ⁿ。（事实上​​，状态机中恰好有 n·2 ^{n-1 次}转换。）此外，每个产生式的右手边最多有两个符号。