19 votes 19 votes Consider the following grammar. $S \rightarrow aSB \mid d$ $B \rightarrow b$ The number of reduction steps taken by a bottom-up parser while accepting the string $aaadbbb$ is ___________. Compiler Design gatecse-2020 numerical-answers compiler-design lr-parser 1-mark + – Arjun asked Feb 12, 2020 retagged Nov 30, 2022 by Lakshman Bhaiya Arjun 12.3k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply palashbehra5 commented Oct 27, 2021 reply Follow Share | Stack | Input | Action | | ------- | ----- | ---------------- | | $aaad | bbb$ | | | $aaaS | bbb$ | reduction S->d | | $aaaSb | bb$ | reduction B->b | | $aaaSB | bb$ | reduction S->aSB | | $aaSb | b$ | reduction B->b | | $aaSB | b$ | reduction S->aSB | | $aSb | $ | reduction B->b | | $S | $ | reduction S->aSB | Note : Skipped shift steps. 2 votes 2 votes Gajanan Purud commented Sep 17, 2023 reply Follow Share Nice question 0 votes 0 votes Please log in or register to add a comment.
Best answer 33 votes 33 votes In parse tree, all the non terminals are reductions. So total 7 reductions. Navneet Singh Tomar answered Feb 12, 2020 edited May 8, 2021 by gatecse Navneet Singh Tomar comment Share Follow See all 3 Comments See all 3 3 Comments reply gleise_21 commented Oct 2, 2021 reply Follow Share Can’t we take the string and try to reach to the initial symbol? That is how bottom up works right? 0 votes 0 votes Navneet Singh Tomar commented Oct 5, 2021 reply Follow Share Yes, you can use that approach as well. 0 votes 0 votes Philosophical_Virus commented Feb 1, 2023 reply Follow Share can we think of the idea from Gribeck Normal form 0 votes 0 votes Please log in or register to add a comment.
28 votes 28 votes Given string : aaadbbb Bottom-up parsers : rightmost derivation in reverse. S -> aSB S -> aSb S -> aaSBb S -> aaSbb S -> aaaSBbb S -> aaaSbbb S -> aaadbbb So, there are 7 steps. Shaik Masthan answered Feb 12, 2020 Shaik Masthan comment Share Follow See all 0 reply Please log in or register to add a comment.