Writing a compiler in Python using Lex, Yacc and LLVM
wiki.alcidesfonseca.com
wiki.alcidesfonseca.com
I've got the lexer and parser done, thanks to Parsec, and some basic C code generation as a sanity check. Now for the runtime LLVM code generation, to make it feel like an interpreter! Thanks, HN!
Here's a tutorial that uses it to parse a simplified Scheme: http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H...
-- Not true. modern compilers do a lot of optimization long before code generation, and you really want to have for example floating point to be behaving exactly like in target language - if you collapse operations on constants such as 1.0D + 4.0. And aside from optimization, lexer - it has to distinguish single-precision and double precision floats.
However, if you do not have the target datatype you dealing with during compilation, you are destined to simulate them.
Example: ((unsigned char) 2) + ((unsigned char)255) = 1
That is in C. In ruby you'll have to manually check for overflow, and do it for each operation. You can invent classes all kind of things, but why? Use a language with types, and the check will be done for you by you Core Duo.
You keep writing that like it's a hard thing to do. It isn't. More to the point, it's a small part of the whole problem.
I do compiler development every day, and I no longer touch low-level compilers. Everything I write is Boo (for my OS), Ruby (for my startup -- by far my favorite language for compiler dev, despite not liking it in general), or Python. As a result, I have far more maintainable code than the majority, and the code I output is incredibly well optimized.
Edit: To clarify, by 'support forms that are difficult to deal with ...' I mean things like using a pure S-exp structure. Rather than a traditional intermediary form, you can represent your compiler state as an S-exp and iteratively optimize and compile it. Standardizing around a form like that, when it's easy to deal with, greatly simplifies code. (This is actually the reason Ruby is my compiler language of choice these days.)
High-level languages for compilation are, 9 times out of 10, a better choice.
2. Having never used OCaml for compiler dev, I can't speak on this.
3. The lack of strong typing has no effect on the ability of Python or Ruby to handle compilation. Like the Lisp family, these are very, very flexible languages with strong benefits to compiler developers, and I wouldn't trade them for anything else I've used.
TBH, I think ML-based languages are poor choices for compiler development. You spend as much time worrying about your own code as you do the code you're compiling, which you just don't do when you write a compiler in Scheme, Ruby, or another 'dynamic' language.
Pattern matching is a great feature, and it's available in all of the languages I mentioned. It's a built-in in Boo, there are many libraries for it in Scheme, and I have my own Sexp pattern matching libraries for Python and Ruby. It may have come from the ML world, but it's by no means exclusive to it.
As for proving correctness, depending on the language to provide this is simply not realistic in compilers. You've got a much better shot at correctness by making your compiler easier to work on, IMO.
In theory, proving correctness is a good way to go. In the real world, it's not remotely viable.
During the compilation? Would you even see the difference if the compiler did 0.1*0.2 by emulating cpu processing, instead of via one instruction? The cost of register allocation for a simple function will be greater than optimising many constant fp expressions. It simply doesn't matter here. If you have a convenient type, you use it, if you don't, you download any libieee754 and interface with its functions...
Seriously - if you're writing a compiler, there are so many more important problems than lack of mapping between the target and local types :( It may not be an elegant solution to handle fp expression evaluation via an external library, but it's only done during the compile time (so only once) and it's easily solvable.
(Not that this would stop the GNU people. Have you seen the code from bison? They actually emit code for their own reimplementation of memcpy() on some platforms. They are fanatical about compatibility. Or they were last time I checked. Which was sometime during the 90s.)
No. You don't need that. You can treat your data however you want until you place it into the final binary. Before that, you can even treat all your numbers as strings if you really want to. If you need some constant expression evaluation, you just have to replicate the target machine's math operations in software - no magic involved here. As long as you get the right result, noone cares what you do internally.
If your compilation machine == target machine, you can even construct a function that calculates the expression and actually run it to get the result.
What makes you think everyone is out to write a C compiler?
Another example of performance-sensitive application of compilers is background Java compiler in Eclipse - even for rather small programs it has to be fast. Ruby is 10-100 (actually more than that) times slower than C/Java, So if you optimizer (wriiten in C/Java/Haskell) needs 0.5 second to optimize code, same code will need (by very optimistic measure) 30 sec. Python not much better. Scheme a bit better (especially Stalin compiler), Lisp almost good.
i.e. benchmarks or it didn't happen.
And do not forget by the way that Ruby is a memory hog.
http://shootout.alioth.debian.org/u32q/benchmark.php?test=al...
I appreciate your choice, but I'd myself do differently.
If you can't manage that, then, geeze, what kind of crappy programmer are you?