1
$\begingroup$

I am studying the basics of predictive parsing and I think I have missed a concept that I would like to understand instead of just accepting and memorizing. I am watching this video and I am confused as to why

E' -> TE' | ε is valid

because

E -> E + T is not valid since we have "left recursion" (a variable that calls itself).

in other words, why doesn't E' -> TE' | ε or T' -> *FT' have left recursion? To me it looks a lot like E' and T' are calling themselves.

$\endgroup$
2
$\begingroup$

... is not valid since we have "left recursion" (a variable that calls itself).

That's not what a left recursion is. That's simply recursion.

Direct left recursion is when a rule $A \to A\alpha$ exists for arbitrary $\alpha$.

Indirect left recursion exists when there's a rule $A \to^* A\alpha$ for arbitrary $\alpha$. Note the star, implying possibly many derivation steps (and if we're being precise, more than one, otherwise it's just direct left recursion).

Only left recursion (whether indirect or direct) is problematic for $\text{LL}(1)$. But your grammar doesn't contain left recursion, only right recursion. Right recursion has the form $A\to^* \alpha A$. See the difference?

$\endgroup$
  • $\begingroup$ Thank you for your answer. I will study this soon and reply back in about 4-7 hours. $\endgroup$ – Aaron Miller Oct 17 '19 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.