Java Reference
In-Depth Information
1 Start
→
S$
2 S
→
lpMrp
3
|
lbMrb
4
|
lp U rb
5
|
lb U rp
6 M
→
expr
7 U
→
expr
Figure 6.35: A grammar that is not LALR(
k
).
In this section we describe an LR table-construction method that accommo-
dates all deterministic, context-free languages. While that may seem attrac-
tive, LR(
k
) parsing is not very practical because even LR(1) tables (
k
=
1) are
typically much larger than the LR(0) tables upon which SLR(
k
)andLALR(
k
)
parsing are based. Moreover, it is rare that LR(1) can handle a grammar for
which LALR(1) construction fails. We present such a grammar in Figure 6.35,
but such grammars do not arise very often in practice. When LALR(1) fails, it
is typically for one of the following reasons:
•
The grammar is ambiguous—LR(
k
) cannot help.
•
More lookahead is needed—LR(
k
) canhelp (for
k
>
1). However, LALR(
k
)
might su
ce in such cases.
•
No amount of lookahead su
ces—LR(
k
) cannot help.
The grammar in Figure 6.35 allows strings generated by the nonterminal M
to be surrounded by
matching
parentheses (lp and rp)orbraces(lb and rb). The
grammar also allows S to generate strings with
unmatched
punctuation. The
unmatched expressions are generated by the nonterminal U. The grammar can
easily be expanded by replacing the terminal expr with a nonterminal that de-
rives arithmetic expressions, such as E in the grammar of Figure 6.21. While M
and U generate the same terminal strings, the grammar distinguishes between
them so that a semantic action can report the mismatched punctuation—using
reduction by U
expr.
A portion of the LALR(1) analysis of the grammar in Figure 6.35 is shown
in Figure 6.37; the complete analysis is left for Exercise 29. Consider the
lookaheads that will propagate into State 6. For Item 14, which calls for the
reduction M
→
expr, rp is sent to Item 8 and then to Item 14. Also, rb is sent
to Item 12 and then to Item 14. Thus,
→
ItemFollow
(14)
= {
rb
,
rp
}
. Similarly,
