Java Reference
In-Depth Information
definition of LR(
k
)intermsofthepropertiesanLR(
k
) parser must possess. All
shift-reduce parsers
operate by shifting symbols and examining lookahead
information until the end of the handle is found. Then the handle is reduced to
a nonterminal, which replaces the handle on the stack. An LR(
k
) parser, guided
by its parse table, must decide whether to shift or reduce, knowing only the
symbols already shifted (left context) and the next
k
lookahead symbols (right
context).
A grammar is LR(
k
) if, and only if, it is possible to construct an LR parse
table such that
k
tokens of lookahead allows the parser to recognize
exactly
those strings in the grammar's language. An important property of an LR
parse table is that each cell accommodates only one entry. In other words, the
LR(
k
)parseris
deterministic
—exactly one action can occur at each step.
We next formalize the properties of an LR(
k
) grammar, using the following
definitions and notation from Chapter 4:
⇒
β
•
If S
,then
β
is a
sentential form
of a grammar with goal symbol S.
•
First
k
(
α
) is the set of length-
k
terminal prefixes that can be derived from
α
.
Assume that in some LR(
k
) grammar there are two sentential forms
αβ
w
and
αβ
y
with
w
,
y
∈Σ
. These sentential forms share a common prefix
αβ
. Further-
more, with the prefix
αβ
on the stack, assume that their
k
-token lookahead sets
are identical: First
k
(
w
)
=
First
k
(
y
). Suppose the parse table calls for reduction
by A
→β
given the left context of
αβ
and the
k
-token lookahead present in
w
; this results in
A
w
. With the same lookahead information in
y
,theLR(
k
)
parser must make the same decision:
α
A
y
. Formally, a grammar
is LR(
k
) if, and only if, the following conditions imply
αβ
y
becomes
α
α
A
y
=γ
B
x
.
⇒
rm
α
•
S
A
w
⇒
rm
αβ
w
•
S
⇒
rm
γ
B
x
⇒
rm
αβ
y
•
First
k
(
w
)
=
First
k
(
y
)
This implication allows reduction by A
is on top-of-stack and
the
k
-symbol lookahead is First
k
(
w
). In other words, LR(
k
) parsers are defined
such that they can always determine the correct reduction given the following:
→β
whenever
αβ
•
The left context up to the end of the handle
•
The next
k
symbols of the input
This definition is instructive in that it defines the minimum properties a gram-
mar must possess to be parsable by LR(
k
) techniques. It does not tell us how
to
build
a suitable LR(
k
) parser; in fact, the primary contribution of Knuth's
early work [Knu65] was an algorithm for LR(
k
) construction. We begin with
