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

Question

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

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

示例语法:

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

生成的程序示例:

import jkhbhhuob
import aaaaa888_

namespace u8nFGubgykb
{ class ui0op_np { ... }
}

Answer 1

这是一个使用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()))

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

Answer 2

我不知道有一个“通用”算法可以做到这一点。随机程序生成用于遗传编程，因此您可以寻找基于语法的 GP 系统并了解它们如何处理程序生成。我会做一个递归规则生成算法，如伪代码：

void GenerateRule(someRule)
{
  foreach (part in someRule.Parts)
  {
    if (part.IsLiteral) OutputLiteral(part);
    if (part.IsIdentifier) Output(GenerateIdentifier(part)));
    if (part.IsRule) GenerateRule(part.Rule);
  }
}

这假设您已将所有部分读入某个数据结构。您还需要处理重复（随机生成它们发生的次数）和可选规则（掷硬币看看它们是否存在）。

编辑：哦，如果规则有多个选项，您只需选择其中一个选项，并以相同的方式处理它。因此，如果某个规则是（文字|变量），您将在两者之间随机选择。