LR Parsers

• The most powerful shift-reduce parsing (yet efficient) is:

LR(k) parsing

left to right right-most k lookhead

scanning derivation (k is omitted  it is 1)

• LR parsing is attractive because:

– LR parsing is most general non-backtracking shift-reduce parsing, yet it is still efficient.
– The class of grammars that can be parsed using LR methods is a proper superset of the class
of grammars that can be parsed with predictive parsers.
LL(1)-Grammars  LR(1)-Grammars
– An LR-parser can detect a syntactic error as soon as it is possible to do so a left-to-right
scan of the input.
41

LR Parsers
• LR-Parsers
– covers wide range of grammars.
– SLR – simple LR parser
– CLR – Canonical LR parser
– LALR – intermediate LR parser (Look-Ahead LR parser) LLR
– SLR, LR and LALR work same (they used the same algorithm),
only their parsing tables are different.

1
LR Parsing Algorithm

input a1 ... ai ... an $

stack
Sm
Xm
LR Parsing Algorithm output
Sm-1
Xm-1
.
.
Action Table Goto Table
S1 terminals and $ non-terminal
X1 s s
t four different t each item is
S0 a actions a a state number
t t
e e
s s
43

Actions of a LR-Parser
1. shift s -- shifts the next input symbol and the state s onto the stack
( So X1 S1 ... Xm Sm , ai ai+1 ... an $ )  ( So X1 S1 ... Xm Sm ai s, ai+1 ... an $ )

2. reduce A (or rn where n is a production number)

– pop 2|| (=r) items from the stack;
– then push A and s where s=goto[sm-r , A]
( So X1 S1 ... Xm Sm, ai ai+1 ... an $ )  ( So X1 S1 ... Xm-r Sm-r A s, ai ... an $ )

– Output is the reducing production reduce A

3. Accept – Parsing successfully completed

4. Error - Parser detected an error (an empty entry in the action table)
45
Constructing SLR Parsing Tables
• It uses LR(0) item, augmented grammar, CLOSURE function and GOTO
function.
I. LR(0) item of a grammar G is a production of G a dot at the some
position of the right side.
• Ex: A  aBb Possible LR(0) Items: ..
A  aBb
A  a Bb
(four different possibility)
A  aB b
A  aBb
..
• Sets of LR(0) items will be the states of action and goto table of the SLR
parser.
• A collection of sets of LR(0) items (the canonical LR(0) collection) is
the basis for constructing SLR parsers.
II . Augmented Grammar:
G’ is G with a new production rule S’S where S’ is the new starting
symbol. 49

III. 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).
3. Example:
E’  E closure({E’  .E}) =
E  E+T { E’  .E kernel items
ET E  .E+T
T  T*F E  .T
TF T  .T*F
F  (E) T  .F
F  id F  .(E)
F  .id } 50
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).

... ... .
Example:
I ={ E’  E, E  E+T, E  T,
T  T*F, T  F,
F  (E), F  id }

... ..
goto(I,E) = { E’  E , E  E +T }
goto(I,T) = { E  T , T  T *F }
goto(I,F) = {T  F }
.. ..
goto(I,() = { F  ( E), E  E+T, E 
F  (E), F  id }
. T, T  . T*F, T  . F,

.
goto(I,id) = { F  id }
52

Constructing SLR Parsing Table

(of an augumented grammar G’)

1. Construct the canonical collection of sets of LR(0) items for G’.

C{I0,...,In}
2. Create the parsing action table as follows
• If a is a terminal, A.a in Ii and goto(Ii,a)=Ij then action[i,a] is shift j.
• If A. is in Ii , then action[i,a] is reduce A for all a in FOLLOW(A)
where AS’.
• If S’S. is in Ii , then action[i,$] is accept.
• If any conflicting actions generated by these rules, the grammar is not SLR(1).

3. Create the parsing goto table

• for all non-terminals A, if goto(Ii,A)=Ij then goto[i,A]=j

4. All entries not defined by (2) and (3) are errors.

5. Initial state of the parser contains S’.S
57
SLR(1) Grammar
• An LR parser using SLR(1) parsing tables for a grammar G is called as
the SLR(1) parser for G.
• If a grammar G has an SLR(1) parsing table, it is called SLR(1)
grammar (or SLR grammar in short).
• Every SLR grammar is unambiguous, but every unambiguous grammar
is not a SLR grammar.

59

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.

70
2. Canonical LR Parser ( CLR Parser)

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.

closure(I) is: ( where I is a set of LR(1) items)

– every LR(1) item in I is in closure(I)
.
– if A B,a in closure(I) and B is a production rule of G;
then B.,b will be in the closure(I) for each terminal b in
FIRST(a) .

76

goto operation

• If I is a set of LR(1) items and X is a grammar symbol

(terminal or non-terminal), then goto(I,X) is defined as
follows:
– If A  .X,a in I
then every item in closure({A  X.,a}) will be in
goto(I,X).

77
Construction of LR(1) Parsing Tables
1. Construct the canonical collection of sets of LR(1) items for G’.
C{I0,...,In}

2. Create the parsing action table as follows

• .
If a is a terminal, A a,b in Ii and goto(Ii,a)=Ij then action[i,a] is shift j.
• .
If A ,a is in Ii , then action[i,a] is reduce A where AS’.
• .
If S’S ,$ is in Ii , then action[i,$] is accept.
• If any conflicting actions generated by these rules, the grammar is not LR(1).

3. Create the parsing goto table

• for all non-terminals A, if goto(Ii,A)=Ij then goto[i,A]=j

4. All entries not defined by (2) and (3) are errors.

5. Initial state of the parser contains S’.S,$

82

3. Look Ahead LR Parser (L ALR Parser)

i. Most commonly used method because the tables generated by it are very smaller than the
canonical LR tables.

ii. In this we use the same LR(1) set of items, but we find out the set of items where the core
part (i.e. set of first components) of the items is same but the look ahead part is different.
We merge these sets with common core values into one set of items.
LALR Parsing Tables
• 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.

84

Construction of LALR Parsing table from CLR Parsing table.

A. To construct LALR Parser –
We first construct LR(1) set of items as seen in previous examples.
B. Then we check the core part of LR(1) items we choose those items whose core part is same
and lookahead part is different. We observe CLOSURE set for this. We combine those LR(1)
items to form a new combined state and rewrite the parsing table.