algorithm - 左递归语法识别

Question

通常我们想重构一个上下文无关的语法来移除左递归。有许多算法可以实现这种转换。例如这里或这里。

无论是否存在左递归，此类算法都将重构语法。这具有负面影响，例如从原始语法生成不同的解析树，可能具有不同的关联性。理想情况下，只有在绝对必要时才会转换语法。

是否有一种算法或工具来识别语法中左递归的存在？理想情况下，这也可能对包含左递归的生产规则子集进行分类。

Answer 1

有一个用于识别可空非终结符的标准算法，它在时间上与语法大小成线性关系（见下文）。完成此操作后，您可以A potentially-starts-with B在所有非终结符A,上构建关系B。（事实上​​，在所有语法符号上构建这种关系更正常，因为它也用于构建FIRST集合，但在这种情况下，我们只需要投影到非终结符上。）

完成之后，左递归非终结符都是A这样的，其中是：A potentially-starts-with+ Apotentially-starts-with+

potentially-starts-with ∘ potentially-starts-with*

您可以使用任何传递闭包算法来计算该关系。

---

作为参考，检测可为空的非终结符。

1. 删除所有无用的符号。
2. 将指针附加到每个产生式，最初在第一个位置。
3. 将所有产品放入工作队列。
4. 在可能的情况下，找到适用于以下其中一项的产品：
   • 如果产生式的左侧已被标记为 ε-非终结符，则丢弃产生式。
   • 如果指针右侧的标记是终结符，则丢弃该产生式。
   • 如果指针右侧没有记号（即指针在末尾），则将产生式的左侧标记为 ε-非终结符并丢弃产生式。
   • 如果紧挨着指针右边的记号是一个已被标记为ε-非终结符的非终结符，则将指针向右推进一个记号并将产生式返回到工作队列。

一旦不再可能从工作队列中选择一个生产，所有的 ε-非终结符都已被识别。

只是为了好玩，对上面的算法稍加修改就可以做第1步。我把它留作练习（这也是龙书的练习）。还留作练习的是确保上述算法在线性时间内执行的方法。