通过语法生成随机单词

Question

一些背景

我正在为语法编写一个解析器，出于测试目的，我想出了生成一些随机输入的想法。我正在处理的语法要复杂得多，在这个问题中，为了简单起见，我提出了“最小工作示例”。当然，我可以使用一堆琐碎的启发法来避免我所面临的问题，但这个问题确实让我感到好奇。

问题

假设我们有一个典型的算术表达式的上下文无关语法 $+,*$, 、括号和整数文字：

$$E \longrightarrow F(“+”F)^*$$ $$F \longrightarrow T(“*”T)^*$$ $$T \longrightarrow int|“(”E“)”$$

通过此语法很容易实现生成随机单词的直接算法：我们为每个非终结符实现一个单独的过程。如果非终结符有多个产生式规则（如 $T$ 确实如此），我们通过抛硬币来选择生产规则。如果规则包含 kleene 星号（例如 $(“+”F)^*$），我们还扔一枚硬币并生成零次或一次重复（当然我们可以选择任何随机整数 $k\geq0$ 并生成 $k$ 重复，但为了简单起见，我们将重点关注此过程的最简单版本）。这是我们得到的：

generate_E():
    if coin_toss():
        return generate_F() + "+" + generate_F()
    else:
        return generate_F()

generate_F():
    if coin_toss():
        return generate_T() + "*" + generate_T()
    else:
        return generate_F()

def generate_T():
    if coin_toss():
        return "(" + generate_E() + ")"
    else:
        return random_integer()

调用generate_E() 会产生一个随机表达式。

可能会出什么问题？事实证明，该过程在真机上的执行经常因堆栈溢出而终止。当然，从技术上讲，我们有无限递归的可能性，但我的直觉告诉我，达到递归深度的概率 $k$ 随着增加呈指数衰减 $k$, ，因此获得较深的级别（比方说，1000）几乎是不可能的。显然，几次连续运行表明过程可以轻松达到数千个深度（我所说的深度是指堆栈同时包含的过程调用的最大数量）。

我很好奇如何形式化这个经验事实。我想要一个公式 $P(深度 = k)$, ，或者它的渐近近似，或者下面的 CDF 右尾边界的不等式（类似于 $P(深度 > 1000) > 0.05$)

我的尝试

我试图想出一个公式 $P(深度 = k)$:

让我们表示 $P(深度 = k)$ 作为 $P_E(k)$. 。此外，我们定义了类似的值 生成_F() 和 生成_T() - $P_F(k)$ 和 $P_T(k)$ 分别。

清楚地 （别的 的分支 生成_T), $$P_T(1) = \frac{1}{2}$$ 并为 $k > 1$ (然后 分支）$$P_T(k) = \frac{1}{2}P_E(k - 1)$$

关于 $P_F(k)$, ，我们可以执行 别的 分支，它给出了术语 $$\frac{1}{2}P_T(k - 1)$$, ， 或者 然后 分支，什么给出了更复杂的分支 $$ frac {1} {2} sum _ {（x，y）| max（x，y）= k -1} {p_t（x）p_t（y）} $$ IE。 $$P_F(k)= \frac{1}{2}(P_F(k - 1) + \sum_{(x, y) | max(x, y) = k - 1}{P_T(x)P_T(是）}）$$

最后，公式为 $P_E(k)$ 几乎与 $P_F(f)$, ，我们只需更换 $P_T(x)$ 和 $P_F(x)$.

现在，我们可以计算一些值 $P_e(k)$

\begin{array} {|r|r|}\hline k & P_E(k) & P_E(k) ext{ 十进制}& P_E(k) ext{ 通过蒙特卡罗} \\ \hline 3 & \frac{33}{128} & \approx0.257812 & \approx0.2527 \\ \hline 6 & \frac{4448787585}{34359738368} & \approx0.129477 & \approx0.1282 \\ \hline 9 & \frac {14080391757747154038821618051813151497122305}{178405961588244985132285746181186892047843328} & \approx0.078923 & \approx0.0761 \\ \hline 12 & ext{ 分数太长} & \approx0.053213 & \approx0.0530 \\ \hline \end{array}

正如我们所看到的，循环公式似乎是正确的，但它们都没有让我深入了解 $P_E(k)$, ，第一个值也没有给出封闭形式公式的线索。

任何帮助，将不胜感激。

Answer 1

您的过程是一个教科书示例 分支过程. 。从一开始 $E$, ，我们有一个预期的 $3/2$ 许多 $F$s, $9/4$ 许多 $T$s，等等 $9/8$ 剩下很多 $E$正在期待中。自从 $9/8 > 1$, ，您的进程经常无法终止也就不足为奇了。

为了获得更多信息，我们需要知道数量的准确分布 $E$-offsprings，由以下生成函数给出（请参阅上面链接的维基百科文章）：$ h（z）= frac {33} {128} + frac {7} {16} Z + frac {15} {64} Z^2 + frac {1} {16} {16} Z^3 + frac {1} {128} z^4。$$这意味着灭绝概率是 $d \约0.717778143742483$ （通过解决 $h(z) = z$）。这是程序终止概率的上限。

我们可以通过考虑迭代来轻松恢复您的数字 $h$. 。进程终止的概率 $3k$ 步骤是 $h^{(k)}(0)$. 。所以计算 $h(0),h(h(0))-h(0),h(h(h(0)))-h(h(0))$ 依此类推，我们恢复表中的数字。

什么时候 $k$ 很大， $h^{(k)}(0) \大约 d$. 。我们可以计算 $h'(d) \约 0.882115879977412$. 。我们有$$ frac {d -h^{（k）}（0）} {d - h^{（k -k -1）}（0）} = frac {h（d） - h（h h^{（k） -1）}（0））} {d - h^{（k -1）}（0）} obl h'（d）。$$它遵循$$ d -h^{（k）}（0） propto h'（d）^k。$$因此，该过程恰好终止的概率 $3k$ 步骤是$$ h^{（k）}（0） - h^{（k -1）}（0）= [d -h^{（k -1）}（0）（0）] - [d -h^{（（ k）}（0）] propto h'（d）^{k -1} -h'（d）^k propto h'（d）^k。$$根据经验，我们可以检查比例常数大致为 $0.0248011196615094$.

Answer 2

正如 Yuval 所指出的，这种随机生成递归数据结构的方法（通常）最终会得到无限的预期大小。

然而，这个问题有一个解决方案，它允许人们以预期大小位于某个有限区间内的方式权衡递归选择： 玻尔兹曼采样器. 。它们基于结构的组合生成函数并来自组合物种理论。不过，对于实际实现，您不需要理论部分。可以找到 Haskell 的一个很好的编程介绍 在布伦特·约尔吉的博客中. 。如果您可以阅读（或破译）Haskell，则将该方法移植到您自己的数据结构中并不是太困难。

作为像您这样的推导在该框架内的外观示例，请阅读 计算和生成二元 lambda 演算中的项 作者：Grygiel 和 Lescanne（剧透：这是数量惊人的复杂分析）。