Language Implementation Patterns

Directing the Parse with Semantic Information

The parsers we’re working with in this book recognize context-free languages. A context-free language is a language whose constructs don’t depend on the presence of other constructs. Unfortunately, some programming languages have context-sensitive phrases. To handle context-sensitive phrases with a context-free parser, we have to predicate alternatives. In effect, a predicate is just a run-time boolean test that says when it’s OK to match an alternative. The predicates gate the associated alternatives in and out.

To see why we need predicates, let’s look at a context-sensitive phrase within a programming language. C++ is the traditional parsing punching bag, so let’s get our gloves on and limber up ...