The document Constructing SLR(1) Parsing Table Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Compiler Design.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**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].

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

16 videos|44 docs|29 tests