<blockquote>
  <p>... is not valid since we have "left recursion" (a variable that calls itself).</p>
</blockquote>

<p>That's not what a <em>left</em> recursion is. That's simply recursion.</p>

<p><em>Direct</em> left recursion is when a rule <span class="math-container">$A \to A\alpha$</span> exists for arbitrary <span class="math-container">$\alpha$</span>.</p>

<p><em>Indirect</em> left recursion exists when there's a rule <span class="math-container">$A \to^* A\alpha$</span> for arbitrary <span class="math-container">$\alpha$</span>. Note the star, implying possibly many derivation steps (and if we're being precise, more than one, otherwise it's just direct left recursion).</p>

<p>Only <strong>left</strong> recursion (whether indirect or direct) is problematic for <span class="math-container">$\text{LL}(1)$</span>. But your grammar doesn't contain left recursion, only right recursion. Right recursion has the form <span class="math-container">$A\to^* \alpha A$</span>. See the difference?</p>

CC BY-SA 4.0
2019-10-17T17:03:26.180Z
Thank you for your answer. I will study this soon and reply back in about 4-7 hours.
Aaron Miller
CC BY-SA 4.0
2019-10-17T16:32:47.937Z
2019-10-17T16:32:47.937Z
orlp
<p>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 <a href="https://www.youtube.com/watch?v=QgpcZ825ddM&amp;t=3m44s" rel="nofollow noreferrer">video</a> and I am confused as to why </p>

<p><code>E' -&gt; TE' | ε</code> is valid </p>

<p>because</p>

<p><code>E -&gt; E + T</code> is not valid since we have "left recursion" (a variable that calls itself).</p>

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

<parsing><compilers><recursion>
Why can a Predictive Parser contain E' -> TE' | ε
Aaron Miller
# Why can a Predictive Parser contain E' -> TE' | ε

(Asked by: username_0 on 2019-10-15)

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](https://www.youtube.com/watch?v=QgpcZ825ddM&t=3m44s) 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.

**Tags:** parsing, compilers, recursion

---

## 1 answers

### Answer by username_1 on 2019-10-17. Score: 2 | Accepted answer

> ... 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?

> **Comments:**
> **username_0**: Thank you for your answer. I will study this soon and reply back in about 4-7 hours.  

---

