SLR Parsers
Computing Canonical Collection of LR(0) Item
To compute this collection for a grammar G, we need to
define and compute the following three things for a grammar G:
Augmented Grammar
Closure
Goto
Augmented Grammar
- If G is a grammar with start symbol S, then G’, the augmented grammar for G is G with a new start symbol S’ and production S’ →.S
Example 1:
E →
E + T | T
T
→ T * F | F
F
→ ( E ) | id
It’s
augmented grammar is:
E’
→ E
E
→ E + T | T
T
→ T * F | F
F
→ ( E ) | id
- The use of new production is to indicate to the parser when it should stop parsing and announce acceptance of the input. This would occur when the parser was about to reduce S’ → S
Closure
- If ‘I’ is a set of one item of a grammar G, then the closure(I) is computed by using the following algorithm:
setofItems CLOSURE(I) {
J = I;
repeat
for(each
item A→ α.Bβ in J)
for(each production B → γof G)
if(B → γ is not
in J)
add
B → γ to J;
until no
more items are added to J on one round;
return J;
}
For example, the closure of item E’ → .E in the example 1 includes:
E’ → .E
E → .E + T
E → .T
T → .T * F
T → .F
F → .( E )
F → .id
Goto
- The Goto(I, X) where I is a set of items and X is a grammar symbol, is defined as the closure of the set of all items A → αX.β such that A → α.Xβ is in I
- For example, if I is the set of items {E’ → E., E → E + T}, then Goto(I, +) is,
- E→E+.T T→.T*F T→.F F→.(E) F→.id method involves considering the items with . to the left of + and then move the . to the right of + and take its closure
- Another example: If I is the set of items {E’→E., T→T.*F}, then Goto(I, *) is: T→T*.F F→.(E) F→id method involves considering the items with . to the left of * and then move the . to the right of * and take it’s closure
Home
|
