# GATE2003-58

4.5k views

Consider the translation scheme shown below.

S $\rightarrow$ T R

R $\rightarrow$ + T {print(‘+’);} R$\mid \varepsilon$

T  $\rightarrow$ num {print(num.val);}

Here num is a token that represents an integer and num.val represents the corresponding integer value. For an input string ‘$9 + 5 + 2$’, this translation scheme will print

1. $9 + 5 + 2$
2. $9 \ 5 + 2 +$
3. $9 \ 5 \ 2 + +$
4. $+ + 9 \ 5 \ 2$

edited

$9\ 5+2+$

edited
0

Could someone explain this solution in words a little bit ?
Im having trouble in understainding how

9+5 prints 95+ ?

9+5+2

• T+5+2  ( T-> num  output : 9 )
•

Im stuck at here , How to proceed ?

1
in L attribute we evaluate the node first time when we visit it.

so according to this answer should be 9+5+2 ???
Input Translation Output
9 + 5 + 2 S → T R
9 + 5 + 2 T  → num {print(num.val);} 9
+ 5 + 2 R → + T {print(‘+’);} R  (the + is simply consumed as there is no print corresponding to it)
5 + 2 T  → num {print(num.val);} 5+
+ 2  R → + T {print(‘+’);} R
2 T  → num {print(num.val);} 2+

So, output 95+2+. Option B.

2
sir why not option (c)...
1
@SONAM

check the semantic action location
1
@Pranabesh Ghosh 1

Even i also felt the same doubt. But it seems like the actual question in gate with respect to what is mentioned here is different. Notice the location of semantic action.
0
In L attributed SDT we can specify the actions anywhere in the production.

Is it L attributed SDT or S attributed SDT sir?
1

@AnilGoudar It is L attributed SDT

0
Can we think of it as print statement embedded in the production?
0
Please explain how it is L attributed SDT ?
1
How to detect L attributed or S attributed in such grammar
0
@Arjun

Sir, Given grammar is L-SDT right? Then parsing should be done from top to down then left to right and semantics actions will be evaluated when productions are pruned. So, shouldn't the answer be C?

If we perform top down parsing then B is correct but nothing is mentioned about top down or anything else.

So in all both options are correct as question is ambiguous as nothing is mentioned about the parsing method.
0

while creation of parse tree, are we supposed to place the semantic actions in the parse tree in the same order they appear in the grammar?

I was considering the semantic action after complete reduction of +TR into R and hence getting 952++ .

Could you please confirm if my understanding regarding placement of semantic actions is now correct?

Another query : is depth first, left to right traversal the same as top down parsing?

Reduce the Expression Rightmost in Reverse:- (Seeing the first matching reducible symbol)
9 + 5 + 2ε  (Print 9 and reduced to T)
> T + 5 + 2ε  (Print 5 and Reduced to T)
> T + T  + 2ε (+T print + and can't be reduced)
> T + T + Tε   (Print 2 and reduced to T)
> T + T +Tε (+T print + and can't be reduced)
> T + T +TR (ε Reduced to R)
> T +TR (+TR reduced to R)

>TR (+TR reduced to R)

>S (TR reduced to S)

9 5 + 2 +

## Related questions

1
7.5k views
Consider the grammar shown below. $S \rightarrow C \ C$ $C \rightarrow c \ C \mid d$ This grammar is LL(1) SLR(1) but not LL(1) LALR(1) but not SLR(1) LR(I) but not LALR(1)
Consider the grammar shown below $S \rightarrow i E t S S' \mid a$ $S' \rightarrow e S \mid \epsilon$ $E \rightarrow b$ In the predictive parse table, $M,$ of this grammar, the entries $M[S' , e]$ and $M[S' , \$]$respectively are$\{S' \rightarrow e S\ ... $\{S' \rightarrow \epsilon\}$ $\{S' \rightarrow e S, S' \rightarrow \varepsilon$} and $\{S' \rightarrow \epsilon\}$
The following program fragment is written in a programming language that allows global variables and does not allow nested declarations of functions. global int i=100, j=5; void P(x) { int i=10; print(x+10); i=200; j=20; print (x); } main() {P(i+j);} If the ... scoping and call by name parameter passing mechanism, the values printed by the above program are $115, 220$ $25, 220$ $25, 15$ $115, 105$
Consider the syntax directed definition shown below. ... is $X = Y + Z$ $t_1 = Y+Z; X=t_1$ $t_1 =Y; t_2=t_1 +Z; X=t_2$ $t_1 =Y; t_2=Z; t_3=t_1+t_2; X=t_3$