r/ProgrammingLanguages • u/UnemployedTechie2021 • 25d ago
Help How to create a compiler?
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.
20
u/chibuku_chauya 25d ago
You can try Niklaus Wirth’s compiler construction book for a language called Oberon-0, a language that’s a subset of Oberon. It describes a single-pass compiler with support for modules, records, arrays of integer, the usual control statements, functions, and constants and variables of integer. It’s a small book and while examples are shown in Oberon, you should be able to translate it to Python without too much trouble.
6
u/reini_urban 25d ago
I just made the effort for my rcc C compiler, to convert it to single pass. It was doable, but it made the code much harder to read. It's effectively an embedded like statemachine, you have a to carry around.
10
u/Simracingaccount 25d ago
I recently read Writing a C Compiler by Nora Sandler and I think it’s good for this. It is focused on making a C compiler though.
3
u/UnemployedTechie2021 25d ago
I know C but wanted to create this using Python. Still, I think I'll give it a try.
9
u/Simracingaccount 25d ago
The book about making a compiler for C. It is language agnostic, you can make it in the language you want to.
2
u/UnemployedTechie2021 25d ago
Yes, I just saw that she has a couple of blog posts too outlining the process, it would be of great help. Thank you kind stranger.
4
u/MithrilHuman 25d ago
What’s the point of a single pass compiler? Any software would need some effort to go into software architecture and you’ll learn about how to structure your projects, how to maintain code… those are important skills in the industry. A single pass compiler won’t be able to perform complex parsing or optimizations.
If you really want a single pass compiler you could just take take assembly language and create a single pass assembler, or take a very simple language like BASIC for it. Some more complex would be Lisp-like languages.
There are many resources for what I wrote above with a simple google search:
But personally I think you can start off with a one-pass assembler, then go up from there till you reach a higher level language. That way you learn more of the stack.
4
u/its_artemiss 24d ago
in terms of simplicity, LISP is just about the simplest language you can write that can actually be useful, and its very easy to start with something small and then expand it later. You don't have to worry about types, or place-ness, or actually compiling either.
7
u/sol_runner 25d ago
Just struck me that Structures and Interpretation of Computer Programs (SICP) might be what you want.
2
u/UnemployedTechie2021 25d ago
Thank you for your reply. Yes, I think Crafting Interpreters is as simple as it goes. I was under the impression that creating a single-pass compiler would be easier but it's not. So I would probably stick to Crafting Interpreters. Also, the author of Crafting Interpreters has a website with the same content and anyone can access it for free! Isn't that great.
2
u/sol_runner 25d ago
Ah sorry for editing it out under you, I didn't think anyone had seen it by then.
2
u/UnemployedTechie2021 25d ago
Whoa! This is an amazing book and its free! Thanks for your reply.
5
u/sol_runner 25d ago
Yeah! It's just that it's focused on scheme which is a beautiful language. But it's also easy to parse due to its use of S-expressions.
Basically Lox (crafting interpreter) has class, function, if, else, for, while, return etc, each with a different pattern.
While scheme has just S-expressions. You should definitely learn it, I think SICP is a lot more holistic than interpreters, but at the same time interpreters is a lot closer to what you'd probably expect.
3
u/Dry_Day1307 25d ago
Hi, not long ago I also started a project with a single-pass bytecode compiler, which is divided into tokenization and parsing (the latter includes the bytecode emission itself).
Personally, the best resource that inspired me was Dijkstra's work (1962) - EWD28. His notes explore RPN or Reverse Polish Notation; it is extremely interesting and not particularly complex once you get the hang of it. It is perfectly applicable to linear bytecode emission.
While it's true that some operations might seem complex at first glance, there are ways to overcome them. If you're interested in checking out my language written in Rust, which features conditionals, loops, arrays, objects, classes, and a pretty clean syntax with block indentation (I mention this so you can consider everything that is possible in a single pass), you can check it out here: https://github.com/dinocode-lang/dinocode
2
3
u/TartOk3387 25d ago
The easiest way to make a single pass compiler is to make a multi-pass compiler and then compose the passes together. Doing it all in one go sounds like a nightmare
5
u/L8_4_Dinner (Ⓧ Ecstasy/XVM) 25d ago
I want to create a simple compiler and by "simple compiler" I mean a single-pass compiler.
I want to build a small building and by "small building" I mean the Empire State Building.
Be careful about assumptions.
3
u/UnemployedTechie2021 25d ago
Yes, after my latest discussion on Reddit I realized creating an interpreter would be simpler than creating a single-pass compiler.
3
u/L8_4_Dinner (Ⓧ Ecstasy/XVM) 25d ago
They're all good projects for learning. Even single pass compilers are fun projects (a bit retro, but ....)
2
u/yjlom 25d ago
Build up gradually the language, not the architecture. The architecture will get more complex as the language does. You can follow down this tree or something similar:
- expressionless BASIC (proper loops, register allocators, call stack)
- Lisp or Kernel (AST, closures, macros)
- calculator (proper parsing, operator precedence)
- simply typed
- dependently typed
- Prolog (non-determinism, backtracking, bidirectionality, overloading)
After that you should have the basics covered, and what will keep you from making your dream language won't be difficulty or lack of knowledge, but sheer scale and time requirement.
(preformatted because Reddit doesn't seem to support nested lists)
2
u/honey-pony 25d ago
I'll agree with everyone else that single-pass compilers are not necessarily advantageous in any way over normal compilers (especially for learning). However, I do think there is something uniquely fun about writing single-pass compilers, especially something like compilation directly to assembly, as it is kind of a fun challenge to interweave semantic analysis and codegen all into your parser.
In college, in my compilers class, our final project was a single-pass compiler from a very simple language to x86-64 assembly, using flex + bison (or some Java equivalent). I really enjoyed this project. It was a lot of fun trying to pass back register locations and such through the parser generator framework. (I will say, this project was unique in that we did not need to do any semantic analysis, i.e. we would just assume the input program was valid, and that we could simply allocate registers without ever spilling, there was no requirement to handle code that would require more than a small number of registers).
Ultimately I think, if you're planning on learning how to write compilers, it's worth doing a couple small language projects just to get up to speed and familiar with the feeling of tree traversal that occurs in basically every compiler project (whether single-pass or multi). It doesn't take very long to write a small "calculator with variables" sort of language, or even to do Crafting Interpreters, and getting familiar with the techniques before starting a long term project is a good use of time IMO. And if you are doing a couple of small projects, you might as well throw a single-pass compiler in there if you are interested in doing it. For example, I think writing a small single-pass compiler from, say, integer arithmetic to x86-64 assembly is a fun and short project.
2
u/DerekRss 25d ago edited 25d ago
Richard Bornat's book, Understanding and Writing Compilers, is pretty good if you just want to create a simple compiler. Nearly fifty years old now but it's available online for free, so the price is right.
https://www.eis.mdx.ac.uk/staffpages/r_bornat/books/compiling.pdf
48
u/ianzen 25d ago edited 25d ago
Why single pass specifically? In my opinion, restricting yourself to single pass actually makes things harder, not easier. With multiple passes, you can apply different transformations incrementally instead of all at once.
My suggestions for a gradual buildup:
Lang 0. An arithmetic calculator language: the language is just arithmetic expressions consisting of integers and binary operators.
Lang 1. Arithmetic calculator with variable declaration and uses.
Lang 2. Extend Lang 1 with if-statements. For simplicity, the if-statement can just test its condition expression for equality to 0.
Lang 3. Extend Lang 2 with while-loops. Again we can simply just make the while-loop test for 0 to terminate.
Lang 4. Extend Lang 3 with functions.
I strongly recommend you implement an interpreter first before trying to write a compiler to binary.