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

问题描述

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

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

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屋！