So I’ve already posted this question on Stack Overflow, but I wanted to ask it here as well, since I am not sure if they will simply say it is a duplicate (even though the other answers from other questions don’t answer what I asked in a way that helps me).
[https://stackoverflow.com/questions/78539284/in-bootstrapping-how-is-the-compiler-written-in-the-other-langauge-such-that-it](https://stackoverflow.com/questions/78539284/in-bootstrapping-how-is-the-compiler-written-in-the-other-langauge-such-that-it)
So I was wondering if there were direct examples people could give of how the bootstrap compiler is actually written such that it actually represents the language you want to write in another language, because my head can’t wrap itself around it and most sources are fairly vague and just assume you know how it is done.
Hell, maybe if people try and explain it in a metaphorical way and walk me through how the bootstrap compiler is written to represent language X in language Y, that might help too, since I am not a programmer, but this concept is stressing me out from knowing I don’t understand it.
In: Technology
Unfortunately you’re not going to really understand this without having programming experience. It’s one of the most difficult computer science topics.
The bootstrap compiler is very bare bones. It can only support basic statements and is not a good compiler. You’ll want to make it so that you can, at least, construct a compiler in your new language from the bootstrap compiler. So there needs to be a decent amount of functionality.
Now, *actually* doing that is hard. I don’t know how it’s exactly done and I have a degree in CS. The thing is I’ve never written a compiler and never will need to, it’s very niche and very complex and I have no interest in writing my own language or working on one.
The compiler needs to be able to parse your language. Essentially, it needs to take some input like “for k in 1..10” and recognize that you want to iterate over a variable k 10 times. And then it needs to write code for that in assembly.
This is the hard part. You need to build an abstract architecture that can handle all of this. Compiler books go into this, and again, I’m not exactly sure how, but I do know that you need to formally represent your language with things such as Backus-Naur Form and the compiler needs to create abstract syntax trees. Backus Naur Form is a formal way to represent a language. An abstract syntax tree is a tree that contains valid arrangements of syntax of your language. If this is going over your head, it should, because there are all Cs topics that the layperson won’t understand (many CS people don’t use backus naur firm, and syntax trees are only ever used in compilers).
If you want to *really* know how a compiler works you need to read a textbook about it. And even then you’ll want to have a lot of programming experience otherwise a lot of concepts and a lot of understanding of why will go over your head. And there isn’t a good ELI5 explanation for something so complex and niche.
The general idea isn’t that hard. A compiler is a program that takes some input written in some language L (set of grammar, symbols) and outputs something in another language L’. Usually L’ is machine code, which can be directly executed by the CPU.
Denote as L -> L’ meaning “something written in L transformed into something written in L’ “ … in other words a compiler.
Then it should be possible to daisy chain compilers, as long as the input language of one compiler matches the output of another:
L -> L’ -> L’’ -> … -> L_final
The trick is, if we group arrows together…
L -> (L’ -> L’’) the stuff inside the parentheses is just a compiler.
What this is telling me is that I can write a L’ -> L’’ compiler in L.
And we’re done because I just basically described bootstrapping.
I think this is more a question about how a compiler works in general.
A compiler takes some text input (the program you wrote) and turns it into machine code.
Let’s make up a simple programming language, that only contains two possible instructions. “Add number1 number2” and “Subtract number1 number2”.
Let’s use an example program in our made up language, “Subtract 4 2”
The first step splits the code up into tokens, in this case we would have three tokens, [“Subtract”, 4, 2]. A compiler for this language could then look something like this:
“`
token = tokenize(input)
if(token[0] == “Add”):
//output machine instruction “ADD token[1] token[2]”
else if(token[0] == “Subtract”):
//output machine instruction “SUB token[1] token[2]”
“`
This compiler can take the instructions from our new programming language and output the correct machine code. You might notice that it doesn’t actually matter which language you use to write this compiler. You could use C, Python, Java, whatever you want.
This is obviously very oversimplified, a real compiler has a lot more steps, because real programming languages are a lot more complex than my example.
So I think basically you need to understand what a programming language is. It’s a code. Like, think about spies. They write messages to each other, in secret code, and they have a little book that tells them what the code is, and they can translate the message. And make it readable.
So, the only language that a computer actually speaks is binary. It has to be 1s and 0s, at the end, or else the computer doesn’t understand.
When you write “code” in a programming “language”. The language is really a specific “code book”. All the words and symbols and syntax represent blocks of 1s and 0s. And the compiler just takes all that, and translates it into the computer language. Makes it actually be 1s and 0s. So it’s like you’re a spy, and the computer is the other spy, and you’re writing a coded message. The compiler is that part where you need a code book to translate the meaning.
So the compiler itself is just a computer program. Everything the computer does is a computer program. The program can be written in any language. It just needs to have access to the specific “code book” that this specific “spy”is using.
This might be a bit more ELI15 than it is ELI5, but let’s give it a shot anyway: Let’s actually look at how these things are built.
There’s this tiny toy programming language called [Brainfuck](https://en.wikipedia.org/wiki/Brainfuck). It’s almost completely useless, and named for how hard/annoying it is to write anything useful in it, but it’s an incredibly simple language to write an interpreter for. I mean “if you know what you’re doing, it’s an afternoon project” sort of simple. So, when I learn a new programming language, I like to write a Brainfuck interpreter as one of my first projects. It covers all the basics and serves as a nice tour of a language. [I have a few of them online](https://github.com/pdpi/brainfuck/), so let’s look at my Haskell version to explain this thing.
[First off](https://github.com/pdpi/brainfuck/blob/master/haskell/src/interpreter.hs#L7-L14):
“`
data Instruction = Get
| Put
| Next
| Prev
| Add Int
| Loop [Instruction] deriving (Show, Eq)
type Program = [Instruction]
“`
I’m saying two things here. One is that there are six instructions we know about (Get, Put, Next, Prev, Add, Loop), the other is that a (Brainfuck) Program is just a list of Instructions. (the `[]` mean “list of”). This is the first really important concept: At this point, a Brainfuck “program” just means some data inside our Haskell program. A more complex language would’ve had a bunch more stuff happening here, but it’s just more of the same, really.
[Then over here](https://github.com/pdpi/brainfuck/blob/master/haskell/src/parser.hs#L18-L30):
“`
parse :: String -> Program
parse src = reverse . head $ foldl’ (flip parseChar) [[]] src
“`
First line just says “we have a thing called ‘parse’ that takes a string of text and spits out our interpreter’s idea of a program”. This is the second important concept: You can just read a bunch of text and turn it into that program-like data we saw earlier (it should come as no surprise that this is called ‘[parsing](https://en.wikipedia.org/wiki/Parsing)’).
You can safely ignore all the gobbledygook in the second line, it defines how `parse` works in an incredibly terse style that only really makes sense in the context of “I wrote this as a way to learn Haskell”, but you might notice that you have the word `parseChar` in there: I defined parsing the whole program in terms of repeatedly parsing a single character at a time.
So if you keep reading:
“`
parseChar :: Char -> Parser -> Parser
parseChar ‘.’ = add Put
parseChar ‘,’ = add Get
parseChar ‘>’ = add Next
parseChar ‘<‘ = add Prev
parseChar ‘+’ = add $ Add 1
parseChar ‘-‘ = add $ Add (-1)
parseChar ‘[‘ = push
parseChar ‘]’ = pop
parseChar _ = id
“`
That line that says `parseChar ‘.’ = add Put` basically means “when you see the character ‘.’, that translates into the ‘Put’ instruction, so add that to the program”. The rest of the lines are just variations, “when you see this character, add that instruction”. If you look at [this sample](https://github.com/pdpi/brainfuck/blob/master/examples/99botles.bf), you can see that the actual program is really just made of those characters `.,<>+-[]`. That last `parseChar _ = id` line is a fancy way of saying “if you see any other character, do nothing”. Same as before, more complex languages would need a correspondingly more complex parser.
Now, this is where a compiler and an interpreter diverge. I have [this bit of code](https://github.com/pdpi/brainfuck/blob/master/haskell/src/interpreter.hs#L16-L33) that takes that internal representation of a Brainfuck program, and immediately runs that program. A compiler would, instead, take that and produce an executable, but that’s largely just writing a file with a very specific format of its own. E.g. by the time you’ve turned into assembly, an `Add 5` instruction in our brainfuck program might get translated into an `ADD RAX, 5`.
These fundamentals are the same no matter what language you use to write your interpreter, and what language you are interpreting. It’s just reading text data and making sense of it. So… some nutcase out there wrote [a brainfuck interpreter, in brainfuck](https://github.com/canoon/bfbf/blob/master/bf.bf). If I had written my interpreter as a compiler, you’d be able to compile that crazy bf-in-bf thing with my interpreter-that-we’re-pretending-is-actually-a-compiler, and you’d have bootstrapped the language. Wee!
I’m not an expert, but think this may help: I think the question is more about why a compiler is necessary in the first place– at the end of the day, the processor has what is called an Instruction set, the actual commands it can perform. What the CPU takes are these commands and the data on which they operate, sometimes called machine code. These are very low level operations like adding numbers, moving values from Memory to cache — you give it a command like add, subtract, copy to/ from RAM, and the values to add/copy/ move/ etc. Doing anything of utility requires many of these simple steps, written in a form that is barely human readable. All other languages must ultimately be compiled into machine code that your processor can understand. There are intermediate steps– assembly is in a sense a slightly more readable version of what the processor actually uses (which are all 1s and 0s, but nobody programs in actual binary, ever.) So compilers take source code in a higher level language that humans can read and understand and output the processors instruction set commands to achieve the goals described in the source code, in a way the processor can understand with its limited vocabulary. I hope that makes sense.
Imagine a set of rules that when followed translate English to German. You could write that set of rules in English, or German, or French. It doesn’t really matter what language the rules are written in as long as they work.
In this analogy English is the source language (maybe C or Java). German is the target language (probably machine code). The compiler is the set of translation rules. French is the language the compiler was created in.
But this doesn’t quite capture the concept of “boot strapping”. To understand boot strapping you have to recognize that target language (machine code) is great for computers but hard for humans to understand.
So we invent a language A that’s a bit easier for humans to read and write, and build a translator from that to machine code (using machine code to build it, which is hard work, but not too hard because A isn’t very different from machine code)
Then we invent a language B that’s a bit easier for humans to read than A, and we write a translator from B to machine code, using A. Again, not easy but easier than if we had to write it in machine code.
“Rinse and repeat”, after a few iterations we have a language that is easy enough for humans called F. And a translator from F to machine code written in E.
As a final step we write a better translator from F to machine code, written in F itself. And we translate it to machine code using our translator written in E.
From now on we can improve the compilation (translation) time needed or the efficiency of the machine code produced (run time) by improving our F compiler written in F .
Latest Answers