random - 从上下文无关文法生成 n 条语句

Question

所以不要重新发明轮子，我想知道在从上下文无关语言（如 yacc 生成的语言等）生成随机语句方面已经做了什么。这些语法主要用于解析，但也许有人做了一些测试来测试解析器？谢谢

Answer 1

看看这篇博文。基本上，它会随机化在每个规则应用程序中选择的 RHS。

Answer 2

这里有一篇古老但仍然很有趣的文章，它说明了为什么你需要更多的约束来有效生成随机句子而不是解析——它还提出了一种提供这些额外约束的简单方法，并给出了一个完整的示例程序 (.. .in Fortran IV ......但是，嘿，它已经超过 40 年了......！-)。

不幸的是，我不知道关于这个主题的任何最新工作（或更现代语言的实现——但是将 Fortran 尘土飞扬的甲板转码成你最喜欢的任何语言不应该像自己提出这些概念那样难； -) -- 这只是我上大学时在实际的纸质图书馆中阅读的那种已经很古老的东西，我很惊讶 ACM 的在线搜索工具让我能够找到我依稀记得的参考资料，这么快（赞，ACM！-）。我从未对这个主题进行过任何原创性研究。

Answer 3

像这样生成一系列随机标记有点简单；从目标符号开始，选择任何未填充的非终结符的随机扩展。您可能希望在生成的解析树的任何分支上进行某种分支定界搜索，以便控制深度/大小。

但是我看不出以这种方式测试解析器有什么价值，至少如果您的解析器生成器直接接受上下文无关语言描述，则不会。当您使用完整的上下文无关解析器生成器/工具（例如 GLR（我们在程序转换系统 DMS 中使用的）或 Earley 解析器）时，就会发生这种情况。

你还有另一个问题：如果你想测试一个解析器，你需要给它提供它想要的东西，而且肯定不是令牌。现在您必须为终端叶生成有效的词位。这也不是太难，但如果你想对这种方法保持纯粹，你会以无扫描风格编写语法。

但最后一个问题是很难为大多数语言找到上下文无关的语法。所以现在你也必须调试你的黄金语法；你会怎么做？一旦你到了那个阶段，你很可能会放弃，调试解析器，然后继续你的生活。

如果您可以拼接随机树以修复源流，则生成随机子树在错误恢复中很有用。我们为 DMS 的解析器做了一个简化的形式，这意味着我们只有一个错误处理机制。