Is a grammar that accepts function declarations, function calls and expressions (at any order!) necessarily cyclic?

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?

• Define "cyclic" please? I don't see why "cyclic" implies ambiguous. I don't think Lisp is ambiguous. – Wandering Logic Dec 3 '14 at 12:18
• 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. – Xpl0 Dec 3 '14 at 12:21
• ... 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"?) – Wandering Logic Dec 3 '14 at 12:28
• But what you just wrote is in fact ambiguous. – Xpl0 Dec 3 '14 at 12:30
• 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), – 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.

• I see... I think recursion is the way to go in my problem! Thank you once more! – Xpl0 Dec 3 '14 at 12:48