GATE CSE
First time here? Checkout the FAQ!
x
+7 votes
1.3k views

Consider the following Syntax Directed Translation Scheme $( SDTS )$, with non-terminals $\{S,A \}$ and terminals $\{a,b \}$.

          $S \to aA  \quad \{\text{print }1\}$

          $S \to a    \quad   \{\text{print }2\}$

          $A \to Sb  \quad \{\text{print }3\}$

Using the above $SDTS$ , the output printed by a bottom-up parser, for the input $aab$ is:

  1.  $1 \ 3 \ 2 $ 
  2.  $2 \ 2 \ 3  $ 
  3.  $2 \ 3 \ 1 $ 
  4.  syntax error
asked in Compiler Design by Boss (9.2k points) 111 163 215
edited by | 1.3k views

1 Answer

+31 votes
Best answer

aab could be derived as follows by the bottom up parser:

S->aA prints 1
A->aSb prints 3
A->aab  prints 2
Now since bottom up parser will work in reverse of right most derivation, so it will print in bottom up fashion i.e., 231 which is option C.

Note that this could also be visualized easily by drawing the derivation tree.
 

answered by Boss (8.7k points) 14 35 91
edited by
Just a doubt... If the grammar given is not CLR(1) and the string is derivable will it be considered as parsable and sdt would be possible..??
@monanshi I did not get why itwill print 231 pls explain

shweta1920 if you draw parse tree for i/p aab then you will get 



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
Top Users Oct 2017
  1. Arjun

    23346 Points

  2. Bikram

    17058 Points

  3. Habibkhan

    8142 Points

  4. srestha

    6254 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4968 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4298 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3794 Points


Recent Badges

Notable Question Sandeep Suri
100 Club stdntlfe
Nice Question thor
100 Club Vamp thehacker
Popular Question LavTheRawkstar
Notable Question shubham vashishtha
Nice Answer Habibkhan
Good Question jenny101
Regular Ashish Subscription
Famous Question Akash Kanase
27,301 questions
35,155 answers
83,985 comments
33,244 users