I've mentioned before that when it comes to the implementation of regular expression matching, the conversation as it appears in the literature tends to begin with NFA's, gives a quick run down of Thompsons Construction, and ends at DFA's with
When it comes to implementing Finite State Automata picking a data structure with which to model the machine is an interesting problem. On the one hand the choice is obvious: Finite state machines be them deterministic or NFAs are generally viewed as d
In my past projects when needed I have always implemented AST building parsers for regular expressions bottom-up by using the shunting yard algorithm. I've covered the process of doing so in my post on Thompsons Construction. While this approach certai
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