LR Parser:

LR parsing is a bottom up syntax analysis technique that can be applied to a large

class of context free grammars. L is for left –to –right scanning of the input and R
for constructing rightmost derivation in reverse.

General Framework:

Let x1x2 x3… … … xk be the string to be parsed by LR parsing method.

A configuration of an LR parser is a pair whose first component is the stack and whose second
component is the unexpended part of the input string:

s0Y1s1Y2si+1… … Yjsi+k xp… … xk

A B
part which is already part of the input string.
considered for parsing.

STACK

Shift:
s0……… |Yjsi+k xpsi+k*|xp+1… … xk
Reduce:
[s0………..si+gA] xpfrom
State … …thexktable
Reduce A  α, | α | = N
Pop 2*| N | elements including states
Push A
Put a state s
[s0………..si+gAs] xp… … xk

Example:
Consider the following grammar

1. S’  S
2. S  aABe
3. A  Abc
4. A  b
5. B  d

Table for parsing action and goto function for the given grammar is:-

STATE action goto

a b c d e $ S A B
I0 s2 1
I1 acc
I2 s4 3
I3 s6 s7 5
I4 r4 r4
I5 s8
I6 s9
I7 r5
I8 r2
I9
I r3 r3

Where
1. rj means reduce by production numbered j,
2. acc means accept
3. si means shift and stack state i.
4. blank means error.

STATE input action

0 abbcbcde$ shift
0a2 bbcbcde$ shift
0a2b4 bcbcde$ Ab
0a2A3 bcbcde$ shift
0a2A3b6 cbcde$ shift
0a2A3b6c9 bcde$ A  Abc
02A3 bcde$ shift
02A3b6 cde$ shift
0a2A3b6c9 de$ A  Abc
0a2A3 de$ shift
0a2A3d7 e$ Bd
0a2A3B5 e$ shift
0a2A3B5e8 $ S  aABe
0S1 $ accepted

Moves of LR parser

Forming the Parsing able:

1. Item:
Item of a grammar G is a production of G with a dot at some position of the right side.
The production A  XYZ has the following four items

A  .XYZ
A  X.YZ
Z  XY.Z
A  XYZ.

2. Item closure:
If A  X.YZ belongs to Is
Yβ
Then add Y  .β in Is

Item closure for the above example

I0 = {[S’  .S], [S  .aABe]}

I1 = {S’  S.}
I2 = {S  a.ABe, A  .Abc, A  .b}
I3 = {S  aA.Be, A  A.bc, B  .d}
I4 = {A  b.}
I5 = {S  aAB.e}
I6 = {A  Ab.c}
I7 = {B  d.}
I8 = {S  aABe.}
I9 = {A  Abc.}
Lectrure 1: Deepak Kumar Behera 03CS3018 dt: 05.09.05
Lectrure 2: Joy Deep Nath 03CS3021 dt:06.09.05

Constructing the GOTO graph from the LR(0) Items ABOVE derived.
1. Enlist all the collection of Items: C (I0, I1,…..)
2. Put all the transitions in the between the Items in he GOTO graph.
Rules for putting the label on the transition
If there is a transition from,
A->α . Xβ to A-> αX . β
 then, the transition in the GOTO Graph is labeled X
If there is a transition
A-> α . Bβ to B-> .γ
then, the transition is labeled ε, and since we take ε-closure of all Items, these productions lie in
the same item as that of A->α . Bβ to A-> αB . β.
So, the GOTO Graph of the given grammar is produced follows.

S’-> .S a
S->.aABe S-> a.Abe
A->.Abc
A->.b b
I0
I2
A -> b.
$
I4
A

S’ -> S.
S->aA.Be S->aABe.
e
A->A.bc
I1 B->.d I8
B
b I3
S->aAB.e

A->Ab.c d I5

B->d.
I6
I7

A->Abc.

I9

The GOTO Graph for the given grammar.

…………………………………………………………………………………….

