21CS51

Automata Theory

and

Compiler Design

Lecture Notes for LR(0) Parsing

Shridhar Venkatanarasimhan

Computer Science and Engineering Department

Raja Reddy Institute of Technology

Chikkabanavara, Bengaluru 560090.

February 11, 2024

 CONTENTS

1. Introduction to Shift-Reduce Parsing . . . . . . . . . . . . . . . . 6

1.1 What is a handle? . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2 Shift-Reduce Example . . . . . . . . . . . . . . . . . . . . . . 6

2. LR(0) Parsers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1 What is an LR(0) Item? . . . . . . . . . . . . . . . . . . . . . 8

2.2 Sets of LR(0) Items . . . . . . . . . . . . . . . . . . . . . . . . 8

2.3 The GOTO Function . . . . . . . . . . . . . . . . . . . . . . . 9

2.4 LR(0) Automaton . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.5 LR(0) Parsing Table . . . . . . . . . . . . . . . . . . . . . . . 11

2.6 Use of the LR(0) Parsing Table . . . . . . . . . . . . . . . . . 12

 LIST OF FIGURES

1.1 Shift-Reduce Parsing . . . . . . . . . . . . . . . . . . . . . . 7

2.1 LR(0) Automaton with Sets of Items (States) and the GOTO

Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 LR(0) Parsing Table for the Expression Grammar . . . . . . 11

2.3 LR Parsing Algorithm . . . . . . . . . . . . . . . . . . . . . . 12

2.4 LR(0) Parsing Steps for id * id . . . . . . . . . . . . . . . . . 13

 ABSTRACT

In these notes, we consider bottom-up parsing. In bottom-up parsing,

the input (string of terminals) is scanned (usually from left-to-right)

and a form of the parse tree is constructed from the bottom to the top.
 Abstract 5

Disclaimer: Students are requested to read the prescribed text-

books and the reference books. There might be errors in these

notes. If you come across any mistake, please let me know.

 1. INTRODUCTION TO SHIFT-REDUCE PARSING

Shift-Reduce is a kind of bottom-up parsing which users a stack for

holding grammar symbols. The input is scanned from left-to-right. In

each step, the current input symbol is either shifted on to the stack, or

a handle on the top of the stack is reduced to a non-terminal.

1.1 What is a handle?

Consider a production A → β. Assume that αβ is on the stack. The

shift-reudue parser might decide to replace β with A. In this case we

can think of the position of β on the stack as a handle which is pruned

to A.

1.2 Shift-Reduce Example

An example of shift-reduce parsing is given for the string id ∗ id$ for the

following expression grammar.

1. E → E + T

2. E → T

3. T → T ∗ F

4. T → F

5. F → (E)

6. F → id
 1. Introduction to Shift-Reduce Parsing 7

Fig. 1.1: Shift-Reduce Parsing

Note that this grammar is unambiguous, left recursion is not elimi-

nated and the productions are number from 1 to 6.

Please refer to figure 1.1 for how shift-reduce parsing occurs.

Note that this parser makes a left-to-right scan of the input and

traces a rightmost derivation in reverse.

 2. LR(0) PARSERS

An LR(0) parser is a kind of shift-reduce parser. L stands for left-to-

right scan of input, R stands for rightmost derivation in reverse and 0

stands for 0 symbols of lookahead.

In LR(0) parser a state is pushed on the stack. A state represents a

set of LR(0) items.

2.1 What is an LR(0) Item?

If A → αβ is a production, A → α.β is an item representing that in the

process of seeing this production, the parser has recognized α thus far.

2.2 Sets of LR(0) Items

Let us begin with a set of items which represent a state of what the

parser has recognized. Let I be this set. Then if A → α.Bβ is in I and

B → γ is a production, add B → .γ to I. Keep doing this till no more

items can be added. Then this set is called CLOSU RE(I).

For constructing LR(0) Parser, we need an augmented grammar.

That is a production S ′ → S is added to the grammar. The expression

grammar after augmentation becomes:

• E′ → E

• E →E+T

• E→T
 2. LR(0) Parsers 9

• T →T ∗F

• T →F

• F → (E)

• F → id

The initial set of items after CLOSURE of E ′ → .E is

• E ′ → .E

• E → .E + T

• E → .T

• T → .T ∗ F

• T → .F

• F → .(E)

• F → .id

2.3 The GOTO Function

If a set of LR(0) items I contains an item A → α.Xβ where X is a gram-

mar symbol (variable or terminal) then GOTO(I, X) contains A → αX.β.

Thus from a set of items I we GOTO a set J (J=CLOSURE(J)) on X.

2.4 LR(0) Automaton

Refer to figure 2.1 for the LR(0) automaton which has these states and

the GOTO functions for the augmented expression grammar.

 2. LR(0) Parsers 10

Fig. 2.1: LR(0) Automaton with Sets of Items (States) and the GOTO Function
 2. LR(0) Parsers 11

Fig. 2.2: LR(0) Parsing Table for the Expression Grammar

2.5 LR(0) Parsing Table

An LR(0) Parsing Table has a row for every state. It has a column for

every terminal and a column for $ which signifies end-of-input. It has

columns for every variable too.

Refer to figure 2.2 for the LR(0) parsing table for the expression

grammar.

If GOT O(Ii , a) = Ij , then the entry for state i on input a is sj where s

stand for shift. If GOT O(Ii , A) = Ij dfor a non-terminal A then the entry

for i and column A is j. If a set of items contains the complete item

A → α., then for all in FOLLOW(A), the entry for that row is rk where k

is the number of the production. If a set of items Ii contains the item

S ′ → S., then the action of state i on $ is accept.

 2. LR(0) Parsers 12

Fig. 2.3: LR Parsing Algorithm

2.6 Use of the LR(0) Parsing Table

Refer to figure 2.3 for the parsing algorithm which makes use of the

parsing table for shift/reduce decisions.

Refer to figure 2.4 for the example of parsing the input id ∗ id.
 2. LR(0) Parsers 13

Fig. 2.4: LR(0) Parsing Steps for id * id

 BIBLIOGRAPHY

[1] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman;

Compilers, Principles, Techniques, & Tools, Second Edition, Pear-

son.