LALR(1) Items Construction:
Consider the following LR(1)
items for the augmented grammar
S’ →
S S →
CC C → cC | d
I0
S’ → .S, $
S’ → .CC, $
C’ → .cC, c/d
C’ → .d, c/d
I1:
S’ → S., $
I2:
S → C.C, $
C → .Cc, $
C’ → .d, $
I3:
C → c.C, c/d
C → .cC, c/d
C → d., c/d
|
I4:
C → d., c/d
I5:
S → CC., $
I6:
C →c.C, $
C → .cC, $
C → .d, $
I7:
C → d., $
I8:
C → cC., c/d
I9:
C → cC., $
|
As per the algorithm, in the
given LR(1) items we have the following set of items with the same core
- I3 and I6
- I4 and I7
- I8 and I9
Now, after merging the above mentioned
sets we get,
I36:
C → c.C, c/d/$
C → .cC, c/d/$
C → d., c/d/$
I47:
C → d., c/d/$
I89:
C → cC., c/d/$
While merging
- Keep core as it is and
- Merge the second components
Now the LALR(1) items are
I0
S’ → .S, $
S’ → .CC, $
C’ → .cC, c/d
C’ → .d, c/d
I1:
S’ → S., $
I2:
S → C.C, $
C → .cC, $
C’ → .d, $
|
I36:
C → c.C, c/d/$
C → .cC, c/d/$
C → d., c/d/$
I47:
C → d., c/d/$
I5:
S → CC., $
I89:
C → cC., c/d/$
|
DFA from LALR(1) Items:
The goto function of the LALR(1)
collection of set of items defines a DFA that recognizes the viable prefixes of
the grammar. Each set of item becomes a state in the DFA. The DFA for the above
Example from its items is as shown in the image
Home
|
