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

Longest Match and Lookahead

Implementing the longest match rule to correctly tokenize ambiguous input sequences using lookahead techniques.

Longest Match and Lookahead

You'll learn how tokenizers resolve ambiguity by always choosing the longest valid token and peeking ahead in the input stream.

The Core Problem

When scanning input like ifx = 10, a naive tokenizer might see the first two letters if and immediately emit a keyword token. But that's wrong—the correct token is the identifier ifx. The longest match rule solves this: always consume the longest sequence of characters that matches any pattern before emitting a token.

How It Works

Imagine you're reading text left-to-right with a finite automaton. Multiple patterns might match at once (like if matching both the keyword pattern and the identifier pattern). The longest match rule says: keep reading until no pattern matches anymore, then back up to the longest valid match you found.

Lookahead means examining the next character(s) without consuming them. When your automaton can't extend the current match any further, you look ahead to confirm where the token should end. For example:

  • Input: 123abc
  • After reading 123, the number pattern matches
  • Lookahead sees a (not a digit), so the number token ends
  • Token emitted: 123 (number)
  • Next scan starts at a

Why This Matters

Without longest match, tokenizers would incorrectly break return into re + turn, or split == into = + = when you meant the equality operator. Lookahead ensures you don't accidentally consume characters belonging to the next token.

This is implemented in the transition table from the previous lesson: states track whether they're accepting (valid token endpoints), and the scanner only commits to a token when it can't transition further.

Key Takeaway: The longest match rule with lookahead ensures tokenizers correctly identify complete tokens by consuming the maximum valid character sequence and confirming token boundaries before committing.