retagged by
436 views
2 votes
2 votes

Consider the following two parse trees for the expression: $6 - 4 - 3$


          list                                     list
    /       |       \                          /      |     \
  /         |         \                       /       |       \
  list     ---    number        number     ---     list
 /   | \              |                 |                /    |     \
/    |   \            |                 |              /      |       \
list - number   3                6        number  ---     list
|              |                                    |                  |
|              |                                    |                  |
number   4                                   4            number
|                                                                   |
|                                                                   |
6                                                                  3

   (a)                                              (b)

 

Next, consider the below statements:

  1. The parse tree (a) represents right associative operator evaluation and the parse tree (b) represents left associative evaluation.
  2. The grammar generating the sentence is not ambiguous.

 

Which of the above statements are FALSE?

  1. Only $2$
  2. $1$ and $2$
  3. Only $1$
  4. Both statements are correct
retagged by

1 Answer

Best answer
2 votes
2 votes

Observe the parse tree (a), it grows toward left, while (b) grows to-wards right.

The left one (a) represent the following sequence of operations:

list --> list − digit

--> list − digit − digit

--> digit − digit − digit

-->  6 − digit − digit

--> 6 − 4 − digit

--> 6 − 4 – 3

 

This shows that the operators are evaluated in left associative manner that is from left to right. That (a) represent.

The second parse tree evaluates in right associative manner that is from right to left.

 

The grammar is obviously ambiguous since it produces two different parse trees for the same expression.

 

The reality is:

 
1. The parse tree (a) represent left associative evaluation while that of (b) right associative evaluation.
 
2. The grammar is ambiguous.

 

So both the  given statements are false.

selected by
Answer:

Related questions

2 votes
2 votes
0 answers
1
Bikram asked Nov 25, 2016
445 views
$\textbf{goto}$ function of LR class of grammar is represented as:Deterministic Finite Automata transitionsNon-deterministic Finite Automata transitionsPDA transitionsPar...
3 votes
3 votes
1 answer
2
Bikram asked Nov 25, 2016
443 views
Consider the following grammar:$E \rightarrow E + T \mid T$$T \rightarrow T ^* F \mid F$$F \rightarrow (E) \mid id$What are the productions for E, T and F after convertin...
2 votes
2 votes
1 answer
3
Bikram asked Nov 25, 2016
300 views
Which one of the following statements is TRUE?SLR parser has more states than LALR parser.LALR parser has more states than Canonical LR.Canonical LR has fewer states than...
3 votes
3 votes
1 answer
4
Bikram asked Nov 25, 2016
977 views
Which one of the following can be handled by predictive parsers?Left recursionLeft factorsAmbiguityNon-determinism