World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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?

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.