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.
0 comments:
Post a Comment