逐步消除这种间接的左递归 [英] Step by step elimination of this indirect left recursion

问题描述

我已经看到此算法应该可以用来删除所有剩余的递归. 但是我在使用这种特定语法时遇到了问题:

I've seen this algorithm one should be able to use to remove all left recursion. Yet I'm running into problems with this particular grammar:

A -> Cd
B -> Ce
C -> A | B | f

无论我尝试什么，我最终都会陷入循环或仍然是间接左递归的语法.

Whatever I try I end up in loops or with a grammar that is still indirect left recursive.

在此语法上正确实施此算法的步骤是什么?

What are the steps to properly implement this algorithm on this grammar?

推荐答案

规则是您首先为非终结点建立某种顺序，然后找到发生间接递归的所有路径.

Rule is that you first establish some kind of order for non-terminals, and then find all paths where indirect recursion happens.

在这种情况下，顺序将为A< B ＜ C，非终端C的递归路径可能是

In this case order would be A < B < C, and possible paths for recursion of non-terminal C would be

C=> A => Cd

和

C=> B => Ce

因此C的新规则将是

C=> Cd | Ce | f

现在您只需删除直接的左递归即可:

now you can simply just remove direct left recursion:

C=> fC'
C'=> dC' | eC' | eps

，由此产生的非递归语法将是:

and the resulting non-recursive grammar would be:

A => Cd
B => Ce
C => fC'
C' => dC' | eC' | eps

这篇关于逐步消除这种间接的左递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！