A Compiler for tinyC

A complete compiler for tinyC, a subset of C, built step by step over six assignments in the Compilers Laboratory at IIT Kharagpur (Autumn 2022). It takes tinyC source through lexing, parsing and three-address-code generation down to x86-64 assembly that links into a native Linux executable.

Built with flex, bison and C++.

flowchart LR
    src["tinyC source (.c)"] --> lex["Lexer<br/>flex"]
    lex -- tokens --> parse["Parser<br/>bison"]
    parse --> tac["Three-address code<br/>+ symbol tables"]
    tac --> asm["x86-64 assembly (.s)"]
    asm -- "gcc + I/O library" --> bin["Executable"]

Loading

Assignments

#	Folder	Stage	What it does
1	01-x86-assembly	Groundwork	Compiles a C program with gcc -S and annotates every line of the x86-64 output, to learn the calling convention and stack-frame layout the code generator later has to produce.
2	02-io-library	Runtime library	printStr, printInt, printFlt, readInt and readFlt, written in C with inline-assembly syscalls and no libc I/O. Packaged as a static library that compiled tinyC programs link against.
3	03-lexer	Lexical analysis	flex specification for tinyC: keywords, identifiers, integer, float and character constants, string literals, punctuators, and single-line and block comments.
4	04-parser	Syntax analysis	bison grammar for the full tinyC language (expressions, declarations, statements, function definitions). Prints the reduction sequence and reports syntax errors with line numbers.
5	05-tac-generator	Intermediate code	Syntax-directed translation into three-address code (quads), with nested symbol tables, type checking and conversions, and backpatching for boolean expressions and control flow.
6	06-target-codegen	Code generation	Turns the quads into x86-64 assembly: activation records, stack offsets for locals and parameters, parameter passing, global data, and string literals in .rodata. Links against the assignment 2 library.

Each folder includes the original problem statement as a PDF.

What tinyC supports

• Types: int, char, float, void, pointers, one-dimensional arrays
• Expressions: arithmetic, relational, logical (with short-circuiting), bitwise, shift, unary & * + - !, increment and decrement, the ternary ?:, assignment
• Statements: if / else, for, while, do … while, return, blocks with nested scopes
• Functions: declarations, definitions, array and pointer parameters, recursion
• Globals: global variables with initialisers

The code generator (assignment 6) covers the integer, character, pointer and array subset. Floating-point and bitwise operations are translated to TAC only.

Example

From 06-target-codegen/ass6_20CS10024_20CS30015_test1.c, a binary search:

int binarySearch (int a[], int l, int r, int x) {
    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] == x) {
            return mid;
        ...

Three-address code (excerpt from quads1.out):

8   : binarySearch:
9   :    t1 = 1
10  :    if l <= r goto 14
11  :    t1 = 0
12  :    goto 50
14  :    t2 = l + r
15  :    t3 = 2
16  :    t4 = t2 / t3
17  :    mid = t4
...
22  :    t7 = a[t5]
24  :    if t7 == x goto 28
28  :    return mid

x86-64 assembly (excerpt). Each quad is emitted as a comment above its translation:

binarySearch:
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$80, %rsp
# if l <= r goto .L0
	movl	24(%rbp), %eax
	cmpl	32(%rbp), %eax
	jg	.L20
	jmp	.L0
# t2 = l + r
.L0:
	movl	24(%rbp), %eax
	movl	32(%rbp), %edx
	addl	%edx, %eax

The quad files also print every symbol table: the global table and one per function, with each entry's name, type, initial value, size, offset and nested table.

Building and running

Requirements

• flex
• bison 3.x (the grammars use %empty)
• gcc / g++
• x86-64 Linux to run the generated programs. Assignments 2 and 6 use raw Linux syscalls and emit x86-64 assembly.

On macOS, the system bison is 2.3, which is too old. Install a newer one with brew install bison and put $(brew --prefix bison)/bin first on your PATH. Assignments 3–5, and the compiler in assignment 6, build and run on macOS. Running the programs that assignment 6 compiles needs x86-64 Linux, for example a VM or a Docker container.

Commands

# 2 – I/O library and its test driver
cd 02-io-library && make && ./a.out

# 3 – lexer; writes the token stream to ass3_..._output.txt
cd 03-lexer && make

# 4 – parser; writes the reduction trace to output.txt
#     (line 53 of the test file has a deliberate syntax error)
cd 04-parser && make

# 5 – TAC generator; writes ass5_..._quads{1..6}.out
cd 05-tac-generator && make test

# 6 – full compiler: quads, .s files, link, and run all six test programs
cd 06-target-codegen && make test

# compile your own program
./parser.out myprog < myprog.c > myprog_quads.out   # writes ass6_20CS10024_20CS30015_myprog.s
gcc ass6_20CS10024_20CS30015_myprog.s -L. -lass2_20CS10024 -no-pie -o myprog

Run make clean in any folder to remove the build output.

Test programs

Assignment 5	Assignment 6
1. Declarations	1. Binary search over a read-in array
2. Function calls, conditionals, ternary	2. Recursive Fibonacci, globals, arithmetic
3. Arrays, loops, nested loops	3. Same as test 2
4. Type casting and pointers	4. Maximum subarray sum (array parameters)
5. Nested if-else and recursion	5. Merge sort
6. Recursion and loops (Fibonacci)	6. Pointers, do … while, globals

Repository layout

01-x86-assembly/    annotated gcc output for a sample C program
02-io-library/      myl.h + syscall-based I/O library + test driver
03-lexer/           .l spec, driver, test input, token output
04-parser/          .l + .y, driver, test input
05-tac-generator/   .l + .y, translator.{h,cxx}, tests and quad outputs
06-target-codegen/  .l + .y, translator.{h,cxx}, target_translator.cxx,
                    I/O library, tests and quad outputs

Authors

• Deepiha S (20CS30015)
• Devendra Palod (20CS10024)

Compilers Laboratory, Department of Computer Science and Engineering, IIT Kharagpur, Autumn 2022.