The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 votes

Consider the syntax directed translation scheme (SDTS) given in the following. Assume attribute evaluation with bottom-up parsing, i.e., attributes are evaluated immediately after a reduction.

E$\rightarrow $ E$_{1}$ * T {E.val = E$_{1}$.val * T.val}

        E$\rightarrow $ T {E.val = T.val}

T$\rightarrow $ F - T$_{1}$ {T.val = F.val - T$_{1}$.val}

        T$\rightarrow$ F {T.val = F.val}

        F$\rightarrow$2 {F.val = 2}

        F$\rightarrow$4 {F.val = 4}

  1. Using this SDTS, construct a parse tree for the expression $4 - 2 - 4 * 2$  and also compute its $E.val$.
  2. It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the SDTS given, without changing the grammar, to find $$, the number of reductions performed while reducing an input to $E$.
asked in Compiler Design by Veteran (59.9k points)
edited by | 1.4k views
$-$ is farthest from the start symbol, and $*$ is nearest to the start symbol, therefore, $-$ has higher precedence than $*$. $-$ is right associative as if an expression contains more than one $-$ then tree will grow towards right side, and $-$ present at the lower part of the tree towards right side will be evaluated before the $-$ present at the upper part of the tree towards left side, as Production T is right recursive.

So, expression will evaluate to 12.
Dont assume precedence of operator by yourself always take care of precedence and associativity given in question.

3 Answers

+18 votes
Best answer

   Given expression $4-2-4*2$

Total reduction $=10$

  1. expression value =12
  2. a total number of reductions performed =10


answered by Loyal (8.5k points)
edited by
number of reductions is nothing but the number of non-leaves in the parse tree ...
+15 votes
SDTS to find the number of reductions::

E→ E1 * T { =}

E→T { =}

T→F - T1 { = +}

T→F { =}

F→2 { = 1}

F→4 { = 1}
answered by Boss (10.4k points)
@VS ,you can edit the selected answer to include this as part b answer.
+11 votes

A. Given Expression is 4 - 2 - 4 * 2 , which can be rewritten as ((4 - (2 - 4))* 2) which is equal to 12.

answered by Active (3k points)
how do we know that minus '-' is right to left?
second minus is at lower level than 1st minus so first 2-4=-2 then 4-(-2)=6 then 6*2 since is at higher level

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
49,443 questions
53,648 answers
70,910 users