Constructing SLR(1) Parsing Table Notes | EduRev

Compiler Design

Computer Science Engineering (CSE) : Constructing SLR(1) Parsing Table Notes | EduRev

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)


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 → 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!

Related Searches

Semester Notes






Objective type Questions


Extra Questions


mock tests for examination


Previous Year Questions with Solutions


Sample Paper


past year papers


shortcuts and tricks


practice quizzes




study material




Constructing SLR(1) Parsing Table Notes | EduRev


video lectures


Constructing SLR(1) Parsing Table Notes | EduRev




Viva Questions


Constructing SLR(1) Parsing Table Notes | EduRev


Important questions