Introduction to Compiler Construction in a Java World

94 An Introduction to Compiler Construction in a Java World

Algorithm 3.7 The LR(1) Parsing Algorithm

Input: Action and Goto tables, and the input sentence w to be parsed, followed by the

terminator #

Output: a right-most derivation in reverse

Initially, the parser has the configuration

Stack Input

s

0

a

1

a

2

. . . a

n

#

where a

1

a

2

. . . a

n

is the input sentence

repeat

If Action[s

m

, a

k

] = ss

i

, the parser executes a shift (the s stands for “shift”) and goes

into state s

i

, going into the configuration

Stack Input

s

0

X

1

s

1

X

2

s

2

. . . X

m

s

m

a

k

s

i

a

k+1

. . . a

n

#

Otherwise, if Action[s

m

, a

k

] = ri (the r stands for “reduce”), where i is the number

of the production rule Y ::= X

j

X

j