Difference between a cyclic and a left-recursive context-free grammar?

Question

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!

Answer 1

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.