Java Reference
In-Depth Information
code grows with the size of the grammar. Moreover, the overhead of method
calls and returns can be a source of ine
ciency. In this sectionwe examine how
to construct a table-driven LL(1) parser. Actually, the parser itself is standard
across all grammars, so we need only provide an adequate parse table.
To make the transition from explicit code to table-driven processing, we
use a stack to simulate the actions performed by
and by the calls to the
nonterminals' procedures. In addition to the methods typically provided by
a stack, we assume that the top-of-stack contents can be obtained nondestruc-
tively (without popping the stack) via the method TOS.
In code form, the generic LL(1) parser is given in Figure 5.8. At each
iteration of the loop at Marker
5
, the parser performs one of the following
actions:
match
•
If the top-of-stack is a terminal symbol, then
is called. This
method, defined in Figure 5.5, ensures that the next token of the in-
put stream matches the top-of-stack symbol.
match
If successful, the call to
match
advances the token input stream. For the table-driven parser, the
matching top-of-stack symbol is popped at Marker
9
.
•
If the top-of-stack is some nonterminal symbol A, then the appropriate
production A
...X
m
is determined by table lookup at Marker
10
.
If a valid production is found, then
→X
1
is called to pop the A from the
top of the stack (Marker
11
). The symbols
apply
X
...X
m
are then pushed at
1
Marker
12
onto the stack starting with
X
m
, so that the resulting top-of-
stack is
X
1
.
The parse is complete when the end-of-input symbol is matched at Marker
8
.
LL1 test in Figure 5.4, we next examine
how to build its LL(1)parsetable. Therowsandcolumnsoftheparsetable
are labeled by the nonterminals and terminals of the CFGs, respectively. The
table, consulted at Marker
10
in Figure 5.8, is indexed by the top-of-stack
symbol (obtained by the TOS( ) call) and by the next input token (obtained by
the
ts
.
peek( ) call).
Each nonblank entry in a row is a production that has the row's nontermi-
nal as its
left-hand side
(LHS) symbol. A production is typically represented
by its rule number in the grammar. The table is used as follows:
Given a CFGs that has passed the I
s
•
The nonterminal symbol at the top-of-stack determines which row is
chosen.
•
The next input token (i.e., the
lookahead
) determines which column is
chosen.
