LR(0) Table Construction

In this class, We discuss LR(0) Table Construction.

For Complete YouTube Video: Click Here

The readers should have a prior understanding of LR(0) items construction. Click Here.

We construct Lr(0) parsing table for the example chosen in the last class.

We use the parsing table to parse the given input string for acceptance.

The below diagram shows the LR(0) item construction and parsing table.

We need to give some sequence numbers to the productions.

1) E – E + T

2) E – T

3) T – T * F

4) T – F

5) F – (E)

6) F – id

The parsing table is divided into two parts.

1) GOTO

2) Action

The GOTO says to which state we need to move.

The action says to take a shift or reduce action.

The GOTO will consider the non-terminals.

The action will consider terminal symbols.

The parsing table considers a row for each state in the LR(0) items.

We give the line numbers from zero to eleven the same in-state numbers in a state diagram.

On state I0, with non-terminal E, we move to state I1. It is shown in the table GOTO part.

Similarly, on non-terminal E and F, we move to states I2 and I3, respectively.

On the I0 state, if we see the input symbol ‘(‘we do shift action and move to the I4 state.

Why shift action?

The I0 state dot is present at the start of the production F – .(E). So we take shift action.

If the dot is present in the middle of the production, we do shift action.

The dot symbol in the middle shows the incompletion of the production.

When reducing action?

If the dot is present at the end of the production, we do reduce action.

The dot symbol at the end shows the completion of the production.

These Shift-Reduce conditions help take a shift and reduce actions in shift-reduce parsing.

The symbol s4 in the table says to move the input symbol onto the stack and move to state four.

Similarly, on the id symbol, we take the S5 action. I.e. shift the input symbol and move to state five.

We need to construct the table for all the states in the LR(0) state diagram.

A total of twelve states are present in the table.

Important: On the state I1, with the dollar symbol, we do accept the input string.

E’ – E. in the production dot is present at the end of the production. We need to take reduced action.

But this is a special case because The user added the E’ production.

After completion of the production, E means the input string will have a dollar symbol.

On the state I1, with the symbol ‘+’, we move to state I6. We do shift action.

Whatever knowledge we learned is shown in the terminology used in the textbook.

1) A – α.aβ if a is a terminal symbol and by taking symbol ‘a’ we move to state Ii to Ij Set [Ii, a] to shift j.

2) A – α. The dot is present at the end of production. So reduce A – α to all the terminal symbols.

3) S’ – S. is seen in the state Ii then set [Ii, $] to accept.

On the state I2. we have E – T., i.e. the production completed.

We need to take reduced action on all the terminal symbols.

We have written r2 for all the terminal symbols in the action part.

Why is r2 written?

We assigned number 2 to the production E – T.

r2 means reduce to the second production.

On the state I2. with the start symbol, we move to the I7 state. So shift action is considered.

Important: We have reduced and shifted actions on [I2, *].

The above statement is a conflict; we should not have these conflicts.

We have confusion during parsing these conflicts as to which action to consider.

Remember this point we discuss conflict when discussing input string evaluation in our next classes.

Similarly, we write the actions for all the remaining states.

The above table shows the complete LR(0) parsing table.