Language Implementation Patterns

Chapter 3Enhanced Parsing Patterns

In the previous chapter, we looked at the fundamental language recognition patterns. They’re sufficient to handle most parsing tasks, but some languages defy even Pattern 4, ​LL(k) Recursive-Descent Parser​. In this chapter, we’ll explore how to crank up the parsing power at the cost of some complexity and run-time efficiency. We’ll look at three important specialized parsing patterns:

• Pattern 5, ​Backtracking Parser​. This pattern adds a speculative parsing facility to recursive-descent parsers. It’s useful to have because sometimes it’s hard to distinguish between alternatives without simply trying them. A backtracking parser attempts alternatives in order until one of them matches the current input. In effect, ...