CODEWITHSUNDEEP
grammarcontext-free-grammaroperator-precedencebnfebnf
ambiguousrocket
ambiguousrocket

Reputation: 167

Why is this EBNF grammar ambiguous?

Currently studying for an exam and looking through past papers when I came across this question.

Below is a grammar in EBNF that describes simple arithmetic expressions, like 1 + 2 * 3 - 4: 

Expression = Operand, {Operator, Operand}; 
Operand = "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"; 
Operator = "+"|"-"|"*"|"/";

(iv) Using this grammar, there are multiple ways of evaluating an expression like 1 + 2 * 3 - 4. Describe two of them, and explain what this means about the grammar provided. [2 marks]

To my understanding, ambiguous grammar means there is either more than one left-most or right-most derivation, which usually implies there is some ambiguity in the grammar's order of precendence. But there is no precedence here, and the recursion is linear.

Advice?

Upvotes: 3

Views: 1106

Answers (1)

Brian Tompsett - 汤莱恩
Brian Tompsett - 汤莱恩

Reputation: 5893

You have part of the answer in your question.

Yes; you have almost the correct definition of an ambiguous grammar. If one performs a left-most and a right most derivation of the grammar they should produce an identical parse tree.

Yes; You are almost correct when you think this implies a problem with the grammars order of precedence, and yes, this grammar does not have any. Therein lies the problem: The operators are all given the same precedence and thus the different derivations will result in different answers from evaluating the example.

We could reduce 1 + 2 * 3 - 4 into either:

(1+2) * (3-4)
1 + (2 * 3) - 4
1 + (2 * (3 - 4))

depending on how the precedence of the operators are treated.

If you draw out explicitly the left-most and right-most reductions and hence derive the parse trees it will be clearer. This is often what students are expected to do for full marks in an exam question like this. I will therefore leave this as a revision exercise.

Upvotes: 1

Related Questions