Chapter 6: Bottom-Up Parsing

Overview


Because of their power, efficiency, 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.

Given a suitable grammar, top-down parsers can be constructed automatically 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.