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 $Xstackrel*Rightarrow X$. What you often need is recursive rules and non-terminals, such that $Xstackrel*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
