7 ms·

Writing Your Own Toy Compiler Using Flex, Bison and LLVM

96 points by sha90 17y ago

mikedouglas 17y ago
Many of the best articles posted here have very few comments. I wonder if news.yc's promotion algorithm could be altered to reflect this.
- asdlfj2sd33 17y ago
  Yeah, that's what happens when actually have some competence, and thus you know that you know very little AND you also know the crowd here will call your BS on these subject. Oh but politics or other crap like that will fill with comments right quick.
  - mahmud 17y ago
    [Summary: read this paper instead http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf] The article is both acceptable and appreciated, but not good. There are far better, not to mention easier ways to start hacking a compiler quickly than doing it with Flex/Bison/LLVM and in C++. Look at this over engineering: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/4/ http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/4/ A compiler should be written as a fluid, jelly-like organism; you will be changing it so much and so often, it's a waste of time to introduce any structure like that to it so early. The only place where you need a heavy design is the intermediate representation; and to this extent, you want the most flexible "design", if you can get away with Lisp-like S-expressions, by all means do it. You will be annotating the intermediate representation in multiple phases, so don't hesitate to copy deeply instead of mutating it with surgery. Don't bother with an elaborate symbol table design, just use the cheapest/easiest hash-table you can find. Keep your IR human readable or you will be forced to write binary analysis tools before you even settle on an IR format (horrible chicken and egg problem; and that's what you get when you model your IR with a giant C union .. you know, that trick, don't do it!) For the last 20+ years, Schemers have been losing their voices preaching the trivialization of compiler hacking. Listen to them; Schemers live in a parallel universe to the mainstream compiler community, which still, even if they don't know it, are hard at work improving the first Fortran compiler. Have fun!
    - abecedarius 17y ago
      I also like Kragen's Ur-Scheme as a concrete readably-small example of a self-hosted compiler to x86, inspired by the Ghuloum paper you reference. [At http://www.canonical.org/~kragen/sw/urscheme/ http://www.canonical.org/~kragen/sw/urscheme/ ]
    - Dobbs 17y ago
      Sadly we don't all have these options. The project I'm working on right now, a prototype DSL for writing counters to check data, can't be written in a fancy language like ML, Haskell or hell even Python. They don't want any "weird languages" that someone else will have to maintain once I leave. So C/Lex/Yacc it is.
      - cema 17y ago
        What about Clojure? It's a lisp and can be used the Scheme way. At the same time, it runs in Java virtual machine and therefore can be controlled directly from Java. That is, your legacy code can be written so that it can be maintained by Java programmers (this is to sell it to "them".)
        theBobMcCormick 17y ago
        That might work if their concern is deployment of his code. But if their concern is actually maintenance (you know, patches, updates, bug fixes), than I don't see how Clojure, Scala, JPython, etc. would be any more acceptable. The concern is probably having legacy code in a language that nobody else on staff knows how to program in.
        cema 17y ago
        Correct: they will not be able to program in clojure. But they should be able to interop java with the classes created in clojure. No REPL environment and all code compiled is a requirement for this kind of legacy work, but it can be done easily. (Or "should" be done easily.)
      - mahmud 17y ago
- kqr2 17y ago
  One of the reasons why I like HN is that for a good article, you don't get a ton of one-liner "that's cool", "awesome", etc. type comments.
- deleted 17y ago
  [deleted]
