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?

, , No Comments
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 :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback