Creating a Regex Compiler/Parser - Research

Posted on 18 Dec, 2020
Making a regex parser/compiler is not simple as it sounds, here is the overview of the steps:
1.Convert the expression to Postfix notation.
While converting to postfix, you also need to handle Character Classes & Range Quantifiers. Tutorials on internet haven't done this. Read this for an insight on how to do this.
2.Convert the postfix in above step to AST.
3.Convert the AST to a state machine, preferably a NFA (non-deterministic finite automata)
Resources
​Regular Expression Matching Can Be Simple And Fast by Russ Cox
​Converting Regular Expressions to Postfix Notation with the Shunting-Yard Algorithm​
​Postfix to NFA using Thompson algorithm​
​Regex Compiler: Part 2​
​Regular Expressions Based on Nondeterministic Finite Automaton​
​Using NFA to evaluate regular expressions​
​How to implement regular expression NFA with character ranges?​
​Regex under the hood: Implementing a simple regex compiler in Go​
Last modified 5mo ago