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$ – Wandering Logic Dec 3 '14 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 Dec 3 '14 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$ – Wandering Logic Dec 3 '14 at 12:28
  • $\begingroup$ But what you just wrote is in fact ambiguous. $\endgroup$ – Xpl0 Dec 3 '14 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 Dec 3 '14 at 12:41

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.

| cite | improve this answer | |
  • $\begingroup$ I see... I think recursion is the way to go in my problem! Thank you once more! $\endgroup$ – Xpl0 Dec 3 '14 at 12:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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