The Gateway to Computer Science Excellence
+20 votes

Consider the grammar with the following translation rules and $E$ as the start symbol$$\begin{array}{lll}
E \rightarrow   E_ 1\# \: T & \qquad\left\{E.value = E_1.value * T.value\right\}\\
\qquad\mid T & \qquad \{E.value = T.value\}\\
T \rightarrow  T_1 \& \: F &\qquad \{T.value = T_1.value + F.value\}\\
\qquad\mid F&\qquad \{T.value = F.value\}\\
F \rightarrow \text{num}&\qquad \{F.value=num.value\}
\end{array}$$Compute E.value for the root of the parse tree for the expression:$2$ # $3$ & $5$ # $6$ & $4$

  1. $200$
  2. $180$
  3. $160$
  4. $40$
in Compiler Design by Veteran (52.2k points)
edited by | 2.2k views
GATE 2004_45
 original  question was :

Consider the grammar with the following translation rules and E as the start symbol

E→ E1 # T       {E.value=E1.value ∗ T.value}
        | T             {E.value=T.value}
T→T1 & F        {T.value=T1.value + F.value}
       | F               {T.value=F.value}
F→num            {F.value=num.value}
please draw parse tree?

3 Answers

+37 votes
Best answer

Here # is multiplication and & is addition by semantics rules given in the question.
By observation of productions,

  1. here &(+) is higher precedence than #(*), because & is far from starting symbol
  2. both &,# are left associative

So, we can solve the expression as $((2*(3+5))*(6+4)) =160$

Answer is (C).

by Boss (17k points)
edited by

Can you please explain how and both &,# are left associative ???

if there is left recursion then operator will be left associative .. or if right recursion then operator will be right associate ..

eg : E---> E+T(here E derive E+T so it is left recursive

      E---->T+E (here E derive T+E so it is right recursive
Nice explanation.
Formal procedure of determining associativity and precedence in operator precedence grammar is using "Leading" and "Trailing". After computing leading and trailing of Nonterminals, we make operator precedence table that tells everything u want to know about associativity and precedence of operators in grammar.
I am not able to prepare parse tree here. Can anyone help?

parse tree

here is E and E1 is different


Sachin sir ,

So everytime decide precedence and asscociativity operator relation table constructed using Lead and Trails is needed ??

Can't we answer it using this argument 

"Operator which is at lower level in the grammar is termed to have higher precedence."


@Sachin Mittal 1

can you explain a bit more about trailing and leading method.. Or are there any good references for it?

–3 votes
C   will   be ans.
by Junior (715 points)
–5 votes
answer - B
by Loyal (8.6k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,461 answers
100,245 users