来自 "Compilers - Principles, Techniques, & Tools" 的练习 4.2.8（a.k.a。龙之书）
Exercise 4.2.8 from "Compilers - Principles, Techniques, & Tools" (a.k.a. Dragon Book)
我已经为这个问题苦苦思索了一段时间。
这是练习的文本：
图 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）部分的泛化允许矛盾的声明and/or冗余，例如
declare foo real fixed real floating
我们可以坚持认为语言的语法禁止这样的声明；也就是说，语法生成的每个声明对于 n 个选项中的每一个都只有一个值。如果我们这样做，那么对于任何固定的 n，只有有限数量的合法声明。因此，法律声明的语言有一个语法（还有一个正则表达式），就像任何有限语言一样。明显的语法，其中开始符号有一个产生式，每个合法声明都有 n！生产和 O(n x n!) 的总生产长度。你必须做得更好：总生产长度为 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）?
谢谢
我们可以创建一个有限状态机（正如我们所知，它等同于常规语法），而不是尝试编写语法。应该清楚的是，在这个有限状态机中，每个状态都将对应于 n 属性类型的某个子集，并且其所有有效转换都将指向代表子集的状态恰好是另一种属性类型。 （所有状态都接受，因为没有最小属性数。）所以对于具有四种属性类型的文法（原始文法），我们最终得到 16 个状态：
要将其转换为文法，我们只需要使每个状态成为非终结符，each edge a production。由于来自任何节点的转换永远不会超过 n，因此边的总数（以及产生式）少于 n·2n。 （实际上，状态机中恰好有 n·2n-1 次转换。）此外，每个产生式右侧最多有两个符号。
我已经为这个问题苦苦思索了一段时间。
这是练习的文本：
图 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）部分的泛化允许矛盾的声明and/or冗余，例如
declare foo real fixed real floating
我们可以坚持认为语言的语法禁止这样的声明；也就是说，语法生成的每个声明对于 n 个选项中的每一个都只有一个值。如果我们这样做，那么对于任何固定的 n，只有有限数量的合法声明。因此，法律声明的语言有一个语法（还有一个正则表达式），就像任何有限语言一样。明显的语法，其中开始符号有一个产生式，每个合法声明都有 n！生产和 O(n x n!) 的总生产长度。你必须做得更好：总生产长度为 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）?
谢谢
我们可以创建一个有限状态机（正如我们所知，它等同于常规语法），而不是尝试编写语法。应该清楚的是，在这个有限状态机中，每个状态都将对应于 n 属性类型的某个子集，并且其所有有效转换都将指向代表子集的状态恰好是另一种属性类型。 （所有状态都接受，因为没有最小属性数。）所以对于具有四种属性类型的文法（原始文法），我们最终得到 16 个状态：
要将其转换为文法，我们只需要使每个状态成为非终结符，each edge a production。由于来自任何节点的转换永远不会超过 n，因此边的总数（以及产生式）少于 n·2n。 （实际上，状态机中恰好有 n·2n-1 次转换。）此外，每个产生式右侧最多有两个符号。