As the title suggests, assume a grammar which has to recognize function declarations, function calls, and expressions, at any order. Does that mean it has to be cyclic, and therefore ambiguous?

I mean, it would have to look something like:

  • S -> function_declaration | function_call | expr
  • function_declaration -> ... | S
  • function_call -> ... | S
  • expr -> ... | S

Maybe not all of them would have to point back to S, that depends on the specifics. Is there any way to solve this?

  • 1
    $\begingroup$ Define "cyclic" please? I don't see why "cyclic" implies ambiguous. I don't think Lisp is ambiguous. $\endgroup$ Commented Dec 3, 2014 at 12:18
  • $\begingroup$ Assume A -> B | a and B -> A | b. There are two derivations for a. One is A => a, one is A => B => A => a. So it's ambiguous. $\endgroup$
    – Xpl0
    Commented Dec 3, 2014 at 12:21
  • $\begingroup$ ... which (by simple substitution) is equivalent to A -> A | b | a, which is not ambiguous. Okay. Why did I assume that? (And what does that assumption have to do with giving a concrete definition of "cyclic"?) $\endgroup$ Commented Dec 3, 2014 at 12:28
  • $\begingroup$ But what you just wrote is in fact ambiguous. $\endgroup$
    – Xpl0
    Commented Dec 3, 2014 at 12:30
  • 1
    $\begingroup$ Not at all. $S \to aS \mid \varepsilon$ is "cyclic" but clearly an unambiguous grammar (for $a^*$). The two concepts are simply unrelated (which is quite apparent from the definition of ambiguity), $\endgroup$
    – Raphael
    Commented Dec 3, 2014 at 12:41

1 Answer 1


There is just no need for rules (or non-terminals) that are cyclic, which I understand means that, for some non-terminal $X$, you have $X\stackrel*\Rightarrow X$.

What you often need is recursive rules and non-terminals, such that $X\stackrel*\Rightarrow uXv$, where $u$ and $v$ are strings of symbols. Without them, the language is finite.

For example, in the case of expressions you may have:

  • $Expr \to Term + Expr \mid Term$

  • $Term \to Factor * Term \mid Factor$

  • $Factor \to Ident \mid Literal \mid ( Expr )$

This said, you are right that cyclicity, as you define it, does make the grammar ambiguous iff the cyclic symbol can also derive on a terminal string.

  • $\begingroup$ I see... I think recursion is the way to go in my problem! Thank you once more! $\endgroup$
    – Xpl0
    Commented Dec 3, 2014 at 12:48

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.