Compiler design question on SDT : 1

Question

Consider the following SDT,

S → M {PRINT “2”;} A

M → 1 {PRINT “ ”;}

A → D {PRINT “1”;} E

D → 2 {PRINT “ ”;}

E → E {PRINT “ ”;} A

E → 3 {PRINT “ ”;}

A → S {PRINT “4”;} Y

S → 4 {PRINT “ ”;}

Y → ∈ {PRINT “ ”;}

If the bottom up parsing is used to parse the input string “1234” then the output number produced (without any spaces) is _______

Comments

is it 214?

---

plz upload ur pic again .

---

How the value is 214 with Top down Parser ?

Answer 1

Parse tree for $1234$ looks like $\Rightarrow$

​

In TDP, Traverse the tree top $\rightarrow$ down, left $\rightarrow$ right, and perform a semantic action for the first time it occurs during tree traversal. Thus $214$ is the answer.

In BUP we perform semantic action during reduction, Thus $412$ is the answer in the case of BUP.

Comments

@radha gogia 

---

@Leen can you tell me the difference between bottom up and top down,best if u can draw a diagram for top down and tell me the approach to do the top down approach..it will be agrt help..

---

 

 

 

 

 

 

 

 

 

@LeenSharma but here in ullman, these statements contradicts ur answer,how about right answer ? iam confused

Answer 2

In my opnion the input string is not parsed successfully.

why because of at the output 2 and 3 we are not getting the S symbol that means starting symbol or there is no way to derive the starting symbol. Based on the bottom up we are parsing the string from leaves to root but it is not successfully here yet. Please suggest me if i am wrong.

Answer 3

For top down approach answer is 214 why  because we write the productions along with parse tree and carry out that action when we encounter one but in case of bottom up approach we totally focus on reduction, when ever we encounter any reduction we go to production and carry out that action so according to that BUP gives me 412 as answer.