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

Question

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

当没有递归时似乎可行,但我无法弄清楚如何在一般情况下这样做,它可能包含各种(可能是间接的)递归.

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

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>元组队列开始,初始化为由空字符串和空状态集组成的元组.然后我们(无限地)从队列的头部移除一个元组,并将所有可能的元组添加到队列的末尾,这些元组可以通过将一个符号从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.

上述算法对于明确的语法可以正常工作,但是如果给出一个模糊的语法,它将多次生成句子(每个最左边的派生一次).要解决这个问题,我们可以先将语法转换为Chomsky Normal Form(参见算法链接).然后,我们为终端和非终端创建总排序,其中非终端都在终端之前,并且对于句子的相应顺序,其中较短的句子在较长的句子之前,并且等长句子按字典顺序排序.然后我们使用上面的算法,但使用优先级队列而不是FIFO队列,并在处理之前消除重复的条目.

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