mahmud 17y ago
For the record, I think it's a terrible idea to keep prototyping compilers in C in this day and age. There is already a DSL for compiler construction and it's called Standard ML. SML/NJ, along with the New Jersey Machine Toolkit, Ramsey and Fernandez' excellent binary-frobbing-utility framework (yes! tools that generate profilers, debuggers, tracers, assemblers and disassemblers!) along with stuff from the SUIF project, you can start writing very sophisticated industrial compilers in fraction of the time it takes to debug just the front-end stuff in C. Even Perl, or your scripting language of choice, is better than C for compiler hacking. http://suif.stanford.edu/papers/ http://suif.stanford.edu/papers/ http://www.cs.tufts.edu/~nr/toolkit/ http://www.cs.tufts.edu/~nr/toolkit/ (devour Norman Ramsey's site and read his joint papers with Mary Fernandez; him, along with Monica Lam at Stanford, the Rice people Linda Torczon, Keith Kooper et al. are producing some of the most accessible tools and papers and certainly most exciting. The Rice group is also responsible for the best introductory compiler hacking text in recent publication: Engineering a Compiler. GET IT! If even just for the carefully curated bibliography. Also, recently, the ACM PLDI published a list of 20 most influential papers in programming languages design and implementation: http://www.cs.utexas.edu/users/mckinley/20-years.html http://www.cs.utexas.edu/users/mckinley/20-years.html I took the time to scrape as many of them as I could off of the internet, wherever they were freely available (i.e. author's websites) and I can say I have 18 of them. I would love to share them with hungry minds in one tarball, or they can google the papers individually: A Data Locality Optimizing Algorithm.pdf A Safe Approximate Algorithm for Interprocedural Pointer Aliasing.pdf An Evaluation of Staged Run-Time Optimizations in DyC.pdf An Implementation of Lazy Code Motion for SUIF.pdf Analysis of Pointers and Structures.pdf Balanced Scheduling- Instruction Scheduling When Memory Latency is Uncertain.pdf Complete Removal of Redundant Expressions.pdf Global Register Allocation at Link Time.pdf How To Read Floating Point Numbers Accurately.pdf Improving Register Allocation for Subscripted Variables.pdf Interprocedural Constant Propagation.pdf Interprocedural Slicing Using Dependence Graphs.pdf Lazy Code Motion.pdf On-The-Fly Detection of Access Anomalies.pdf Register Windows vs. Register Allocation.pdf Soft Typing.pdf Software Pipelining-- An Effective Scheduling Technique for VLIW Machines.pdf The Design and Implementation of a Certifying Compiler.pdf
- ilyak 17y ago
  Well, you can write your own guideline on how to prototype a language in SML, post it to NH, and profit. Now we don't see your guideline but do see Flex/Bison/LLVM one.
liuliu 17y ago
one advantage of bison is that it gets rid of global variables. However, Flex still uses global variables to pass state. Thus, using Flex is damaging the good part of bison (thread-safe).
- cconstantine 17y ago
  Do you have a recommendation for a Flex replacement?
- nostrademons 17y ago
  Umm, both flex and bison can be either reentrant or not, and the default for both is "not reentrant". You need to specify '%option reentrant' in your flex scanner, and '%define api.pure' in your bison parser. The signature changes, naturally - yylex takes pointers to yylval and yylloc that it's supposed to fill in. It's not terribly complicated, but the documentation for it sucks. I've got both my flex lexer and bison parser wrapped in a C++ class, which parses string input, handles all memory management by itself, and hides all the other implementation details from the outside world. I didn't use the built-in C++ wrappers, which suck, but it wasn't hard to throw a few C data structures inside a C++ class and call a few C functions from C++ methods.
a-priori 17y ago
If anyone's interested in a similar project written in Haskell, a few months back I wrote a compiler for C-Minus, which has a similar syntax. It uses Parsec for the front-end and a custom backend that targets a simple virtual machine (this was a school project), so no LLVM unfortunately. An LLVM-based backend wouldn't be cool to add though. Anyways, I figured someone may find it interesting. http://github.com/michaelmelanson/cminus-compiler http://github.com/michaelmelanson/cminus-compiler
- sketerpot 17y ago
  I notice that Haskell has LLVM bindings, and Parsec makes writing parsers remarkably non-painful. http://augustss.blogspot.com/2009/01/llvm-llvm-low-level-virtual-machine-is.html http://augustss.blogspot.com/2009/01/llvm-llvm-low-level-vir...
  - a-priori 17y ago
    Oh, that'll teach me to double-check my posts before I submit them. I meant to say that an LLVM backend wouldn't be hard to add (or, would be cool to add). Thanks for the link!

