domingo, 17 de enero de 2016

Bootstrapped metacompiler using Perl5 and lua

I wrote a Shchorre's metaII implementation myself using perl regexes.

The whole code that is run is just a recursive regexp match against a string (/$bootstrap/ =~ /$program/), which makes it even more mindfucked than usual. It's a simple way to create recursive descent parser just using regexes and perl extended patterns.  The string that tries to match is a representation in meta-II of the very same syntax the string is written on.  Yes.  :-)

I'm taking advantage of the Perl5 extended pattern '(?{})' that runs perl code whenever the regex reaches that point.  The idea is pretty similar to how metaII outputs work themselves even syntax-wise, so I thought it was a nice way to implement it as it's using the same idea that is going to use metaII after being bootstrapped (sorry if this post is difficult to read, but I can't find easy ways to write about without it in clear non-chained-and-recursive-and-self-referent-way). 

To be able to run recursive regexes, we need what MJD calls a proxy parser which is just a delayed 'thunk' that will be evaled just at runtime. We can achieve it in the regex world with (??{}).

If you're not familiar with metacompilers, my advise is to google a bit about them, and find out about them. It's an amazing piece of technology.  Basically you can get a compiler build itself in very few lines of code, and then augment it step by step by modifying the rules it consumes, and creating a slightly more evolved copy of itself, that you can use as a stepping stone to create more advanced compilers.

I added a makefile that shows the process of compiling a compiler using itself and a description of itself.

Here's the repo where there  are more insights in the readme file. Also, check my other posts on metacompilers.