Compiler Design/B.

Tech/S6

MODULE 3

UKFCET 1
Compiler Design/[Link]/S6

3.1 BOTTOM UP PARSING

A bottom-up parse starts with the string of terminals itself and builds from the leaves upward,
working backwards to the start symbol by applying the productions in reverse.

Along the way, a bottom-up parser searches for substrings of the working string that match the
right side of some production.

When it finds such a substring, it reduces it, i.e., substitutes the left side non-terminal for the
matching right side. The goal is to reduce all the way up to the start symbol and report a
successful parse.

3.1.1 SHIFT REDUECE PARSING

Shift reduce parsing attempts to construct a parse tree for an input string beginning at
the leaves (bottom) and working up towards the root (top).

This can be considered as the process of “reducing” a string w to the start symbol of a
grammar.

At each reduction step parser searches for substrings of the working string that match
the right side of some production.

When it finds such a substring, it reduces it, i.e., substitutes the left side non-terminal
for the matching right side. The goal is to reduce all the way up to the start symbol and
report a successful parse.

In Shift-reduce parsing a stack holds grammar symbols and an input buffer holds the
rest of the string to be parsed.

As we shall see, the handle always appears at the top of the stack just before it is
identified as the handle.

We use $ to mark the bottom of the stack and also the right end of the input. Initially,
the stack is empty, and the string w is on the input, as follows:

STACK INPUT

$ w$
During a left-to-right scan of the input string, the parser shifts zero or more input
symbols onto the stack, until it is ready to reduce a string β of grammar symbols on top
of the stack.

It then reduces β to the head of the appropriate production. The parser repeats this
cycle until it has detected an error or until the stack contains the start symbol and the
input is empty as follows:

STACK INPUT

$S $

UKFCET 2
Compiler Design/[Link]/S6

Upon entering this configuration, the parser halts and announces successful completion
of parsing.

There are actually four possible actions a shift-reduce parser can make:

🡪 Shift
🡪 Reduce
🡪 Accept
🡪 Error

1. Shift: The next input symbol is shifted onto the top of the stack.
2. Reduce: The parser knows the right end of the string to be reduced must be at the
top of the stack. It must then locate the left end of the string within the stack and
decide with what nonterminal to replace the string.
3. Accept: Announce successful completion of parsing.
4. Error: Discover a syntax error has occurred and calls an error recovery routine.

EXAMPLE
input
Following figure steps through the actions a shift-reduce parser might take in parsing the
string id *id according to the expression grammar.
1 2

E→ E + T | T
T→ T * F | F

F→ ( E ) | id

Configurations of a shift-reduce parser on input

idl*id2

UKFCET 3
Compiler Design/[Link]/S6

1. OPERATOR PRECEDENCE PARSING

Bottom-up parsers for a large class of context-free grammars can be easily developed
using operator grammars.

In an operator grammar, no production rule can have:

o at the right side (no production).

o two adjacent non-terminals at the right side.

This property enables the implementation of efficient operator-precedence parsers.

EXAMPLE

Precedence Relations
In operator-precedence parsing, we define three precedence relations between certain
pairs of terminals as follows:

The intention of the precedence relations is to find the handle of a right sentential form,

<. with marking the left end,

=· appearing in the interior of the handle, and

.> marking the right end.

In our input string $a1a2...an$, we insert the precedence relation between the pairs of
terminals.

Example: Consider the string id + id * id and the grammar is:

E→ E+E | E-E | E*E | E/E | (E) | -E | id

4
Compiler Design/[Link]/S6

The corresponding precedence relations is

Then the string with the precedence relations inserted is:

$ <. id .> + <. id .> * <. id .> $

<. is inserted between the leftmost $ and id since <. is the entry in row $ and column id.

Handle And Handle Pruning

In our input string $a1a2...an$, we insert the precedence relation between the pairs of
terminals.

Example: Consider the string id + id * id and the grammar is:

Handle is a substring that matches with the right side of the production and if the
substring matches with the right side of the production, it is reduced with the non-
terminal on the left side of the production

EXAMPLE
Consider the

grammar E 🡪 E+E

E 🡪 E*E

E 🡪 (E)

E🡪 id
And the input string is id + id * id
1 2 3

