compiler-constructionlanguage-designbootstrapping

What's the smallest subset of language features you need to bootstrap its compiler?


What would be the absolute necessary core features of a language (inspired from C) as a sub-language which can be used to write a compiler for the whole language?


Solution

  • You need a while loop, if, one true integer variable, and a way to read and write a file. That's it. (Actually, the file reading and writing part is nice-to-have, but not strictly necessary – You only need it to get information into and out of the program. And if you can read and write a file, then you don't need the integer variable anymore, since you can use the file as a temporary store.)

    while, if and one integer variable is Turing-complete, i.e. it can compute any Turing-computable function. A compiler is a Turing-computable function. A compiler which cannot take any input or produce any output is pretty boring, so you need to have a way to read some input and write some output.