Grep-Style Regular Expression Engine with Finite Automata

About

This project is my own implementation of a grep-based regular expression engine built from scratch. It explores how regex engines work by constructing a lexer, parser, and finite automata (NDFA/DFA) to perform pattern matching similar to traditional tools like grep. The goal is to learn and experiment, so some components are still under development.

What This Engine Does

At a high level, the engine takes a regular expression, processes it through several stages, and uses finite automata to match patterns in text:

• Lexer: Tokenizes the regex pattern (e.g., symbols, operators like *, +, |, parentheses).
• Parser: Builds a structured representation of the regex from the token stream.
• Finite Automata: Converts the parsed regex into an NDFA and/or DFA for efficient pattern matching.

Build Project

To build this project, a makefile is provided and used as follows:

make grep

Usage

./regex_engine [OPTION]... REGEX [FILE]...

Examples:

./regex_engine "a"          text.txt   # lines containing 'a'
./regex_engine "ab"         text.txt   # lines containing 'ab'
./regex_engine "a|b"        text.txt   # lines containing 'a' or 'b'
./regex_engine "ab*"        text.txt   # lines containing 'a' followed by zero or more 'b'
./regex_engine "ab+"        text.txt   # lines containing 'a' followed by one or more 'b'
./regex_engine "(ab|cd)+"   text.txt   # lines containing one or more repetitions of 'ab' or 'cd'
./regex_engine -n "a"       text.txt   # show line numbers
./regex_engine -v "a"       text.txt   # lines that do NOT contain 'a'
./regex_engine -c "a"       text.txt   # count matching lines
./regex_engine -in "a"      text.txt   # flags can be combined

Supported Operations

Operation	Syntax	Description
Literal	a	Matches the exact character a
Concatenation	ab	Matches a followed by b
Union	a|b	Matches either a or b
Kleene Star	a*	Matches zero or more repetitions of a
Plus	a+	Matches one or more repetitions of a
Range	[[a-z]]	Matches the range between a and z
Set	[[aeiuo]]	Match all character in the set
Grouping	(ab)	Groups expressions to apply operators to them
Empty	∅	Matches nothing
Lambda	λ	Matches the empty string

Operations can be combined and nested using parentheses:

• (a|b)* — any string of as and bs, including empty
• (ab)+ — one or more repetitions of ab
• a(b|c)*d — a, then any combination of b and c, then d

Supported Flags

Flags can be placed anywhere in the command and combined together (e.g. -in, -vn).

Flag	Description
-c	Print only the count of matching lines
-v	Invert match — print lines that do not match
-n	Prefix each output line with its line number
-i	Ignore case — match regardless of upper/lowercase
-w	Word match — only match if pattern is at a word boundary
-x	Line match — only match if the entire line matches the regex

Examples:

./regex_engine -n  "ab"   text.txt   # show line numbers
./regex_engine -v  "ab"   text.txt   # lines that do NOT contain 'ab'
./regex_engine -c  "ab"   text.txt   # count of matching lines
./regex_engine -i  "AB"   text.txt   # case-insensitive match
./regex_engine -w  "ab"   text.txt   # 'ab' only as a whole word
./regex_engine -x  "ab"   text.txt   # lines where the entire content is 'ab'
./regex_engine -in "AB"   text.txt   # combined: case-insensitive + line numbers
./regex_engine -vn "ab"   text.txt   # combined: invert match + line numbers
./regex_engine -i "[a-z]" text.txt   # case-insensitive match in a range from a to z
./regex_engine [^a-z] text.txt       # not there matching in the range from a to z

Key Concepts

• Regular Expression Engines
  Modern regex implementations (e.g., those in languages and tools) vary in design, but many rely on automata theory for pattern matching performance and correctness.

• Lexer and Parser
  The lexer breaks the raw pattern into tokens; the parser organizes those tokens according to a grammar to form a syntax structure that can be translated into automata.

• Finite Automata

  • NDFA (Nondeterministic Finite Automaton): Easy to construct from regex syntax, can have multiple possible transitions.
  • DFA (Deterministic Finite Automaton): Derived from an NDFA, has a single transition per input per state, enabling faster execution.

• grep
  The Unix tool grep (Global Regular Expression Print) is a classic example of a regex engine used for searching text with patterns. This project is inspired by the matching and automata-based techniques commonly associated with grep.

Clarifications

To treat metacharacters (symbols with special functional meaning) as literal characters, you must use the escape character /. The symbols that require escaping include:

• Operators and Quantifiers: /*, /+, /|
• Grouping Delimiters: /(, /)
• Character Classes (Sets): /[, /]
• Literal Escape: To match a literal forward slash, use //.

Additionally, the engine supports the following special escape sequences:

• /n: Line Feed (Newline).
• /t: Horizontal Tab.
• /r: Carriage Return.

If the first or only literal in a set of the form [] is ^, the literal must be escaped; otherwise, it is not necessary to do so.

References

• Turing machine
• Finite-state machine
• Tsoding Regex From Scratch
• Parser and Lexer

License

This project is licensed under the GNU General Public License v3.0 - see the LICENSE file for details.

Status

This is a work-in-progress implementation of the core components of a regex engine. Contributions, suggestions, and improvements are welcome!