7 ms·

Writing a C Compiler, Part 1

369 points by sidcool 9y ago

bitshiffed 9y ago
Can't wait for the next parts of this! I think this incremental approach must be the way to do it. I was inspired by 8cc to write my own C compiler; but I ended up burnt out on that project. (The standard document is just infuriating. There's so much ambiguity and disorganization in the document, and the actual technical specifications are like an afterthought to the novel of text.) May be time to get back into it!
tptacek 9y ago
A way to do this more directly and without dealing with any assembly syntax and at a deeper level is to compile down to an emulation of a straightforward machine (I really like MSP430 for this), preferably to an emulator you write. Having had the pleasure of writing a couple emulators and a couple compilers at this point: the emulator is easier than the compiler, by a lot. Relative to parsing and emitting code, emulating a straightforward architecture is easy. This is a great post!
- B4TMAN 9y ago
  Any reference(s) where I can read more about writing emulators?
  - deleted 9y ago
    [deleted]
  - wglb 9y ago
    Here is one https://fms.komkon.org/EMUL8/HOWTO.html https://fms.komkon.org/EMUL8/HOWTO.html I found quickly. Writing an emulator is almost as much fun as writing a compiler. And when you are done, you will have another level of appreciation of how computers work.
  - carussell 9y ago
    Wirth came up with a simple RISC architecture for his compiler book. There's an emulator[1] for it, written by Peter De Wachter. Michael Schierl adapted Peter's emulator code into Java and JS. You can run it here: http://schierlm.github.io/OberonEmulator/ http://schierlm.github.io/OberonEmulator/ I sent a bunch of patches to rework the in-browser emulator a couple weeks ago. If you don't know C, I recommend reading through the JS emulator's source. (View source should suffice—it's all unminified vanilla JS; there's no opinionated JS framework involved.) With it running in the browser, the emulator frontend treats the web platform as its widget toolkit. The code to interface with that is in webdriver.js[2] and takes about 1000 lines of code. The CPU and memory operations themselves are implemented in risc.js[3] and only take about 1/3 that. To follow along with instruction fetching/decoding/execution, you'll need to understand the ISA. There's a good 3-page overview linked from projectoberon.com under the title "RISC Architecture"[4]. A more in-depth description of the design is also available[5]. I have some tentative work for a machine-code level debugger online[6]. It's unfinished, however, so it comes with no documentation and the toolbar icons are missing. (There are tooltips, however.) So you can play with it if you feel like watching the registers and flags change while stepping through machine instructions. 1. https://github.com/pdewacht/oberon-risc-emu/ https://github.com/pdewacht/oberon-risc-emu/ 2. https://github.com/schierlm/OberonEmulator/blob/master/JS/webdriver.js https://github.com/schierlm/OberonEmulator/blob/master/JS/we... 3. https://github.com/schierlm/OberonEmulator/blob/master/JS/risc.js https://github.com/schierlm/OberonEmulator/blob/master/JS/ri... 4. https://www.inf.ethz.ch/personal/wirth/FPGA-relatedWork/RISC-Arch.pdf https://www.inf.ethz.ch/personal/wirth/FPGA-relatedWork/RISC... 5. https://www.inf.ethz.ch/personal/wirth/FPGA-relatedWork/RISC.pdf https://www.inf.ethz.ch/personal/wirth/FPGA-relatedWork/RISC... 6. https://www.colbyrussell.com/staging/aubergine/emu.html?image=oberon&width=1024&height=768&debug=true https://www.colbyrussell.com/staging/aubergine/emu.html?imag...
- DSMan195276 9y ago
  I agree completely, and I would add that the compiler doesn't even need to compile down to a system/architecture that actually exists. You can make your own simple 'architecture' with a minimal list of instructions that wouldn't require much more then a loop and some switch statements to emulate, and you're free to design it in any way to make your life easier. For an architecture that's designed to be targeted by C, you likely don't even need registers and could just use memory operands for everything.
  - SAI_Peregrinus 9y ago
    There's also a reasonable chance that if you're interested in compiler design and making an architecture you're the sort of person who would enjoy learning a hardware description language. With a cheap FPGA dev board you could then implement your toy architecture and run your compiled programs on that. This adds substantial difficulty to the project, but is damn fun.
- meadori 9y ago
  > is to compile down to an emulation of a straightforward machine (I really like MSP430 for this) What exactly do you mean by this? Direct object code emission? > the emulator is easier than the compiler, by a lot Yeah, definite +1 there. For most simple machines it really is not much more than a loop with a switch on the opcode where the cases update the CPU state.
  - tptacek 9y ago
    Yes: just spit out opcodes.
