How to Build a RegEx Engine in Python (Part 1: The Grammar)
Tags: python, programming, regex, coding
Published: 2021-05-23 21:47:59

In this series of articles, we will follow the steps to build a RegEx Engine in Python. I chose **Python** over the many alternatives for a few reasons:

1.  It is well integrated with the Linux command line
2.  Because yes.

In a way, I find Python to be a “less verbose version of Java” and a “less confusing version of JavaScript”, which were the other two alternatives I considered.

Please let me explain before get mad at me.  
Before starting this project I had no idea how things should be done, how to code the various modules, and so on.  
I had to figure everything out by myself.

And, when I don’t know how to do things exactly, I find JS a bit too confusing, it’s just a feeling, not a universal truth, and I find that with Java I can organize my ideas better.

But, since I don’t like how verbose and limiting Java is in some way, but wanted classes, and I love having functions as first-class citizens, Python seemed like the perfect blend to me.

Anyway, it’s now time to start with the project itself.

---

What We Need
============

To match a string with a regular expression of our will we need to complete a few steps:

1.  **understand** the regular expression
2.  create an **internal representation** of it (so that we can see if a passed string match with it)
3.  **match** the string with the regex, using the internal representation we built of it.

To complete the _first two steps_ we need two components:

*   a **Lexer** (or scanner) to parse the regex in tokens (“words”, generic “pieces of information”). As an example in the sentence “I am beautiful, very beautiful” each word (“I”, “am”, …) is a token of type “word” and the comma is a token of type “punctuation”
*   a **Parser** which read all the tokens in sequence and “understands” them, building while doing so an internal representation of the regex (which will be a tree, called Abstract Syntax Tree, AST for the friends).

To accomplish the _third step_ we need to build a component able to take as input the AST built by the Parser and a string, and visiting the tree to match each leaf of the tree with some part of the string (and something more, we will discuss later).  
This component is named:

*   **Engine**.

---

The Roadmap
===========

So, now that we know the modules we will have to code, let’s build a roadmap:

1.  _define the_ RegEx _grammar_ we want to recognize
2.  _build the lexer_
3.  _build the parser_
4.  _build the engine_
5.  **_enjoy_**.

---

The Grammar
===========

It’s now time to discuss the **grammar** we want to recognize.

I assume you know what a formal grammar is and that you understand the _EBNF_ notation, if not, _DON’T PANIC_, google it.

The regex grammar we will recognize is the following:

![The grammar.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/z41uvy6ncr1seo530nzm.png)

Top-level production _RE ::= RE\_SEQ_ is indeed useless but is there because I used it in one of the early versions of the project and I was too lazy to remove it later. Anyway, it is completely harmless, I promise, and it will cost you just a couple of lines of code and only one more call on the stack during execution.

The Grammar Explained
---------------------

The features that the described grammar will be able to implement are the following:

So, valid regexes are:

<img alt="" class="t u v ku aj" src="https://miro.medium.com/max/3108/1\*pg7KhpwIY84iy9hq0dkiyQ.png" width="1554" height="558" srcSet="https://miro.medium.com/max/552/1\*pg7KhpwIY84iy9hq0dkiyQ.png 276w, https://miro.medium.com/max/1104/1\*pg7KhpwIY84iy9hq0dkiyQ.png 552w, https://miro.medium.com/max/1280/1\*pg7KhpwIY84iy9hq0dkiyQ.png 640w, https://miro.medium.com/max/1400/1\*pg7KhpwIY84iy9hq0dkiyQ.png 700w" sizes="700px" role="presentation"/>

Examples of recognized regexes.

---

Conclusion
==========

You can browse the code of the final result [here](https://github.com/lorenzofelletti/pyregex).

I think that can be enough for the first part, more in the next articles of the series.

In the _next article_, we will set up the environment and start coding, starting from the lexer.

See you soon! I hope you _enjoyed_ this read!

Please feel free to reply if you don’t understand something, need some hints, whatever. I’ll be glad to answer you.

---

Cover Image by <a href="https://unsplash.com/@pankajpatel?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Pankaj Patel</a> on <a href="https://unsplash.com/s/photos/json?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>