Java Reference
In-Depth Information
In this chapter, we study the following two forms of top-down parsers:
•
Recursive-descent parsers
contain a set of mutually recursive proce-
dures that cooperate to parse a string. Code for these procedures can be
written directly from a suitable grammar.
•
Table-driven LL parsers
use a generic LL(
k
) parsing engine and a parse
table that directs the activity of the engine. The entries for the parse table
are determined by the particular LL(
k
) grammar. The notation LL(
k
)is
explained below.
Fortunately,
context-free grammars
(CFGs) with certainproperties can be used
to generate such parsers automatically. Tools that operate in this fashion are
generally called
compiler compilers
or
parser generators
. They take a gram-
mar description file as input and attempt to produce a parser for the language
defined by the grammar. The term “compiler compiler” applies because the
parser generator is
itself a compiler
: it accepts a high-level expression of a pro-
gram (the grammar definition file) and generates an executable form of that
program (the parser). This approach makes parsing one of the easiest and
most reliable phases of compiler construction for the following reasons:
•
When the grammar serves as a language's definition, parsers can be
automatically constructed to perform syntax analysis in a compiler. The
rigor of the automatic construction guarantees that the resulting parser
is faithful to the language's syntactic specification.
•
When a language is revised, updated, or extended, the associated modi-
fications can be applied to the grammar description to generate a parser
for the new language.
•
When parser construction is successful through the techniques described
in this chapter, the grammar is proved unambiguous. While devis-
ing an algorithmic test for grammar ambiguity is impossible, parser-
construction techniques are of great use to language designers in devel-
oping intuition as to why a grammar might be ambiguous.
As discussed in Chapters 2 and 4, every string in a grammar's language can be
generated by a derivation that begins with the grammar's start symbol. While
it is relatively straightforward to use a grammar's productions to generate
sample strings in its language, reversing this process does not seem as simple.
That is, given an input string, how can we show why the string is or is not in
the grammar's language? This is the
parsing problem
, and in this chapter we
consider a parsing technique that is successful with many CFGss. This parsing
technique is known by the following names:
