Generating LR Collection
The first step is to create an augmented grammar. The augmentation process starts by bringing the start symbol on the right-hand side of a production rule. We cannot alter the existing rule so we add a new rule in the productions. Bringing the start symbol on RHS ensures that the parsing reaches the acceptance state. The REDUCE operation on this newly added rule determines the string acceptance.
For example,
IF we have ‘K’ as a start symbol
THEN L → K is added in productions
(where ‘L’ represents any non-preexisting symbol in the collection)
CLOSURE and GOTO Operations
In the process of construction of deterministic finite automaton, there are two requirements. The first is creating “States” and the second is developing “Transitions” in the automaton.
1) CLOSURE
Closure operation helps us to form the “States”. Before taking the closure operation all the rules must be separated. Then number all the rules. This will be helpful later for making the Shift and Reduce entries in the parsing table. Let I0 be the collection of rules obtained after grammar augmentation. This means we also have a newly added rule in collection I0.
Assumption – (consider [L, K] are non-terminals and [m, t, p] are set of zero or more terminals or non-terminals)
DO REPEAT (Till-No-New-Rule-Gets-Added) {
IF (any production of the form “ L → m · K t ” exists) and (we have production K → · p)
THEN {add production K → · p to the Closure set if not preexisting}
}
2) GOTO
GOTO operation helps us to form the “Transitions”. In operation GOTO (I, X), ‘I’ can be elaborated as the state we are looking at and ‘X’ is the symbol pointed by Dot (·). So, GOTO takes in a state with items and a grammar symbol and produces the new or existing state as output.
The GOTO (I, X) represents the state transition from “I” on the input symbol “X”.
For any production rule “ L → m · K t ” in “I”
GOTO (I, X) outputs the closure of a set of all the productions “ L → m K · t ”
Compiler Design SLR(1) Parser Using Python
Prerequisite: LR Parser, SLR Parser