LR(1) Items Construction

In this class, We discuss LR(1) Items Construction.

For Complete YouTube Video: Click Here

The reader should have prior knowledge of LR(0) items construction. Click Here.

Example:

S – CC

C – cC | d

LR(1) = LR(0) + Lookahead symbol

Augmented Grammar:

First, we need to write the augmented grammar for the given grammar.

Why do we need to write augmented grammar? We Explained in LR(0) items construction class.

S’ – S

S – CC

C – cC | d

We start at state I0.

In the state I0, we add the production S’ – .S, $

The dollar symbol shows the lookahead after completion of production S.

We follow two steps to generate LR(1) items.

1) We write the CLOSURE

2) We define GOTO.

CLOSURE:

S’ – .s , $

The dot is present before the non-terminal S. So add the productions of S.

S’ – .S, $

S-.CC , $

After writing production S. Why we get the lookahead symbol dollar?

First condition: In the production S’ – .S, $ after the non-terminal S we do not have any symbols, so add the same lookahead symbols.

Second Condition: Explained with the continuation example

In the production S –.CC, $ the dot is present before C. So add the productions of C.

S’ – .S, $

S –.CC, $

C – .cC, c|d

C – .d, c|d

we got the lookahead symbols c|d because in the production S –.CC after the symbol C, we have non-terminal C.

We add First(c) as lookahead symbols for the production C.

The below diagram shows the productions present in state I0.

GOTO:

The GOTO is the same as written in LR(0).

Here in LR(1), we have lookahead symbols. So we transfer the same lookahead symbols in GOTO.

On the I0 state with GOTO on S, we move to the I1 state.

On I1 state, we have production S’ – S., $

The production S’ – S. completed, so the state I1 stopped extending.

On the state I1, if the input symbol dollar encountered, we move to the acceptance state.

On I0 state with GOTO on C, we move to state I2.

On the state I2, we have production S – C.C, $

The dot is present before C., so we add productions of C.

S – C.C, $

C – .cC , $

C – .d, $

Why the dollar is lookahead for product C?

In the production S – C.C , $ We do not have any symbols after the second C., so add the same lookahead symbols present for S – C.C, $.

Similarly, we need to update the remaining states.

The below diagram shows the complete state diagram.

Important: The number of states in LR(1) >= LR(0). why?

The above diagram checks the I3 and I6 states the productions are the same, and the lookahead symbols are changing.

In LR(0), we consider I3 and I6 one state because we do not have lookahead symbols.