从无上下文的语法中删除左递归 - 非末端的排序

Question

我最近实施了Paull的算法，以从无上下文的语法中删除左记录：

将订购$ a_1， dots，a_n $分配给语法的非终端。

对于$ i：= 1 $ to $ n $确实开始
$ quad $ for $ j：= 1 $ to $ i-1 $开始
$ Quad Quad $ $ a_i to a_j alpha $的每种制作的$ quad $开始
$ quad quad quad $ remove $ a_i to a_j alpha $从语法中
$ Quad Quad Quad Quad $用于表格$ a_j to beta $的每个制作
$ quad quad quad quad $ add $ a_i to beta alpha $ to Grammar
$ Quad Quad Quad $ end
$ Quad Quad $结束
$ quad $ end
$ quad $转换$ a_i $ - 生产以消除直接左递归
结尾

根据 这个文件, ，该算法的效率至关重要地取决于一开始选择的非终端的排序；本文详细讨论了此问题，并提出了优化。

一些符号：

我们会说符号$ x $是一个 直接左角 如果有$ x $作为$ x $的$ a $ a $，则是右侧最左侧的符号。我们定义 左角关系 成为直接左角关系的反身及其闭合，我们定义 适当的左角关系 成为直接左角关系的及时封闭。非终端是 左递归 如果它是自身的左角；非终端是 直接左递归 如果它是自身的直接左角；并且非终端是 间接左递归 如果左递归，但不是直接递归。

这是作者提出的：

在Paull算法的内部环中，对于非终端$ a_i $和$ a_j $，因此$ i> j $和$ a_j $是$ a_i $的直接左角，我们将所有出现$ a_j $作为直接的出现$ a_i $的左角，所有可能的扩展为$ a_j $。

如果$ a_i $是左恢复非终端，这仅有助于从语法中消除左递归，而$ a_j $则位于使$ a_i $左递归的路径上；也就是说，如果$ a_i $是$ a_j $的左角（除了$ a_j $是$ a_i $的左角）。

如果我们可以订购语法的非终端，那么我们可以消除删除左递归无用的替换，如果$ i> j $和$ a_j $是$ a_i $的直接左角，那么$ a_i $也是一个$ a_j $的左角。

我们可以通过以减少其拥有的不同左角数量的顺序订购非终端来实现这一目标。

由于左角的关系是传递的，如果C是B的直接左角，则C的每个左角也是B的左角。

此外，由于我们将左角关系定义为反身关系，因此B是自身的左角。

因此，如果c是B的直接左角，则必须以b的左下角数量减少，除非B是C的左角。

我只想知道如何在一开始就订购非终端，但是我不会从纸上获得它。有人可以简单地解释它吗？伪代码将帮助我更好地理解它。

Answer 1

这实际上不是很复杂。我会假设Epsilon Productions已经从该语言中消除了，因为这只会掩盖“左角”的关键概念。

形成图G，其中顶点是语法的所有非末端。现在，如果有任何看起来像“ A-> b [...]”的生产规则，则从A到B绘制一个定向边缘。该论文称B称为A的“直接左角”。更一般而言，如果从A到C沿此图的边缘有一些路径，则称为A的其他非末端C。这可以通过计算 传递闭合 G，称其为H。

该论文建议通过计算每个顶点a具有左角的数量来订购顶点（即您可以从A中获得多少其他非末端，或图中A中的A级超级，然后以减小顺序排序它们通过这个数字。

这项政策的一种手动动机是，如果有一个重要的非终端（例如起始符号）与许多其他符号的连接），那么从S早期清除左回归是有意义的，因为如果您离开它直到稍后，您需要扩大更多的S副本。我认为论文中的解释更具说服力，但也许不那么明显。