<p>A context-free grammar is <em>cyclic</em> if there exists a non-terminal $A$ and a derivation in one or more steps $A\Rightarrow^+ A$.  It is <em>left-recursive</em> if there exists a non-terminal $A$, a mixed sequence of terminals and non-terminals $\gamma$, and a derivation in one or more steps $A\Rightarrow^+ A\gamma$.</p>

<p>Hence cyclic implies left-recursive, but the converse does not hold.  Note that a cyclic grammar can have infinitely many parses for a single terminal string---that might be problematic---, while there is little interest in having cycles in the applications I know (natural language processing and programming languages syntax), thus they are usually removed.</p>

CC BY-SA 3.0
2013-08-14T15:39:54.550Z
Thank you for the clarification! Do you have a trustworthy source for that? I was told by others and have meanwhile seen it mentioned on Wikipedia, but I could need some "real" reference for a paper. Thanks :-) Edit: Harrison'sIntroduction to Formal Language Theory has a definition of it (or more precisely of cycle-free, which is simply the negotiation)
me.at.coding
CC BY-SA 3.0
2013-08-13T11:00:49.873Z
2013-08-13T11:00:49.873Z
Sylvain
<p>I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things:</p>

<blockquote>
  <p>The original purpose of the LC transform is to allow
  simulation of left-corner parsing by top-down parsing,
  but it also eliminates left recursion from any noncyclic
  CFG.
  (from page 5 of <a href="http://research.microsoft.com/pubs/68869/naacl2k-proc-rev.pdf" rel="nofollow">http://research.microsoft.com/pubs/68869/naacl2k-proc-rev.pdf</a>)</p>
</blockquote>

<p>Note the second part of this quote:</p>

<blockquote>
  <p>it also eliminates left recursion from any noncyclic
  CFG.</p>
</blockquote>

<p>I though that a cyclic grammar and a left-recursive grammar go hand in hand? What's the difference?</p>

<p>Thanks for any hint on this!</p>

<fl.formal-languages><grammars><context-free><recursion>
Difference between a cyclic and a left-recursive context-free grammar?
me.at.coding
# Difference between a cyclic and a left-recursive context-free grammar?

(Asked by: username_0 on 2013-08-11)

I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things:

> The original purpose of the LC transform is to allow
> simulation of left-corner parsing by top-down parsing,
> but it also eliminates left recursion from any noncyclic
> CFG.
> (from page 5 of <http://research.microsoft.com/pubs/68869/naacl2k-proc-rev.pdf>)

Note the second part of this quote:

> it also eliminates left recursion from any noncyclic
> CFG.

I though that a cyclic grammar and a left-recursive grammar go hand in hand? What's the difference?

Thanks for any hint on this!

**Tags:** fl.formal-languages, grammars, context-free, recursion


---

## 1 answers

### Answer by username_1 on 2013-08-13. Score: 5

A context-free grammar is *cyclic* if there exists a non-terminal $A$ and a derivation in one or more steps $A\Rightarrow^+ A$. It is *left-recursive* if there exists a non-terminal $A$, a mixed sequence of terminals and non-terminals $\gamma$, and a derivation in one or more steps $A\Rightarrow^+ A\gamma$.

Hence cyclic implies left-recursive, but the converse does not hold. Note that a cyclic grammar can have infinitely many parses for a single terminal string---that might be problematic---, while there is little interest in having cycles in the applications I know (natural language processing and programming languages syntax), thus they are usually removed.

> **Comments:**
> **username_0**: Thank you for the clarification! Do you have a trustworthy source for that? I was told by others and have meanwhile seen it mentioned on Wikipedia, but I could need some "real" reference for a paper. Thanks :-) Edit: Harrison'sIntroduction to Formal Language Theory has a definition of it (or more precisely of cycle-free, which is simply the negotiation)  

---