96 points by sha90 17y ago

Many of the best articles posted here have very few comments. I wonder if news.yc's promotion algorithm could be altered to reflect this.

asdlfj2sd33 17y ago
Yeah, that's what happens when actually have some competence, and thus you know that you know very little AND you also know the crowd here will call your BS on these subject. Oh but politics or other crap like that will fill with comments right quick.
- mahmud 17y ago
  [Summary: read this paper instead http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf] The article is both acceptable and appreciated, but not good. There are far better, not to mention easier ways to start hacking a compiler quickly than doing it with Flex/Bison/LLVM and in C++. Look at this over engineering: http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/4/ http://gnuu.org/2009/09/18/writing-your-own-toy-compiler/4/ A compiler should be written as a fluid, jelly-like organism; you will be changing it so much and so often, it's a waste of time to introduce any structure like that to it so early. The only place where you need a heavy design is the intermediate representation; and to this extent, you want the most flexible "design", if you can get away with Lisp-like S-expressions, by all means do it. You will be annotating the intermediate representation in multiple phases, so don't hesitate to copy deeply instead of mutating it with surgery. Don't bother with an elaborate symbol table design, just use the cheapest/easiest hash-table you can find. Keep your IR human readable or you will be forced to write binary analysis tools before you even settle on an IR format (horrible chicken and egg problem; and that's what you get when you model your IR with a giant C union .. you know, that trick, don't do it!) For the last 20+ years, Schemers have been losing their voices preaching the trivialization of compiler hacking. Listen to them; Schemers live in a parallel universe to the mainstream compiler community, which still, even if they don't know it, are hard at work improving the first Fortran compiler. Have fun!
  - abecedarius 17y ago
    I also like Kragen's Ur-Scheme as a concrete readably-small example of a self-hosted compiler to x86, inspired by the Ghuloum paper you reference. [At http://www.canonical.org/~kragen/sw/urscheme/ http://www.canonical.org/~kragen/sw/urscheme/ ]
  - Dobbs 17y ago
    Sadly we don't all have these options. The project I'm working on right now, a prototype DSL for writing counters to check data, can't be written in a fancy language like ML, Haskell or hell even Python. They don't want any "weird languages" that someone else will have to maintain once I leave. So C/Lex/Yacc it is.
    - cema 17y ago
      What about Clojure? It's a lisp and can be used the Scheme way. At the same time, it runs in Java virtual machine and therefore can be controlled directly from Java. That is, your legacy code can be written so that it can be maintained by Java programmers (this is to sell it to "them".)
      - theBobMcCormick 17y ago
        That might work if their concern is deployment of his code. But if their concern is actually maintenance (you know, patches, updates, bug fixes), than I don't see how Clojure, Scala, JPython, etc. would be any more acceptable. The concern is probably having legacy code in a language that nobody else on staff knows how to program in.
        cema 17y ago
        Correct: they will not be able to program in clojure. But they should be able to interop java with the classes created in clojure. No REPL environment and all code compiled is a requirement for this kind of legacy work, but it can be done easily. (Or "should" be done easily.)
    - mahmud 17y ago
kqr2 17y ago
One of the reasons why I like HN is that for a good article, you don't get a ton of one-liner "that's cool", "awesome", etc. type comments.
deleted 17y ago
[deleted]

mahmud 17y ago

