CODEWITHSUNDEEP
grammarcontext-free-grammarambiguous-grammar
Yodism
Yodism

Reputation: 247

Unambigous grammar to ambiguous

I don't know if it is the right site to ask this. But we're studying about ambiguities of grammar. Including left most derivation and right most derivation. My practice problem is this:

E -> E * E | E + E | N
N -> 0N | 1N |
Output: 0110 + 110 * 01111

Is there a way to make it ambiguous? And any tips in making a grammar ambiguous?

Upvotes: 0

Views: 127

Answers (1)

Am_I_Helpful
Am_I_Helpful

Reputation: 19158

Given your grammar, it is clearly ambiguous. Here, it doesn't define the preference between + and * operator.

As you said, if you have to parse this 0110 + 110 * 01111, it can be done using two ways :-

  1. 0110 + 110 * 01111 ----> (0110 + 110) * 01111

  2. 0110 + 110 * 01111 ----> 0110 + (110 * 01111)

So, this grammar is pretty ambiguous as it doesn't define operator precedence. Also, there is no provision of operator associativity.

It clearly depends on the production rules specified by the grammar to remove the ambiguity by specifying distinctions between conflicting cases. Some of the things while doing top-down parsing come to case are left factoring and left-recursion leading to ambiguous grammars.

You should see elimination of left recursion and other related tutorials as it'd be too broad to specify the rules.

Upvotes: 1

Related Questions