Writing a compiler in Python using Lex, Yacc and LLVM

http://wiki.alcidesfonseca.com/blog/writing-compiler-using-python-lex-yacc-and-llvm/

by Alcides • 17 years ago

67 43 17 years ago

wiki.alcidesfonseca.com

ilkhd216• 17 years ago

Impractical: 1) The compiler is gonna be very slow; 2) If you make compiler for low-level language, such as C you need precise correspondence between data types used in cpu, datatypes used in compiler's implementation language and datatypes in the target language.

pmorici2• 17 years ago

Did you read the post? The guy was writing this for an academic project where speed didn't matter and secondly he was using LLVM for code generation. low level details don't really come into play in compiler construction until the code generation step most of the work up to that point is text parsing, syntax checking, and AST creation. In other words tasks suited perfectly to a language like Python.

ilkhd216• 17 years ago

> low level details don't really come into play in compiler construction until the code generation

-- 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.

daeken6• 17 years ago

On the contrary. Compilers written in a high-level language are at a distinct advantage: they're easier to optimize (significantly so), easier to debug, and support forms that are difficult to deal with in a low(er)-level language like C or C++.

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.)

ilkhd216• 17 years ago

if you read carefully what I said, i never said that hig-level languages are bad - I said only this: 1) Compiler written in python, ruby and other "slow" (do not beleive that pyruby is slow?) languages going to take eternity to compile linux kernel. 2) You need to have _precise_ mapping between types in compiler and the language you implement. It is so important that gcc use a software library for floating point computation, otherwise you are locked-in wit you cpu's FP implementation and can not write cross-compilers.

judofyr• 17 years ago

May I ask you what tools you use in Ruby?

ilkhd216• 17 years ago

Ok, the discussion is becoming pointless: you like ruby for compiler construction. Well I'd rather use a language with proper tail recursion, algebraic data types, with pattern matching as a part of it, fast, strongly typed [I beleive algebraic types with pat. matching gives roughly same possibilities as does dyn. typing, for this task], with standard or at least big industrial backing behind - such as F# or Haskell. And at the end of the day get warm feeling that my code is "green" - does not waste joules, by working fast.

I appreciate your choice, but I'd myself do differently.

jerf• 17 years ago

Because as everybody knows, just as the correct way to learn about weightlifting is to jump straight to benching 350lbs, the correct way to learn compilers is to write a complete gcc replacement as your first project.

If you can't manage that, then, geeze, what kind of crappy programmer are you?

sketerpot2• 17 years ago

Inspired by this, I've started writing a compiler for a subset of Matlab. I'm sick of Matlab being an interpreted language year after year, and while I don't hope to change that, I can at least do a proof-of-concept to lend weight to my derision.

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!

maximilian2• 17 years ago

I've been fooling around with this idea for a good year now. I've never found the time, but I think about doing something like it all the time. If I come across free time after my thesis, I hope to write a simple typed matlab-like clone that targets llvm code (which supports vectors). To me it seems that there is a vacuum for a simple typed fast numerics language with native vector support. Writing numerics in Matlab is great, but if you ever have to loop, it ends up dog slow. Porting the code to C is usually not terribly difficult, but is always a big pain, but usually yields a factor 10x or more speedup which is pretty significant. It would seem that applied mathematicians and physicists around the world would love a new, modern and fast numerics language to replace coding in C/C++/Fortran.

ilkhd216• 17 years ago

Probably frontend can be taken from GNU Octave? Claims to be similar to Matlab...

maximilian2• 17 years ago

Could you post a link to Parsec. Quick googling didn't come up with any compiler tools. Thanks!

anatoly• 17 years ago

http://www.haskell.org/haskellwiki/Parsec

GeoJawDguJin• 17 years ago

It's a Haskell library: http://hackage.haskell.org/package/parsec

Here's a tutorial that uses it to parse a simplified Scheme: http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_H...

jwecker• 17 years ago

He mentioned that llvm-py documentation was lacking... I was going through it, seems pretty darn good to me (relatively). http://mdevan.nfshost.com/llvm-py/userguide.html

Writing a compiler in Python using Lex, Yacc and LLVM

Related Stories