- kerkeslager 9y ago
  Yet another approach which I have used in Fur (https://github.com/kerkeslager/fur https://github.com/kerkeslager/fur) is to compile to a low(er)-level programming language (in the case of Fur, I'm compiling to C). These approaches aren't just for toy languages. Java/C#/Python standard implementations compile to byte code that runs on virtual machines. Glasgow Haskell Compiler compiles to C--, and a bunch of languages compile to JavaScript.
- pjmlp 9y ago
  The approach taken at my compiler course was one that I consider the best one for toy compilers, but it does mean having to deal with Assembly. Do the generation to some kind of byte code as you are suggesting, but using an instruction format that be used as macro calls in macro assemblers. Then just write the macros for each bytecode, doesn't matter matter if the register usage is bad, goal is just to have a plain native executable that runs.
tomcam 9y ago
Love it. This is exactly how I wrote compilers for a living back in the day – I always got the minimum in end-to-end demo running because it was always the best way to avoid ugly surprises.
anton_gogolev 9y ago
Check out http://www.craftinginterpreters.com http://www.craftinginterpreters.com for something more in-depth.
margorczynski 9y ago
To someone who knows more about the subject - am I correct that actually encoding/parsing the language is a small part of creating a compiler comparing to AST optimization? Optimizing e.g. C to create much more optimal Assembly (especially using some more non-standard instructions) seems like a much more daunting task
- foxhill 9y ago
  absolutely. that's why llvm exists - you write the front end (the comparitvely easy part), emit non-optimised llvm-ir - llvm does the hard optimisations.
- bluetomcat 9y ago
  Lexing, parsing and generating the AST are comparatively straightforward and a very small part of a real optimising compiler. The hard stuff is everything related to the code generation – register allocation, instruction selection and scheduling, dealing with any peculiarities of the target ISA and microarchitecture, etc. Your goal here is to preserve the semantics of the HLL constructs while emitting the optimal sequence of instructions for the CPU to execute.
- barrkel 9y ago
  It depends on your source and target. The two parts are practically different disciplines. If you target llvm or naive assembly as output, most of your work will be in translating semantics, and depending on the language complexity, there can be a lot to implement. Or not that much, in simple languages like C. The back end is mostly about transforms that preserve meaning, with a long tail of attempts to prove things about the code to make things faster in certain cases. You can also have languages with complex front ends that need lots of work, whether it's preserving runtime type information (a big serialisation job that's not strictly back end work), interesting type systems that also are trying to prove things about the code, features that require increasingly elaborate transformations before they can be handed off to any common back end (like closures, iterators, async, continuation passing style).
- tom_mellior 9y ago
  As others have said, yes, that's mostly the case. Even parsing C and elaborating it to a correctly typed AST is not quite as simple as others are making it out to be, though. Getting all the implicit type conversions correct is not completely trivial, and is a popular source of bugs (see some examples in http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf for instance). There are also some annoying ambiguities in the grammar and in name resolution rules that mean that sometimes it's not easy to tell whether something is supposed to be a type name or a variable name: https://jhjourdan.mketjh.fr/pdf/jourdan2017simple.pdf https://jhjourdan.mketjh.fr/pdf/jourdan2017simple.pdf C is a "simple" language in many senses of the word, but it has a lot of complex details. It's fine to gloss over them when writing a compiler for a language very similar to C for learning purposes, but getting everything just right for actual C is tough.
jHackenthal 9y ago
East this covered 15 years ago
pjmlp 9y ago
Anyone that wants to write C compilers has two good books for it. "A Retargetable C Compiler: Design and Implementation", from David R. Hanson and Christopher W. Fraser "Compiler Design in C", from by Allen I. Holub A bit old, but there are not significant changes to C since they were written, other than optimizers taking advantage of UB.
- Majora320 9y ago
  I read that as "A Regrettable C Compiler"
oldandtired 9y ago
I find that the assumption that program control requires boolean values (of any kind) facinating, since there are at least two languages that use success/failure as the controlling mechanism - Snobol (in all its incarnations) with the follow up language of Icon/UnIcon. Neither have the concept of booleans, but use the idea that a computation can succeed and return a result or fail and return no result. This leads to making certain kinds of expressions that normally require booleans and the associated logical operators to be simpler and more clear, as below: if a < b && b < c && c < d then ... compared with if a < b < c < d then .... Which is easier to mentally parse?
- cpeterso 9y ago
  I really liked how Icon handles function success/failure separately from return values. It seems very close to Go's error handling conventions, but with a little more magic. Wikipedia gives the following Icon example code: if a := read() then write(a) which would translate into something like the following Go code: a, err := read() if err == nil { write(a) }
  - oldandtired 9y ago
    Simplify this to write(a := read()) where write will not be executed if read fails, nor will a have any value assigned to it. Failure is an option and not an error. So to copy standard input to standard output, we do every write(read()) At the end of file, the read fails, the write fails and then the every fails and on you go.
