Course contentsShow
← Computer Science
Lesson 1961 of 2,87244. Lexical Analysis and ParsingFree lesson

Handles and Viable Prefixes

Understanding handles as reducible substrings and viable prefixes in the parsing process.

Handles and Viable Prefixes

What you'll learn: You'll understand how bottom-up parsers identify the right substrings to reduce and track valid progress through a grammar.

What is a Handle?

In bottom-up parsing, a handle is a substring of the current input that matches the right-hand side of a production rule and can be safely reduced back to its left-hand side non-terminal. Think of it as the parser's "next move"—the portion of the partially-parsed string that should collapse into a single symbol.

For example, if your grammar has E → E + T and your current parsing state contains E + T, the substring E + T is a handle that can be reduced to E.

The key insight: Not every substring matching a production's right side is a handle—only the rightmost one that, when reduced, moves you correctly toward the start symbol. Handles are essentially the breadcrumbs showing you're on the right path in reverse-engineering the parse tree.

What are Viable Prefixes?

A viable prefix is any prefix of a right-sentential form that doesn't extend past the end of its handle. In simpler terms: it's any portion of the input (from left to right) that could appear on the parser's stack without causing an error.

Analogy: Imagine assembling a puzzle from right to left. A viable prefix is any partially-assembled configuration that could legally exist before you place the next piece. If you've gone too far or placed pieces incorrectly, you've left the "viable" zone.

Viable prefixes matter because they define what the parser can safely see on its stack—they represent states where parsing can still succeed.

Why They Matter Together

Bottom-up parsers use viable prefixes to track progress and identify handles. The parser maintains a stack of viable prefixes and looks for handles at the top to perform reductions.

Key Takeaway: Handles are the reducible substrings a bottom-up parser acts upon, while viable prefixes are the valid partial parses the parser can encounter—together, they form the foundation for efficient shift-reduce parsing strategies.