Compiler-Programming: What are the most fundamental ingredients?

Question

I am interested in writing a very minimalistic compiler.

I want to write a small piece of software (in C/C++) that fulfills the following criteria:

• output in ELF format (*nix)
• input is a single textfile
• C-like grammar and syntax
• no linker
• no preprocessor
• very small (max. 1-2 KLOC)

Language features:

• native data types: char, int and floats
• arrays (for all native data types)
• variables
• control structures (if-else)
• functions
• loops (would be nice)
• simple algebra (div, add, sub, mul, boolean expressions, bit-shift, etc.)
• inline asm (for system calls)

Can anybody tell me how to start? I don't know what parts a compiler consists of (at least not in the sense that I just could start right off the shelf) and how to program them. Thank you for your ideas.

Answer 1

With all that you hope to accomplish, the most challenging requirement might be "very small (max. 1-2 KLOC)". I think your first requirement alone (generating ELF output) might take well over a thousand lines of code by itself.

One way to simplify the problem, at least to start with, is to generate code in assembly language text that you then feed into an existing assembler (nasm would be a good choice). The assembler would take care of generating the actual machine code, as well as all the ELF specific code required to build an actual runnable executable. Then your job is reduced to language parsing and assembly code generation. When your project matures to the point where you want to remove the dependency on an assembler, you can rewrite this part yourself and plug it in at any time.

If I were you, I might start with an assembler and build pieces on top of it. The simplest "compiler" might take a language with just a few very simple possible statements:

print "hello"
a = 5
print a

and translate that to assembly language. Once you get that working, then you can build a lexer and parser and abstract syntax tree and code generator, which are most of the parts you'll need for a modern block structured language.

Good luck!