6

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

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

（我不是在寻找像本页那样深奥的解决方案；我在寻找一种可以映射到标准命令式代码的算法。）

4

1 回答 1

10

这是一个明显但效率较低的算法：

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 算法的 Wikipedia 文章。我也跳过了枚举 A* 中所有字符串的问题，这是一个简单的基本|A|计数器。

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

在这两种情况下，如果我们知道给定的语法属于一些更容易解析的 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.

上述算法适用于明确的语法，但给定一个不明确的语法，它将多次生成句子（每个最左边的推导一次）。为了解决这个问题，我们可以首先将语法转换为乔姆斯基范式（算法见链接）。然后，我们为终结符和非终结符创建一个总排序，其中非终结符都在终结符之前，并为句子创建相应的顺序，其中较短的句子在较长的句子之前，并且等长的句子按字典顺序排列。然后我们使用上述算法，但是使用优先级队列而不是 FIFO 队列，并在处理之前消除重复条目。

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

于 2013-06-30T17:24:53.840 回答