左递归语法识别

Question

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

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

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

Answer 1

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

\n\n

完成此操作后，左递归非终结符都A满足，其中是：A potentially-starts-with+ Apotentially-starts-with+

\n\n

potentially-starts-with \xe2\x88\x98 potentially-starts-with*

\n\n

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

\n\n\n\n

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

\n\n

\n
1. 删除所有无用的符号。
\n
2. 将指针附加到每个产品，最初位于第一个位置。
\n
3. 将所有作品放入工作队列中。
\n
4. 如果可能，请找到适用以下条件之一的产生式:\n
   \n
   • 如果产生式的左侧已被标记为 ε-非终结符，则丢弃该产生式。
   \n
   • 如果紧邻指针右侧的标记是终结符，则丢弃该产生式。
   \n
   • 如果紧邻指针右侧没有标记（即指针位于末尾），则将产生式的左侧标记为 ε 非终结符并丢弃该产生式。
   \n
   • 如果紧邻指针右侧的令牌是已标记为 ε 非终结符的非终结符，则将指针向右移动一个令牌并将产生式返回到工作队列。
   \n
\n

\n\n

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

\n\n

只是为了好玩，可以对上述算法进行简单修改来执行步骤 1。我将把它作为练习（这也是龙书中的练习）。确保上述算法在线性时间内执行的方法也作为练习。

\n