Java Reference
In-Depth Information
0
(continued from Figure 6.6)
Ac$
1
0
shift A
c $
1
c
11
0
shift c
$
A
1
0
Reduce c to C
C $
A
1
C
14
0
shift C
$
0
Reduce ACto S
S $
S
4
0
shift S
$
$
8
4
0
shift $
$
0
Reduce S $toStart
Start $
Start
0
0
shift Start
$
Accept
Figure 6.7: Continuedbottom-upparseofabbdc$.
the next input token, for the purpose of indexing the parse table to determine
the appropriate action. The “0” in LR(0) refers not to the lookahead at parse-
time, but rather to the lookahead used in
constructing
the parse table. At
parse-time, LR(0) and LR(1) parsers index the parse table using one token of
lookahead; for
k
≥
2, an LR(
k
) parser uses
k
tokens of lookahead.
The number of columns in an LR(
k
) parse table grows dramatically with
k
. For example, an LR(3) parse table is indexed by the parse state to select a
row, and by the next 3 input tokens to select a column. If the terminal alphabet
has
n
symbols, then the number of distinct three-token sequences is
n
3
.More
generally, an LR(
k
)tablehas
n
k
columns for a token alphabet of size
n
. To keep
the size of parse tables within reason, most parser generators are limited to
one token of lookahead. Some parser generators do make selected use of extra
lookahead where such information is helpful.
Most of this chapter is devoted to the problems of constructing LR parse
tables. Before we consider such techniques, it is instructive to formalize the
