15 votes 15 votes Consider the syntax directed translation scheme $\textsf{(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 \qquad \{E.val = E_{1}.val * T.val\}$ $E\rightarrow T \qquad \qquad \{E.val = T.val\}$ $T\rightarrow F - T_{1}\qquad \{T.val = F.val - T_{1}.val\}$ $T\rightarrow F \qquad \qquad \{T.val = F.val\}$ $F\rightarrow 2 \qquad \qquad \{F.val = 2\}$ $F\rightarrow 4 \qquad \qquad \{F.val = 4\}$ Using this $\textsf{SDTS},$ construct a parse tree for the expression $4 - 2 - 4 * 2$ and also compute its $E.val$. It is required to compute the total number of reductions performed to parse a given input. Using synthesized attributes only, modify the $\textsf{SDTS}$ given, without changing the grammar, to find $E.red$, the number of reductions performed while reducing an input to $E$. Compiler Design gatecse-2000 compiler-design syntax-directed-translation normal descriptive + – Kathleen asked Sep 14, 2014 • edited May 8, 2021 by gatecse Kathleen 8.3k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply chauhansunil20th commented Nov 30, 2018 reply Follow Share $-$ 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. 0 votes 0 votes Nitesh Singh 2 commented Jan 20, 2019 reply Follow Share Dont assume precedence of operator by yourself always take care of precedence and associativity given in question. 0 votes 0 votes Yashdeep2000 commented Jan 30 reply Follow Share I wonder what would have been different in B section if, instead of using “Synthesized Attribute” we use inherited attribute? 0 votes 0 votes Please log in or register to add a comment.
Best answer 30 votes 30 votes Given expression $4-2-4*2$ Total reductions = 10 Expression value, $E.val = 12$ Total number of reductions performed, $E.red = 10$ (number of non-leaf nodes in the parse tree) Prateek kumar answered Aug 30, 2016 • edited May 8, 2021 by gatecse Prateek kumar comment Share Follow See all 3 Comments See all 3 3 Comments reply Vicky rix commented Dec 31, 2017 reply Follow Share number of reductions is nothing but the number of non-leaves in the parse tree ... 19 votes 19 votes Hira Thakur commented Sep 11, 2022 reply Follow Share Please explain part B of the question. 0 votes 0 votes Thadymademe commented Oct 24, 2022 reply Follow Share @Hira Thakur From the perspective of parsing the input its not necessary to compute the total number of reductions. btw are u preparing for GATE?? 0 votes 0 votes Please log in or register to add a comment.
33 votes 33 votes SDTS to find the number of reductions:: E→ E1 * T {E.red = E1.red+ T.red+1} E→T {E.red = T.red+1} T→F - T1 {T.red = F.red + T1.red+1} T→F {T.red = F.red+1} F→2 {F.red = 1} F→4 {F.red = 1} VS answered Jul 6, 2017 VS comment Share Follow See 1 comment See all 1 1 comment reply rahul sharma 5 commented Jan 23, 2018 reply Follow Share @VS ,you can edit the selected answer to include this as part b answer. 1 votes 1 votes Please log in or register to add a comment.
10 votes 10 votes A. Given Expression is 4 - 2 - 4 * 2 , which can be rewritten as ((4 - (2 - 4))* 2) which is equal to 12. Aditya answered Aug 12, 2015 Aditya comment Share Follow See all 2 Comments See all 2 2 Comments reply Purple commented Jan 24, 2016 reply Follow Share how do we know that minus '-' is right to left? 0 votes 0 votes shivanisrivarshini commented Jan 24, 2016 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.