The rightmost derivation is:

E🡪E+E

🡪E+E*E
🡪 E + E * id
3

🡪 E + id * id
2 3

🡪 Id id * id
1+ 2 3

5
 Compiler Design/[Link]/S6

In the above derivation, the underlined substrings are called handles.

HANDLE PRUNING

The process of obtaining rightmost derivation in reverse order is called “handle pruning”.
(i.e.) if w is a sentence or string of the grammar at hand, then w = γ where γ is the n th right
n n

sentinel form of some rightmost derivation.

2. LR PARSING
LR parsing is most efficient method of bottom up parsing which can be used to parse large class
of context free grammar.

The technique is called LR(k) parsing; the “L” is for left to right scanning of input symbol, the “R”
for constructing right most derivation in reverse, and the k for the number of input symbols of
lookahead that are used in making parsing decision.

There are three types of LR parsing,

🡪 SLR (Simple LR)

🡪 CLR (Canonical LR)
🡪 LALR (Lookahead LR)

The schematic form of LR parser is given below.

Requirements of LR parser:
🡪 Input Buffer
🡪 Stack

6
Compiler Design/[Link]/S6

🡪 Parsing Table
🡪 LR Parsing Program

Input Buffer
The parsing program reads characters from an input buffer one at a time.

Stack

Parsing program uses a stack to store string of the form s X s X s X ………X s

0 1 1 2 2 3 m m

where s is on the top.

m

X is a grammar symbol and S is the state

i i

Each state symbol summarizes the information contained in the stack below it
Combination of state symbol on stack top and current input symbol are used to index
the parsing table and determine the shift reduce parsing decision

Parsing Table

Consist of 2 parts
1. parsing action function action
2. goto function goto

Action
This function takes as arguments a state i and a terminal a (or $, the input end marker). The
value of ACTION [i, a] can have one of the four forms:
i. Shift j, where j is a state.
ii. Reduce by a grammar production A---> β.
iii. Accept.
iv. Error.
Goto
This function takes a state and grammar symbol as arguments and produces a state. If GOTO
[Ii ,A] = Ij, the GOTO also maps a state i and nonterminal A to state j.

Parsing Program works as follows

It determines s , the state currently on top of stack and a the current input symbol It
m i

consults parsing action table entry for action[s ,a ] which can have 4 values:
m i

The function goto takes a state and grammar symbol as arguments and produces a
state.

1. Shift s, where s is a state

2. Reduce by a grammar production A→b
3. Accept
4. Error 7
Compiler Design/[Link]/S6

The function goto takes a state and grammar symbol as arguments and produces a
state.

A configuration of LR parser is a pair whose first component is stack contents and

second component is remaining input:

( s X s X . . .X s , a a . . . a $)
0 1 1 2 m m i i+1 n

The next move of the parser is determined by reading ai, the current input symbol and
sm, state on stack top and then consulting parsing action table entry action[sm,ai].

The configuration resulting after each of four types of moves are as follows:
1. If action [sm, ai] = shift s, the parser executes a shift move, entering the

configuration

( s X s X . . .X s , a a ...a
0 1 1 2 m m i i+1 n
$)
Here the parser has shifted both the current input symbol a and the next state s,
i

which is given in action [s , a ], onto the slack; a becomes the current input
m i i+1

symbol.
2.
If action [s , a ] =reduce A 🡪β , then the parser executes a reduce move, entering
m i

the configuration

(s X s X s ...X s A s, a a . . . a $)
0 1 1 2 2 m-r m-r i i+1 n
where s = goto [s , A] and r is the length of β , the right side of the production.
m-r

Here the parser first popped 2r symbols off the stack (r state symbols and r
grammar symbols), exposing state s . The parser then pushed both A, the left side
m-r

of the production, and s, the entry for goto[s , A] , onto the stack. The
m-r current
3. input symbol is not changed in a reduce move.

4. If action [s , a ] = accept, parsing is completed.

m i

If action [s , a ] = error, the parser has discovered an error and calls an error
LR Parsing Algorithm
m i

recovery routine.
INPUT : Input string w, LR-Parsing table with functions ACTION and GOTO for a grammar G

