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

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 的论文，或者更简洁地说，关于Earley 算法 的维基百科文章。我也跳过了枚举 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（请参阅算法链接）。然后，我们为终结符和非终结符创建总排序，其中非终结符都在终结符之前，以及相应的句子顺序，其中较短的句子在较长的句子之前，并且等长的句子按字典顺序排列。然后我们使用上面的算法，但是使用优先级队列而不是 FIFO 队列，并在处理之前消除重复条目。

在 CNF 中，随着 length-then-lexicographic 排序，所有产生式都在增加，因为它们要么用终结符替换非终结符，要么使句子更长一个符号。 （其余的正确性证明是通过归纳法进行的。）因此，完全派生的句子将按照长度然后是字典顺序进行枚举，就像开始这个答案的朴素算法一样。

Answer 2

查看这篇论文，它通过了 CFG 和整数之间的简单双射：https://arxiv.org/abs/2305.00522