Regular expressions for token patterns in Compiler Design - Time & Space Complexity

Time Complexity: Regular expressions for token patterns

O(m * n)

Understanding Time Complexity

We want to understand how the time to match tokens using regular expressions changes as the input grows.

How does the matching process scale when scanning longer source code?

Scenario Under Consideration

Analyze the time complexity of the following token matching using regular expressions.

for each token_pattern in token_patterns:
    if regex_match(token_pattern, input_string):
        return matched_token
return no_match
    

This code tries each token pattern one by one to find a match at the start of the input string.

Identify Repeating Operations

Look for repeated checks and scans.

• Primary operation: Matching each regular expression against the input string.
• How many times: Once per token pattern, scanning input characters as needed.

How Execution Grows With Input

As the input string gets longer, each regex may need to scan more characters to confirm a match or failure.

Input Size (n)	Approx. Operations
10	Checks each pattern scanning up to 10 chars
100	Checks each pattern scanning up to 100 chars
1000	Checks each pattern scanning up to 1000 chars

Pattern observation: The work grows roughly in proportion to the input length times the number of token patterns.

Final Time Complexity

Time Complexity: O(m * n)

This means the time grows linearly with both the number of token patterns (m) and the input length (n).

Common Mistake

[X] Wrong: "Matching tokens with regex is always constant time regardless of input size."

[OK] Correct: Regex matching scans input characters, so longer inputs take more time to check.

Interview Connect

Understanding how regex matching scales helps you explain lexer performance and design efficient tokenizers.

Self-Check

What if we used a single combined regex for all tokens instead of checking each pattern separately? How would the time complexity change?