For the record, I think it's a terrible idea to keep prototyping compilers in C in this day and age. There is already a DSL for compiler construction and it's called Standard ML. SML/NJ, along with the New Jersey Machine Toolkit, Ramsey and Fernandez' excellent binary-frobbing-utility framework (yes! tools that generate profilers, debuggers, tracers, assemblers and disassemblers!) along with stuff from the SUIF project, you can start writing very sophisticated industrial compilers in fraction of the time it takes to debug just the front-end stuff in C. Even Perl, or your scripting language of choice, is better than C for compiler hacking. http://suif.stanford.edu/papers/ http://suif.stanford.edu/papers/ http://www.cs.tufts.edu/~nr/toolkit/ http://www.cs.tufts.edu/~nr/toolkit/ (devour Norman Ramsey's site and read his joint papers with Mary Fernandez; him, along with Monica Lam at Stanford, the Rice people Linda Torczon, Keith Kooper et al. are producing some of the most accessible tools and papers and certainly most exciting. The Rice group is also responsible for the best introductory compiler hacking text in recent publication: Engineering a Compiler. GET IT! If even just for the carefully curated bibliography. Also, recently, the ACM PLDI published a list of 20 most influential papers in programming languages design and implementation: http://www.cs.utexas.edu/users/mckinley/20-years.html http://www.cs.utexas.edu/users/mckinley/20-years.html I took the time to scrape as many of them as I could off of the internet, wherever they were freely available (i.e. author's websites) and I can say I have 18 of them. I would love to share them with hungry minds in one tarball, or they can google the papers individually: A Data Locality Optimizing Algorithm.pdf A Safe Approximate Algorithm for Interprocedural Pointer Aliasing.pdf An Evaluation of Staged Run-Time Optimizations in DyC.pdf An Implementation of Lazy Code Motion for SUIF.pdf Analysis of Pointers and Structures.pdf Balanced Scheduling- Instruction Scheduling When Memory Latency is Uncertain.pdf Complete Removal of Redundant Expressions.pdf Global Register Allocation at Link Time.pdf How To Read Floating Point Numbers Accurately.pdf Improving Register Allocation for Subscripted Variables.pdf Interprocedural Constant Propagation.pdf Interprocedural Slicing Using Dependence Graphs.pdf Lazy Code Motion.pdf On-The-Fly Detection of Access Anomalies.pdf Register Windows vs. Register Allocation.pdf Soft Typing.pdf Software Pipelining-- An Effective Scheduling Technique for VLIW Machines.pdf The Design and Implementation of a Certifying Compiler.pdf

ilyak 17y ago
Well, you can write your own guideline on how to prototype a language in SML, post it to NH, and profit. Now we don't see your guideline but do see Flex/Bison/LLVM one.

liuliu 17y ago

one advantage of bison is that it gets rid of global variables. However, Flex still uses global variables to pass state. Thus, using Flex is damaging the good part of bison (thread-safe).

cconstantine 17y ago
Do you have a recommendation for a Flex replacement?
nostrademons 17y ago
Umm, both flex and bison can be either reentrant or not, and the default for both is "not reentrant". You need to specify '%option reentrant' in your flex scanner, and '%define api.pure' in your bison parser. The signature changes, naturally - yylex takes pointers to yylval and yylloc that it's supposed to fill in. It's not terribly complicated, but the documentation for it sucks. I've got both my flex lexer and bison parser wrapped in a C++ class, which parses string input, handles all memory management by itself, and hides all the other implementation details from the outside world. I didn't use the built-in C++ wrappers, which suck, but it wasn't hard to throw a few C data structures inside a C++ class and call a few C functions from C++ methods.

a-priori 17y ago

If anyone's interested in a similar project written in Haskell, a few months back I wrote a compiler for C-Minus, which has a similar syntax. It uses Parsec for the front-end and a custom backend that targets a simple virtual machine (this was a school project), so no LLVM unfortunately. An LLVM-based backend wouldn't be cool to add though. Anyways, I figured someone may find it interesting. http://github.com/michaelmelanson/cminus-compiler http://github.com/michaelmelanson/cminus-compiler

sketerpot 17y ago
I notice that Haskell has LLVM bindings, and Parsec makes writing parsers remarkably non-painful. http://augustss.blogspot.com/2009/01/llvm-llvm-low-level-virtual-machine-is.html http://augustss.blogspot.com/2009/01/llvm-llvm-low-level-vir...
- a-priori 17y ago
  Oh, that'll teach me to double-check my posts before I submit them. I meant to say that an LLVM backend wouldn't be hard to add (or, would be cool to add). Thanks for the link!