如何从正式语法生成句子？ [英] How do I generate sentences from a formal grammar?

问题描述

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

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

I want an algorithm that's sort of the opposite of a parser. That is, given a formal context-free grammar (say LL), I want to generate an arbitrary sentence that conforms to that grammar. I use sentence here to mean any valid body of text, so it can actually be a whole program (even if it doesn't make any sense—as long as it's syntactially correct).

语法示例：

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 { ... }
}

推荐答案

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

I don't know that there's a "common" algorithm for doing this. Random program generation is used in genetic programming so you could look for a grammar based GP system and see how they handle program generation. I would do a recursive rule generation algorithm like the pseudo-code:

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);
  }
}

这假设你已经读过所有部分组成一些数据结构。你还需要处理重复（随机生成它们发生的次数）和可选规则（翻转一个硬币，看看它们是否存在）。

This assumes that you've read in all of the parts into some data structure. You'd also need to handle the repetitions(randomly generate the number of times they occur) and optional rules (flip a coin to see if they are there or not).

编辑：哦，如果规则有多个选项，你只需选择一个选项，并以同样的方式处理。所以如果一些规则是（Literal | Variable），你就可以在两者之间随机选择。

Oh, and if the rule has more than one option, you'd just pick one of the options to go with, and process it the same way. So if some rule was (Literal|Variable), you'd randomly pick between the two.

这篇关于如何从正式语法生成句子？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！