19

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

我想要一种与解析器相反的算法。也就是说，给定一个正式的上下文无关语法（比如 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 { ... }
}
4

9 回答 9

16

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

该示例改编自该书。生成的句子在语法上是正确的，但仍然完全是胡言乱语。

于 2010-07-20T16:11:00.447 回答
4

我不知道有这样做的“通用”算法。随机程序生成用于遗传编程，因此您可以寻找基于语法的 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);
  }
}

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

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

于 2009-03-02T20:00:29.823 回答
2

在我的头顶上：

我会递归地工作（基本上与递归体面的解析器相反）使用一些关于如何处理范围（(...)：可能是随机选择）选项（?：参见下面的[]），重复（' '泊松分布？）的启发式方法。文字 ( "...") 被简单地写入输出，而子标记 (`<...>') 生成递归。

除非您想保证某种完整的覆盖范围，否则这应该不会太难。即使那样，仅生成一堆数据也会有所帮助...

[*] 您需要在少于 50% 的时间内包含选项，以防止在处理规则时无限回归

 nonterm:  otherstuff <nonterm>?

很好的底座。

与重复类似，抛出一个强烈收敛的分布。

如果输入语法以 BNF 形式呈现，则需要先解析输入语法，如此处所示。最简单的做法是使用映射(name, string)，然后从最高级别的令牌开始（您可能会认为这意味着第一个......）。

这给了你：

("program", "<imports> NEWLINE?<namespace>")

("imports", ("import" <标识符> NEWLINE)*)

...

你从“程序”开始，点击“<imports>”，所以你会重复......回来时，点击“NEWLINE？”，所以掷骰子并写或不写，点击“<namespace>”所以重复......返回时你就完成了。

我发现自己怀疑以前有人做过。如果您只需要输出，我会在网上搜索...也许http://portal.acm.org/citation.cfm?doid=966137.966142，尽管那里有大量的解析器生成器使搜索空间变得混乱。 .. 也试试这篇论文。

顺便说一句——你当地的大学可能有这些期刊的在线订阅，所以你可以通过在图书馆联系来免费获得它们。

于 2009-03-02T19:51:43.230 回答
2

您的解决方案应遵循语法的归纳结构。你如何为以下每一个生成随机话语？

  • 端子符号
  • 非终结符
  • 右手边的序列
  • 右手边的选择
  • 右侧星形闭合

如果您写下用于表示语法的数据结构，这一切都会更加清晰。您的一组相互递归生成器函数的结构将非常紧密地反映该数据结构。

处理无限递归有点冒险。最简单的方法是生成话语流并保持深度截止。或者，如果您使用像 Haskell 这样的惰性语言，您可以生成所有话语并剥离任意数量的有限话语（比原始问题更棘手，但非常有趣）。

于 2009-03-02T23:22:49.663 回答
1

我的第一个建议是广度优先搜索。只需设置规则图并搜索它们。您将从最小的程序开始吐出程序，然后慢慢变大。但是，您可能会发现，对于给定数量的规则，您的语法会以指数方式吐出更多的程序，并且您可能不会在使用 DFS 的程序中获得超过 30 个左右的标记。

深度优先搜索的问题在于，一旦你有了左递归规则，你的搜索就会陷入无限循环。

另一个大问题是语法正确的程序距离语义正确的程序还有很长的路要走。除了最基本的情况外，生成后一种类型可能完全不可行。

于 2009-03-02T19:46:27.080 回答
1

您将遇到的问题是图形的递归性质使得您可以生成无限大小的正确语法。您可能想要做一些事情，例如在您的语法中设置节点类型的哈希，其中包含您允许自己点击该节点的次数和限制。然后深度优先搜索您的内容。

于 2009-03-02T20:02:47.273 回答
1

像往常一样，我会建议不要重新发明轮子。我已经为 ARM 汇编器编写了其中一个，但我对此表示遗憾（软件：实践和经验2007 年 4 月）：

“回想起来，应该使用现成的表达式生成器来生成随机 ARM 汇编指令以进行比较。取而代之的是，逐步构建 Perl 脚本，获取每个 ARM 指令定义并生成实例。然而，增量内部方法的一个优势是简单的替换可以检测到简单的错误，并且可以逐步进行错误搜索。”</p>

恐怕我不记得是什么让我改变了主意，而且我怀疑它是否与您的特定需求相关，但我确实建议更加努力地寻找预先存在的解决方案。自己写这样的东西需要更少的纪律，但它总是比你预期的要花更长的时间。

于 2009-04-29T17:49:43.227 回答
0

不是答案，但请检查有关语法生成的维基百科条目： http ://en.wikipedia.org/wiki/Context-free_grammar_generation_algorithms

它描述了一些常用的算法。

于 2009-03-02T19:46:00.480 回答
-1

虽然这个想法很好（我之前已经想过很多次），但现实情况是，如果没有一些样本数据和/或大量的生成器约束/努力限制，这是一项相当大的工作。

人们可能会发现手工编写样本更容易。:)

于 2009-03-02T19:46:56.627 回答