我怎么产生的句子从一个正规语法？

Question

什么是一个共同的方式产生的句子从语法？

我想了一种算法，是一种相反的一种分析器。那就是，给予一个正式的上下文的免费法(说LL)，我希望产生一种任意判决，符合该法。我用 句子 这里的意思是任何有效的体的文本，所以它实际上是一个整体的程序(即使它没有任何意义--只要它syntactially正确的)。

例法:

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

我不知道有一个<！> quot; common <！> quot;这样做的算法。随机程序生成用于遗传编程，因此您可以查找基于语法的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），您可以在两者之间随机选择。

Answer 2

以下是使用 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 3

你的解决方案应该遵循的感应式结构的语法。你怎么产生的一个随机的话语用于以下各个?

• 终端的象征
• 非终结符号
• 序列的右手边
• 选择的右手边
• 星封闭的右手边

这一切将更清楚如果你写下来的数据结构你用来表示一语。该结构的组互相递归的发电机的功能将一面镜子，数据结构非常密切的合作。

处理无限递归是有点冒险。最简单的方法就是产生流的言论和保持一个深入的截止。或如果你使用一个懒惰的语言Haskell，你可以产生 所有 言论和剥许多有限的，因为你喜欢(一个棘手的问题要比原来的问题，但非常有趣的).

Answer 4

脱离我的头顶：

我会递归地工作（基本上与递归的正确解析器相反）使用一些关于如何处理范围的启发式（(...)：可能随机选择）选项（?：参见[]，下面），重复（''泊松分布？）。文字（"..."）很容易写入输出，而字符（`<！> lt; ... <！> gt;'）会产生递归。

除非你想保证某种完整的保险，否则这不应该太难。即使这样，只需生成束数据也是一种帮助......

---

[*]在处理

等规则时，您需要包含少于50％时间的选项以防止无限回归

 nonterm:  otherstuff <nonterm>?

plinth

同样重复，抛出强烈收敛的分布。

---

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

这会给你：

  

（<！> quot; program <！> quot;，<！> quot; <！> lt; imports <！> gt; NEWLINE？<！> lt; namespace <！> gt; <！> quot; ）

     

（<！> quot; imports <！> quot;，（<！> quot; import <！> quot; <！> lt; identifier <！> gt; NEWLINE）*）

     

...

你从<！>“程序<！>”开始，点击<！>“; <！> lt; imports <！> gt; <！> quot;所以你重复...回来，直到<！>“NEWLINE？<！>”，所以扔掉骰子然后写或不，点击<！>“; <！> lt; namespace <！> gt; <！> QUOT;所以重复......回来后你就完成了。

---

我发现自己怀疑以前已经做过这件事。如果您只需要输出，我会搜索网页...也许 http：/ /portal.acm.org/citation.cfm?doid=966137.966142 ，虽然大量的解析器生成器使搜索空间变得混乱...尝试 _ UDI = B6V0B-3SP62KK-9 <！> _用户= 10 <！> _的RDoc = 1 <！> _ FMT = <！> _原稿=搜索<！> _排序= d <！>视图= c <！> _ acct = C000050221 <！> _ version = 1 <！> _ urlVersion = 0 <！> _ userid = 10 <！> md5 = ab18c231faad1c54e63358d7ea589459“rel =”nofollow noreferrer“>本文也是。

BTW--你当地的大学可能已经在线订阅这些期刊，所以你可以通过连接图书馆免费获得它们。

Answer 5

您将遇到的问题是图的递归性质使您可以生成无限大小的正确语法。您可能希望做一些事情，例如在语法中设置节点类型的哈希值，以及允许自己命中该节点的次数和数量限制。然后深入探索心脏的内容。

Answer 6

我的第一个建议是广泛的第一次搜索。只需设置规则图并搜索它们即可。你将从最小的程序开始吐出程序，然后逐渐变大。但是，您可能会发现，您的语法会针对给定数量的规则吐出指数级更多的程序，并且您在使用DFS的程序中可能不会超过30个左右的标记。

深度优先搜索的问题在于，第二个你有一个左递归规则，你的搜索将陷入无限循环。

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

Answer 7

像往常一样，我<！>＃8217;我会建议不要重新发明轮子。我已经为ARM汇编程序编写了其中一个，但我>＃8217;记录为后悔（软件：实践和经验 2007年4月）：

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

我<！>＃8217;恐怕我不知道<！>＃8217;回想起是什么让我改变了主意，我怀疑它会与你的具体需求相关，但我建议你更难以预先存在解。要自己写这样的东西需要较少的纪律，但它总是需要比你预期的更长的时间。

Answer 8

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

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

Answer 9

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

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