Java Reference
In-Depth Information
-
If the parser's stack grew superlinearly, then the the parser would
require more than linear time just to push entries on the stack.
Many entries in the parse tables of Figures 5.10 and 5.19 are blank. In an array
implementation, such entries would be filled by an otherwise unused integer
such as zero. If a parser accesses a zero entry while parsing some input string
then the string is determined to contain an syntax error. With respect to the
non-zero entries, LL(1) parse tables tend to be sparsely populated because the
Predict sets for most productions are small relative to the size of the grammar's
terminal vocabulary. For example, an LL(1) parser was constructed for a subset
of Ada using a grammar that contained 70 terminals and 138 nonterminals. Of
the 9660 potential LL(1) parse table entries, only 629 (6.5%) allowed the parse
to continue.
In some parse tables, blanks are not prevalent, but a single action is re-
peated across many columns. For example, action 1 is predicted for nonter-
minal S in the parse table of Figure 5.10 for all possible lookahead symbols
except d.
Given such statistics, it makes sense to view a row's most popular entry as
a
default
.Wethenstrivetorepresentthe
nondefault
entries e
ciently. Gen-
erally, consider a two-dimensional parse table with
N
rows,
M
columns, and
E
nondefault entries. The parse table constructed in Section 5.4 occupies space
proportional to
N
×
M
. Especially when
E
N
×
M
, our goal is to represent
the parse table using space proportional to
E
. Although modern workstations
are equipped with ample storage to handle LL(1) tables for any practical LL(1)
grammar, most computers operate more e
ciently when storage accesses ex-
hibit greater locality. A smaller parse table loads faster andmakes better use of
high-speed storage. Thus, it is worthwhile to consider sparse representations
for LL(1) parse tables. However, any increase in space e
ciency must not
adversely a
ff
ect the e
ciency of accessing the parse table.
We next consider strategies for decreasing the storage required to represent
parse tables. The table shown in Figure 5.20 serves as an example for the
techniques presented below. In a table used for LL(1) parsing, the table entries
(L, P, Q, etc.) would be integers denoting a grammar rule. Similar tables are
used for the bottom-up parsing methods presented in Chapter 6. Although
the table's entries encode information di
erently for bottom-up parsing, the
space-reducing techinques presented below are equally applicable to such
tables.
ff
