2
$\begingroup$

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!

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$ Aug 14, 2013 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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