Compiler Design and Construction - Old Questions

1. Differentiate between top-down and bottom-up parsing methods. Construct SLR parse table for the following grammar.

10 marks | Asked in Model Question

Difference between top-down and bottom-up parsing methods

Top-down Parsing	Bottom-up Parsing
It is a parsing strategy that first looks at the highest level of the parse tree and works down the parse tree by using the rules of grammar.	It is a parsing strategy that first looks at the lowest level of the parse tree and works up the parse tree by using the rules of grammar.
Top-down parsing attempts to find the left most derivations for an input string.	Bottom-up parsing can be defined as an attempt to reduce the input string to start symbol of a grammar.
In this parsing technique we start parsing from top (start symbol of parse tree) to down (the leaf node of parse tree) in top-down manner.	In this parsing technique we start parsing from bottom (leaf node of parse tree) to up (the start symbol of parse tree) in bottom-up manner.
This parsing technique uses Left Most Derivation.	This parsing technique uses Right Most Derivation.
Its main decision is to select what production rule to use in order to construct the string.	Its main decision is to select when to use a production rule to reduce the string to get the starting symbol.
A top-down parser can be easily structured and formed.	It is difficult to produce a bottom-up parser
It is less powerful.	It is more powerful.
Error detection is easy.	Error detection is difficult.

Now,

Given grammar:

1. S → aETe

2. E → Ebc

3. E → b

4. T → d

The augmented grammar of given grammar is,

S‘ → S

S → aETe

E → Ebc

E → b

T → d

Next, we obtain the canonical collection of sets of LR(0) items, as follows,

I₀ = closure({S'→•S}) = {S'→•S, S→ •aETe }

goto(I₀, S) = {S'→S•}= I₁

goto(I₀, a) = closure({S→ a•ETe}) = {S→ a•ETe, E → •Ebc, E → •b}= I₂

goto(I₂, E) = closure({S→ aE•Te, E → E•bc}) = {S→ aE•Te, E → E•bc, T → •d}= I₃

goto(I₂, b) = closure({E → b•}) = {E → b•} = I₄

goto(I₃ , d) = closure({T → d•}) = I₅

goto(I₃ , b) = closure({E → Eb•c}) = {E → Eb•c}= I₆

goto(I₃ , T) = closure({S→ aET•e}) = {S→ aET•e} = I₇

goto( I₆ , c) = closure({E → Ebc•}) = {E → Ebc•}= I₈

goto(I₇ , e) = closure({S→ aETe•}) = {S→ aETe•}= I₉

FOLLOW set for non-terminals are,

FOLLOW(S) = {$}

FOLLOW(E) = {b, d}

FOLLOW(T) = {e}

Now, the SLR parsing table is,