I suggest studying "A Regular Expression Matcher" by Rob Pike:

https://www.cs.princeton.edu/courses/archive/spr09/cos333/be...