Bottomup parsing:
In this methodology, it follows the process which is exactly controversy to the topdown parsing. It starts with the input symbol first and determines the start symbol.
Bottomup parsing:
SLR:
It is one type of parsing technique in bottomup parsing. It follows two functions to find the parse tree.
Goto:
The goto functions act as the onestep movement function. We use (.) operator in SLR. Goto function pushes the dot after the specified symbol.
Example:
S^{1}→.S is the production.
If we specify goto (S^{1},S) the output will be S^{1}àS.
Closure:
For suppose if there are productions like
Closure (I_{0},S) gives the production of nonterminal after the dot operator.
S^{1}→.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 (S^{1}→.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 nonterminals 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



I_{0 }on S gives I_{1}
S is a nonterminal so write only state number in (0 ,S) field.
I_{0 }on C gives I_{2}
C is a nonterminal so write only state number in (0 ,C) field.
I_{0 }on a gives I_{3}
a is a terminal so write only state number along with shift(s) in (0 ,a) field.
I_{0 }on d gives I_{4}
d is a terminal so write state number along with shift in (0 ,d) field.
I_{2 }on C gives I_{5}
C is a nonterminal so write only state number in (2 ,C) field.
I_{2 }on a gives I_{3}
a is a terminal so write state number along with the shift in (2 ,a) field.
I_{2 }on d gives I_{4}
d is a terminal so write state number along with the shift in (2 ,d) field.
I_{3 }on C gives I_{6}
C is a nonterminal so write only state number in (3 ,C) field.
I_{3 }on a gives I_{3}
a is a terminal so write state number along with the shift in (3 ,a) field.
I_{3 }on d gives I_{4}
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 3^{rd} production in the problem statement).
I5→ S→CC
FOLLOW(S)→{$}
In place of (5,$) mark R1 as it is 1^{st} production.
I6→C→aC
FOLLOW(C)→{a,d,$}
In place of (6,a), (6,d), (6,$) mark R2 as it is in 2^{nd} 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.
S^{1}→.S
S→.CC
C→.aC
C→.d
Look ahead symbol of initial production will be $.
S^{1}→.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



I_{0 }on S gives I_{1}
S is a nonterminal so write only state number in (0 ,S) field.
I_{0 }on C gives I_{2}
C is a nonterminal so write only state number in (0 ,C) field.
I_{0 }on a gives I_{3}
a is a terminal so write state number along with shift in (0 ,a) field.
I_{0 }on d gives I_{4}
d is a terminal so write state number along with shift in (0 ,d) field.
I_{2 }on C gives I_{5}
C is a nonterminal so write only state number in (2 ,C) field.
I_{2 }on a gives I_{6}
a is a terminal so write state number along with shift in (2 ,a) field.
I_{2 }on d gives I_{7}
d is a terminal so write state number along with the shift in (2 ,d) field.
I_{0 }on S gives I_{1}
S is a nonterminal so write only state number in (0 ,S) field.
I_{3 }on C gives I_{8}
C is a nonterminal so write only state number in (3 ,C) field.
I_{3 }on a gives I_{3}
a is a terminal so write state number along with shift in (3 ,a) field.
I_{3 }on d gives I_{4}
d is a terminal so write state number along with shift in (3 ,d) field.
I_{6 }on C gives I_{9}
C is a nonterminal so write only state number in (6 ,C) field.
I_{6 }on a gives I_{6}
a is a terminal so write state number along with shift in (6 ,a) field.
I_{6 }on d gives I_{7}
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 1^{st} 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 2^{nd} production.
C→d is present in I4, I7 are (a/d) and $ respectively place (4,a) (4,d) , (7,$). R3. As it is 3^{rd} 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 I_{3} and I_{6} found same but with different lookahead symbols, so we have to club those into I_{36}.
We found I4 and I7 found same but with different lookahead symbols, so we have to club those into I47
We found I_{8} and I_{9} found same but with different lookahead symbols, so we have to club those into I_{89}
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 lookahead 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 lookheads 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 lookahead 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.