Chapter 5: Top-Down Parsing

Overview


Chapter 2 presents a recursive-descent parser for the syntax analysis phase of a small compiler. Manual construction of such parsers is both time consuming and error prone, especially when applied at the scale of a real programming language. At first glance, the code for a recursive-descent parser may appear to be written ad hoc. Fortunately, there are principles at work. This chapter discusses these principles and their applications in tools that automate the parsing phase of a compiler.

Recursive-descent parsers belong to the more general class of top-down (also called LL parsers), which were introduced in Chapter 4. In this chapter, we discuss top-down parsers in greater detail, analyzing the conditions under which such parsers can be reliably and automatically constructed from grammars. Our analysis builds on the algorithms and grammar-processing concepts presented in Chapter 4.

Top-down parsers are in theory not as powerful as the bottom-up parsers we study in Chapter 6. However, because of their simplicity, performance, and excellent error diagnostics, top-down parsers have been constructed for many programming languages, almost always using the recursive-descent approach. Such parsers are also convenient for prototyping relatively simple front-ends of larger systems that require a rigorous definition and treatment of the system's input.