Constructing SLR(1) Parsing Table

CONSTRUCTING SLR(1) PARSING TABLE

To perform SLR parsing, take grammar as input and do the following:

1.   Find LR(0) items.

2.  Completing the closure.

3.  Compute goto(I,X), where, I is set of items and X is grammar symbol.

LR(0) items:

An LR(0) item of a grammar G is a production of G with a dot at some position of the right side. For example, production A → XYZ yields the four items :

A→.XYZ

A → X . YZ

A → XY . Z

A → XYZ .

Closure operation:

If I is a set of items for a grammar G, then closure(I) is the set of items constructed from I by the two rules:

1.   Initially, every item in I is added to closure(I).

2.   If A → α . Bβ is in closure(I) and B → γ is a production, then add the item B → . γ to I , if it

is not already there. We apply this rule until no more new items can be added to closure(I).

Goto operation:

Goto(I, X) is defined to be the closure of the set of all items [A→ αX . β] such that [A→ α . Xβ] is in I.

Steps to construct SLR parsing table for grammar G are:

1.   Augment G and produce G’

2.  Construct the canonical collection of set of items C for G’

3.  Construct the parsing action function action and goto using the following algorithm that requires FOLLOW(A) for each non-terminal of grammar.

Algorithm for construction of SLR parsing table:

Input : An augmented grammar G’

Output : The SLR parsing table functions action and goto for G’

Method :

1. Construct C = {I0, I1, …. In}, the collection of sets of LR(0) items for G’.

2. State i is constructed from Ii.. The parsing functions for state i are determined as follows:

(a) If [A→α∙aβ] is in Ii and goto(Ii,a) = Ij, then set action[i,a] to “shift j”. Here a must be

terminal.

(b) If [A→α∙] is in Ii , then set action[i,a] to “reduce A→α” for all a in FOLLOW(A).

(c)   If [S’→S.] is in Ii, then set action[i,$] to “accept”.

If any conflicting actions are generated by the above rules, we say grammar is not SLR(1). 3. The goto transitions for state i are constructed for all non-term

If goto(Ii,A) = Ij, then goto[i,A] = j.

4.   All entries not defined by rules (2) and (3) are made “error”

5.   The initial state of the parser is the one constructed from the [S’→.S].