Java Reference
In-Depth Information
6
Because of their power, e
ciency, and ease of construction, bottom-up parsers
are commonly used in the syntax-checking phase of a compiler. Grammar
features that are problematic for top-down parsing (Chapter 5), such as left-
recursive productions and common prefixes, can typically be accommodated
without issue in bottom-up parsing. For example, the grammar shown in
Figure 5.12 on page 156 is su
ciently clear to serve as a definition of its
language's syntax. However, due to common prefixes and left-recursive rules,
that grammar is not suitable for top-down parsing. When those problems
are addressed, the grammar shown in Figure 5.16 on page 158 is obtained.
Unfortunately, that grammar does not clearly articulate the language's syntax.
It turns out that the original grammar in Figure 5.12, while unsuitable for
top-down parsing, is usable as is for bottom-up parsing. In fact, bottom-up
parsers can handle the largest class of grammars that allow parsing to proceed
deterministically
(i.e., without backtracking). For many programming lan-
guages, grammars suitable for bottom-up parsing serve as the very definition
of the language's syntax.
Given a suitable grammar, top-down parsers can be constructed automat-
ically using the techniques described in Chapter 5. This chapter discusses
analogous techniques and tools for automatically constructing bottom-up
parsers. These
parser generators
or
compiler compilers
are useful not only
because they automatically construct tables that drive bottom-up parsing, but
also because they are powerful diagnostic tools for developing or modifying
grammars.
179
