edited by
4,381 views
19 votes
19 votes

Consider the following grammar for arithmetic expressions using binary operators $-$ and $/$ which are not associative

  • $E \rightarrow E -T\mid T$
  • $T \rightarrow T/F\mid F$  
  • $F \rightarrow (E) \mid id$

($E$ is the start symbol)

Is the grammar unambiguous? Is so, what is the relative precedence between  $-$ and $/$? If not, give an unambiguous grammar that gives $/$ precedence over $-$.

edited by

3 Answers

Best answer
20 votes
20 votes

Yes. It is unambiguous grammar since for any string no more than $1$ parse tree is possible.

For precedency draw the parse tree and find the depth of operator -   and  

Here "/" having more depth than " - " operator so precedency of" /"  is higher than "-".

edited by
0 votes
0 votes

No, the given grammar is ambiguous.

Here's why:

  • Ambiguity arises in expressions containing both - and /. Consider the expression a-b/c. It could be parsed in two ways:

    • (a - b) / c
    • a - (b / c)
  • The grammar doesn't specify a clear precedence for - and /. This lack of precedence rules leads to the ambiguity.

To create an unambiguous grammar that gives / precedence over -:

  1. Introduce a new non-terminal symbol, say T, to represent expressions with higher-precedence operators.
  2. Modify the productions for E and T as follows:
E -> T - T | T
T -> F / F | F
F -> (E) | id

 

Explanation:

 

  • E now directly produces T expressions, ensuring / is applied first.
  • T handles both / operations and F (factor) productions.
  • F remains unchanged for parentheses and identifiers.

 

With this grammar:

 

  • Expressions with both operators are parsed consistently, giving / higher precedence.
  • Parentheses can still be used to override the default precedence.

 

Example:

 

  • a-b/c will be parsed as a - (b / c), matching the intended precedence.

 

Related questions

22 votes
22 votes
3 answers
3