From the GOTO Graph we now start filling the Parsing table for the SLR (simple LR) parser, Which
contains State i as the row index and action & goto as the vertical column index.
The Rules for filling the action entries in the table are:
1.If [ A-> α .a β ] is in Ii and goto ( Ii , a ) = Ij, then set action [i ,a] to “shift j “.Here a must be a
terminal.
2. If [A-> α .] is in Ii, then set action[i , a ] to “reduce A -> α “ for all a in FOLLOW (A); here A
may not be in S’.
3. If [ S’-> S.] is in Ii , then set action [I, $] to accept.

If any conflicting actions are generated by the given rules, then we say the grammar is not in SLR or
LR (0) and we fail to produce a parser.

We then fill the goto entries.

The goto transitions for the state i are constructed for all the non-terminals A using the Rule:
If goto( Ii, A ) = Ij , then goto [i , A ] = j .

…. Note : goto (Ii, A) is an entry in graph, whereas goto[i, A] is the corresponding entry in parsing
table .

Also the initial state of the parser is one constructed from the set of items containing [S’-> .S]

So, the Parsing table for the grammar comes out to be.

Using this we go ahead with the parsing action.

A grammar having a SLR parsing table is said to be a SLR grammar, and it has a lookahead of 1.

We have a noteworthy point in the grammar we just now used. We have the starting production as
S’-> S and then S had its own set of productions. Intuitively, we see that, there arises no need for the
extra production rule S’->S and this rule might be treated as a dummy rule. We could always do away
with S’ and have S as the start state. However, closer inspection brings to light on the fact that, while
staring the parsing, we may not have any problem, but on making reduction to start state (remember we
are parsing bottom up!), we might just end up having reduce conflicts. So, a need to have a ‘one-level’
higher hierarchy is necessitated and is provided by the rule S’-> S, whenever the start state S, has
multiple productions.

We now look into the problems underlying the SLR grammar, and move onto greener pastures where
we could possibly cope up with these problems.
Lectrure 2: Joy Deep Nath 03CS3021 dt:06.09.05
Lectrure 3: Bhaben Deori 03CS3020 dt:06.09.05

• Problems with SLR parser:

The SLR parser discussed in the earlier class has certain flaws.
1. A state may include a final item (one in which the position marker is at the end) and a non-
final item. This is called a shift-reduce conflict
2. A state may include two different final items. This is called a reduce-reduce conflict
• Can we have reduce-reduce conflicts in unambiguous grammars?
• Can we have a shift-shift conflict ?
 However SLR reduces only when the next token is in Follow of the left-hand side of the
production. Such choices may help to resolve reduce-reduce conflicts.However, still similar
conflicts exist:
->Shift-reduce conflicts include the case in which
Follow of the final lhs of the final item overlaps with first of the remainder
-> Reduce-reduce conflicts include the case Follow of both left-hand-sides overlap.

Let us consider the grammar.

1. S->E$
2. E->L=R
3. E->R
4. L->*R
5. L->id
6. R->L

Consider the two items—

Io={S->.E$,
E->.L=R,
E->.R,
L->.*R,
L->.id,
R->.L}
I1= {E->L. =R,
R->L.}

Follow(R) = {$, =}

So in the Parsing table we have the following conflict when the follow ‘=’ appears.

|.…..……………………………………
| …. ….. ‘=’ ….. ……
I1 …. ….. s2/r6 ….. ……. -> shift reduce conflict

In such a case we break up the item into separate parts. Here the two items will be:
{E->L. =R, $} and {R->L., =}
In general terms, we have-
A1->alpha1 A1->alpha1, Follow (A1) Product of
A2->alpha2  A2->alpha2, Follow (A2)  Follow (Ai)
A3->alpha3 A3->alpha3, Follow (A3) elements.
Suppose there are ‘k’ items in the SLR.
Each item has ‘p’ rules.
Each follow has N elements.
Then the total number of items after separation is
K*POW (N, P). Even if we have one step look ahead the
Complexity will be exponential!!!!!!