6 ms·

Writing a compiler in Python using Lex, Yacc and LLVM

67 points by Alcides 17y ago

ilkhd2 17y 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.
- pmorici 17y 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.
  - ilkhd2 17y 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.
    - pmorici 17y ago
      If what you are saying is true and the language you write the compiler in needs to mirror the type properties of the target then there would be no cross compilers or new architectures or new languages because you would be stuck with the type semantics of your original platform. It doesn't make common sense let alone technical correctness.
      - ilkhd2 17y ago
        Of course it is true. And of course it does not make common sense - common sense usually made by brain/mind. If you cannot mirror properties of target machine - you cannot optimize code for that target - period. Any computatiuon made in compiler will be potentially different from the same, nonoptimized computation made in target. The more computations have been optimized in the compiler the bigger probabilty you'll get wildly different code. 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.
    - anamax 17y ago
      > you really want to have for example floating point to be behaving exactly like in target language 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.
- daeken 17y 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.)
  - ilkhd2 17y 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.
    - daeken 17y ago
      You said they were impractical, then went on to explain why. I then explained why they are not impractical. The speed I'll give you, but the type issue is nonsensical. GCC's use of a software FP implementation is in support of this. Regardless of the language, you'll need to have an FP implementation that matches the target, which is nearly always done in software. High-level languages for compilation are, 9 times out of 10, a better choice.
      - ilkhd2 17y ago
- jerf 17y 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?
sketerpot 17y 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!
- maximilian 17y 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.
  - ilkhd2 17y ago
    Probably frontend can be taken from GNU Octave? Claims to be similar to Matlab...
- maximilian 17y ago
  Could you post a link to Parsec. Quick googling didn't come up with any compiler tools. Thanks!
  - anatoly 17y ago
    http://www.haskell.org/haskellwiki/Parsec http://www.haskell.org/haskellwiki/Parsec
  - GeoJawDguJin 17y ago
jwecker 17y 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 http://mdevan.nfshost.com/llvm-py/userguide.html

67 points by Alcides 17y 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.

pmorici 17y 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.
- ilkhd2 17y 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.
  - pmorici 17y ago
    If what you are saying is true and the language you write the compiler in needs to mirror the type properties of the target then there would be no cross compilers or new architectures or new languages because you would be stuck with the type semantics of your original platform. It doesn't make common sense let alone technical correctness.
    - ilkhd2 17y ago
      Of course it is true. And of course it does not make common sense - common sense usually made by brain/mind. If you cannot mirror properties of target machine - you cannot optimize code for that target - period. Any computatiuon made in compiler will be potentially different from the same, nonoptimized computation made in target. The more computations have been optimized in the compiler the bigger probabilty you'll get wildly different code. 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.
  - anamax 17y ago
    > you really want to have for example floating point to be behaving exactly like in target language 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.
daeken 17y 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.)
- ilkhd2 17y 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.
  - daeken 17y ago
    You said they were impractical, then went on to explain why. I then explained why they are not impractical. The speed I'll give you, but the type issue is nonsensical. GCC's use of a software FP implementation is in support of this. Regardless of the language, you'll need to have an FP implementation that matches the target, which is nearly always done in software. High-level languages for compilation are, 9 times out of 10, a better choice.
    - ilkhd2 17y ago
jerf 17y 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?

sketerpot 17y 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!

maximilian 17y 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.
- ilkhd2 17y ago
  Probably frontend can be taken from GNU Octave? Claims to be similar to Matlab...
maximilian 17y ago
Could you post a link to Parsec. Quick googling didn't come up with any compiler tools. Thanks!
- anatoly 17y ago
  http://www.haskell.org/haskellwiki/Parsec http://www.haskell.org/haskellwiki/Parsec
- GeoJawDguJin 17y ago

jwecker 17y 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 http://mdevan.nfshost.com/llvm-py/userguide.html