Courses

# Introduction and Difference Between Top Down and Bottom Up Praising - Compiler Design | EduRev Notes

## Computer Science Engineering (CSE) : Introduction and Difference Between Top Down and Bottom Up Praising - Compiler Design | EduRev Notes

The document Introduction and Difference Between Top Down and Bottom Up Praising - Compiler Design | EduRev Notes is a part of the Computer Science Engineering (CSE) Course Compiler Design.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

BOTTOM UP PARSING:
Bottom-up parser builds a derivation by working from the input sentence back towards the start symbol S. Right most derivation in reverse order is done in bottom-up parsing.
(The point of parsing is to construct a derivation. A derivation consists of a series of rewrite steps)
S⇒r0⇒r1⇒r2⇒- - - ⇒rn-1⇒rn⇒sentence
Bottom-up

Assuming the production A →b, to reduce ri ri-1 match some RHS b against ri then replace b with its corresponding LHS, A.

In terms of the parse tree, this is working from leaves to root.

Example – 1: S→if E then S else S/while

E do S/ print E→ true/ False/id

Input: if id then while true do print else print.

Parse tree:
Basic idea: Given  input  string  a,  “reduce”  it  to  the  goal  (start)  symbol,  by  looking  for substring that match production RHS.

⇒ if E then S else S
lm
⇒ if id then S else S
lm
⇒ if id then while E do S else S
lm
⇒ if id then while true do S else S
lm
⇒ if id then while true do print else S
lm
⇒ if id then while true do print else print
lm
⇒ if E then while true do print else print
rm
⇒ if E then while E do print else print
rm
⇒ if E then while E do S else print
rm
⇒ if E then S else print
rm
⇒ if E then S else S
rm
S
rm

Topdown Vs Bottom-up parsing:

→ Bottom-up can parse a larger set of languages than topdown.
→Both work for most (but not all) features of most computer languages.

Example – 2:

Right-most derivation

S → aAcBe          llp  : abbcde/ S              → aAcBe
A→ Ab/b                                                    →aAcde
B→d
→aAbcde
→abbcde

Bottom-up approach

Steps correspond to a right-most derivation in reverse.

(must choose RHS wisely)
Example – 3:
S →aABe
A →Abc/b
B →d
1/p:abbcde

Right most derivation:
S →aABe
→aAde Since ( ) B →d
→aAbcde Since ( )A →Abc
→abbcde Since ( ) A →b
Parsing using Bottom-up approach:

S parsing is completed as we got a start symbol Hence the 1/p string is acceptable.

Example – 4 E→E+E

E→E*E

E→(E)

E→id 1/p: id1+id2+id3

Right most derivation
E →E+E
→E+E*E
→E+E*id3 →E+id2*

id3 →id1+id2*id3

Parsing using Bottom-up approach:

Go from left to right
id1+id2*id3
E+id2*id3
E+E*id3
E*id3

E*E
E→id
E→id
E→E+E
E→id
E

= start symbol, Hence acceptable.

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

## Compiler Design

16 videos|44 docs|29 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;