Simple Regex Engine

This project is a simple regex engine implemented in C++. It is based on the concept of Non-deterministic Finite Automaton (NFA) and Thompson's construction algorithm to convert regular expressions into NFAs. The engine supports basic regex features such as alternation, concatenation, and Kleene star.

My subject at my university, "Automata and Formal Languages" inspired me to create this project as a way to deepen my understanding of the concepts covered in the course. The implementation includes a parser that can handle regular expressions and convert them into an internal representation for NFA construction. The engine can be used for membership testing, allowing users to check if a given string matches the regular expression.

Allowed Characters

• a-z, A-Z
• | - Alternation (OR)
• * - Zero or more occurrences of the preceding element
• . - Concatenation
• ( ) - Grouping

Usage

To use the regex engine, create an instance of the RegexEngine class with a regular expression as a constructor parameter. Look at the examples/ directory for usage examples.

Features

• Membership testing: The engine can test if a given string matches the regular expression.

Parsers

The regex engine includes a parser that converts regular expressions into an internal representation that can be used to construct the NFA. Two types of parsers are implemented:

• ONP (Reverse Polish Notation) parser
• AST (TODO) (Abstract Syntax Tree) parser

Both parsers can handle the allowed characters and features of the regex engine. An Abstract Syntax Tree (AST) is used to represent the structure of the regular expression, which is then used to construct the NFA.

Future Plans

• Support for more regex features such as character classes, quantifiers, and backreferences.
• Optimization of the NFA construction and matching algorithms for improved performance.

Building the Project

To build the project, you can use CMake. Follow these steps:

1. Clone the repository:

   git clone 

2. Navigate to the project directory:

   cd simple-regex-engine

3. Create a build directory and navigate into it:

    mkdir build
    cd build

4. Run CMake to configure the project:

   cmake ..

5. Build the project using Make:

   make

Author - Mateusz Wojaczek