Difference between a cyclic and a left-recursive context-free grammar? 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!
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.