[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?

Asked By : Xpl0

Answered By : babou

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33789

3.2K people like this

 Download Related Notes/Documents