LR(0) Items Construction
In this class, We discuss LR(0) Items Construction.
For Complete YouTube Video: Click Here
The reader should have prior knowledge of bottom-up parsing. Click Here.
In our shift-reduce parsing class, we had confusion about when to shift and when to reduce?
The Lr(0) items will help identify the shift and reduce conditions.
Follow the procedure to construct the LR(0) items construction.
Understanding the concept behind the construction of items is discussed in the next class.
Augmented Grammar:
First step: Convert the given grammar to augmented grammar.
The below example shows the conversion of given grammar to augmented grammar.
Given Grammar:
E – E + T
E – T
T – T* F
T – F
F – id
F – (E)
Augmented Grammar:
E’ – E
E – E + T
E – T
T – T * F
T – F
F – id
F – (E)
We add extra production E’ points to the start symbol E in the augmented grammar.
Why the extra production? Given the explanation below.
Finding Closure:
We use state diagrams similar to finite automata.
We give the first state the name I0.
The first production, E’ – E, is added to the state I0.
The below diagram shows the state I0 with the production E’ – .E
The dot symbol shows the position at which we are in the execution of the grammar.
We start from the production E, so we added a dot before E.
If the dot is present before the non-terminal, add the closure(non-terminal).
Closure: Closure(E) means adding the productions related to E.
E – .E + T
E – .T
The above two productions are added to the state I0.
The symbol dot is present before the non-terminal T. So, we add the productions related to T.
T – .T * F
T – .F
Similarly, the symbol dot is present before the non-terminal F. We add the productions related to F.
F – .id
F – .(E)
The below diagram shows the final productions in-state I0.
GOTO:
The goto says about the transitions of the state diagram.
Move one step to the right.
E’ – E.
E – E.+T
We moved the dot symbol one step right in the above two productions.
The movement states that after completion of the production, E.
We show the transition moving on E in state I1.
Important: We added E’ – E production to show the completion of the first not-terminal.
The first non-terminal is E. After completing E means. We identified the syntax correctly.
The compiler will add a dollar at the end of the input. We explained about dollar symbol in the last class.
After completion of the production E, if we see the input symbol dollar, that shows the input string’s acceptance.
Similarly, we move one step on T, F, (, and id. We get the states I2, I3, I4, and I5, respectively.
The diagram below shows the complete state diagram for the construction of LR(0) items.
Understanding I4 is essential.
Moving one step on ‘(‘means after seeing the input symbol ‘(. ‘
The dot is present before non-terminal E.
So add E productions.
The dot symbol is present before T., so add T productions.
Similarly, add F productions.
Now we have identified transitions on the I0 state.
We need to identify transitions in all other states until all the productions are completed.
If the dot symbol is present at the end, we say the production has been completed.
In the state I1, we see the dot symbol present at the end of the production E’ – E.
On the state I0, if we see the dollar symbol, we move to acceptance because production E has been completed.
On the state I1, We move using the ‘+’ symbol. We move to state I6.
In-state I6, the dot is present before the non-terminal T., so add closure(T).
Similarly, construct the remaining states I7, I8.
From state I6, we move to state I9 using the symbol T.
From state I6, We move to state I3 using the symbol F.
Important: In our transition, we move to the constructed state if we see the state already constructed.
We need to construct all the remaining states until there are no possible states.