grammar - 如何枚举上下文无关文法的字符串？

Question

您使用什么算法来枚举由上下文无关文法生成的字符串？

当没有递归时，这似乎是可行的，但我无法弄清楚在一般情况下如何做到这一点，其中可能包含各种(可能是间接的)递归。

(我不是在寻找像 this page 那样深奥的解决方案；我正在寻找一种可以映射到标准命令式代码的算法。)

Answer 1

这是一个明显但有点低效的算法:

Construct R, the Earley parser for the grammar.

For each string S in A* (A is the alphabet for the grammar):
  If R recognizes S:
    Output S

此处略过构建 R的细节-- 例如，参见 Earley's thesis或者，更简洁地说，维基百科上的文章 the Earley algorithm .我还跳过了枚举 A* 中所有字符串的问题，这是一个简单的基数 |A|柜台。

显然，通过使用 Earley 解析器本身来避免(某些)死胡同，可以使该算法更加高效。而不是枚举 A* 中的所有字符串，我们从 <string, state-set> 的队列开始元组，初始化为由空字符串和空状态集组成的元组。然后我们(无限地)从队列的头部删除一个元组，并将所有可能的元组添加到队列的末尾，这些元组可以通过从 A 中输入一个符号来构造。进入 Earley 解析器(通常，解析器将无法处理每个符号；实际上，它可能无法处理任何符号)。如果解析器识别出元组中的字符串，我们就输出它。

在这两种情况下，如果我们知道给定的语法属于某个更容易解析的 CFG 子集，我们可以将 Earley 解析器替换为更高效的语法解析器。

上述两种算法都具有以简单可预测的顺序生成语言字符串的优点:首先按长度，然后在给定长度内，按字典顺序排列，这保证即使语法有歧义，每个字符串也只会生成一次。

另一种解决方案是按照所需的减少次数按顺序构造字符串；实际上，这会产生所有(最左边的)减少。这里我们用开始符号开始一个队列，然后重复:

Remove the first sentence in the queue.
If it contains only terminals, output it.
Otherwise, for each production for the first non-terminal in the sentence,
  append to the queue the result of expanding that production.

上述算法适用于无歧义的语法，但给定一个歧义的语法，它将多次生成句子(每个最左边的派生一次)。为了解决这个问题，我们可以先将语法转换为 Chomsky Normal Form (算法见链接)。然后我们为终结符和非终结符创建一个总排序，其中非终结符都在终结符之前，并为句子创建相应的顺序，其中较短的句子在较长的句子之前，等长的句子按字典顺序排列。然后我们使用上面的算法，但是使用优先级队列而不是先进先出队列，并在处理它们之前消除重复条目。

在 CNF 中，随着长度然后词典排序，所有产生式都在增加，因为它们要么用终结符替换非终结符，要么使句子长一个符号。 (正确性证明的其余部分是通过归纳。)因此，完全导出的句子将按长度然后词典顺序枚举，就像开始这个答案的朴素算法一样。