Nine out of ten times when we reach for regular expressions its because we want to simply know "does this text contain this pattern?". A simple boolean expression: yes or no. Sometimes we want to know the position of the entire match, as in lexic
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