12 ms·
Writing a C Compiler: Build a Real Programming Language from Scratch
- shoggouth 2y agoIt also will be available via Amazon after August 20, 2024. https://www.amazon.com/Writing-Compiler-Programming-Language-Scratch/dp/1718500424/ https://www.amazon.com/Writing-Compiler-Programming-Language...
- quibono 2y agoI swear I've seen this cover before... is this a new release or an updated edition of an older book?
- orktes 2y agoMany compiler related books take inspiration from the "Dragon book" (Compilers: Principles, Techniques and Tools). So with likely lots of books with similar looking covers.
- hdbxbxndj 2y agoThe cover looks nothing like the dragon book however?
- orktes 2y agoPoint was more that there are bunch of compiler related books featuring a dragon (and knight/other character). The original also has a different looking dragon & knight themed cover for every edition. Like if I’d see the book on a shelf I would instantly guess it’s related to compilers. And I bet that’s completely intentional homage to the original.
- jdnendm 2y agoBook is not yet published but in early access since a couple of years Was featured here a couple of times. Unfortunately the timing of the release is quite unfortunate with regards to the summer holidays. Will take a look at it next year
- sgbeal 2y ago> Book is not yet published but in early access since a couple of years According to the top post's link, it was released in July 2024.
- hdbxbxndj 2y agoI seem to be mistaken. The 20th of August as listed by Amazon must be the European release date then
- byteplane 2y agoIt’s actually out now, I have a copy! Ordered directly fro No Starch Press.
- halfcat 2y ago”Automate the Boring Stuff with Python” has a similar cover, by the same publisher.
- Almondsetat 2y agoI believe the author first started by making blog posts and then interrupted them to simply make a book about it
- thejteam 2y agoThere was a HN article about the same book about a month ago: https://news.ycombinator.com/item?id=40940799 https://news.ycombinator.com/item?id=40940799 So maybe you saw it then.
- Coolbeanstoo 2y agoThis looks cool, been interested in learning more about compilers since I did the basics in college. Lots of things seem to focus on making interpreters and never make it to the code generation part so its nice to see that this features information about that.
- spinningslate 2y agoWith no disrespect to the book that's the subject of this thread as I haven't read it, but Bob Nystrom's Crafting Interpreter [0] is a fantastic book. It covers all phases in compilation, including both an interpreter and a VM. It's been covered on several threads here over the years [1]. [0]: https://craftinginterpreters.com/ https://craftinginterpreters.com/ [1]: https://hn.algolia.com/?q=crafting+interpreters https://hn.algolia.com/?q=crafting+interpreters
- jcpst 2y agoI remember seeing this a while back. That typesetting is beautiful. Thank you for bringing it up here, I might have to pick that one up. I’ve been bored with building line-of-business applications, despite designing for complex requirements in high-volume distributed systems. In fact I took a break from CS learning entirely 9 months ago. Even reading HN. I’ve been studying electronics and analog signal processing instead. But now that I’ve built about 50 guitar pedals of increasing complexity, I feel ready to switch back to CS studies again.
- agent281 2y agoThis book covers compiling to assembly whereas Crafting Interpreters only has a bytecode VM implementation. We'll see how good this book is when it drops, but I think that's a worthwhile feature that Crafting Interpreters punted on.
- i_don_t_know 2y agoSomewhat unrelated: Is there a book that walks you through building a database system from storage to queries, optimizer, execution, indexing, transactions, etc?
- gtirloni 2y agoRelated: https://news.ycombinator.com/item?id=27731896 https://news.ycombinator.com/item?id=27731896
- deleted 2y ago[deleted]
- rramadass 2y agoIn the early 90's Al Stevens wrote 2 books C Database Development and C++ Database Development with source code which might be a good starting point.
- myth_drannon 2y agoInteresting suggestion! here is the book on archive.org: https://archive.org/details/cdatabasedevelop00stev/mode/2up https://archive.org/details/cdatabasedevelop00stev/mode/2up
- kragen 2y agotransaction processing by gray (rip) and reuter was pretty close back in the 90s. i don't think it covered query optimization because it's really about tp monitors rather than databases, but, perhaps surprisingly, it does cover the other topics you're asking about
- rednab 2y agoDatabase Design and Implementation, ISBN 3030338355 ¹). Java source code for the SimpleDB system from the book available from the author's website ²). ¹) https://www.amazon.com/dp/3030338355/ https://www.amazon.com/dp/3030338355/ ²) http://www.cs.bc.edu/~sciore/simpledb/ http://www.cs.bc.edu/~sciore/simpledb/
- hasbot 2y agoSo what's different about writing a compiler in 2024 than say 10, 20, or 30 years ago? When I started writing compilers in the 80's and 90's lex/flex and yacc/bison were popular. ANTLR came out but I never had a chance to use it. Everything after lexing and parsing was always hand rolled.
- mjburgess 2y agoParser-generators were always academic projects that had little relevance to making real-world programming languages -- where parsing is very easy to write, and necessarily benefits from doing it (ie., you can get better error handling/etc.). Today most languages are front-ends for LLVM IR, but LLVM is very slow and takes a long time to optimize. Many new languages target x86/arm directly with their own weakly optimized backends, and output an LLVM IR for "release builds".
- sestep 2y agoCould you give some specific examples of those new languages with their own backends for faster builds?
- mjburgess 2y agoI was immediately thinking of Jai, Zig, .. but I've seen a few
- stefanos82 2y agoCorrect me if I'm wrong, but I think both Zig and Jai use LLVM as their default backend...at least, that's what I have seen via live streaming for Jai, and from Zig's repo.
- vulcan01 2y agoZig is moving away from LLVM (https://github.com/ziglang/zig/issues/16270 https://github.com/ziglang/zig/issues/16270) and Rust has added Cranelift as a debug backend (https://lwn.net/Articles/964735/ https://lwn.net/Articles/964735/). Not sure about Jai.
- badsectoracula 2y agoWeird that this is about building a C compiler[0] in OCaml. I expected the implementation language to also be C both for consistency but also because i'm willing to bet that there are more people who can read C than OCaml. [0] actually from the readme in the github repo[1] it seems to be a C subset, not all of C [1] https://github.com/nlsandler/nqcc2 https://github.com/nlsandler/nqcc2
- Croftengea 2y agoOCaml? Thanks for saving me a click!
- hdbxbxndj 2y agoOCaml is one of the most used languages for compiler design A good engineer should be able to use the right tool for the job
- materielle 2y agoFor hobbyist compiler implementations, right? Compilers for the most popular languages are either written in C/C++, or self-hosted. You can write compilers in almost any language. I fail to see how C, C++, or even Java or Python aren’t the right tool for the job here. I like pattern matching too, but given that hundreds of successful production compilers have been written without pattern matching, it’s surely just a personal preference.
- porcoda 2y agoI’ve worked on multiple compilers in industry that are written in Ocaml. A number of industrial static analyzers are written in Ocaml too (eg, Infer from Facebook/Meta). Yes, LLVM and GCC are the big ones written in the C/C++ family but they don’t represent everything.
- materielle 2y agoAnd the Go, Java, Ruby, JavaScript, C#, Typescript, PHP, Kotlin, R compilers, and so on. But even for hobby projects, it’s just a matter of personal preference. OCaml is great for implementing compilers. So are Go, C++, and Java.
- sergius 2y agoHow does it compare with N.Wirth's? https://onlinebooks.library.upenn.edu/webbin/book/lookupid?key=olbp42539 https://onlinebooks.library.upenn.edu/webbin/book/lookupid?k...
- hdbxbxndj 2y agoThe book is a very hands on tutorial whereas Wirths is basic literature for the general case. While they teach similar content, they have a different approach. There are literally thousands of compiler design books out there, I don't really see anything particularly comparable between this book and Wirth's
- anta40 2y agoSimilar to studying OS concepts using Silberschatz' Operating System Concept and Tanenbaum's Operating Systems Design and Implementation. The former only explains the theoritical ideas, while the latter is the documentation of an implementation.
- cxr 2y agoWirth's book does not implement a "real" programming language. Whatever your thoughts on Oberon and Pascal-like SHOUTCASE languages, it's largely irrelevant. Oberon is arguably a "real" language (and operating system), but Wirth's book does not cover the implementation of Oberon. It covers the implementation of Oberon0, an inarguably toy subset of Oberon. (Actually, "subset" is not even correct.) The example code has also diverged from the book, with Wirth abandoning the strategy described in the book for avoiding redundant initialization of the module static base, among other things. Aside from that, I encourage everyone who cites Compiler Construction to actually work through the first 10% of the book and then count the number of errata.
- alok-g 2y agoI would love to see a book that talks about going all the way to generate machine code, i.e., not stopping at generation of assembly. Alternatively, I would like to learn about not just how to make a compiler, but also simultaneously a debugger, hot-reloading, etc.
- hdbxbxndj 2y agoWriting an simple assembler is trivial. Even macro assemblers are very easy. However, it's also boring. Nevertheless the contents of the book cover all the techniques required to write an assembler, if you'd really like to
- alok-g 2y agoI understand that assembly file can be parsed in the same way. However, I want to learn about the machine instructions to the level of bits, and likewise the layouts of binary files. Unless I am able to go all the way to machine code loaded in memory, I would not know where in memory to add a breakpoint instruction when a developer wants the same on a line of code. If there is some library that can help create machine code from assembly instructions on a line by line basis (at least as opposed to invoking a separate program that generates the entire binary collectively from the assembly code), that could also work. In my case, I already know enough of the lexer, parser, etc., parts. What's missing is going all the way to making a debugger, profiler, etc.
- fuhsnn 2y ago>If there is some library that can help create machine code from assembly instructions on a line by line basis That's what JIT libraries do, for example asmjit: https://github.com/asmjit/asmjit/blob/master/test/asmjit_test_assembler_x64.cpp https://github.com/asmjit/asmjit/blob/master/test/asmjit_tes...
- alok-g 2y agoLooks cool! Thanks.
- signaru 2y agoHave read the first few chapters and it expects that you either read the accompanying source code or implement your own and pass the tests. The pseudo code presented in the book often look like function calls with the inner details not there in the book. Furthermore, as already pointed out in another comment, the available implementation is in OCaml, which is probably not something many C programmers have experience with. Nevertheless, I think I'm learning more from this book than most other books I've tried before that are far more theoretical or abstract. I'm still eager to reach the chapter on implementing C types. I think it's a good book, but it requires more effort than something like Crafting Interpreters or Writing a Compiler/Interpreter in Go, while also covering topics not in those books.
- wrycoder 2y agoNand2Tetris is also like that - they provide an outline and tests, but you have to do the work. And, having the implementation language be different from the target language reduces confusion. Plus, you get to become proficient in OCaml, which is a pretty good language.
- kragen 2y agothat's a good point—it was pretty confusing when i wrote ur-scheme in scheme, or stoneknifeforth in stoneknifeforth, because i kept getting confused about which level of the language i was changing things in
- myko 2y agoI thought this book looked neat but closed the tab before reading the comments here, and after this one decided to go ahead and buy it. Sounds really fun!
- synack 2y agoI’ve been working through this book implementing the compiler in Ada. So far, I’m really enjoying it. The book doesn’t make too many assumptions about implementation details, leaving you free to experiment and fill in the blanks yourself. It feels like a more advanced version of Crafting Interpreters. I haven’t looked at the OCaml implementation at all. The text and unit tests are all you need. Discussion on the Ada Forum: https://forum.ada-lang.io/t/writing-a-c-compiler/1024 https://forum.ada-lang.io/t/writing-a-c-compiler/1024
- fuhsnn 2y agochibicc[0] complement this book nicely, in addition to a basic compiler, it guides you through writing the preprocessor and driver, which, although not addressed much in literature, are the missing link between the compiler built from the book and real C projects. [0] https://github.com/rui314/chibicc https://github.com/rui314/chibicc
- markus_zhang 2y agoThanks, I wish the companion book were ready!
- sunday_serif 2y agoI’m working through this book now and really enjoying it! Each chapter of the book includes a test suite to run against the code you’ve written. In some ways, the tests in this book feel very similar to the labs in the book Computer Systems: A programmers perspective — which is high praise!
- sylware 2y agoI wonder why there is not the same book for c++... mmmmh... I really wonder... (irony).
- sylware 2y agoIt is because c++ has an absurdely and grotesquely massive and complex syntax (like rust...).
- stevefolta 2y agoYeah, Rust is the language for people who think C++ is not complex (or hostile) _enough_.
- sylware 2y agoWhen I tried to read some rust, I was surprised on how much alien it is to mainstream languages and how convoluted the syntax is.
- whytevuhuni 2y agoMy experience (and I admit I may be too biased given years of prior C/C++ experience) is that Rust's syntax is a necessity, since no other mainstream languages besides C/C++ are as low-level as Rust. Most mainstream languages have a GC, and don't support distinguishing between values on the stack or references, don't need to deal with lifetimes or don't provide the safety you get with them, etc. I'm curious though, could you give an example of syntax you consider convoluted, and how you would do it instead?
- sylware 2y agoHow do you want to be taken seriously if you don't see the convolution of the syntax of c++ and rust? You are going against an absolute truth.
- 2y ago
- the_panopticon 2y agoIn Ocaml, interesting. I was similarly surprised when I learned that the firs Rust compiler was written in Ocaml, too https://users.rust-lang.org/t/understanding-how-the-rust-compiler-is-built/87237/7 https://users.rust-lang.org/t/understanding-how-the-rust-com...
- mananaysiempre 2y agoTree processing is best done in a language with decent algebraic datatypes and pattern matching. I would’ve preferred Standard ML, but, well, pot-ay-to, pot-ah-to. Haskell is another choice but the techniques you need to use there (while undeniably gaining you some possibilities) don’t really generalize to other languages, so you’re now writing a book about compiler construction in Haskell rather than just compiler construction. Ditto for Rust. Kotlin has deliberately anemic pattern matching. C# or F# leave you depending on Microsoft’s benevolence (sic). Metalua and Sweet.js both have decent ADT support but both are pretty much dead. Racket exists, I guess, and there are some pattern-matching libraries for normal Scheme as well, but the charisma malus of the parenthesis is real even if I don’t understand what causes it. So OCaml was probably the most mainstream choice among the languages with appropriate tools, as funny as that sounds. And honestly, once you get over the syntax, it doesn’t actually have anything outrageous.
- bunderbunder 2y agoML (short for "meta-language") was originally designed for use in programming language research, and really shines for that purpose. And OCaml is probably the most pragmatic dialect for the purpose. SML is very dated and the standard library and ecosystem lack many things that are considered table stakes for a viable programming language nowadays. And F# and Scala are fine as enterprise languages, but being tied to .NET and Java respectively makes them less desirable for implementing a language that won't itself be coupled to one of those runtimes.
- viraj_shah 2y agoDropping this one here! (no affiliation) https://www.linuxfromscratch.org/ https://www.linuxfromscratch.org/ "Linux From Scratch (LFS) is a project that provides you with step-by-step instructions for building your own custom Linux system, entirely from source code."
- pull_my_finger 2y agoWhy though? It doesn't seem to be related at all to the OP other than both are tutorial books?
- jsnnsjxj 2y agoThis has nothing to do with the post?
- sim7c00 2y agocool, remember some tutorials online i think from the same author (not 100% sure) doing stuff around c compilation in python. shame its not in a language i want to learn. the other book on compilers i got is almost to heavy to lift! :D
- jerjerjer 2y agoI uh misread the title and thought someone built a C compiler in Scratch. On topic, though: wouldn't a simpler language (maybe even a pseudo language) be a better target for a first learning compiler. I understand they don't build a full C compiler, but still. It looks to me like there's a lot of complexity add from choosing such a lofty target.
- tuveson 2y agoWhat do you think would make a better target? C maps pretty closely to assembly, so it seems like it would be the simplest. Maybe Pascal or BASIC, but most people these days don’t have experience with Pascal, and BASIC would probably be too simple for a full-length book. For writing an interpreter or transpiler, there are probably better options, but for a true compiler I can’t think of a better choice than C (or at least a subset of C).
- francogt 2y agoI see many comments saying that the book implements the C compiler in ocaml. In the introduction the author states that the book actually uses pseudo code so you are actually free to implement it in any language. The only recommendation is that you use a language with pattern matching because the pseudo code makes heavy use of it. The reference implementation is in ocaml.
- ashconnor 2y agoUseful list considering that feature: https://en.wikipedia.org/wiki/Category:Pattern_matching_programming_languages https://en.wikipedia.org/wiki/Category:Pattern_matching_prog...
- markus_zhang 2y agoThanks, can you please lemme know which part uses pattern matching? I'd assume mostly in the lexer, but the parser should just be something that consume the tokens and spit out AST. Unless of course it combines the two.
- shawn_w 2y agoPresumably anything that walks the syntax tree.
- markus_zhang 2y agoThanks. At first I thought it is something like regex, but then I found it's something in functional programming. I need to read a few chapters of the book before buying it because I'm not interested in learning FP at the moment.
- CrimsonCape 2y agoQuestion for HN, pattern matching is defined as “runtime type/value checking”, is that correct? Is duck typing the pseudo-unsafe alternative? (Not unsafe as in accessing unsafe memory, but as in throwing exceptions if the duck-typed function doesn’t exist on the current type) Can C handle both? Coming from a static type system like rust and c#, i’m doing alot of “if this is a duck, duck.quack()” and i’m looking for faster alternatives and less verbosity if possible
- WalterBright 2y agoI learned how to write a compiler by studying BYTE magazine in the 70's which published the source to a complete Pascal compiler as an article! https://archive.org/details/byte-magazine-1978-09 https://archive.org/details/byte-magazine-1978-09 (part 1) All 3 parts of Tiny Pascal: https://albillo.hpcalc.org/publications/Easter%20Egg%20-%20TBBOP.pdf https://albillo.hpcalc.org/publications/Easter%20Egg%20-%20T...
- deleted 2y ago[deleted]
- nj5rq 2y agoThank you for sharing this, very useful. The BYTE magazine is absolutely amazing, it's a shame nothing similar could be done today.
- barelyauser 2y agoThe Byte magazine is incredible. First time reading it. The archive.org collection is a gold mine for learning. Thank you very much for posting it.
- carom 2y agoI took a compilers course in university and the course culminated in having a compiler for C Minus (a subset of C). The professor noted how each year the line count of the compilers was dropping as students found ways libraries or languages that made it easier. I think the evolution was Java -> Antlr -> Python. I used OCaml and emitted LLVM and blew that metric out of the water.
- whartung 2y agoWhat approach does this book take to error recovery? Several "compiler light" style articles and books kind of walk over that part, and it can be non-trivial to do properly, especially with modern expectations. I remember way back in the day, one of the early C compilers for the PDP, and, honestly, it could almost be argued that ed(1) had better error messages than what that thing produced. A lot of simple compilers hit an error and just give up. So, just curious what the approach was in this book.
- tzs 2y agoI don't really need to know how to build a compiler, and I've got enough other "don't need but am doing out of curiosity" things going on that I don't need any more of those, but if it wasn't $70 I'd probably get it anyway. It would be interesting to compare to the last building a compiler book I read back and see how things have changed. Based on the comments here a lot has changed. That last book was Allen Holub's "Compiler Design in C", which is from 1990. Here's how the blurb on the back describes it: > Allen I. Holub's Compiler Design in C offers a comprehensive, new approach to compilers that proves to be more accessible to computer science students than the other strictly mathematical books. > With this method in mind, the book features three major aspects: > (1) The author develops fully functional versions of lex and yacc (tools available in the UNIX® operating system to write compilers), (2) he uses lex and yacc to develop a complete C compiler that includes parts of C that are normally left out of compiler design books (eg., the complete C "type" system, and structures), and (3) the version of yacc developed here improves on the UNIX version of yacc in two ways (error recovery and the parser, which automatically produces a window-oriented debugging environment in which the parse and value stacks are visible). It's out of print, but the author has made a searchable PDF available on his website [1]. I found it quite useful. Holub seems to like the "learn by doing" approach. He's got another book, "Holub on Patterns" that teaches all the design patterns from the gang of four book organically by developing two programs that together use all of those patterns. The two programs are an embedded SQL interpreter and a GUI application for Conway's Game of Life. PS: Ooh. It occurred to me that No Starch Press books are often available on O'Reilly Learning. I checked and this one is there. So I guess it is going on my "don't need but am doing out of curiosity" pile after all. [1] https://holub.com/compiler/ https://holub.com/compiler/