论文标题
解析随机性：统一和区分解析器和随机发电机
Parsing Randomness: Unifying and Differentiating Parsers and Random Generators
论文作者
论文摘要
“发电机是随机性的解析器。”在编程语言社区中，对随机数据结构的发电机的看法已被很好地确定为民间传说，但显然从未正式化，也没有深入探索其后果。 我们提出了自由发电机，该发电机使用共同的结构统一解析和生成，该结构使两个概念之间的关系精确。自由发电机自然而然地证明了一大类生成器可以纳入解析器和选择序列上的分布。此外，自由发电机支持一种类似于熟悉的Brzozowski正式语言衍生物的衍生物概念，它允许分析工具“预览”特定发电机选择的效果。反过来，这产生了一种新颖的算法，用于生成满足用户指定前提的数据结构。
"A generator is a parser of randomness." This perspective on generators for random data structures is well established as folklore in the programming languages community, but it has apparently never been formalized, nor have its consequences been deeply explored. We present free generators, which unify parsing and generation using a common structure that makes the relationship between the two concepts precise. Free generators lead naturally to a proof that a large class of generators can be factored into a parser plus a distribution over choice sequences. Further, free generators support a notion of derivative, analogous to familiar Brzozowski derivatives of formal languages, that allows analysis tools to "preview" the effect of a particular generator choice. This, in turn, gives rise to a novel algorithm for generating data structures satisfying user-specified preconditions.
