SLR Parsers

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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.