compiler-construction - 如何从形式语法生成句子？

Question

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

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

Answer 1

我不知道这样做有一个“通用”算法。基因编程中使用了随机程序生成，因此您可以寻找基于语法的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），则可以在两者之间随机选择。