SLR 1 Parsing Compiler Design
SLR(1) Parsing
It is a simple LR parsing. Most of the function of this parsing is the same as LR(0) parsing. The parsing table for both the parser vary. The SLR(1) parsing use canonical LR(0) item. The reduce move is placed only in the FOLLOW of those variables whose production is reduced.
The step involves in SLR(1) parsing is given below:
- Write a CFG for the given input string
- Check if the grammar is ambiguous or not.
- Add an augmented grammar.
- Create a canonical LR(0) item.
- Draw DFA
- Construct an SLR(1) parsing table.
Example
E => BB
B => cB / d
Add augment production and insert '.' symbol in the first position for every production in G.
E’ => .E
E => .BB
B => .cB
B => .d
I0 state
Add starting production to the I0 State and Compute the Closure.
I0 = closure (E’ => .E)
Since "." is on the left side of the symbol. It means we have not seen anything on the right-hand side. Therefore, all productions beginning with E will be added in the I0 State because "." is followed by the non-terminal. So, the modified I0 State will be:
I0 = E’ => .E
E => .BB
Here we can see that “.” is on the left of the variable B. Therefore, all productions beginning with B will be added in the I0 State because "•" is followed by the non-terminal. So, the modified I0 State becomes:
E’ => .E
E => .BB
B => .cB
B => .d
I1 = Here we have applied Goto on (I0 E) = closure (E’ => E.)
Here, the "." is on the right side of the symbol, so production is reduced so close the state.
I1 becomes E’ => E.
I2 = we have applied Goto on (I0 B) = Closure (E => B.B)
We apply closure and will get all the A production with "." in the beginning. So I2 becomes:
E => B.B
B => .cB
B => .d
Goto (I2 c) = Closure (B => c.B) (Same as I3)
Goto on (I2 d) = Closure (B => .d) (Same as I4)
I3 = Goto on (I0 c) = Closure (B => c.B)
Add productions starting with B in I3.
B => c.B
B => .cB
B => .d
Go to on (I3 c) = Closure (B => c. B) (Same as I3)
Go to on (I3 d) = Closure (B => d.) (Same as I4)
I4 = Go to on (I0 d) = Closure (B => d.) = B => d.
I5 = Go to on (I2 B) = Closure (E => BB.)
I6 = Go to on (I3 B) = Closure (B =>cB.)
Productions are numbered as follows:
E =>BB (1)
B => cB (2)
B => d (3)
Drawing DFA
SLR(1) Table
| States | Action | Go to |
| c d $ | E B | |
| I0 | S3 S4 | 1 2 |
| I1 | Accept | 5 |
| I2 | S3 S4 | 6 |
| I3 | S3 S4 |
| I4 | r3 r3 r3 | |
| I5 | r1 | |
| I6 | r2 r2 r2 |
Explanations:
Follow of B = First of B = c and d and Follow of E = $
- I1 state have the final item which drives E => E and follow(E) = ($), so action (I1 $) = Accept
- I4 state have the final item which drives B => d and follow(B) = c, d and follow(E) = $ , So action c, d, and $ will be r3
- I5 state have the final item which drives E => BB and follow(E) = $, So action $ in I5 will be r1
- I6 state have the final item which drives B => cB and follow(B) = c, d and follow(E) =$, So action c, d, and $ in I6 will be r2.
NOTE:
When a state moves to some other state on terminals, it will correspond to a shift move in the action part.
When a state moves to another state on a variable, it will correspond to the goto move in the go-to part.
When a state has a final item with no transition to the next state, the production is known as reduce production.