SLR(1) Input Acceptance

In this class, We discuss SLR(1) Input Acceptance.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of SLR(1) table construction. Click Here.

The below table shows the SLR(1) parsing table for the expression grammar.

We need to parse the input string and check for acceptance using this parse table.

We consider a stack to parse the given input string.

The below table shows the step-by-step parsing of the input string id * id + id.

We are giving numbers to the productions.

1) E – E+T

2) E – T

3) T – T * F

4) T – F

5) F- (E)

6) F – id

Initially, the symbol ‘0’ was pushed onto the stack.

The stack symbol 0 shows we are starting from the I0 state.

We need to understand the shift and reduce steps.

The input is placed in a buffer, and at the end of the input, we add a dollar symbol.

The first line in the table says to check the parse table block [0, id].

We take the symbol 0 from the stack and the input point to id.

The block [0, id] is showing shift action s5.

Shift action:

So, we shift the input symbol id to symbols, and ‘5’ is pushed onto the stack.

The symbol five on top of the stack shows we moved to state I5.

The second line in the table shows to check the block [5, *].

The block [5, *] shows reduced action r6.

The value 6 in r6 is the number of the production.

The 6th production is F – id.

We need to reduce the id to the non-terminal F.

Reduce Action:

The right side of the production F – id has one symbol.

So we pop one symbol from the stack.

After popping five from the stack, the stack remains with the symbol zero.

Now we check the block [0, F] because we reduce id to F.

the block [0, F] had a value of 3. We pushed the value three onto the stack.

The value 3 shows the I3 state.

We repeat the above shift and reduce actions.

Important:

The seventh line of the table shows reduced action on the production T – T * F

The right side of the production has three symbols, T * F, so pop three elements from the stack.

Similarly, the reader can do the remaining steps for better practice.

If the input remains with the dollar symbol and the stack contains starting non-terminal symbol, we accept the input.