Bottom up Parsing

Bottom-up parsing:

In this methodology, it follows the process which is exactly controversy to the top-down parsing. It starts with the input symbol first and determines the start symbol.

Bottom-up parsing:

  • SLR
  • CLR
  • LALR

SLR:

It is one type of parsing technique in bottom-up parsing. It follows two functions to find the parse tree.

  • Closure
  • Goto

Goto:

The goto functions act as the one-step movement function. We use (.) operator in SLR. Goto function pushes the dot after the specified symbol.

Example:

S1→.S is the production.

If we specify goto (S1,S) the output will be S1àS.

Closure:

For suppose if there are productions like

Closure (I0,S) gives the production of non-terminal after the dot operator.

 S1→.S

                                     S→.CC

                                     C→.ac

                                     C→.d

For example:

S→CC

C→aC

C→d

To solve a problem, SLR follows a methodology like finding the kernel items. Kernel items are nothing but adding the dot operator before every symbol in the starting of the right hand side and adding a extra production i.e. complementary of the root gives rise to root. Converting the productions into the kernel items is as follows.

In next step we have to find the closure of newly added production.

Closure (S1→.S)

We have to take all the dot operators to the end of the production in every production.

To do this we have to do closure and goto operator.

If a set or certain productions are repeated denote with same I value.

We have to terminate the process once all the productions have the dot operator at the ending.

Flow graph will be

 

Parse table: parse table consists of action and go parts. All the terminals will be in action phase and all the non-terminals will be in go phase. All the I values obtained in production rules while finding the closure productions.

States

a

d

$

S

C

0

S3

S4

 

1

2

1

 

 

 

accept

 

2

S3

S4

 

 

5

3

S3

S4

 

 

6

4

R3

R3

R3

 

 

5

 

 

R1

 

 

6

R2

R2

R2

 

 

I0 on S gives I1

S is a non-terminal so write only state number in (0 ,S) field.

I0 on C gives I2

C is a non-terminal so write only state number in (0 ,C) field.

I0 on a gives I3

a is a terminal so write only state number along with shift(s) in (0 ,a) field.

I0 on d gives I4

d is a terminal so write  state number along with shift in (0 ,d) field.

I2 on C gives I5

C is a non-terminal so write only state number in (2 ,C) field.

I2 on a gives I3

a is a terminal so write  state number along with the shift in (2 ,a) field.

I2 on d gives I4

d is a terminal so write  state number along with the shift in (2 ,d) field.

I3 on C gives I6

C is a non-terminal so write  only state number  in (3 ,C) field.

I3 on a gives I3

a is a terminal so write  state number along with the shift in (3 ,a) field.

I3 on d gives I4

d is a terminal so write  state number along with the shift in (3 ,d) field.

up to now there are productions with which we can fill shift and we have to fill remaining fields by some process given below.

We have to find the first and follow of the productions to fill the remaining fields.

S→CC

C→aC

C→d

FIRST(S)→FIRST(C)→{a,d}

FIRST(C)→{a,d}

FIRST (a)→{a}

FIRST (d)→{d}

FOLLOW(S)→$

FOLLOW(C)→FIRST(C)→{a,d}

FOLLOW(C)→FOLLOW(S)→ {a,d,$}

FOLLOW(C)→{a,d}

We have filled the table up to 3 so consider I4 as it is final production coz dot is in the last position.

C→d.

FOLLOW (root)àFOLLOW(C)→ {a,d,$}

So in place of (4,a), (4,d), (4,$) write R3( as it is the 3rd production in the problem statement).

I5→ S→CC

FOLLOW(S)→{$}

In place of (5,$)  mark R1 as it is 1st production.

I6→C→aC

FOLLOW(C)→{a,d,$}

In place of (6,a), (6,d), (6,$) mark R2 as it is in 2nd production.

CLR:

Canonical left to right scanning and rightmost derivative in reverse order

In clr the general form of an item is A→α.Bβ,a