OUTPUT : If w is in L(G), a bottom-up parse for w, otherwise, an error indication.

8
Compiler Design/[Link]/S6

METHOD : Initially, the parser has s on its stack, where s is the initial state, and w$ in the
0 0

input buffer. The parser then executes the following program until an accept or error action is
encountered.

set ip to point to the first symbol of w$

repeat forever begin

Iet s be the state on top of the slack and

a the symbol pointed to by ip;

if action [s, a]= shift s' then begin

push a then s' on lop of the stack;

advance ip to the next input symbol

end
else if action [s,a] = reduce A🡪β then begin

pop 2*|β| symbols off the stack ;

let s' be the state now on top of the stack;

push A then goto [s', A ] on top of the stack;

output the production A🡪β

end
else if action [s,a] = accept then

return

else error();

end

Different types of LR Parsers

All LR parsers use the same parsing algorithm but the difference is only in terms of the
construction of parsing tables. There are three widely used algorithms available for
constructing an LR parsing Tables. Different types of LR parsers are:

SLR(l) - Simple LR

🡪 Works on smallest class of grammar.

🡪 Few number of states, hence very small table.
🡪 Simple and fast construction.

LR( 1) - LR parser

🡪 Also called as Canonical LR parser.

🡪 Works on complete set of LR(1) Grammar. 9
Compiler Design/[Link]/S6

🡪 Generates large table and large number of states.

🡪 Slow construction.

LALR(1) - Look ahead LR parser

🡪 Works on intermediate size of grammar.

🡪 Number of states are same as in SLR(1).

Reasons for attractiveness of LR parser

LR parsers can handle a large class of context-free grammars.
The LR parsing method is a most general non-back tracking shift-reduce parsing
method.
An LR parser can detect the syntax errors as soon as they can occur.

LR grammars can describe more languages than LL grammars.

Drawbacks of LR parsers
It is too much work to construct LR parser by hand. It needs an automated parser
generator.

If the grammar contains ambiguities or other constructs then it is difficult to parse in a

left-to-right scan of the input.

Construction of LR Parsing Table

3 techniques for constructing LR parsing table for a grammar :-

1. SLR
2. CLR
3. LALR

Simple LR (SLR)

Easy to implement

Least powerful

Canonical LR

Most powerful

Most expensive

LookAhead LR(LALR)

Intermediate in power and cost between other 2

10
Compiler Design/[Link]/S6

Limitations Of SLR Parser

For an SLR parser, if we are in a state with the item A -> α ., then we reduce by A -> α iff the next
input symbol ‘a’ belongs to Follow(A).

This is actually a weak rule and can lead to erroneous results and/or shift/reduce conflicts.

EXAMPLE

Consider A -> α
State i: A -> α .

State j: A -> α .

String 1: γ α a

String 2: β α a

11
 Compiler Design/[Link]/S6

1. CONSTRUCTING SLR PARSING TABLES

LR(0) Item
LR parser using SLR parsing table is called an SLR parser.

A grammar for which an SLR parser can be constructed is an SLR grammar.

An LR(0) item (item) of a grammar G is a production of G with a dot at the some
position of the right side.
Ex: for the productions A → aBb

Possible LR(0) Items are:

A → .aBb

A → [Link]

A → aB.b

A → aBb.

A production rule of the form A →ε yields only one item A → .

Intuitively, an item shows how much of a production we have seen till the current point
in the parsing procedure.

A collection of sets of LR(0) items (the canonical LR(0) collection) is the basis for
constructing SLR parsers.

To construct the canonical LR(0) collection for a grammar we define:

🡪 Augmented grammar

🡪 Two functions: CLOSURE and GOTO

Augmented grammar
G’ is the augmented grammar of G with a new production rule S’→S where S’ is the new
starting symbol i.e,

G’= G ∪ {S’ → S} where S is the start state of G.

The start state of G’ = S’.
This is done to signal to the parser when the parsing should stop to announce
acceptance of input.

Kernel and Non-Kernel items

Kernel items include the set of items that do not have the dot at leftmost end. S’

→ .S is an exception and is considered to be a kernel item.

Non-kernel items are the items which have the dot at leftmost end.

12
Compiler Design/[Link]/S6

Sets of items are formed by taking the closure of a set of kernel items.

The Closure Operation

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

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

2. If A → α .Bβ is in closure(I) and B→γ is a production rule of G; then B→.

γ will be in the closure(I).

We will apply this rule until no more new LR(0) items can be added to closure(I).

Computation of Closure
function closure ( I )

begin

J := I;

repeat

for each item A → α .Bβ in J and each production

B→γ of G such that B→.γ is not in J do

add B→.γ to J

until no more items can be added to J

return J

end

13
Compiler Design/[Link]/S6

Goto Operation
If I is a set of LR(0) items and X is a grammar symbol (terminal or non-terminal), then
goto(I,X) is defined as follows:

🡪 If A → α . Xβ in I then every item in closure({A → α . Xβ }) will be in goto(I,X).

🡪 If I is the set of items that are valid for some viable prefix γ, then goto(I,X) is the
set of items that are valid for the viable prefix γX.

EXAMPLE
I ={ E’ → E., E → E.+T}

goto(I,+) = { E → E+.T

T →.T*F

T →.F

F →.(E)

F →.id }

Construction of Canonical LR(0) Collection

To create the SLR parsing tables for a grammar G, we will create the canonical LR(0)
collection of the grammar G’.

ALGORITHM
Procedure items( G’ )

begin

C := { closure({S’→.S}) }
repeat for each set of items I in C and each grammar symbol X

if goto(I,X) is not empty and not in C

add goto(I,X) to C

until no more set of LR(0) items can be added to C.

\end

goto function is a DFA on the sets in C.

14
Compiler Design/[Link]/S6

I: I : goto(I , +) I : goto(I , id) I : goto(I , ( )

0 6 1 5 4 4 7

F → (.E)
E’ → .E E → E+.T F → id.
E → .E+T T → .T*F
E → .E+T
E → .T T → .F
I :goto(I , T) E → .T
T → .T*F 9 6
F → .(E)
E → E+T. T → .T*F
T → .F
F → .id
T → T.*F T → .F
F → .(E)

F → .id I : goto(I , *) F → .(E)

7 2
I : goto(I , F)
T → T*.F 3 6 F → .id
I : goto(I , E) F → .(E) T → F.
1 0
I : goto(I , )
11 8
E’ → E.
F → .id
E → E.+T I : goto(I , ( ) )
4 6 F → (E).
F → (.E)
I : goto( I , E)
8 4
I :goto(I , T) E → .E+T
2 0 F → (E.)
I : goto(I , +)
E → T. E → E.+T E → .T 6 8

T → T.*F T → .T*F E → E+.T

T → .T*F

I :goto(I , T) T → .F T → .F
I : goto(I , F) 2 4
3 0
E → T. F → .(E) F → .(E)
T → F.
T → T.*F F → .id F → .id

I : goto(I , ( )
4 0
I : goto(I , F) I : goto(I , id)
F → (.E) 3 4
5 6
I : goto(I , *)
7 9

T → F. T → T*.F
E → .E+T F → id.
F → .(E)
E → .T
I : goto(I , ( )
4 0 I : goto(I , F)
T → .T*F 10 7 F → .id
F → (.E)
T → .F E → .E+T T → T*F.

E → .T
F → .(E)
T → .T*F I : goto(I , id)
5 7
F → .id
T → .F
F → id.
15
I : goto(I , id) F → .(E)
5 0
F → .id
F → id.
Compiler Design/[Link]/S6

Constructing SLR Parsing Table

INPUT: An augmented grammar G'.
OUTPUT: The SLR parsing table functions action and goto for G' .

METHOD:

1. Construct C ={I , I ,…..I }, the collection of sets of LR(0) items for G'.
0 1 n
2. State i is constructed from I . The parsing actions for state i are determined as follows:
i

16
Compiler Design/[Link]/S6

If any conflicting actions are generated by the above rules, we say the grammar is not
SLR (1). The algorithm fails to produce a parser in this case.
3. The goto transitions for state i are constructed for all nonterminals A using the rule:
if GOTO(I , A)=I then GOTO[I, A]=j .
i 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 set of items containing [S’
🡪 S].

Parsing Tables of Expression Grammar

Blank entries are error entries.

Number the given Grammar

E’ → E
E →E+T --------(1)
E→T --------(2)
T →T*F --------(3)
T →F --------(4)
F →(E) --------(5)
F →id --------(6)

17
Compiler Design/[Link]/S6

I : E’ → E. (1, $) ====> ACCEPT

1

(2, $), (2, )), (2, +) ====> r2

I : E → T.
2
(3, $), (3, +), (3,)), (3, *) ====> r4
I : T → F.
3 (5, *), (5, +), (5, )), (5, $) ====> r6
I : F → id.
5 (9, $), (9, )), (9, +) ====> r1
I : E → E+T. (10, $), (10, +), (10, )), (10, *) ====> r3
9

