Java Reference
In-Depth Information
function
S
can
D
igits
()
returns
token
tok
.
val
← ""
while
s
.
peek()∈{0,1,...,9}
do
tok
.
val
←
tok
.
val
+
s
.
advance()
if
s
.
peek()
"."
then
tok
.
type
←
inum
else
tok
.
type
←
fnum
tok
.
val
←
tok
.
val
+
s
.
advance()
while
s
.
peek()∈{0,1,...,9}
do
tok
.
val
←
tok
.
val
+
s
.
advance()
return
(
tok
)
end
Figure 2.6: Finding inum or fnum tokens for the ac language.
compilers the grammar serves not only to define the syntax of a programming
language, but also to guide the automatic construction of a parser, as described
in Chapters 4, 5, and 6. In this section we build a parser for ac using a well-
known parsing technique called
recursive descent
, which is describedmore fully
in Chapter 5.
Recursive descent
is one of the simplest parsing techniques used in practi-
cal compilers. The name is taken from the mutually recursive parsing routines
that, in e
ect, descend through a derivation tree. In recursive-descent pars-
ing, each nonterminal in the grammar has an associated
parsing procedure
that
is responsible for determining if the token stream contains a sequence of to-
kens derivable from that nonterminal. For example, the nonterminal Stmt is
associated with the parsing procedure shown in Figure 2.7.
We next illustrate how to write recursive descent parsing procedures for
the nonterminals Stmt and Stmts from the grammar in Figure 2.1. Section 2.5.1
explains how such parsers predict which production to apply, and Section 2.5.2
explains the actions taken on behalf of a production.
ff
Eachprocedure first examines the next input token to predict whichproduction
should be applied. For example, Stmt o
ff
ers two productions:
Stmt
→
id assign Val Expr
Stmt
→
print id
In Figure 2.7, Markers
1
and
6
pick which of those two productions should
be followed by examining the next input token:
