Compilers

What is a compiler?

Simply put, a compiler is a program that translates text in one language (called the source language) to another (called the target language). It might perform numerous other tasks alongside translation — optimization, enforcing security, ensuring compliance with the target language's rules — but its principle task is translation.

For most compilers, the source language is some high-level language; e.g., Java, C++, C, Python, Swift, etc. The target language is some language a little "closer to the metal" — Java bytecode or some other virtual machine language, varieties of Assembly, or for some languages, machine code. This is a key point to keep in mind. Generally, compilers fall into three categories:

1. Two-tiered compilers are compilers that take source code inputs and return virtual machine code outputs. The virtual machine code outputs then translated by the relevant virtual machine into machine code.
2. Single-tiered compilers are compilers that take source code inputs and output straight to either the system's Assembly language or the system's machine language.

Anatomy of a Compiler

Most compilers — two- or single-tiered — have the following anatomy:

From the diagram, we see that a compiler consists of three main components:

1. A tokenizer,
2. A parser, and
3. A code generator.

The first two components are encapsulated in a larger module called the syntax analyzer. We begin by considering the tokenizer.

Lexical Analysis

Suppose we had the following code snippet:

if (x < 0) {
	// determines the sign
	return "negative input";
}

The snippet above contains various characters: i, f, (, x, <, and so on. To create meaning, a language can a particular character a meaning (e.g., the symbol < has the meaning "less than"), or a group of the characters meaning (e.g., the grouping if marks the introduction of a sufficient condition). In the world of programming languages, these basic units — a character or group of characters — are called tokens.

Informal Definition. A token is a string of characters that has a meaning.

The language can further classify these tokens into token types. For example, a simple language might have the following token types:

1. keywords,
2. symbols,
3. integers,
4. strings,
5. identifiers

For example, the program above might result in outputs that look like any of the following:

// in some implementation A
<keyword> if </keyword>
<symbol> { </symbol>
<identifier> x </identifier>

// in some implementation B
{ token: "if", type: "keyword" }
{ token: "{", type: "symbol" }
{ token: "x", type: "identifier" }

// in some implementation C
["if", "keyword"]
["{", "symbol"]
["x", "identifier"]

Ultimately, how the token is represented is entirely up to the designer. In the first approach, an XML-like output is used; in the second, a struct-like output; and in the third, a jagged array.

Broadly, a tokenizer is program the performs the following:

1. abstracts the compiler input as a token stream,
2. ensures the token stream continues flowing so long as there are inputs, and
3. supply the current token value and type, and

To put this in object-oriented pseudocode, the tokenizer might look like the following:

const tokenizer = new Tokenizer("program.file");
tokenizer.advance();
while (tokenizer.hasMoreTokens()) {
	// tokenize tokens
}

Grammars

A language needs more than just tokens to convey meaning. For example, consider this sequence of words:

hates sprouts she brussels

Each word has a meaning, but all together, the sequence doesn't make much sense. If we put the sequence in another order:

she hates brussels sprouts

Now it makes sense. Programming languages are the same way. For the language to convey meaning, it must have rules for how tokens should be arranged. The set of all these rules is called the language's grammar.

Informal Definition. A grammar is a set of rules for how tokens must be arranged to create valid language constructs.

he grows bananas
he grows the bananas
she ate the apple
he shared the bananas

statement :  ifStatement
				  |  whileStatement
				  |  letStatement

statement  :  ifStatement
				   |  whileStatement
				   |  letStatement
statements : statement*

ifStatement : 'if' '(' expression ')' '{' statement '}'
					  | 'if' '(' expression ')' '{' statements '}'

whileStatement : 'while' '(' expression ')' '{' statement '}'
						   | 'while' '(' expression ')' '{' statements '}'

letStatement : 'let' identifier '=' expression ';'

identifier : a string not beginning with a digit

expression : term (op term)?

term : identifier | constant

constant : a decimal number

op : '+' | '-' | '=' | '>' | '<'

statement  :  ifStatement
				   |  whileStatement
				   |  letStatement
statements : statement*
ifStatement : 'if' '(' expression ')' '{' statement '}'
					  | 'if' '(' expression ')' '{' statements '}'
whileStatement : 'while' '(' expression ')' '{' statement '}'
						   | 'while' '(' expression ')' '{' statements '}'
letStatement : 'let' identifier '=' expression ';'
identifier : a string not beginning with a digit
expression : term (op term)?
term : identifier | constant
constant : a decimal number
op : '+' | '-' | '=' | '>' | '<'

let pi = 3.14;

let pi = 3.14

if (x < 0) {
	let x = 0;
}

if x < 0 {
	let x = 0;
}

Symbol Tables

Using the same pseudocode from earlier:

class Foo {
	field int x, y;
	static int pointCount;

	method int distance(Point other) {
		var int dx, dy;
		let dx = x - other.getX();
		let dy = y - other.getY();
		return Math.sqrt((dx*dx) + (dy*dy));
	}
}

a symbol table might look like the following:

Above, we see four columns. The name column provides the name for each variable, the type the type, etc. The # is a running count of times the kind variable kind has appeared, starting at 0. Thus, after the variable y, we have two field variables, yielding the 1 we see in the # column

The class method is a little different. Here, the symbol table might look like the following:

Why doesn't this look like the other symbol table? Because this is a class method. If it were a function, we would have just three variables: dx, dy, and other. And because it's a method, it can only act on the current object. The rest of the symbol table is as we'd expect:

The Code Writer

The program responsible for creating and updating the symbol table is the codewriter. To do so, the codewriter must do two things:

1. Handle variable declarations, and
2. Handle variable usage

double y = 1;
class Foo {
	field n = 0;
	static int count;
}

let x = y - other.getX();

Nested Scoping

In languages like Java and C++, programmers have access to unlimited nested scoping. For example, say we had the following pseudocode in such a language:

class foo {
	// code_block_1
	method f() {
		// code_block_2
		let x;
		{
			// code_block_3
			let x;
			{
				// code_block_4
				let x;
				for (let i = 0; i < arr.length; i++) {
					// code_block_5
					{
						// code_block_6_a
						let x;
					}
					{
						// code_block_6_b
						let x;
					}
				}
			}
		}
	}
}

In the code above, every opening curly brace and its closing curly brace denotes scope. Because these are all separate scopes, the identifier x can be reused multiple times throughout the code. How is this accomplished? By creating a linked list of symbol tables.

As we saw earlier, when a program is fed to the compiler, it will first look for the main entry point. In languages like C++, this is indicated by the function main() and in Java, by the class Main. Focusing on the compiler's codewriter, a symbol table is created for the program. When the codewriter encounters a scope (e.g., a method), it creates symbol table for that method, and then links that symbol table to the class- or program-level symbol table. When it encounters a scope within the method, it creates another symbol table for that scope, and links that scope to the method's symbol table. And when it encounters another scope it links that, and so on. This results in a linked list that looks like:

where each node in the linked list is a symbol table.

Handling Expressions