如何从正式语法生成句子？

从语法中生成句子的常用方法是什么？

我想要一种与解析器相反的算法.也就是说,给定一个正式的无上下文语法(比如LL),我想生成一个符合该语法的任意句子.我在这里使用句子来表示任何有效的文本体,因此它实际上可以是一个完整的程序(即使它没有任何意义 - 只要它的语法正确).

示例语法:

program   :  NEWLINE? 
imports   : ("import"  NEWLINE)* 
namespace : "namespace "  NEWLINE "{"  "}" 
identifier: (A-Za-z_) (A-Za-z0-9_)*
...

生成的程序示例:

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

Björn Lindqv.. 14

这是一个使用NLTK的Python示例:

from nltk import parse_cfg, ChartParser
from random import choice

def produce(grammar, symbol):
    words = []
    productions = grammar.productions(lhs = symbol)
    production = choice(productions)
    for sym in production.rhs():
        if isinstance(sym, str):
            words.append(sym)
        else:
            words.extend(produce(grammar, sym))
    return words

grammar = parse_cfg('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
V -> 'shot' | 'killed' | 'wounded'
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog'
P -> 'in' | 'outside'
''')

parser = ChartParser(grammar)

gr = parser.grammar()
print ' '.join(produce(gr, gr.start()))

这个例子改编自这本书.生成的句子在语法上是正确的,但仍然完全是胡言乱语.

这是一个使用NLTK的Python示例:

from nltk import parse_cfg, ChartParser
from random import choice

def produce(grammar, symbol):
    words = []
    productions = grammar.productions(lhs = symbol)
    production = choice(productions)
    for sym in production.rhs():
        if isinstance(sym, str):
            words.append(sym)
        else:
            words.extend(produce(grammar, sym))
    return words

grammar = parse_cfg('''
S -> NP VP
PP -> P NP
NP -> Det N | Det N PP | 'I'
VP -> V NP | VP PP
V -> 'shot' | 'killed' | 'wounded'
Det -> 'an' | 'my' 
N -> 'elephant' | 'pajamas' | 'cat' | 'dog'
P -> 'in' | 'outside'
''')

parser = ChartParser(grammar)

gr = parser.grammar()
print ' '.join(produce(gr, gr.start()))

这个例子改编自这本书.生成的句子在语法上是正确的,但仍然完全是胡言乱语.