Understanding Parsing using Examples
In every example, we introduce a new start symbol (S’), and define a new production from this new start symbol to the original start symbol of the grammar.

Consider the following grammar (putting an explicit end-marker $ at the end of the first production):

(1) S’ → S$

(2) S → Sa

(3) S → b

For this example, the NFA for the stack can be shown as follows:

After doing ε-closure, the resulting DFA is as follows:

The states of DFA are also called “Canonical Collection of Items”. Using the above notation, the ACTION-GOTO table can be shown as follows:

Notice that there are two entries for state 2 on input ‘a’. So, this cannot be LR(0) grammar. So, the next enhancement is to look into the FOLLOW set of S’ (which is {$}) and it is different from the shift symbol, this shift-reduce conflict can be resolved easily by reducing on input if it belongs to the FOLLOW set for

S’. This enhancement to parsing is called SLR(1) parsing. The correspondingtable can be…

Consider the following grammar (putting an explicit end-marker $ at the end of the first production):

(1) S’ → S$

(2) S → Sa

(3) S → b

For this example, the NFA for the stack can be shown as follows:

After doing ε-closure, the resulting DFA is as follows:

The states of DFA are also called “Canonical Collection of Items”. Using the above notation, the ACTION-GOTO table can be shown as follows:

Notice that there are two entries for state 2 on input ‘a’. So, this cannot be LR(0) grammar. So, the next enhancement is to look into the FOLLOW set of S’ (which is {$}) and it is different from the shift symbol, this shift-reduce conflict can be resolved easily by reducing on input if it belongs to the FOLLOW set for

S’. This enhancement to parsing is called SLR(1) parsing. The correspondingtable can be…