逐步消除这种间接左递归
问题描述:
我见过this algorithm应该可以使用它来删除所有左递归。 然而,我正在与这个特定的语法问题:逐步消除这种间接左递归
A -> Cd
B -> Ce
C -> A | B | f
无论我尝试我在循环或语法仍然是间接的左递归的结束。
在此语法上正确实施this algorithm的步骤是什么?
答
规则是你首先为非终端建立某种顺序,然后找到所有发生间接递归的路径。对于非终端C递归
在这种情况下为了将是一个<乙< C,和可能的路径将是
C=> A => Cd
和
C=> B => Ce
对于C会如此新规则
C=> Cd | Ce | f
现在你可以简单地删除直接的左递归:
C=> fC'
C'=> dC' | eC' | eps
所得非递归语法是:
A => Cd
B => Ce
C => fC'
C' => dC' | eC' | eps
答
已经算出来了。
我的疑惑是,按照这个顺序,算法似乎什么都不做,所以我认为肯定是错的,并开始在第一次迭代中替换A - > Cd(忽略j不能超越i)进入无限循环。
1)通过重排的规则:
C -> A | B | f
A -> Cd
B -> Ce
2)中所述的替换C - >镉
C -> A | B | f
A -> Ad | Bd | fd
B -> Ce
3)乙尚未在j的范围内,所以留给和替换直接的
C -> A | B | f
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ce
4左递归)在乙替换C - >铈
C -> A | B | f
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> Ae | Be | fe
5)尚未完成!还需要更换新的规则B - > AE(制造用的是j的范围内)
C -> A | B | f
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> BdA'e | fdA'e | Be | fe
6)B中
哇噢的C -> A | B | f
A -> BdA' | fdA'
A'-> dA' | epsylon
B -> fdA'eB' | feB'
B'-> dA'eB' | eB' | epsylon
生产代替直接左递归!左递归*语法!
这应该被迁移到cstheory.stackexchange.com,因为这已经无关编程,只需CS理论。 – Boggartfly