左递归消除问题

Question

左递归语法

E → E Op1 E2 | E2

实际上是左递归，所以我通过添加另一个步骤来消除左递归:

E → X E2
X → E Op1 E2 | ε

我有一种不祥的感觉，但是我错误地消除了它，因为如果我跟踪它，那么E的第一组仍然将从E开始。我说的对吗?还是我错过了什么?这个问题是一个更大的语法集的一部分，供参考。

Answer 1

您错过的是递归消除的第二部分:而不是

X → E Op1 E2 | ε

你需要

X → Op1 E2 X | ε