Java Reference
In-Depth Information
Program
floatdcl
b
intdcl
a
assign
assign
print
b
plus
id
a
inum
id
b
5
id
a
fnum
3.2
Figure 2.9: An abstract syntax tree for the ac program shown in
Figure 2.4.
Throughout Figures 2.7 and 2.8, calls to
match
appear on behalf of ter-
minal symbols within a production.
•
The last two symbols in Stmt
id assign Val Expr are nonterminals. The
recursive descent parser has a method responsible for the derivation of
each nonterminal in a grammar. Thus, the code at Marker
4
calls the
procedure V
→
al
associated with the nonterminal Val . Finally, the E
xpr
method is called on behalf of the last symbol.
In Figure 2.8, the code executed on behalf of Stmts
→
Stmt Stmts first
calls S
recursively at Marker
10
.
Recursive calls appear on behalf of grammar productions that reference
each other. Recursive descent parsers are named after the manner in
which the parser's methods call each other.
tmt
at Marker
9
and then calls S
tmts
•
The only other symbol that can be encountered is
.For
such productions, no symbols are derived from the nonterminal. Thus,
no code is executed on behalf of such rules, as shown at Marker
12
in
Figure 2.8.
λ
,asinStmts
→λ
The recursive-descent parser for Figure 2.1 is completed by writing a method
for eachnonterminal using the approachdescribed above. The resulting parser
can be found in the
Crafting a Compiler Supplement
.
