This post was originally featured as a section of my post on implementing Thompsons Construction for NFA from a regular expression. Having since implemented several FA constructions, all of which utilized an AST representation of the given exp
In part one of this post I covered building and annotating an abstract syntax tree from a postfix regular expression, as well as populating the firstpos, lastpos, and followpos sets for each node in the AST is it relates to it's position in the regular
Quite frankly, I feel like I am breaking some unwritten rule by writing this post. There is so little information available on implementing this algorithm it would seem as if everyone who has managed to implement it all abide by some type
Regular expressions and NFA have been an active area of study in theoretical computer science since the late 1950's. As such, there is a large body of work exploring a multitude of ways to evaluate regular expressions for the purpose of pattern matchin
Regular expressions are a fantastic way to describe patterns in text. Thanks to the work of pioneers like Stephen Kleene we know that for any regular expression there is cooresponding finite automaton (FA) and vice versa. This is known as Kleenes Theor