从语法生成句子的常见方法是什么?
我想要一种与解析器相反的算法。也就是说,给定一个正式的无上下文语法(例如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 { ... }
}
最佳答案
我不知道这样做有一个“通用”算法。基因编程中使用了随机程序生成,因此您可以寻找基于语法的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),则可以在两者之间随机选择。
关于compiler-construction - 如何从形式语法生成句子?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/603687/