Regex compiler

Thompson's algorithm for parsing regular expressions

Steps:

• parse infix to postfix
• compile postfix to NFA
• walk nfa with input

Supported grammars:

• |
• ( )
• *

Example:

regex := "abc*(ab)"

postfix := compiler.Re2post(regex)
nfa := compiler.Post2nfa([]rune(postfix))

compiler.MatchRe(nfa, "abcccab") // => true
compiler.MatchRe(nfa, "abccc") // => false

Inspired by Regular Expression Matching Can Be Simple And Fast by Russ Cox