Write a Regex Engine Subset That Can Describe Token Patterns

Topic Overview

Regex Patterns Describe Tokens

Lexical specifications are often written as regular expressions: [0-9]+ for integers, [a-zA-Z_][a-zA-Z0-9_]* for identifiers. Flex translates these to DFAs. Building a small regex matcher teaches you what Flex generates under the hood.

Subset: Concatenation, Alternation, Kleene Star

A minimal regex engine supports concatenation (ab), alternation (a|b), and Kleene star (a*). Compile the pattern to an NFA, subset-construct to a DFA, or interpret with a recursive matcher. Each match corresponds to a token pattern in your language.

cCopy
Loading…

• Digit class [0-9] matches one decimal digit
• + means one or more of the preceding element
• * means zero or more
• Anchor patterns to full lexeme, not substring search

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement a regex matcher subset that can describe token patterns for your lexer. This exercise asks you to parse simple regex syntax and test whether an input string matches, forming the foundation for generated or table-driven scanners.

Your Task

Build a small regular-expression engine the way lexer generators do: parse the pattern, compile it to a Thompson NFA, and simulate the NFA over the input. Patterns describe whole tokens, so a match must cover the entire text (no substring search).

Pattern syntax

A pattern is invalid if it has unbalanced parentheses, an unterminated [, an empty [], a trailing lone \, or a * + ? with nothing to apply to (at the start, or right after ( or |). An empty alternative such as a| is allowed and matches the empty string.

Input

One test per line: the pattern, a single space, then the text (the rest of the line, which may contain spaces or be empty). The pattern itself never contains a space; use \s. A line with no space at all is a pattern with empty text.

Output

cCopy
Loading…

then matches=M.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Compile to an NFA of character-set states and ε-split states (Thompson's construction), then run it by tracking the set of active states: no backtracking. (a*)*b against 30 as must return instantly.
2. Patterns are at most 200 characters.

Hidden tests cover string-literal and float patterns, nested groups, escapes, the empty text, pathological patterns, and invalid patterns.