I : T → T*F. (11, *), (11, +), (11, )), (11, $) ====> r5

10

I : F → (E).
11
Shift/Reduce and Reduce/Reduce conflicts
If a state does not know whether it will make a shift operation or reduction for a
terminal, we say that there is a shift/reduce conflict.

If a state does not know whether it will make a reduction operation using the
production rule i or j for a terminal, we say that there is a reduce/reduce conflict.

If the SLR parsing table of a grammar G has a conflict, we say that that grammar is not
SLR grammar.

Stack Implementation
Check whether the given input is valid or not?

18
Compiler Design/[Link]/S6

EXAMPLE

SLR ( 1 ) GRAMMAR

S→E

E→E+T|T
T→T*F|F

F → id

AUGMENTED GRAMMAR

S’ → S

S→E

E→E+T|T
T→T*F|F

F → id

CANONICAL COLLECTION OF LR(0) ITEMS

I I = Go to (I , F) I = Go to (I , T)
0 3 0 7 5

S’→ S T → F• E → E + T•

S → •E
E → •E + T
I = Go to (I , id) I = Go to (I , F)
E → •T 4 0
3 5

T → •T * F F → id•
T → F•
T → •F

I = Go to (I , +)
F → •id 5 1 I = Go to (I , id)
4 5
E → E +•T
F → id•
T → •T * F
I = Go to (I , E)
1 0
T → •F
S` → E• I = Go to (I , F)
8 6

E → E• + T F → •id T → T * F•

I = Go to (I , T) I = Go to (I , *) I = Go to (I6, id)
2 0 6 2 4
E → T•T T → T * •F
F → id•
T• → * F F → •id

19
Compiler Design/[Link]/S6

DRAW CANONICAL COLLECTION OF LR(0) ITEMS

NUMBER THE PRODUCTIONS

1. S→E
2. E→E+T|T
3. T → T * F | F
4. F → id

SLR(1) TABLE

FOLLOW (S) = {$}

FOLLOW (E)= {+, $}
FOLLOW (T) = {*, +, $}
FOLLOW (F) = {*, +, $}
🡪 I contains the final item which drives S → E• and follow (S) = {$}, so action
1

{I , $} = Accept
1
🡪
I contains the final item which drives E → T• and follow (E) = {+, $}, so action
2
🡪 {I , +} = R2, action {I , $} = R2
2 2

I contains the final item which drives T → F• and follow (T) = {+, *, $}, so action
3

{I , +} = R4, action {I , *} = R4, action {I , $} = R4

3 3 3
20
Compiler Design/[Link]/S6

🡪 I contains the final item which drives F → id• and follow (F) = {+, *, $}, so
4

action {I , +} = R5, action {I , *} = R5, action {I , $} = R5

4 4 4
🡪
I contains the final item which drives E → E + T• and follow (E) = {+, $}, so
7
🡪 I8 contains
action {I , +}the final
= R1, item {I
action which, $} =drives
R1 T → T * F• and follow (T) = {+, *, $}, so
action {I , +} = R3, action {I , *} = R3, action {I , $} = R3.
7 7
8 8 8

EXAMPLE
Every SLR (1) grammar is unambiguous, but there are many unambiguous grammars that are
not SLR(1). Consider the grammar with productions

S🡪L=R
S🡪R L

🡪*R

L🡪 id R

🡪L

AUGMENTED GRAMMAR
S’ 🡪 S

S🡪L=R
S🡪R L

🡪*R

L🡪 id R

🡪L

21
Compiler Design/[Link]/S6

CANONICAL COLLECTION OF LR(0) ITEMS

I I = Go to (I , id) I = Go to (I , R)
0 5 0 9 6

S’ 🡪• S L 🡪 id• S 🡪 L = R•
S 🡪 •L = R

S 🡪 •R
I = Go to (I , =) I = Go to (I , L)
L 🡪 •* R 6 2 8 6

S 🡪 L = •R
L 🡪 •id R R🡪L•
R🡪•L
🡪•L

I = Go to (I , L)
L 🡪 •* R 7 6

L 🡪 •id L 🡪 * R•
I = Go to (I , S)
1 0

S’ 🡪 S •
I = Go to (I , R) I = Go to (I , *)
7 4 4 6

L 🡪 *• R
I = Go to (I , L) L 🡪 * R•
2 0
R🡪•L L
S 🡪 L •= R
I = Go to (I , L) 🡪 •* R L
R 🡪 L• 8 4

R 🡪 L• 🡪 •id

I = Go to (I , R)
3 0
I = Go to (I , *)
4 4 I = Go to (I , id)
S 🡪 R• L 🡪 * •R
5 6

L 🡪 id•
R🡪•L L
I = Go to (I , *)
4 0
🡪 •* R L
L 🡪 * •R
🡪 •id
R🡪•L L

🡪 •* R
I = Go to (I , id)
5 4
L 🡪 •id
NUMBER THE PRODUCTIONS
L 🡪 id•
1. S 🡪 L = R
2. S 🡪 R
3. L 🡪 * R
4. L🡪 id
5. R 🡪 L

22
Compiler Design/[Link]/S6

PARSING TABLE

I = S’ 🡪 S •
1
FOLLOW (S)={$}
I = R 🡪 L•
2
FOLLOW (L)= {=,$}
I = S 🡪 R• FOLLOW (R)= {=,$}
3

I = L 🡪 id•
5
I = L 🡪 * R•
7

I = R 🡪 L• I =
8 9
(2, =), (2, $) =====> r5
S 🡪 L = R• (3, $) =====> r2

(5, =), (5, $) =====> r4

(7, =), (7, $) =====> r3

(8, $), (8, =) =====> r5

(9, $) =====> r1

STATE ACTION GOTO

id * = $ R L S

0 s5 s4 3 2 1

1 ACCEPT

2 s6/ r5 r5

3 r2

4 s5 s4 7 8

5 r4 r4

6 s5 s4 9 8/7

7 r3 r3

8 r5 r5

9 r1

Here there is a shift reduce conflict in (2,=) so grammar is not SLR(1)

23
Compiler Design/[Link]/S6

[Link] CONSTRUCTING CANONICAL LR(CLR)

PARSING TABLES

24
Compiler Design/[Link]/S6

Canonical Collection of Sets of LR(1) Items

The construction of the canonical collection of the sets of LR(1) items are similar to the
construction of the canonical collection of the sets of LR(0) items, except that closure
and goto operations work a little bit different.

Construction of CLR (canonical LR) Parsing Tables

Algorithm: Construction of canonical- LR parsing tables.

INPUT: An augmented grammar G’.

OUTPUT: the canonical-LR parsing table functions ACTION AND GOTO for G’.

METHOD:

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

State i of the parser is constructed from I The parsing action for

2. i.

state
i is determined as follows.

(a If [ A 🡪 α.aβ,b] is in Ii, and GOTO (Ii, a) = Ij, then set ACTION [i, a] To
)
“shift j”. Here a must be a terminal.
If [A 🡪 α., a] is in I A ≠ S’, then set ACTION[ i, a ] to “reduce A 🡪 α.”
(b) i,

If [ S’ 🡪 S., $ ] is in I then set ACTION[ i, $ ] to “accept”.

(c) i,

If any conflicting actions result from the above rules, we say the grammar is
not LR(1). The algorithm falls to produce a parser in this case.
3. The goto transitions for state i are constructed for all non terminals
using the rule: if GOTO( I , A) = I , then GOTO[ i, A ]= j.
A i 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 set of items
containing [S’ 🡪 .S, $ ]. 25
Compiler Design/[Link]/S6

EXAMPLE
Construct CLR parsing table for the flowing grammar

S🡪 CC

C🡪 cC| d

AUGMENTED GRAMMAR
S’🡪 S

S🡪 CC

C🡪 cC

C🡪 d

CANONICAL COLLECTION OF LR(1) ITEMS

I I = GOTO (I , c) I = GOTO (I , C)
0 6 2 8 3
S’ 🡪 •S , $ C 🡪 c•C, $ C 🡪 c C•, c | d
S🡪 •CC, $ C 🡪 •c C ,$ C
C🡪 •cC, c | d 🡪 •d , $ I = GOTO (I , c)
3 3
C🡪 •d, c | d
C 🡪 c• C , c | d
I = GOTO (I , d) C🡪 •cC, c | d
I = GOTO (I , S) 7 2
C🡪 •d, c | d
1 0
C 🡪 d• , $
S’ 🡪 S•, $
I = GOTO (I , d) I = GOTO (I , d)
4 3
I = GOTO (I , C) 4 0
2 0 C🡪 d •, c | d
C 🡪 d• , c | d
S 🡪 C•C, $
C 🡪 •cC, $ C I = GOTO (I , C)
I = GOTO (I , C) 9 6
🡪 •d, $ 5 2
C 🡪 c C• , $
S 🡪 CC•, $

I = GOTO (I , c) I = GOTO (I , c)
6 6
I = GOTO (I , c) 6 2
3 0 C 🡪 c• C ,$
C 🡪 c•C, $
C 🡪 c•C, c | d C🡪 •cC, $
C 🡪 •c C ,$ C
C 🡪 •c C , c | d C C🡪 •d, $
🡪 •d , $
🡪 •d, c | d
I = GOTO (I , d)
7 6
I = GOTO (I , d) I = GOTO (I , d)
4 0
7 2 C🡪 d•, $
C 🡪 d• , c | d C 🡪 d• , $

I = GOTO (I , C)
5 2
S 🡪 CC•, $
26
Compiler Design/[Link]/S6

GOTO GRAPH FOR THE GRAMMAR

NUMBER THE PRODUCTIONS

1. S🡪 CC
2. C🡪 cC
3. C🡪 d

PARSING TABLE

I = S’ 🡪 S• , $
1

I = C 🡪 d• , c | d
4

I = S 🡪 CC•, $
5

I = C 🡪 d• , $
7

I = C 🡪 c C•, c | d
8

I = C 🡪 c C• , $
9

27
Compiler Design/[Link]/S6

[Link] CONSTRUCTING LALR PARSING TABLE

LALR stands for Lookahead LR.

LALR parsers are often used in practice because LALR parsing tables are smaller than
LR(1) parsing tables.
The number of states in SLR and LALR parsing tables for a grammar G are equal. But

LALR parsers recognize more grammars than SLR parsers.

yacc creates a LALR parser for the given grammar.

A state of LALR parser will be again a set of LR(1) items.

Creating LALR Parsing Tables

Canonical LR(1) Parser ➔ LALR Parser

The Core of A Set of LR(1) Items

The core of a set of LR(1) items is the set of its first component

We need to do following update in the parsing table.

28
Compiler Design/[Link]/S6

INPUT: An augmented grammar G’.

OUTPUT: The LALR parsing – table functions ACTION and GOTO for G’

METHOD:

Construct C = { I I I }, the collection of sets of LR(1) items.

1. 0, 1, ......, n

2. For each core presentamong the set of LR(1) find all

sets
items, having that core, and replace these sets by their union.
3. Let C’ = {J J },the collection of sets of LR(1)
........,
0, 1,
m
parsing action for state i are constructed from J in the same manner as
items. The i there
in Algorithm.
is a parsingaction conflict, the
If a parser, and the grammar is said not to be LALR(1)
to produce algorithm fails
more
4. The GOTO table is constructed as follows. if J is the union of one or
sets of LR(1) items, that is, J = I ∪ I ∪ ... ∪ I , then the I I ....., I all
1 2 k 1, 2, k

have the same core. Let K be the union of all sets of items having the same

core as GOTO( I X ). Then GOTO (J, X) = K.

1,

*********
*
29