Java Reference
In-Depth Information
SLR(
k
) attempts to resolve LR(0) inadequate states using Follow
k
information.
Such information is computed by considering
all
of a grammar's rules. Some-
times SLR(
k
) construction fails only because the Follow
k
information is not
rule
specific
. Consider the grammar and its partial LR(0) construction shown in
Figure 6.25. This grammar generates the language
.Thegram-
mar is not ambiguous because each of these strings has a unique derivation.
However, State 3 has an LR(0) shift
{
a
,
ab
,
ac
,
xac
}
/
reduce conflict. SLR(
k
)triestoresolvethe
shift
/
reduce conflict by computing
b$
k
−1
c$
k
−1
$
k
Follow
k
(A)
={
,
,
}
In other words, A can be followed in some sentential form by any number
of $ (end-of-string) symbols, possibly prefaced by b or c. This information
is insu
reduce conflict in State 3. Based on SLR(1)
analysis, the symbol c could signal a shift to State 6 or a reduction by A
cient to resolve the shift
/
→
a.
If we examine States 0 and 3 more carefully, we see that it is not possible
for c to occur after the expansion of A in State 3. In the closure of State 0, a
fresh item for A was created by the item S
AB. Following the shift of A,
only b or $ can occur—there is no sentential form Ac$.
→•
reduce conflict bymodi-
fying the grammar to have two “versions” of A.UsingA
1
and A
2
, the resulting
SLR(1) grammar is shown in Figure 6.26. Here, State 2 is resolved since
Follow(A
1
)
Given the above analysis, we can address the shift
/
={
$
,
b
}
.
culty with the grammar in Figure 6.25 be-
cause SLR's Follow sets are computed using all of a grammar's rules. Copying
productions and renaming nonterminals can cause the Follow computation to
become more production-specific, as in Figure 6.26. However, this is tedious
and the resulting grammar is more di
To summarize, SLR(
k
)hasdi
cult to understand and maintain. In
this section we consider LALR(
k
)(Lookahead Ahead LRwith
k
tokens of looka-
head) parsing, which o
ers amore specialized computation of the symbols that
can follow a nonterminal. The term LALR is not particularly informative—
SLR and LR also use lookahead. However, LALR o
ff
ff
ers superior lookahead
analysis for constructing the bottom-up parsing table.
Like SLR(
k
), LALR(
k
)isbasedontheLR(0) construction given in Sec-
tion 6.3. Thus, an LALR(
k
) table has the same number of rows (states) as does
an LR(0) table for the same grammar. While LR(
k
) (discussed in Section 6.5.4)
o
ers more powerful lookahead analysis, this is achieved at the expense of
introducing (typically, many) more states.
ff
