CIS 324: Language Design and Implementation
Constructing LR Parsing Tables
1. Constructing LR Parsing Tables
In order a grammar to be LR it is sufficient that a left-to-right shift-reduce parser be able to recognize handles when they appear on top of the stack.
Difference between LL and LR grammars: for a grammar to be LR(k)
we must be able to recognize the occurrence of the right-hand side of
a production, having seen of all what is derived from that right side
with k input symbols of lookahead.
This requirement is far less stringent than that for LL(k) grammars where
we must be able to recognize the use of a production seeing only the
first k symbols of what its right side derives. Thus, LR grammars
can describe more languages than LL grammars !
2. The Sets-of-Items Construction Algorithm
An LR(1) item of a grammar G is a production of G with a dot
at some position of the right side.
Example: The production AXYZ yields the following four items
AXYZ
AXYZ
AXYZ
AXYZ
Example: The production A generates only one item A
If G is a grammar with start symbol S, the the augmented grammar G for G
is the old one plus the production SS, where S is a new start symbol.
2.1 The Closure Operation
If I is a set of items for a grammar G, then closure( I ) is the
set of items constructed form I by the two rules:
1 ) Initially, every item in I is added to closure( I )
2 ) If AB is in closure(I) and B is a production,
then add the item B to closure( I ) if it is not already there.
Example: Consider the grammar
EE
E E + T | T
T T * F | F
F ( E ) | id
If I is the set of one item {[ EE ]}, then closure( I ) contains the items
EE
E E + T
E T
T T * F
T F
F ( E )
F id
Algorithm for Computing Closures
functionclosure( I )
begin
J = I ;
repeat
for each item AB in J and each production
B such that B is not in J do
add B to J
until no more items can be added to J ;
return J
end
2.2 The Goto Operation
The operation goto( I, X ) is defined to be the closure of the set of
all items [AX] such that [AX] is in I, where I is
a set of items and X is a grammar symbol..
Example: Consider the grammar
EE
E E + T | T
T T * F | F
F ( E ) | id
If I is the set of two items { [ EE ], [E E + T] },
then goto( I, + ) contains the items
E E + T
T T * F
T F
F ( E )
F id
Algorithm for Sets-of-Items Construction
// Constructs the canonical collection of sets of LR(1) items
// for an augmented grammar
procedureitems( G )
begin
C = { closure[ SS ] ;
repeat
for each set of items I in C and each grammar symbol X
such that goto( I, X ) is not empty and not in C do
add goto( I, X ) to C
until no more sets of items can be added to C ;
end
Example: Consider the grammar
EE
E E + T | T
T T * F | F
F ( E ) | id
The canonical LR(1) collection for this grammar is
I0:EE I3:T FI5:F idI7:T T * F
E E + TF ( E )
E TI4:F ( E )I6:E E + TF id
T T * FE E + T T T * F
T FE T T FI8:F ( E )
F ( E )T T * F F ( E )E E + T
F idT F F id
F ( E )I9:E E + T
I1:E EF idT T * F
E E + T
I10:T T * F
I2:E TI11:F ( E )
T T * F
Algorithm for Constructing SLR Parsing Tables
1 ) Construct C = { I0, I1, ... In} the collection of sets of LR(1) items for G
2 ) State i is constructed from Ii. The parsing actions for state i are
determined as follows:
a ) If [Aa] is in Ii and goto( Ii, a ) = Ij ,
then set action[ i, a ] to “shiftj”
b ) If [A ] is in Ii , then set action[ i, a ] to “reduceA”
for all a in FOLLOW( A )
c ) If [ SS ] is in Ii , then set action[ i, $ ] to “accept”
3 ) The goto transtitions for state i are constructed for all nonterminals A
using the rule: 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
set of items containing [ SS ]