CLR Parsers
CLR Parsers table entries are filled by using an algorithm
that uses LR(1) items constructed for the given grammar
For constructing the LR(1) items for a given grammar the
method is similar to LR(0) item construction with only few changes in the
closure and goto functions after constructing the augmented grammar
Closure:
setOfItems CLOURE(I) {
repeat
for(each
item[A → α.Bβ, a] in I)
for(each
production B → γ in G’)
for(each
terminal b in FIRST(βa))
add[B
→ .γ, b] to set I;
until
no more items are added to I;
}
Example:
Consider the augmented grammar S’
→ S S → CC
C → cC | d. Now the closure of the item [S’ → .S, $] includes
S’ → .S, $
S → .CC, $
C → .Cc, c/d
C → .d, c/d
Explanation:
\[To\text{
}proceed,\text{ }compare\text{ }your\text{ }item\text{ }with\text{ }\left[
A\text{ }\to \text{ }\alpha .B\beta ,\text{ }a \right].\text{ }Initially\text{
}A\text{ }=\text{ }S,\text{ }a\text{ }=\text{ }\varepsilon ,\text{ }B\text{
}=\text{ }S,\text{ }\beta \text{ }=\text{ }\varepsilon \text{ }and\text{
}a\text{ }=\text{ }\$.~\]
\[Now\text{ }compute\text{ }FIRST\left( \beta a \right)\text{ }=\text{ }FIRST\left( \text{ }\$\text{}\right)\text{}=\left\{\text{}\$\text{}\right\}\]
\[Now\text{ }compute\text{ }FIRST\left( \beta a \right)\text{ }=\text{ }FIRST\left( \text{ }\$\text{}\right)\text{}=\left\{\text{}\$\text{}\right\}\]
\[Now\text{
}add\text{ }all\text{ }productions\text{ }of\text{ }the\text{ }form\text{
}B\text{ }\to \text{ }.\text{ }Y,\text{
}\$\text{}to\text{}the\text{}set.\text{}So,\text{}S\text{}\to\text{}CC,\text{}\$\text{}is\text{}added\]
\[Now\text{
}comparing\text{ }S\text{ }\to \text{ }.CC,\text{
}\$\text{}with\text{}\left[A\text{}\to\text{}\alpha.B\beta,\text{}a\right].A\text{}=\text{}S,\text{}a\text{}=\text{}\varepsilon,\text{}B\text{}=\text{}C,\text{}\beta\text{}=\text{}C\text{}and\text{}a\text{}=\text{}\$.~\]
\[Now\text{ }compute\text{ }FIRST\left( \beta a \right)\text{ }=\text{ }FIRST\left( C\$\right)\text{}=\text{}\left\{\text{}c,\text{}d\right\}\]
\[Now\text{ }compute\text{ }FIRST\left( \beta a \right)\text{ }=\text{ }FIRST\left( C\$\right)\text{}=\text{}\left\{\text{}c,\text{}d\right\}\]
So
C → .cC, c/d and C → .c, c/d are added. No further productions can be added (as
B matches no variable)
Goto:
SetOfItems GOTO(I, X) {
Initialize
J to be the empty set;
for(each
item [A → α.Xβ, a] in I)
add
item item [A → αX.β, a] to set J;
return
CLOSURE(J);
}
Example:
Let the set of items I contains
S’
→ .S, $ S → .CC, $
C → .Cc, c/d C → .d, c/d
Then goto(I,
S) includes moving over S and taking its closure. This results in only one item
set S’ → S., $
Similarly
goto(I, C) includes moving over C and taking its closure
S → .CC, $ C → .Cc, $
C → .c, $
LR(1) Items Constructions:
The following algorithm is used to generate LR(1) items:
Void items(G’) {
initialize
C to CLOSURE({[S’ → .S,
$]});
repeat
for(each
set of items I in C)
for(each
grammar symbol X)
if(GOTO(I,
X) is not empty and not in C)
add
GOTO(I, X) to C;
until no new sets of items are
added to C;
}
LR(1) Items Construction:
Example 1:
For the augmented grammar S’ →
S S → CC
C → cC | d the sets of LR(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, $
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., $
|
The Goto function for the LR(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
example 1 from it’s items is as shown in the image.
