10 ms·
Writing a Compiler is Surprisingly Easy (part 1)
- mati365 3y ago* compiler without optimization phase
- TheChaplain 3y agoProbably adheres to the principle; "Make it work, then make it fast"
- kevindamm 3y agoIt's actually three steps: make it, make it work, make it work faster. this may actually be somewhere between step one and two.
- phtrivier 3y agoIf I read the article correctly, it's actually "a compiler for a language that only supports basic arithmetic, without a lexer, a parser, symbols, nor an optimization phase". Which _is_ surprisingly easy to write. But it might be a stretch to call it "a compiler" :D
- cmrdporcupine 3y agoYeah, I've written stuff like this many times -- mostly producing AST then bytecode, etc. I never really wanted to call it a 'compiler' per se though that's what it is. Because I generally stand in awe of serious optimizing compiler engineers, they have deep domain expertise that is admirable.
- mattgreenrocks 3y agoTrue, but no need to self-gatekeep the terminology here just to appease a rando commenter. :)
- ozim 3y agoYes draw two circles and then the rest of the owl kind of thing.
- eichin 3y agoEh, a college friend put together a C compiler in 100 lines of yacc (not particularly golfed, either, C just isn't that sophisticated.) Great for playing with "what if C + this one feature" kind of things in a concrete way. So from my perspective, not a stretch at all...
- sebastianmestre 3y agoParsing and symbol resolution on simple languages is kinda trivial in my opinion, but I'll probably write some articles about that stuff later Control flow and pointers are coming in the next part, and it's still surprisingly easy
- phtrivier 3y agoIs memory / register allocation in your roadmap too ? (honest question, I'm not sure it's in the scope of your articles)
- sebastianmestre 3y agoRegister allocation is not on the roadmap, I think it's too hard for this series... But maybe I just haven't figured out an easy enough way to do it yet :^) Memory allocation? You mean making a heap allocator? In the spirit of lowering the bar for creating new languages, I lean more towards calling into libc's malloc instead of building a custom solution haha
- acchow 3y ago* compiler without good error messages
- musicale 3y agoClang may have better static checking, but Apple's MPW C compiler still had better error messages. https://news.ycombinator.com/item?id=37283375 https://news.ycombinator.com/item?id=37283375
- deleted 3y ago[deleted]
- acchow 3y agoCute and whimsical, but I was thinking along the lines of context for answering "why?" "..because it was defined at [....] and used [....] and [...] as a int32 type (thus coerced to int64), but passed in [...] as a"
- zem 3y agoif you use the nanopass approach you can add optimisation phases relatively easily
- agumonkey 3y agobut since he hardcodes the register allocation, i wonder how he can control anything here
- mepian 3y agoAs opposed to a tree-walking interpreter, which is usually presented as the only viable way to write your first programming language implementation.
- mamcx 3y agoAka: a compiler. A compiler is just `source -> generate -> target`. All the other fancy things are optional. IMPORTANT things, but don't detract from calling it a "compiler". --- This is similar to anything else: A single `.html` served on `:80` is a website. A 2d, grayscale `pacman` is a videogame. `print("hello world")` is a program, etc.
- aatd86 3y agoAka a function tongue-in-cheek :p
- deleted 3y ago[deleted]
- FeepingCreature 3y agoIf you cared about performance, you'd feed it into LLVM anyways.
- t14n 3y agoI like the sentiment of the title, even if it gets people riled up. I'm fondly reminded of the introduction from Bob Nystrom's _Crafting Interpreter_ [1] > This last reason is hard for me to admit, because it’s so close to my heart. Ever since I learned to program as a kid, I felt there was something magical about languages. When I first tapped out BASIC programs one key at a time I couldn’t conceive how BASIC itself was made. > Later, the mixture of awe and terror on my college friends’ faces when talking about their compilers class was enough to convince me language hackers were a different breed of human—some sort of wizards granted privileged access to arcane arts. > It’s a charming image, but it has a darker side. I didn’t feel like a wizard, so I was left thinking I lacked some inborn quality necessary to join the cabal. Though I’ve been fascinated by languages ever since I doodled made-up keywords in my school notebook, it took me decades to muster the courage to try to really learn them. That “magical” quality, that sense of exclusivity, excluded me. > And its practitioners don’t hesitate to play up this image. Two of the seminal texts on programming languages feature a dragon and a wizard on their covers. > When I did finally start cobbling together my own little interpreters, I quickly learned that, of course, there is no magic at all. It’s just code, and the people who hack on languages are just people. > There are a few techniques you don’t often encounter outside of languages, and some parts are a little difficult. But not more difficult than other obstacles you’ve overcome. My hope is that if you’ve felt intimidated by languages and this book helps you overcome that fear, maybe I’ll leave you just a tiny bit braver than you were before. 1: https://craftinginterpreters.com/ https://craftinginterpreters.com/
- deleted 3y ago[deleted]
- musicale 3y agoI like this approach, but why not take it one step further toward Turbo Pascal and generate the opcodes? ;-)
- sebastianmestre 3y agoAuthor here. I wanted to get the bar for writing a compiler as low as possible, and emitting assembly code seemed better in that regard. Also I don't have time to learn x86 instruction encoding right now :(
- musicale 3y agoThanks for the response! I was joking a bit (though not entirely - I really like dynamic code generators and am inspired by tiny, powerful systems) but as I mentioned I like the approach and hope that you get the chance to finish the series.
- JohnMakin 3y agoWho needs a lexer, a parser, and an AST when you can just explicitly feed the tokens into a switch statement that completely falls through if it runs into something it doesn't recognize? This is super easy! Sorry, I am by no means a compiler expert, but spent enough years in study of them and taken enough stabs at writing my own that this take is hopelessly naive, and I really hope the author realizes it.
- mianos 3y agoI have written multiple compilers, from C-like interpreters to protobuffer like compilers over the years, all in production, some still. Not doing a finite state machine for any stream interpretation is a huge mistake, just as much as it is outside of the compiler tokenisation, such as protocol decoders and even just parsing config files. edit: There is a well known book with a dragon on it, but I first learnt from The Unix Programming Environment, by Brian W. Kernighan and Rob Pike. In just a few pages they clearly explain how to write an basic calculator like this, that generates intermediate code to run on a stack based interpreter. I started with this and expanded it to emit assembly for an arcane DG machine. I know that code generated ran for at least 20 years. Kinda surreal as nothing lasts that long usually.
- musicale 3y agoCould you elaborate on what you mean by that? To me this looks like a code generation library, an approach I like because of its concreteness and adaptability (for example, if we changed it to emit opcodes then it could be used for dynamic code generation, which has many fun and interesting applications.) Also this post is aimed at the author's imagined teenage self. Does that change anything?
- mianos 3y agoWhen writing a compiler you want to first look at what you expect and when you get that, what to expect next. If that does not come, where do you go? We call this a graph, but there is no need to confuse things with advanced terms.
- kragen 3y agoa problem that a lot of these series run into is that the author runs out of steam before they finish writing them. crenshaw's otherwise excellent series suffers from this, for example so far the author of this one has only written the first chapter i've written a few didactic compilers that are complete enough to compile themselves, though not complete enough to compile anything else; these may be of more interest to someone who's looking for how to make writing a compiler surprisingly easy, though they do lack the extensive explanatory text in the linked blog post - http://canonical.org/~kragen/sw/urscheme http://canonical.org/~kragen/sw/urscheme (from a subset of scheme to at&t-syntax i386 assembly, 1553 lines of code) - https://github.com/kragen/stoneknifeforth https://github.com/kragen/stoneknifeforth (from a forth-like language to an i386 linux elf executable, 132 lines of code) - https://github.com/kragen/peg-bootstrap/blob/master/peg.md https://github.com/kragen/peg-bootstrap/blob/master/peg.md (from a peg grammar with semantic actions to javascript, 66 lines of code) - https://github.com/kragen/peg-bootstrap/blob/master/handaxeweb.md https://github.com/kragen/peg-bootstrap/blob/master/handaxew... (tangles a literate program in virtually any plain-text format, such as markdown, html, restructuredtext, or tex, into virtually any plain-text programming language, 208 lines of code; used to tangle both itself and the peg compiler compiler above) - http://canonical.org/~kragen/sw/dev3/meta5ix.m5 http://canonical.org/~kragen/sw/dev3/meta5ix.m5 (from meta5ix, a language for writing parsers derived from val schorre's meta-ii, to meta5ix assembly, 18 lines of code; it is a top-down parsing language with limited backtracking, like pegs, but less expressive and implementable without heap allocation or the ability to backtrack past the beginning of a line; see http://canonical.org/~kragen/sw/dev3/meta5ixrun.py http://canonical.org/~kragen/sw/dev3/meta5ixrun.py for an m5asm interpreter) - http://canonical.org/~kragen/sw/dev3/meta5ix2c2.m5 http://canonical.org/~kragen/sw/dev3/meta5ix2c2.m5 (from a slightly different variation of meta5ix to c, 133 lines of code) most of these do take the same ast-free approach as the linked blog post and crenshaw, just emitting code as they finish parsing a production (or, in the case of stoneknifeforth, a token), but ur-scheme in particular does not; it uses scheme s-expressions as its syntax tree, because some kind of syntax tree is necessary to be able to allocate some local variables on the stack while also supporting closures. peg-bootstrap can certainly handle code that builds an ast with its semantic actions, but its implementation of itself just glues together snippets of javascript text also worth mentioning in this connection: - darius bacon's work, especially parson (for example, https://github.com/darius/parson/blob/master/eg_calc_compile.py https://github.com/darius/parson/blob/master/eg_calc_compile...) - the oberon compiler in wirth and gutknecht's oberon book - the later chapters of sicp
- pklausler 3y agoWriting a toy compiler for one sane input language and one target platform is indeed surprisingly easy, and very educational. I had to do this back in the 90's for C when the O/S SW group I worked for needed to start work on a UNIX port to a new proprietary architecture (simulator) and the company's compiler group wasn't getting anything started any time soon. It took maybe 3-4 KLOC to get a boring old recursive descent parser and simple code generator working well enough to compile a minimal kernel configuration and pass a compiler self-replication test. The most interesting bit was actually the preprocessor.
- mr_toad 3y agoWriting a compiler was part of the undergraduate compsci curriculum back where I did it. I still have vague memories of ancient tools like Flex and Bison (and I’m puzzled that the author seems to be hand-rolling code rather than use existing tooling).
- badsectoracula 3y agoAFAIK nowadays it is more common to write a recursive descent parser to build whatever structure you want to work with (if not use the parsing directly) than rely on Flex/Bison. Personally i've written so many parsers over the years that the code for writing one "flows" naturally and i feel like Flex/Bison would introduce complexity and dependencies for no gain.
- jakobson14 3y agoThose Dodekalogue people are laughing.
- kragen 3y agoit introduces knowing where the ambiguities are in your grammar and eliminates large classes of parsing bugs it's also dramatically easier for other people to understand
- 3y ago
- gigel82 3y agoThat's... not a compiler. It's a small part of a compiler backend (code generator).
- ww520 3y agoWriting a compiler is not too difficult. Most of the techniques and procedures are well researched and documented. The best thing is that you can pick the parts that are useful and stop instead of implementing the full blown end to end pipeline. Recently in an app, instead of supporting the bare minimum I wanted to support a bit more sophisticated search expression, like embedded commands and compounded conditional expression. I just hand-rolled the lexical tokenizer and the parser, and stopped without going the full mile. The tokenizer used simple regex to break up the terms and tagged them with token types. Came up with a grammar for the mini language. The parser used the standard recursive descent parsing technique on the grammar production. It's simple to handle errors and do auto-completion of the missing syntax because the parser knew what to expect at the point of error and could fill in the default nodes in the tree as needed. The generated AST was enough to implement the search tree and the embedded commands. The whole thing was only couple files and done in couple days, but it's very useful for the app.
- 13of40 3y agoI wrote a parser/interpreter for VBA a few years back, and even though the core concepts were straightforward, conforming to a language that had been in development for decades turned out to be brain-wreckingly tedious. One of the biggest parts of it was a block of thousands(?) of conditional statements to figure out the result type of every combination of type+operator+type. At the end of the ordeal, though, I threw the engine into a test app that looked like GWBASIC, and got a little nostalgia kick from being able to run BASIC like it was 1983.
- sancarn 3y agoIs that really needed? You can use VBA to do all the heavy lifting. That's what we do here: https://github.com/sancarn/stdVBA/blob/master/src/stdLambda.cls#L939-L962 https://github.com/sancarn/stdVBA/blob/master/src/stdLambda....
- tomcam 3y agoThat and there were never official grammars published for any version of any basic from Microsoft afaik
- tester756 3y agoYet it is more and more time consuming the closer you want to get to the real world compilers
- armchairhacker 3y agoIt gets harder when you try to deviate from the norm of “40 years of research and experience, and this has survived 40 years for a reason”
- bachmeier 3y agoThe nice thing about real world compilers is that they already exist. You can write your own compiler for situations where you need to do other things. If you need performance, compile to a language with a high-performance compiler.
- deleted 3y ago[deleted]
- deleted 3y ago[deleted]
- RagnarD 3y agoPlaying chess is easy. Playing good chess - not so much. Playing world class chess - good luck.
- atan2 3y agoSometimes people just want to learn how to play chess, and that's ok.
- blt 3y agoBut a lot of programmers think compilers are magic. Maybe because they read about stuff like parser generators, register allocators, optimizations, etc., that are not strictly necessary. It's empowering to remind people that a seemingly hard task is within their reach.
- lawn 3y agoPeople always think that what they dont understand is magic, and when they do understand it they think its simple. For example: React, Operating Systems, AI, CSS and assembly.
- RagnarD 3y agoTo elaborate, I've written a number of compilers in years past. I highly recommend it as an exercise in learning about parsing, code emission, etc. Anything that gets a developer closer to understanding that process, rather than a mystery black box, is a very good thing. So I'm not trying to be a downer, just noting that it can rapidly become an extremely complex task to make an excellent compiler which includes end user expected code optimizations, informative error messages, syntax error recovery, etc.
- userbinator 3y agoWe will store that intermediate value in the stack, and read it back after the right term is done computing. If we take care that the code we generate for the right term doesn't write into the same stack slot, then we can be sure that the value will be preserved. There are push and pop instructions which are perfectly suited to this nested value use. In the past, lamenting how many compilers don't seem to realise that (and the fact that push/pop are specially optimised on x86 via hardware known as the stack engine), I wrote a piece of a code generator with similar capabilities to the one in this article as a proof-of-concept, and with the addition of some trivial (rotating FIFO-like) register allocation, was able to generate surprisingly compact and fast code that looks like it could've been written by a human Asm programmer. I believe Crenshaw's famous compiler tutorial also makes the same simplification, and it's also a powerful generalisation since it means that arbitrarily deep nested expressions can be compiled, as long as there is sufficient stack space.
- kragen 3y agocrenshaw mostly just emits pushes and pops; he recommends a simpler version of that rotating fifo technique (just spilling deeply nested values onto the stack so you get a performance cliff, instead of pushing old values out of the fifo) but doesn't actually show it in ur-scheme i just pushed and popped, getting performance much less terrible than i expected, but still probably a third of the performance the rotating fifo register allocator would give
- sebastianmestre 3y ago> There are push and pop instructions which are perfectly suited to this nested value use. In the past, lamenting how many compilers don't seem to realise that (and the fact that push/pop are specially optimised on x86 via hardware known as the stack engine) That's fair, but in the article I also store local variables relative to %rsp, so I wouldn't want it changing at all I could use %rbp for that instead, but then I'd have to explain it in the article :^)
- userbinator 3y agoThat's fair, but in the article I also store local variables relative to %rsp, so I wouldn't want it changing at all You only need to keep track of how much you've put on the stack (which can be a single counter) and adjust the offsets appropriately. But then you'd have to explain that too...
- duped 3y agoI wish there were a standard cross platform assembler library in C for x86, ARM, and WASM. Because frankly writing an asm text generator and shelling out to GCC or NASM is really annoying, and it feels like something so foundational should just exist. I get there's yasm, and libnasm, and asmjit, and libgccjit, and llvm, etc but they're all varying degrees of "bad" for the purposes of a simple code generator for someone that doesn't want to dig through ARM and Intel's developer docs.
- lelanthran 3y ago> I wish there were a standard cross platform assembler library in C for x86, ARM, and WASM. Because frankly writing an asm text generator and shelling out to GCC or NASM is really annoying, and it feels like something so foundational should just exist. It does, it's called C :-) > I get there's yasm, and libnasm, and asmjit, and libgccjit, and llvm, etc but they're all varying degrees of "bad" for the purposes of a simple code generator for someone that doesn't want to dig through ARM and Intel's developer docs. This is only for language developers who aren't writing in C, right? Because if you're writing in C, what would you use this assembler for? Anything a cross-platform assembler emits is going to be portable, so it's only going to be as performant as C is, so why not just emit C? Having a C library that emits C might be a nice thing to have - then all the other languages can emit "code" that is cross-platform.
- duped 3y agoC is not assembler nor is it close to assembler nor is it desirable to have a C compiler in your toolchain to compile something that needs assembler For example, C has a calling convention. It has a notion of a stack and heap. Certain things like arbitrary control flow, threading, and process spawning cannot be expressed in C. It has a memory model that you must adhere to. If you actually want to implement a programming language, C is not sufficient as a transpilation target except for mostly trivial designs.
- kragen 3y agoworks pretty well most of the time; chicken scheme even compiles call/cc to c
- sebastianmestre 3y agoWow! My blog made the HN front page! I've been lurking for a while but only now made an account :^)
- kragen 3y agothanks for writing it! i look forward to seeing future installments
- kvemkon 3y agoThanks for your article. Perhaps (after some more parts) you'd like to compare how tinycc (tcc) [1] differs from your approach. In case tcc would be more complex, is it only due to dealing with C or because of any general issues. [1] https://repo.or.cz/tinycc.git https://repo.or.cz/tinycc.git
- jojobas 3y agoThe 2014 (doesn't time fly) edition of the ICFP Programming Contest had participants make a Pacman brain, deliverable in SECD machine assembly, and ghost brains, deliverable in a simple microcontroller assembly. Most teams, ours included, wrote 2 (probably rather crappy) compilers in 3 days. https://en.wikipedia.org/wiki/ICFP_Programming_Contest https://en.wikipedia.org/wiki/ICFP_Programming_Contest https://en.wikipedia.org/wiki/SECD_machine https://en.wikipedia.org/wiki/SECD_machine
- Animats 3y agoWirth's classic recursive descent Pascal compiler in his 1976 book Algorithms + Data Structures = Programs is a basic compiler for a somewhat useful language. That's kind of dated. What's a modern equivalent?
- bartekpacia 3y agoCrafting Interpreters?
- ramon156 3y agoI'd argue that crafting interpreters is becoming dated as well. There are modern alternatives that could make the process a lot more streamline. Would love a rewrite!
- GuestHNUser 3y agoCould you expand on what alternatives you prefer? I'm not sure what is dated about Crafting Interpreters (but I'm also not following the latest developments in the compiler space). Thorston Ball's Compiler and Interpreter book series is the only other book on the subject I find widely recommend and modern.
- codr7 3y agoIf you don't mind interpreters and/or swift, I'm working on a tutorial here: https://github.com/codr7/swift-interpreter https://github.com/codr7/swift-interpreter
- dna_polymerase 3y agoI keep recommending “Compiling to Assembly”, by Vladimir Keleshev: https://keleshev.com/compiling-to-assembly-from-scratch/ https://keleshev.com/compiling-to-assembly-from-scratch/ The author chose TypeScript for the Compiler, which makes it somewhat more accessible to these days programmers.
- Jtsummers 3y ago
- 7373737373 3y agoOne thing I haven't seen yet is how a compiler would keep track of types and emit the corresponding assembly
- FeepingCreature 3y agoclass Type { int size; } and then add methods for every conceivable type-dependent operation. Alternately, a sumtype or enum+pointer will also do. Then you just attach a type to every expression. At least, that's how you do it in a "forward-typed" language like C. In a language like Haskell it's a bit harder because your type assignment is a full graph, not a DAG like in C.
- rossant 3y ago"Writing a Compiler is Surprisingly Easy (part 1/72)" Joke aside, great work up! Thank you.
- carra 3y agoI can agree with that approach, because I used it to write a C compiler for a fantasy console I made (Vircon32). Since it has a fully custom ISA and set of chips I could not use something like LLVM, so I wrote it more "manually". The first versions were very barebones (they supported little more than variables, expressions and if/else), but over time I expanded it to support loops, arrays, pointers, structures... nowadays it's still not a full C compiler but it has been good enough for me to write several full games reliably, and even a few people have been using it too.
- FeepingCreature 3y agoHave written compilers, can confirm. For parsing especially using recursive descent is surprisingly pleasant, even in something badly suited like C.
- HarHarVeryFunny 3y agoWriting a toy compiler is easy enough - often given as a comp. sci. student exercise. Writing a highly optimizing standards compliant one, one with dozens of real world constraints is another story, especially if you are writing the whole thing and not building atop of something like LLVM. It's a bit like saying that building a rocket is no big deal, and wanting others to assume you've built a space shuttle when really it's a hobby rocket.
- red-iron-pine 3y agoi'd have phrased it more like building a shed vs. building a mansion or shopping mall. you can learn a lot of basics building a shed -- pouring concrete, adding spaces for wiring, drainage, etc. -- but ultimately it's just a small one off for learning.
- elegantlie 3y agoExactly this, the complexity of a production compiler project is its sheer vastness. Hundreds to thousands of language features need to work together in a performant and correct manner. Plus, the language itself is probably less than 15% of the work. You'll need a build system, a standard library, a code formatter, a syntax highlighter, support for incremental and cached builds, helpful error messages, bindings for a systems language like C, among other things.
- zackangelo 3y agoMy first introduction to this subject was “Let’s Build a Compiler” by Jack Crenshaw. Even though it’s quite old now, I still highly recommend if you’re looking for a gentle, no-frills introduction: https://compilers.iecc.com/crenshaw/ https://compilers.iecc.com/crenshaw/
- deleted 3y ago[deleted]
- cmmon 3y agoI did not understood the stack part. Lets say the slot value is 2, instruction for this would be to move the value located at %rsp-24, into the %rax register. So your instruction becomes mov -24(%rsp), %rax Correct?
- sebastianmestre 3y agoThat's right!
- deleted 3y ago[deleted]