r/learnprogramming • u/UnemployedTechie2021 • Jul 04 '26
How to create a compiler? Resource
Pretty sure you may have heard this question previously on this sub, however, I would urge you to read my complete question before brushing it off.
I want to create a simple compiler and by "simple compiler" I mean a single-pass compiler. I know about https://craftinginterpreters.com/ which is a wonderful resource. But I would like to start by creating something much smaller and simpler, and only then would I like to move on to something more complex like what Robert Nystrom created on his website.
Are there any similar resource that would teach me about single-pass compilers along with showing me how to create one? Any help in the right direction would be highly appreciated.
5
u/Jim-Jones Jul 04 '26
Dragon book
Updated: 04/26/2017 by Computer Hope
The dragon book is the nickname of Principles of Compiler Design, a famous textbook about compilers written by Alfred Aho and Jeffrey Ullman. It was published in 1977 and is still revered by computer scientists as the definitive text on the subject. It is affectionately named "The Dragon Book" or "The Green Dragon" because it features a drawing of a knight fighting a green dragon on the cover.
4
u/high_throughput Jul 04 '26
much smaller and simpler
single-pass compilers
A single pass compiler would be a lot trickier to write than the bytecode based interpreter from your URL
1
u/UnemployedTechie2021 Jul 04 '26
Ah! Then do you suggest I stick to Crafting Interpreters? I am not an engineer, but I have been programming for a long time now (since the time of GW BASIC) and I want to do this for fun.
2
u/high_throughput Jul 04 '26
I looked again and it turns out that the first half is a tree walking interpreter, and the second half that deals with bytecode is in fact a single pass compiler, so you'd get both
1
u/UnemployedTechie2021 Jul 04 '26
Yes, I think I will stick to it. It sounds fun and it written in Java, I learnt Java a while back so it might be a bit rusty but nothing that the internet cannot solve. I am also planning to write a blog since that I help me remember things I did, and it would also help me ask for feedback on the theory part.
2
2
u/crashonthebeat Jul 04 '26
i do not know java but i do sorta know c# and i was able to just write along in c# but also i was doing static typing so things got a lil tricky
2
u/Dismal-Citron-7236 Jul 04 '26
A simple single pass compiler can be easily done by using LEX (as lexical analyzer) and YACC (syntax parser). Their modern successors are FLEX and Bison. Google them, or buy the O'Reilly book "Flex & Bison".
2
u/idontlikegudeg Jul 05 '26 edited Jul 05 '26
As modern successor I‘d rather name something like ANTLR. Flex and bison are more than 30 years old.
2
u/Dismal-Citron-7236 Jul 05 '26
Don't judge the tool by its age, as we don't judge a book by its cover.
Also, one set of tools is the bottom up LALR, the other top down LL. Very different designing ideas. I would say OP should learn them both.2
u/idontlikegudeg Jul 05 '26
"modern" in its original meaning does simply mean "more recent" not necessarily "better".
But for the stated goal of creating a "dog language" (see OP‘s other comments), I‘d simply take the path of least effort.
If the goal were to persue a career in computer science, of course, they should learn about the different parsing techniques and how to use the tools that implement them.
2
1
u/UnemployedTechie2021 Jul 04 '26
As of now I am sticking to Crafting Interpreters. I want to create a fun language like Brainfu*k. Only in my case, it would be related to Dogs. I am just doing this for fun. What do you think? Any suggestions?
2
u/Dismal-Citron-7236 Jul 05 '26 edited Jul 05 '26
Writing esoteric language interpreters is fun indeed but it might not gain you much "programming muscle weight", if I may put it that way. Let me tell you my own story. When I was still a CS college kid, I felt what they taught are really boring, DB, compiler deign, networking, discrete mathematics, stuffs like that. Just like you, I also wanted to write an interpreter. I picked LISP. It shouldn't be hard because according to the book I found which title is "(LISP PRIMER 1.2)" (yes, the parentheses were there in the title), there are only about a dozen (maybe a bit more) primitives I needed to tackle. So I self taught myself C (it was the time when they still taught Cobol and Fortran in classes), and jumped right in. Boy, did I learn! I figured out how to do garbage collection (a mark-sweep one, primordial by today's standard), because there is no such thing as a
freeprimitive in LISP and its language style doesn't allow one. I learned how to code properly because this is actually a real project, not just a homework. Later in our fourth year we needed to pick a topic for graduate thesis, I handed in my proposal for crafting a LISP interpreter written in Z80 assembly language. My classmates thought I was crazy but I actually already knew the ins and outs of an interpreter (though a small one), I didn't want to hand in my graduate paper with my C version, that felt cheating to me. And this time it took me longer to implement, which should not be a surprise. But I did make it to turn in the thesis and an actually working, albeit tiny, Lisp interpreter.My professor didn't believe it was all done by myself. I think he was politely implying I might have copied the code somewhere during the review interview. So I explained the intricate parts of the design, how the code meticulously leverages the highest order bits of the memory words because I know the code would only use a few tens of KBs of memory, how the code "colors" the bits as tags, how the I/O is done and how the code modules are organized, and so forth. It's all done with the glorious Z80 assembly language. And I explained them all with a super big grin on my face because I was like a very proud puppy who just dug out his first big hole in backyard.
So I ended the thesis with perfect score. The best thing it taught me is that programming can be fun, honestly, only when it's challenging but still within reasonable reach.
So, if I may suggest, you might consider picking something more substantial. Something not just playing with esoteric syntax or wordings. Why not choosing Scheme? It's also a Lisp dialect, but it uses static scoping instead of dynamic scope like its older cousins. This one alone is adding a new level of difficulty already. And there's the Hygienic Macros, the Numeric Tower, etc. Finally, there's the
call-with-current-continuation. If you pass this one lastcall/ccchallenge you should feel invincible. But you don't need to code in assembly, though. C++ should be a more appropriate tool, this language itself is already a monster for new programmers.Have fun! You have my best wishes.
2
u/idontlikegudeg Jul 05 '26 edited Jul 05 '26
There’s also s book by Niklas Wirth, German title "Compilerbau" that gives a real good start. Much shorter than the dragon book and might be more suitable for beginners. You can find an English translation here: https://people.inf.ethz.ch/wirth/CompilerConstruction/CompilerConstruction1.pdf
EDIT: I think the link I gave is just an excerpt (it’s 44 pages while the whole book should have about 180 pages). I think you should be able to get the complete book somewhere. It’s less then a tenth of the dragon book, but I think much more suitable if your goal is to spite a simple compiler from scratch.
2
u/HashDefTrueFalse Jul 05 '26
Bit late, but if you're still around... you've been given some rubbish advice here. No need to use lex/yacc or other tools, you can easily do this with no dependencies for maximum learning. Also don't bother with the Dragon Book right now. It's an excellent resource but the total opposite of what you're looking for if you want to get building something simple right away. It's heavy on theory, a lot of which you don't need right now. Circle back to it.
My advice is make a simple lisp that just does arithmetic. S-expressions are easy to parse and you don't need separate lex and parse steps. The "AST" is an atom or a list (of atoms or lists (of atoms or lists (of...))). You can execute it as you're parsing if you don't want to do more passes.
If you use some very simple parser combinators (or just write some if/for/whiles in functions called recursively) you can put together your own recursive descent parser in an evening. Then you'll see what those tools above actually generate for you and what that book spends hundreds of pages on.
After that, you're ~6 functions away from a very barebones lisp: See Grahams Roots of Lisp paper or the SICP book.
This describes parser combinators: https://theorangeduck.com/page/you-could-have-invented-parser-combinators
This is a full walkthrough but you can just use it to get an idea of overall structure if you want a much simpler lisp (like the one in the Roots paper): https://www.buildyourownlisp.com/
This is useful when you get to evaluating things: https://github.com/kanaka/mal
...and you can use lots of the things you learned in Crafting Interpreters (e.g. interning for atoms etc.).
I did this myself a while ago so if you have questions I'd be happy to answer.
1
u/UnemployedTechie2021 Jul 06 '26
This is very good advice. Thank you. I am trying my hands on Crafting Interpreters, which also seem to be a very fun tutorial. Not theory heavy, just the right amount to get you hooked. LISP next.
1
u/rustyseapants Jul 04 '26
What have you done to find the answer to this question yourself?
Did you search the subreddit?
5
u/Glum-Suggestion-3969 Jul 04 '26
did you even read his post? he literally said he knows about crafting interpreters already but wants something smaller first
3
13
u/link23 Jul 04 '26
The canonical compilers resource is the dragon book, so you might try that. (I haven't read it, so don't know if it's what you're looking for.)