A→αβ is a production

a is a terminal or write marker

The component is called as the look ahead item.

Example:

S→CC

C→aC

C→d

Construct an augmented grammar from the given problem solution.

S1→.S

S→.CC

C→.aC

C→.d

Look ahead symbol of initial production will be $.

S1→.S,$

 

The following picture describes about the flow graph.

The parse table can be filled in an easy manner unlike the SLR parsing. There is no need to find the FIRST and FOLLOW sets.

Item set no

a

d

$

S

C

0

S3

S4

 

1

2

1

 

 

Accept

 

 

2

S6

S7

 

 

5

3

S3

S4

 

 

8

4

R3

R3

 

 

 

5

8

 

R1

 

 

6

S6

S7

 

 

9

7

 

 

R3

 

 

8

R2

R2

 

 

 

9

 

 

R2

 

 

I0 on S gives I1

S is a non-terminal so write only state number in (0 ,S) field.

I0 on C gives I2

C is a non-terminal so write only state number in (0 ,C) field.

I0 on a gives I3

a is a terminal so write  state number along with shift in (0 ,a) field.

I0 on d gives I4

d is a terminal so write  state number along with shift in (0 ,d) field.

I2 on C gives I5

C is a non-terminal so write only state number in (2 ,C) field.

I2 on a gives I6

a is a terminal so write state number along with shift in (2 ,a) field.

I2 on d gives I7

d is a terminal so write  state number along with the shift in (2 ,d) field.

I0 on S gives I1

S is a non-terminal so write only state number in (0 ,S) field.

I3 on C gives I8

C is a non-terminal so write only state number in (3 ,C) field.

I3 on a gives I3

a is a terminal so write  state number along with shift in (3 ,a) field.

I3 on d gives I4

d is a terminal so write  state number along with shift in (3 ,d) field.

I6 on C gives I9

C is a non-terminal so write only state number in (6 ,C) field.

I6 on a gives I6

a is a terminal so write  state number along with shift in (6 ,a) field.

I6 on d gives I7

d is a terminal so write state number along with shift in (6 ,d) field.

 S→CC is present in I5; look ahead is $ so in place (5,$) mark R1. As it is the 1st production.

C→aC is present in I8,I9; look ahead symbols are (a/d) and $ respectively place (8,a);(8,d) mark R2. As it is 2nd production.

C→d is present in I4, I7 are (a/d) and $ respectively place (4,a) (4,d) , (7,$). R3. As it is 3rd production.

 LALR:

It is the same parsing technique as like CLR but with a change of combining the item sets which are having the first term common without concentrating the lookahead symbol.

Example:

S→CC

C→aC

C→d

The process is as like

We found I3 and I6 found same but with different look-ahead symbols, so we have to club those into I36.

We found I4 and I7 found same but with different look-ahead symbols, so we have to club those into I47

 

 

We found I8 and I9 found same but with different look-ahead symbols, so we have to club those into I89

 

 

Item set no

a

d

$

S

C

0

S3

S4

 

1

2

1

 

 

Accept

 

 

2

S6

S7

 

 

5

36

S36

S47

 

 

89

47

R3

R3

 

 

 

5

8

 

R1

 

 

89

R2

R2

R2

 

 

The process is same as CLR to fill the parse table.

Conclusion:

An SLR parser generator creates an LR(0) state machine and computes the look-ahead from the grammar (This is a simplified approach and may report conflicts that do not really exist in the LR(0) state machine. But Canonical LR parser generator computes an LR (1) state machine and the look-heads are already part of the LR (1) state machine. These parser tables can be very large. An LALR parser generator creates an LR (0) state machine and computes the look-ahead from the LR (0) state machine (via the terminal transitions). This is a correct approach, but occasionally reports conflicts that would not exist in an LR(1) state machine.

 

 

 

 

 

 

 

 

 

 

Contributor's Info

Created: Edited:
0Comment