Ken Thompson's famous paper on implementing regular expressions is surprisingly simple and yet extremely sophisticated at the same time. The "heart" of the method he proposed was the use of a stack in order to compile the expression to code that parses it, which in this case was IBM 7094 object code.
I find this idea beautiful, and wanted a chance to play around with it for myself, as well as demonstrate to anyone interested the way the algorithm works. Since the aim is demonstration rather than a concrete (or usable) implementation, it makes sense to compile to a high-level language, which is why I have started by targeting Go.
Comments
Ken Thompson's famous paper on implementing regular expressions is surprisingly simple and yet extremely sophisticated at the same time. The "heart" of the method he proposed was the use of a stack in order to compile the expression to code that parses it, which in this case was IBM 7094 object code.
I find this idea beautiful, and wanted a chance to play around with it for myself, as well as demonstrate to anyone interested the way the algorithm works. Since the aim is demonstration rather than a concrete (or usable) implementation, it makes sense to compile to a high-level language, which is why I have started by targeting Go.
All suggestions are welcome!