Re: Optimizing off-line Lua compiler

[Asger Ottar Alstrup <aalstrup@...>]

To build an optimising off-line Lua compiler, may I plug the lua2js project?

http://luaforge.net/projects/lua2js/

This contains a lexer and a parser, which is good enough to allow quite 
a bit of Lua code to be compiled to JS.

To get an optimising compiler to native code, you would need to do this:

1) Change the Lua2js parser to ignore comments, rather than preserve 
them to get the parser 100% correct. (This is trivial to do)

2) Find some language to compile to, which has an optimising compiler 
for your target. This could be C++, Java, C--, OCaml, SML, C# or what 
not. The trick is probably to find one which is pretty close to Lua 
semantics, since then the abstraction overhead is probably smaller. I 
think this is the hard part of the task.

3) Once found, design a way to convert each construct in Lua in your 
target language.

4) Implement a new back-end of Lua2js that emits that language. This is 
simple using the lua2js base, since it is built on Gentle, which is a 
high-level language for writing compilers.

5) Implement a runtime library in X.

6) Write a script that invokes your new Lua2X compiler, compiles the 
result with your optimising X compiler, and links the result with your 
runtime in X.

If you need to emit Lua byte-code, one approach is to check out the LLVM 
project. In this case, you would need to use C or C++ in step 2, since 
LLVM can compile those, and then make a separate compiler from LLVM 
byte-code to Lua byte-code. However, the mismatch between these worlds 
is probably so great that this compiler has to be very advanced to work.

A better approach is probably to choose Lua byte-code in step 2, and 
then add a step 3.5 where you implement your optimisations in Gentle. 
This is a lot of work.

The final approach is to implement the optimisations in the real Lua 
compiler, but since that is in C, while Lua2js is in Gentle, I think it 
after all would be simpler to it in Gentle, based on the assumption that 
you would need to introduce some middle representation, like SSA, or 
similar.

Regards,
Asger Ottar Alstrup