Home
Welcome to the compilers wiki!
The wiki gives more in depth information about compiler implementation.
On a high level, compiler includes:
Taken from this tutorial (The author has an awesome tutorial on building interpreter with a lot of pictures! 100% recommended to check it out!)
There are a few stages a compiler goes through to compiles your code:
In a typical compiler, the scanner analyzes the source code breaks the text file into tokens. An example source code for this language is this one. A scanner in this compiler is a big switch. Its implementation is in the files scanner.h and scanner.c.
After that, the tokens are passed to the parser. The parser's job is to expects and parses the tokens according to the language grammar. The parser here is a top-down parser that allows one look ahead. Therefore, it can decide which production grammar it needs to use, or throw an error if no production rule matches. A good reference I read to understand the parser is this.
Another job of the parser is to build the abstract syntax tree (AST). This tree is useful in later stages of type checking and symbol table construction. It is entirely possible to incorporate type checking and building symbol table into the parser without having to build the AST. In fact, the parser of this compiler does just that! However, doing so makes the parser code monolithic, and even difficult at times. Almost all good and commercial compilers use an AST. For an example of a parser that does build an AST while parsing, check out this great tutorial! The Kaleidoscope programming language compiler on LLVM documentation page has a good example of a parser building AST too. The implementation of the parser for this project are in two files parser.h and parser.c.
There are a few tools out in the wild Internet to make building the scanner and parser easier. Some of them include, but not limit to: flex, bison. This article gives a good overview of all the tools.
If the parser builds the AST, the Semantic Analyzer walks the tree and checks for semantic and type correctness. That is the semantic analyzer enforces semantic rules like: - Type signatures of a procedure's arguments must match exactly their parameter declaration. - Arithmetic operations (add, sub, multiply, divide) are defined for integers and floats only. - For relational operations, only comparisons between the compatible types is possible, and that relational operators return a boolean result. - Array indexes must be of type integer. and more.
The semantic analyzer also uses the AST to build and check a scoped symbol table. As the analyzer encounters an identifier in the tree that is not a reserved word, it will check to see if the identifier has been declared in the symbol table. If the identifier is a variable, the symbol table helps the analyzer to decide whether it can declare another variable of the same name and type, to use the variable, or to throw an error. If the identifier is a procedure name, the symbol table helps the analyzer to decide whether it can declare another procedure with the same name and return type, to call the procedure, or to throw an error.
This compiler uses nested scopes, so the symbol table is actually a nested symbol table, where one symbol table holds a reference to its outer scope. The outer scope of global scope is NULL. This nested scope scheme can be compared to a linked list of symbol tables.
For this compiler, semantic checking is carried out in the files semantics.h and semantics.c. The symbol table is implemented in symbol_table.h and symbol_table.c.
The purpose of a compiler is to generate assembly language, so the linker and and assembler can translate into machine code (those 0 and 1 we all know as binary code). For that, I used the LLVM compiler. An example LLVM intermediate representation is like so (some explanations can be found in the language reference):
; ModuleID = 'codegen.bc'
source_filename = "tests/test-array.src"
target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
@format_str = private unnamed_addr constant [3 x i8] c"%d\00"
@format_str.1 = private unnamed_addr constant [3 x i8] c"%s\00"
@format_str.2 = private unnamed_addr constant [3 x i8] c"%d\00"
@format_str.3 = private unnamed_addr constant [3 x i8] c"%s\00"
@string = private unnamed_addr constant [2 x i8] c" \00"
declare i32 @printf(...)
declare i32 @scanf(...)
define void @main() {
main_entry:
%numbers = alloca [10 x i32]
%res = alloca [10 x i32]
%i = alloca i32
store i32 0, i32* %i
br label %start_loop
start_loop: ; preds = %loop, %main_entry
%i1 = load i32, i32* %i
%add = add i32 %i1, 1
store i32 %add, i32* %i
%i2 = load i32, i32* %i
%lt = icmp slt i32 %i2, 10
br i1 %lt, label %loop, label %end_loop
loop: ; preds = %start_loop
%i3 = load i32, i32* %i
%dest_array_GEP = getelementptr inbounds [10 x i32], [10 x i32]* %numbers, i32 0, i32 %i3
%i4 = load i32, i32* %i
store i32 %i4, i32* %dest_array_GEP
br label %start_loop
end_loop: ; preds = %start_loop
%factor_array_GEP = getelementptr inbounds [10 x i32], [10 x i32]* %numbers, i32 0, i32 0
%factor_array_GEP5 = getelementptr inbounds [10 x i32], [10 x i32]* %res, i32 0, i32 0
call void @square_array(i32* %factor_array_GEP, i32* %factor_array_GEP5)
store i32 0, i32* %i
br label %start_loop6
start_loop6: ; preds = %loop7, %end_loop
%i9 = load i32, i32* %i
%add10 = add i32 %i9, 1
store i32 %add10, i32* %i
%i11 = load i32, i32* %i
%lt12 = icmp slt i32 %i11, 10
br i1 %lt12, label %loop7, label %end_loop8
loop7: ; preds = %start_loop6
%i13 = load i32, i32* %i
%factor_array_GEP14 = getelementptr inbounds [10 x i32], [10 x i32]* %res, i32 0, i32 %i13
%factor_array_load = load i32, i32* %factor_array_GEP14
call void @putinteger(i32 %factor_array_load)
call void @putstring(i8* getelementptr inbounds ([2 x i8], [2 x i8]* @string, i32 0, i32 0))
br label %start_loop6
end_loop8: ; preds = %start_loop6
ret void
}
define void @getinteger(i32* %val) {
getinteger:
%getinteger1 = call i32 (...) @scanf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @format_str, i32 0, i32 0), i32* %val)
ret void
}
define void @getstring(i8* %val) {
getstring:
%getstring1 = call i32 (...) @scanf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @format_str.1, i32 0, i32 0), i8* %val)
ret void
}
define void @putinteger(i32 %val) {
putinteger:
%putinteger1 = call i32 (...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @format_str.2, i32 0, i32 0), i32 %val)
ret void
}
define void @putstring(i8* %val) {
putstring:
%putstring1 = call i32 (...) @printf(i8* getelementptr inbounds ([3 x i8], [3 x i8]* @format_str.3, i32 0, i32 0), i8* %val)
ret void
}
define void @square_array(i32*, i32*) {
square_array:
%array = alloca i32*
store i32* %0, i32** %array
%result = alloca i32*
store i32* %1, i32** %result
%i = alloca i32
store i32 0, i32* %i
br label %start_loop
start_loop: ; preds = %loop, %square_array
%i1 = load i32, i32* %i
%add = add i32 %i1, 1
store i32 %add, i32* %i
%i2 = load i32, i32* %i
%lt = icmp slt i32 %i2, 10
br i1 %lt, label %loop, label %end_loop
loop: ; preds = %start_loop
%i3 = load i32, i32* %i
%dest_pointer_load = load i32*, i32** %result
%dest_pointer_GEP = getelementptr inbounds i32, i32* %dest_pointer_load, i32 %i3
%i4 = load i32, i32* %i
%factor_pointer_load = load i32*, i32** %array
%factor_pointer_GEP = getelementptr inbounds i32, i32* %factor_pointer_load, i32 %i4
%factor_array_load = load i32, i32* %factor_pointer_GEP
%i5 = load i32, i32* %i
%factor_pointer_load6 = load i32*, i32** %array
%factor_pointer_GEP7 = getelementptr inbounds i32, i32* %factor_pointer_load6, i32 %i5
%factor_array_load8 = load i32, i32* %factor_pointer_GEP7
%mul = mul i32 %factor_array_load, %factor_array_load8
store i32 %mul, i32* %dest_pointer_GEP
br label %start_loop
end_loop: ; preds = %start_loop
ret void
}
The lli command directly executes program from LLVM bitcode.