Java Reference
In-Depth Information
in order 1
5. The resulting structures, shown in Figure 5.24, can be
explained as follows:
,
2
,
3
,
4
,
Row 1:
This rowcannot be negatively shifted because it has an entry in column
1. Thus,
R
[1] is 0 and
V
[1
...
5] represents row 1, with nondefault entries
at index 1 and 4.
Row 2:
This row can merge into
V
without shifting, because its nondefault
values (columns 2 and 5) can be accommodated at 2 and 5, respectively.
Row 3:
Similarly, row 3 can be accommodated by
V
without any shifting.
Row 4:
When this row is considered, the first slot of
V
that can accommodate
its leftmost column is slot 6. Thus,
R
[4]
=
5 and row 4's nondefault
entries are placed at 6 and 7.
Row 5:
Finally, columns 2 and 4 of row 5 can be accommodated at 8 and 10,
respectively. Thus,
R
[5]
=
6.
As suggested by the pseudocode at Marker
15
, rows can be presented to
F
in any order. However, the size of the resulting compressed table
can depend on the order in which rows are considered. Exercises 20 and 21
explore this point further. In general, finding a row ordering that achieves
maximum compression is an
NP-complete
problem [GJ79]. This means that
the best-known algorithms for obtaining optimal compression would have
to try all row permutations. However, compression heuristics work well in
practice. When compression is applied to the Ada LL(1) parse table mentioned
previously, the number of entries drops from 9660 to 660. This result is only
0.3% o
ind
S
hift
ff
from the 629 nondefault entries in the original table.
A compiler should produce a useful set of diagnosticmessages when presented
with a faulty input. Thus, when a single error is detected, it is usually desirable
to continue processing the input to detect additional errors. Generally, parsers
can continue syntax analysis using one of the following approaches:
•
With
error recovery
, the parser attempts to ignore the current error. The
parser enters a configuration where it is able to continue processing the
input.
•
Error repair
is more ambitious. The parser attempts to correct the syn-
tactically faulty program by modifying the input to obtain an acceptable
parse.
In this section, we explore each of these approaches in turn. We then examine
error detection and recovery for LL(1) parsers.
