上下文无关语法

Question

是否有算法从给定的无上下文语法生成所有字符串？

Answer 1

莱昂纳多的答案在技术上是正确的; 没有终止算法会返回一般CFG 的单词集,因为通常该集合是无限的.

但是有些算法会为CFG 生成一系列单词,每个单词都与"最终"出现的语法相匹配.其中一个应该足以满足您的需要.使用yieldPython 编写其中一种语言相当容易.

这种算法的草图(相当无望的伪代码,我害怕):

generate(g):
    if g is empty:
        yield ""
    otherwise if g is a terminal a:
        yield "a"
    otherwise if g is a single nonterminal:
        for c in every construction of g:
            start a generator for generate(c)
        until all generators are exhausted:
            looping over each nonexhausted generator gen:
                yield "a" where a = next(gen)
    otherwise if g is a pair of symbols m and n:
        for c in every construction of m:
            start a generator in set 1 for generate(c)
        for d in every construction of m:
            start a generator in set 2 for generate(d)
        until all in set 1 or all in set 2 are exhausted:
            loop over all pairs gen1,gen2 of nonexhausted in set 1 and set 2:
                yield "a b" where a = next(gen1) and b = next(gen2)

假设已经转换了语法,使得每个构造都是零到两个终端,这将在语法的所有解析树的树上运行广度优先搜索.BFS是必要的,因为任何给定子树的大小可能是无限的 - 一个DFS可能会被永远地向下看其中一个.

等待给定任何解析树实现的时间和内存成本可能是任意的,但对于该解析树来说它是有限的.