A lightweight regular expression engine implemented from scratch in Python.
This project demonstrates the core principles of regex matching, including parsing, backtracking, and handling of various regex features.
It uses a hand-written recursive descent parser and a generator-based backtracking algorithm to find matches.
This engine supports a useful subset of common regular expression syntax:
- Matches specific characters (e.g.,
a,b,1).
.→ Matches any single character.
+→ One or more.?→ Zero or one.*→ Zero or more.
[abc]→ Matches any ofa,b, orc.[a-z0-9]→ Range-based classes.[^aeiou]→ Negated classes.
\d→ Matches any digit.\w→ Matches any alphanumeric character (letters, numbers) and underscore.
- Capturing groups:
( ... )for sub-patterns. - Alternation:
(cat|dog)to match either branch.
- Match previously captured groups using
\1,\2, etc.
^→ Asserts the start of the string.$→ Asserts the end of the string.
- Single/multi-line file processing (line-by-line matching).
- Multi-file support with
<filename>:prefix. - Recursive directory traversal (
-rflag) with relative paths and<relpath>:prefix. - Exits with code 0 on matches, 1 otherwise; clean output.
python main.py -r -E "<pattern>" [<file1> <file2> ...]# Search a single file
python main.py -E "appl.*" fruits.txt
# Search multiple files (with filename prefix)
python main.py -E "vegetable" fruits.txt veggies.txt
# Recursive search in directory
python main.py -r -E ".*er" dir/
# Output example:
# dir/fruits.txt:strawberry
# dir/subdir/vegetables.txt:celeryThe program is designed to be run from the command line, mimicking the behavior of simple grep.
echo "<input_string>" | python main.py -E "<pattern>"To check if the pattern (\w+) and \1 matches the string "cat and cat":
echo "cat and cat" | python main.py -E "(\w+) and \1"The program will print a success or failure message and exit with:
- Status code 0 → Match found.
- Status code 1 → No match.
The engine is built on two primary components:
- Handles the command-line interface (CLI): Parses flags (-E, -r), optional filenames/directories, and input (stdin or files).
- Supports line-by-line processing for multi-line files/directories.
- Implements recursive file discovery (manual DFS traversal) for -r.
- Parses arguments and reads input.
- Acts as the entry point and orchestrates the matching process.
- Contains all core regex-matching logic.
- Implements a Recursive Descent Parser that parses and evaluates the pattern on-the-fly against the input string.
- Uses recursive backtracking with Python generators.
The core function, match_inner, is a generator that yields all possible successful match lengths for a given pattern and position.
- Additional Quantifiers: Implement
{m,n}and lazy quantifiers (e.g., +?). - Performance Optimization: Introduce memoization (caching) to avoid redundant computations.
- Non-Capturing Groups: Add support for
(?: ... ). - Lookarounds: Implement positive and negative lookaheads/lookbehinds.
- Binary Files: Handle non-text files gracefully (e.g., skip or warn).
- More Escapes: Add \s, \b, etc.