左递归语法识别

Question

通常我们想重构一个上下文无关文法来去除左递归。有很多算法来实现这种转换;例如here或here。

这样的算法将重构语法而不管是否存在左递归。这具有负面的副作用，例如从原始语法产生不同的分析树，可能具有不同的关联性。理想情况下，语法只有在绝对必要时才会被转化。

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

Answer 1

有用于识别为空的非端，它运行在时间的线性在语法的大小的标准算法（见下文）。完成之后，您可以在所有非终端A，B上构建关系A potentially-starts-with B。 （事实上​​，这是比较正常的，构建在所有的语法符号这种关系，因为它也用于构建FIRST套，但在这种情况下，我们只需要投射到非终端）。

已经这样做了，留下-recursive非终端都A这样A potentially-starts-with+ A，其中potentially-starts-with+是：

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

你可以使用任何传递闭包的算法来计算这种关系。

---

仅供参考，用于检测可为空的非终端。

1. 删除所有无用的符号。
2. 附加一个指向每个生产的指针，最初位于第一个位置。
3. 将所有作品放入作品中。
4. 虽然可能，发现生产，其执行以下操作之一适用：
   • 如果生产的左手侧已被标记为＆的ε-; - 壬终端，丢弃生产。
   • 如果指针右侧的标记是终端，则放弃生产。
   • 如果没有立即令牌指针（即，指针是在端部）标注生产的左手侧作为与小量的权利; - 壬终端并且丢弃的生产。
   • 如果令牌立即向指针的右侧是已经标记为＆小量非末端; - 壬终端，前进指针一个令牌的权利和生产返回到工作队列。

一旦它不再能够从工作队列，所有的ε-＆选择生产; - 壬终端已被识别。

只是为了好玩，上述算法的一个微不足道的修改就可以用来做第1步我会离开它作为一个练习（这也是在龙书的练习）。作为练习还剩下的方法是确保上述算法在线性时间内执行。