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 ”

Prerequisite: LR Parser, SLR Parser