pulsarpietro 9y ago
At uni I went through a module on compilers which basically covered all the Dragon book. I then followed this on-line course where you actually write a compiler for the COOL language. It has been one of the best educative things I've ever done in my life and I can't help recommending it. https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about https://lagunita.stanford.edu/courses/Engineering/Compilers/... I'd love to do something like that in my professional career but unfortunately 90% of the time I ended up carrying out way less interesting work (writing application for end users).
- jasim 9y ago
  There's no better advertisement for the utility of learning to write a compiler than this introduction from the excellent "Engineering a Compiler" by Cooper and Torczon: Why Study Compiler Construction? A compiler is a large, complex program. Compilers often include hundreds of thousands, if not millions, of lines of code, organized into multiple subsystems and components. The various parts of a compiler interact in complex ways. Design decisions made for one part of the compiler have important ramifications for other parts. Thus, the design and implementation of a compiler is a substantial exercise in software engineering. A good compiler contains a microcosm of computer science. It makes practical use of greedy algorithms (register allocation), heuristic search techniques (list scheduling), graph algorithms (dead-code elimination), dynamic programming (instruction selection), finite automata and push-down automata (scanning and parsing), and fixed-point algorithms (data-flow analysis). It deals with problems such as dynamic allocation, synchronization, naming, locality, memory hierarchy management, and pipeline scheduling. Few software systems bring together as many complex and diverse components. Working inside a compiler provides practical experience in software engineering that is hard to obtain with smaller, less intricate systems.
  - Someone 9y ago
    ”A compiler is a large, complex program” Writing a compiler isn’t much harder than writing an interpreter, if at all. Assuming your language can be parsed without running it (Perl, for instance, cannot, in general. See https://www.perlmonks.org/?node_id=663393 https://www.perlmonks.org/?node_id=663393), it is just a matter of doing that and emitting code for every statement, plus some bookkeeping in order to fix up branches. If the language you are compiling is simple, that’s not hard to do. The result will not be the fastest possible, but it will be compiled code, and it will be faster (sometimes significantly so) than interpreting the program.
userbinator 9y ago
I really like Ghuloum’s approach: you start by compiling a tiny, trivial subset of your source language all the way down to x86 assembly. Then you add new language features, one step at a time. In step one, you just return constants; in a later step you handle addition and subtraction; and so on. Every step is small enough to feel manageable, and at the end of the every step you have a working compiler. That approach sounds like the same one in Jack Crenshaw's very lucid tutorial: https://compilers.iecc.com/crenshaw/ https://compilers.iecc.com/crenshaw/ He uses Pascal to write a Pascal compiler, but the basic steps seem to be the same --- start with a very simple lexer, add pieces to it incrementally, then write a recursive-descent parser on top of that and gradually extend it to handle more of the language. Another simplification that really helps, once you're used to recursive descent and have noticed that the functions for each operator/precedence level are very similar, is to refactor them into a lookup table and an even simpler function that uses it, creating "precedence climbing": https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm That makes it very easy to add/change/extend operators, or even have them be user-defined(!) and dynamically modifiable. As a demonstration of how absolutely tiny a compiler can be, this one is worth inspecting carefully --- it also uses a handwritten lexer and recursive-descent parser, but doesn't make an AST and just emits code for a stack VM: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 ...and someone modified that one to make an x86 JIT: https://news.ycombinator.com/item?id=8746054 https://news.ycombinator.com/item?id=8746054
- jsteemann 9y ago
  I remember reading Jack Crenshaw's "let's build a compiler" tutorial in the 90's. Though pretty outdated, I can definitely recommend it to everyone interested in compiler construction, because it's written from the perspective of, well, a compiler creator.
bollu 9y ago
Most compiler tutorials show how to write a compiler, but now how to write an optimising compiler. In fact, it's not that much harder, and is a nice walkthrough in some very cool ideas in graph theory, dataflow analysis,etc. Which is why I've been writing a mini-LLVM in haskell as a tutorial to explain optimising compiler construction: [Tiny optimising compiler](https://github.com/bollu/tiny-optimising-compiler https://github.com/bollu/tiny-optimising-compiler)
- DannyB2 9y ago
  There is something to be said for having LOTS and LOTS of non optimizing C compilers written in many languages. Even languages like, say, Python. And plenty of C compilers written in C. A virtue of being non-optimizing is that they are easier to study and verify correct operation. What we need is that the source code for the smaller number of optimizing compilers can be compiled by the many, many different inefficient C compilers. We need to be sure that the binary of the optimizing compiler is not compromised by the compiler which compiled the optimizing compiler. You could compile compilers. Including compiling various compilers written in C. At some point you compile the wanted optimizing compiler's source using various different compilers generated through various chains of compilation. Those binaries of the optimizing compiler may all differ, but the code generated by those multiple binary versions of the optimizing compiler should be identical. Finally use the uncompromised optimizing compiler to compile itself. In fact, using the multiple binaries of the optimizing compiler to compile itself and be sure they all produced the same final binary. Cross compilation doesn't hurt either. For example a Raspbery Pi compiles the optimizing compiler for x86-64. The binary of that compiler should still match the same compiler compiled from other C compilers. Now we not only have to be paranoid about the binary of a compiler being compromised by another compiler, but by the Intel Management Engine. Compromise baked right into the hardware. Every paranoid thing I thought ten years ago turned out to be true.
  - xigency 9y ago
    See Ken Thompson's award speech where he talks about the original C compiler backdoor: http://wiki.c2.com/?TheKenThompsonHack http://wiki.c2.com/?TheKenThompsonHack http://vxer.org/lib/pdf/Reflections%20on%20Trusting%20Trust.pdf http://vxer.org/lib/pdf/Reflections%20on%20Trusting%20Trust....
jokoon 9y ago
I would be more interested in learning how to write a transpiler... As long as I can compile a language in C, it removes a lot of work.
- pjmlp 9y ago
  That is just a compiler whose backend generates code in another language instead of machine code.
  - jokoon 9y ago
    Well I find it more interesting... Also C compilers can do a lot of micro optimizations that are not trivial, so compiling something to C or maybe LLIR seems like a better choice.
    - pjmlp 9y ago
      That is usually a fallacy, that only looks simple as first step. The first issue is the impedance mismatch between the original language semantics and what is possible to represent in C. Two examples are tail calls and continuations, that are hard to get right at C level, either requiring compiler extensions, longjmp/setjmp tricks, or a little bit of assembly. Then there is the whole issue with undefined behaviour in C, introducing bugs that didn't exist on the original code. Even if the generated code is clean today regarding UB, you cannot ensure that a new C compiler version won't be introducing such issues. Having said this, there are languages like Eiffel and Nim, whose main backend relies on C compilers, instead of compiling directly to pure native code. Skipping Objective-C and C++ here, because although they started as C pre-processors, their code was to be an extension to C and so their semantics also imply C semantics. Compiling to some kind of IR, like LLIR is more sane. Then you can do whatever you want with it, generate code in another programming language, machine code, or a plain interpreter for bootstrapping purposes.
      - zakk 9y ago
        I agree with most of your points, but... > Even if the generated code is clean today regarding UB, you cannot ensure that a new C compiler version won't be introducing such issues. This is not correct. Undefined behaviour is specified in the standard, and a good compiler-to-C will always generate UB-free code.
CalChris 9y ago
> You also need to decide whether to write your own parser and lexer or use automatic parser and scanner generators (e.g. flex and bison). Really? There are much better choices available in 2017. ANTRL 4 leaps to mind which has been in development since 1989.
- chubot 9y ago
  ANTLR is really only good for the Java ecosystem. The quality of the generated C/C++ code is low and it has a large number of dependencies. C++ development also lagged pretty far behind Java when ANTLR 4 was released. I don't know of any "real" language written in C or C++ that uses ANTLR. The state of the art for production languages in C/C++ is either hand-written parsers or yacc/bison. I've never even seen flex used, and I've looked at over 20 lexer/parser implementations for "real" languages.
  - CalChris 9y ago
    Java, C#, Go, Python, JavaScript, Swift and C++ although everything gets started with Java and filled out to the other targets. You may be thinking of ANTRL 3. I really didn't much care for the ANTLR 3 C target but I use ANTRL 4 and its C target. It is really much much better than ANTRL 3. TParr says ANTLR 4 is the parser generator he always wanted to make. However, I'm not still pitching ANTRL as a parser for a real compiler. ANTRL rules the world for little languages, domain specific languages but a production language would almost certainly would use a hand crafted recursive decent compiler. This is a learning project. So I'd strongly recommend anyone learn modern tools and methods and learn those. bison is C++ native with experimental Java support and nothing else. flex is C and C++ only. Not a fan.
- pjmlp 9y ago
  Another good one is JavaCC, but not at the same level as ANTRL.
jokoon 9y ago
The "recursive descent parsing" part is not very well explained or thorough. It doesn't have good example... I still enjoyed reading it though. EDIT: I've the recursive descent parsing article on wikipedia, and I'm amazed how the C code example is missing parts... Kinda sad.
komali2 9y ago
Discussion for part 2: https://news.ycombinator.com/item?id=15861788 https://news.ycombinator.com/item?id=15861788

369 points by sidcool 9y ago

Can't wait for the next parts of this! I think this incremental approach must be the way to do it. I was inspired by 8cc to write my own C compiler; but I ended up burnt out on that project. (The standard document is just infuriating. There's so much ambiguity and disorganization in the document, and the actual technical specifications are like an afterthought to the novel of text.) May be time to get back into it!

tptacek 9y ago

A way to do this more directly and without dealing with any assembly syntax and at a deeper level is to compile down to an emulation of a straightforward machine (I really like MSP430 for this), preferably to an emulator you write. Having had the pleasure of writing a couple emulators and a couple compilers at this point: the emulator is easier than the compiler, by a lot. Relative to parsing and emitting code, emulating a straightforward architecture is easy. This is a great post!

B4TMAN 9y ago
Any reference(s) where I can read more about writing emulators?
- deleted 9y ago
  [deleted]
- wglb 9y ago
  Here is one https://fms.komkon.org/EMUL8/HOWTO.html https://fms.komkon.org/EMUL8/HOWTO.html I found quickly. Writing an emulator is almost as much fun as writing a compiler. And when you are done, you will have another level of appreciation of how computers work.
- carussell 9y ago
  Wirth came up with a simple RISC architecture for his compiler book. There's an emulator[1] for it, written by Peter De Wachter. Michael Schierl adapted Peter's emulator code into Java and JS. You can run it here: http://schierlm.github.io/OberonEmulator/ http://schierlm.github.io/OberonEmulator/ I sent a bunch of patches to rework the in-browser emulator a couple weeks ago. If you don't know C, I recommend reading through the JS emulator's source. (View source should suffice—it's all unminified vanilla JS; there's no opinionated JS framework involved.) With it running in the browser, the emulator frontend treats the web platform as its widget toolkit. The code to interface with that is in webdriver.js[2] and takes about 1000 lines of code. The CPU and memory operations themselves are implemented in risc.js[3] and only take about 1/3 that. To follow along with instruction fetching/decoding/execution, you'll need to understand the ISA. There's a good 3-page overview linked from projectoberon.com under the title "RISC Architecture"[4]. A more in-depth description of the design is also available[5]. I have some tentative work for a machine-code level debugger online[6]. It's unfinished, however, so it comes with no documentation and the toolbar icons are missing. (There are tooltips, however.) So you can play with it if you feel like watching the registers and flags change while stepping through machine instructions. 1. https://github.com/pdewacht/oberon-risc-emu/ https://github.com/pdewacht/oberon-risc-emu/ 2. https://github.com/schierlm/OberonEmulator/blob/master/JS/webdriver.js https://github.com/schierlm/OberonEmulator/blob/master/JS/we... 3. https://github.com/schierlm/OberonEmulator/blob/master/JS/risc.js https://github.com/schierlm/OberonEmulator/blob/master/JS/ri... 4. https://www.inf.ethz.ch/personal/wirth/FPGA-relatedWork/RISC-Arch.pdf https://www.inf.ethz.ch/personal/wirth/FPGA-relatedWork/RISC... 5. https://www.inf.ethz.ch/personal/wirth/FPGA-relatedWork/RISC.pdf https://www.inf.ethz.ch/personal/wirth/FPGA-relatedWork/RISC... 6. https://www.colbyrussell.com/staging/aubergine/emu.html?image=oberon&width=1024&height=768&debug=true https://www.colbyrussell.com/staging/aubergine/emu.html?imag...
DSMan195276 9y ago
I agree completely, and I would add that the compiler doesn't even need to compile down to a system/architecture that actually exists. You can make your own simple 'architecture' with a minimal list of instructions that wouldn't require much more then a loop and some switch statements to emulate, and you're free to design it in any way to make your life easier. For an architecture that's designed to be targeted by C, you likely don't even need registers and could just use memory operands for everything.
- SAI_Peregrinus 9y ago
  There's also a reasonable chance that if you're interested in compiler design and making an architecture you're the sort of person who would enjoy learning a hardware description language. With a cheap FPGA dev board you could then implement your toy architecture and run your compiled programs on that. This adds substantial difficulty to the project, but is damn fun.
meadori 9y ago
> is to compile down to an emulation of a straightforward machine (I really like MSP430 for this) What exactly do you mean by this? Direct object code emission? > the emulator is easier than the compiler, by a lot Yeah, definite +1 there. For most simple machines it really is not much more than a loop with a switch on the opcode where the cases update the CPU state.
- tptacek 9y ago
  Yes: just spit out opcodes.
kerkeslager 9y ago
Yet another approach which I have used in Fur (https://github.com/kerkeslager/fur https://github.com/kerkeslager/fur) is to compile to a low(er)-level programming language (in the case of Fur, I'm compiling to C). These approaches aren't just for toy languages. Java/C#/Python standard implementations compile to byte code that runs on virtual machines. Glasgow Haskell Compiler compiles to C--, and a bunch of languages compile to JavaScript.
pjmlp 9y ago
The approach taken at my compiler course was one that I consider the best one for toy compilers, but it does mean having to deal with Assembly. Do the generation to some kind of byte code as you are suggesting, but using an instruction format that be used as macro calls in macro assemblers. Then just write the macros for each bytecode, doesn't matter matter if the register usage is bad, goal is just to have a plain native executable that runs.

tomcam 9y ago

Love it. This is exactly how I wrote compilers for a living back in the day – I always got the minimum in end-to-end demo running because it was always the best way to avoid ugly surprises.

anton_gogolev 9y ago

Check out http://www.craftinginterpreters.com http://www.craftinginterpreters.com for something more in-depth.

margorczynski 9y ago

To someone who knows more about the subject - am I correct that actually encoding/parsing the language is a small part of creating a compiler comparing to AST optimization? Optimizing e.g. C to create much more optimal Assembly (especially using some more non-standard instructions) seems like a much more daunting task

foxhill 9y ago
absolutely. that's why llvm exists - you write the front end (the comparitvely easy part), emit non-optimised llvm-ir - llvm does the hard optimisations.
bluetomcat 9y ago
Lexing, parsing and generating the AST are comparatively straightforward and a very small part of a real optimising compiler. The hard stuff is everything related to the code generation – register allocation, instruction selection and scheduling, dealing with any peculiarities of the target ISA and microarchitecture, etc. Your goal here is to preserve the semantics of the HLL constructs while emitting the optimal sequence of instructions for the CPU to execute.
barrkel 9y ago
It depends on your source and target. The two parts are practically different disciplines. If you target llvm or naive assembly as output, most of your work will be in translating semantics, and depending on the language complexity, there can be a lot to implement. Or not that much, in simple languages like C. The back end is mostly about transforms that preserve meaning, with a long tail of attempts to prove things about the code to make things faster in certain cases. You can also have languages with complex front ends that need lots of work, whether it's preserving runtime type information (a big serialisation job that's not strictly back end work), interesting type systems that also are trying to prove things about the code, features that require increasingly elaborate transformations before they can be handed off to any common back end (like closures, iterators, async, continuation passing style).
tom_mellior 9y ago
As others have said, yes, that's mostly the case. Even parsing C and elaborating it to a correctly typed AST is not quite as simple as others are making it out to be, though. Getting all the implicit type conversions correct is not completely trivial, and is a popular source of bugs (see some examples in http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf http://www.cs.utah.edu/~regehr/papers/pldi11-preprint.pdf for instance). There are also some annoying ambiguities in the grammar and in name resolution rules that mean that sometimes it's not easy to tell whether something is supposed to be a type name or a variable name: https://jhjourdan.mketjh.fr/pdf/jourdan2017simple.pdf https://jhjourdan.mketjh.fr/pdf/jourdan2017simple.pdf C is a "simple" language in many senses of the word, but it has a lot of complex details. It's fine to gloss over them when writing a compiler for a language very similar to C for learning purposes, but getting everything just right for actual C is tough.

jHackenthal 9y ago

East this covered 15 years ago

pjmlp 9y ago

Anyone that wants to write C compilers has two good books for it. "A Retargetable C Compiler: Design and Implementation", from David R. Hanson and Christopher W. Fraser "Compiler Design in C", from by Allen I. Holub A bit old, but there are not significant changes to C since they were written, other than optimizers taking advantage of UB.

Majora320 9y ago
I read that as "A Regrettable C Compiler"

oldandtired 9y ago

I find that the assumption that program control requires boolean values (of any kind) facinating, since there are at least two languages that use success/failure as the controlling mechanism - Snobol (in all its incarnations) with the follow up language of Icon/UnIcon. Neither have the concept of booleans, but use the idea that a computation can succeed and return a result or fail and return no result. This leads to making certain kinds of expressions that normally require booleans and the associated logical operators to be simpler and more clear, as below: if a < b && b < c && c < d then ... compared with if a < b < c < d then .... Which is easier to mentally parse?

cpeterso 9y ago
I really liked how Icon handles function success/failure separately from return values. It seems very close to Go's error handling conventions, but with a little more magic. Wikipedia gives the following Icon example code: if a := read() then write(a) which would translate into something like the following Go code: a, err := read() if err == nil { write(a) }
- oldandtired 9y ago
  Simplify this to write(a := read()) where write will not be executed if read fails, nor will a have any value assigned to it. Failure is an option and not an error. So to copy standard input to standard output, we do every write(read()) At the end of file, the read fails, the write fails and then the every fails and on you go.

pulsarpietro 9y ago

At uni I went through a module on compilers which basically covered all the Dragon book. I then followed this on-line course where you actually write a compiler for the COOL language. It has been one of the best educative things I've ever done in my life and I can't help recommending it. https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about https://lagunita.stanford.edu/courses/Engineering/Compilers/... I'd love to do something like that in my professional career but unfortunately 90% of the time I ended up carrying out way less interesting work (writing application for end users).

jasim 9y ago
There's no better advertisement for the utility of learning to write a compiler than this introduction from the excellent "Engineering a Compiler" by Cooper and Torczon: Why Study Compiler Construction? A compiler is a large, complex program. Compilers often include hundreds of thousands, if not millions, of lines of code, organized into multiple subsystems and components. The various parts of a compiler interact in complex ways. Design decisions made for one part of the compiler have important ramifications for other parts. Thus, the design and implementation of a compiler is a substantial exercise in software engineering. A good compiler contains a microcosm of computer science. It makes practical use of greedy algorithms (register allocation), heuristic search techniques (list scheduling), graph algorithms (dead-code elimination), dynamic programming (instruction selection), finite automata and push-down automata (scanning and parsing), and fixed-point algorithms (data-flow analysis). It deals with problems such as dynamic allocation, synchronization, naming, locality, memory hierarchy management, and pipeline scheduling. Few software systems bring together as many complex and diverse components. Working inside a compiler provides practical experience in software engineering that is hard to obtain with smaller, less intricate systems.
- Someone 9y ago
  ”A compiler is a large, complex program” Writing a compiler isn’t much harder than writing an interpreter, if at all. Assuming your language can be parsed without running it (Perl, for instance, cannot, in general. See https://www.perlmonks.org/?node_id=663393 https://www.perlmonks.org/?node_id=663393), it is just a matter of doing that and emitting code for every statement, plus some bookkeeping in order to fix up branches. If the language you are compiling is simple, that’s not hard to do. The result will not be the fastest possible, but it will be compiled code, and it will be faster (sometimes significantly so) than interpreting the program.

userbinator 9y ago

I really like Ghuloum’s approach: you start by compiling a tiny, trivial subset of your source language all the way down to x86 assembly. Then you add new language features, one step at a time. In step one, you just return constants; in a later step you handle addition and subtraction; and so on. Every step is small enough to feel manageable, and at the end of the every step you have a working compiler. That approach sounds like the same one in Jack Crenshaw's very lucid tutorial: https://compilers.iecc.com/crenshaw/ https://compilers.iecc.com/crenshaw/ He uses Pascal to write a Pascal compiler, but the basic steps seem to be the same --- start with a very simple lexer, add pieces to it incrementally, then write a recursive-descent parser on top of that and gradually extend it to handle more of the language. Another simplification that really helps, once you're used to recursive descent and have noticed that the functions for each operator/precedence level are very similar, is to refactor them into a lookup table and an even simpler function that uses it, creating "precedence climbing": https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm https://www.engr.mun.ca/~theo/Misc/exp_parsing.htm That makes it very easy to add/change/extend operators, or even have them be user-defined(!) and dynamically modifiable. As a demonstration of how absolutely tiny a compiler can be, this one is worth inspecting carefully --- it also uses a handwritten lexer and recursive-descent parser, but doesn't make an AST and just emits code for a stack VM: https://news.ycombinator.com/item?id=8558822 https://news.ycombinator.com/item?id=8558822 ...and someone modified that one to make an x86 JIT: https://news.ycombinator.com/item?id=8746054 https://news.ycombinator.com/item?id=8746054

jsteemann 9y ago
I remember reading Jack Crenshaw's "let's build a compiler" tutorial in the 90's. Though pretty outdated, I can definitely recommend it to everyone interested in compiler construction, because it's written from the perspective of, well, a compiler creator.

bollu 9y ago

Most compiler tutorials show how to write a compiler, but now how to write an optimising compiler. In fact, it's not that much harder, and is a nice walkthrough in some very cool ideas in graph theory, dataflow analysis,etc. Which is why I've been writing a mini-LLVM in haskell as a tutorial to explain optimising compiler construction: [Tiny optimising compiler](https://github.com/bollu/tiny-optimising-compiler https://github.com/bollu/tiny-optimising-compiler)

DannyB2 9y ago
There is something to be said for having LOTS and LOTS of non optimizing C compilers written in many languages. Even languages like, say, Python. And plenty of C compilers written in C. A virtue of being non-optimizing is that they are easier to study and verify correct operation. What we need is that the source code for the smaller number of optimizing compilers can be compiled by the many, many different inefficient C compilers. We need to be sure that the binary of the optimizing compiler is not compromised by the compiler which compiled the optimizing compiler. You could compile compilers. Including compiling various compilers written in C. At some point you compile the wanted optimizing compiler's source using various different compilers generated through various chains of compilation. Those binaries of the optimizing compiler may all differ, but the code generated by those multiple binary versions of the optimizing compiler should be identical. Finally use the uncompromised optimizing compiler to compile itself. In fact, using the multiple binaries of the optimizing compiler to compile itself and be sure they all produced the same final binary. Cross compilation doesn't hurt either. For example a Raspbery Pi compiles the optimizing compiler for x86-64. The binary of that compiler should still match the same compiler compiled from other C compilers. Now we not only have to be paranoid about the binary of a compiler being compromised by another compiler, but by the Intel Management Engine. Compromise baked right into the hardware. Every paranoid thing I thought ten years ago turned out to be true.
- xigency 9y ago
  See Ken Thompson's award speech where he talks about the original C compiler backdoor: http://wiki.c2.com/?TheKenThompsonHack http://wiki.c2.com/?TheKenThompsonHack http://vxer.org/lib/pdf/Reflections%20on%20Trusting%20Trust.pdf http://vxer.org/lib/pdf/Reflections%20on%20Trusting%20Trust....

jokoon 9y ago

I would be more interested in learning how to write a transpiler... As long as I can compile a language in C, it removes a lot of work.

pjmlp 9y ago
That is just a compiler whose backend generates code in another language instead of machine code.
- jokoon 9y ago
  Well I find it more interesting... Also C compilers can do a lot of micro optimizations that are not trivial, so compiling something to C or maybe LLIR seems like a better choice.
  - pjmlp 9y ago
    That is usually a fallacy, that only looks simple as first step. The first issue is the impedance mismatch between the original language semantics and what is possible to represent in C. Two examples are tail calls and continuations, that are hard to get right at C level, either requiring compiler extensions, longjmp/setjmp tricks, or a little bit of assembly. Then there is the whole issue with undefined behaviour in C, introducing bugs that didn't exist on the original code. Even if the generated code is clean today regarding UB, you cannot ensure that a new C compiler version won't be introducing such issues. Having said this, there are languages like Eiffel and Nim, whose main backend relies on C compilers, instead of compiling directly to pure native code. Skipping Objective-C and C++ here, because although they started as C pre-processors, their code was to be an extension to C and so their semantics also imply C semantics. Compiling to some kind of IR, like LLIR is more sane. Then you can do whatever you want with it, generate code in another programming language, machine code, or a plain interpreter for bootstrapping purposes.
    - zakk 9y ago
      I agree with most of your points, but... > Even if the generated code is clean today regarding UB, you cannot ensure that a new C compiler version won't be introducing such issues. This is not correct. Undefined behaviour is specified in the standard, and a good compiler-to-C will always generate UB-free code.

CalChris 9y ago

> You also need to decide whether to write your own parser and lexer or use automatic parser and scanner generators (e.g. flex and bison). Really? There are much better choices available in 2017. ANTRL 4 leaps to mind which has been in development since 1989.

chubot 9y ago
ANTLR is really only good for the Java ecosystem. The quality of the generated C/C++ code is low and it has a large number of dependencies. C++ development also lagged pretty far behind Java when ANTLR 4 was released. I don't know of any "real" language written in C or C++ that uses ANTLR. The state of the art for production languages in C/C++ is either hand-written parsers or yacc/bison. I've never even seen flex used, and I've looked at over 20 lexer/parser implementations for "real" languages.
- CalChris 9y ago
  Java, C#, Go, Python, JavaScript, Swift and C++ although everything gets started with Java and filled out to the other targets. You may be thinking of ANTRL 3. I really didn't much care for the ANTLR 3 C target but I use ANTRL 4 and its C target. It is really much much better than ANTRL 3. TParr says ANTLR 4 is the parser generator he always wanted to make. However, I'm not still pitching ANTRL as a parser for a real compiler. ANTRL rules the world for little languages, domain specific languages but a production language would almost certainly would use a hand crafted recursive decent compiler. This is a learning project. So I'd strongly recommend anyone learn modern tools and methods and learn those. bison is C++ native with experimental Java support and nothing else. flex is C and C++ only. Not a fan.
pjmlp 9y ago
Another good one is JavaCC, but not at the same level as ANTRL.

jokoon 9y ago

The "recursive descent parsing" part is not very well explained or thorough. It doesn't have good example... I still enjoyed reading it though. EDIT: I've the recursive descent parsing article on wikipedia, and I'm amazed how the C code example is missing parts... Kinda sad.

komali2 9y ago

Discussion for part 2: https://news.ycombinator.com/item?id=15861788 https://news.ycombinator.com/item?id=15861788