Language Implementation Patterns

Pattern 7

Predicated Parser

Purpose

This pattern augments any top-down parser with arbitrary boolean expressions that help make parsing decisions.

These boolean expressions are called semantic predicates and specify the semantic applicability of an alternative. Predicates that evaluate to false effectively “turn off” a parser decision path. From a grammar point of view, false predicates make alternatives invisible.

Discussion

We need semantic predicates when the parser cannot use syntax alone to make parsing decisions, that is, when the parser cannot distinguish between alternatives without using run-time information. The most common case is when we need to use symbol table information to guide the parse. (See Chapter 6, ​Tracking and Identifying ...