Skip to content
smichniakPublic

About

Compiler for Latte programming language - Compiler construction Course 2022/2023

Resources

Stars

0 stars

Watchers

1 watching

Forks

Latest commit

 

History

36 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Latte Programming Language Compiler

A full-featured compiler for the Latte programming language that compiles to LLVM IR and produces executable bytecode. This compiler is implemented in Haskell and includes advanced optimization techniques.

Project Description

Latte is an imperative programming language with object-oriented features, supporting:

  • Basic data types (int, string, boolean)
  • Arrays and object-oriented programming with classes and inheritance
  • Functions with recursion
  • Control flow structures (if-else, while, for loops)
  • Method calls and polymorphism
  • Type casting and null values

The compiler performs comprehensive static type checking and generates optimized LLVM IR code with various optimization passes.

Project Structure

latte/
├── src/                          # Source code
│   ├── Main.hs                   # Main compiler entry point
│   ├── Latte.cf                  # BNFC grammar definition
│   ├── Parser/                   # Generated parser (BNFC output)
│   ├── Frontend/                 # Frontend components
│   │   ├── Typechecker.hs        # Static type checking
│   │   ├── TypecheckerEnv.hs     # Type environment management
│   │   ├── TypecheckerError.hs   # Error handling for typechecker
│   │   └── TypecheckerUtils.hs   # Utility functions for typechecking
│   └── Backend/                  # Backend components
│       ├── Compiler.hs           # Main compilation orchestration
│       ├── CompilerEnv.hs        # Compilation environment
│       ├── LLVMRep.hs            # LLVM IR representation
│       ├── ToLLVMRep.hs          # AST to LLVM IR translation
│       └── Optimisation.hs       # Code optimization passes
├── lib/
│   └── runtime.c                 # Runtime library for I/O and utilities
├── lattests/                     # Test suite
│   ├── good/                     # Valid programs with expected outputs
│   ├── bad/                      # Invalid programs (should fail compilation)
│   └── extensions/               # Extended language features tests
├── Makefile                      # Build configuration
├── latte.cabal                   # Haskell package configuration
└── run_tests.py                  # Test runner script

Frontend Architecture

  • Parser: Uses BNFC to generate parser from grammar definition (Latte.cf), producing AST representation for all language constructs
  • Typechecker (Frontend/Typechecker.hs): Performs static type analysis with comprehensive error reporting, manages symbol tables, validates inheritance hierarchies, and ensures scope-aware variable resolution

Backend Architecture

  • Code Generation (Backend/ToLLVMRep.hs): Transforms typechecked AST to LLVM IR in SSA form, handles control flow structures, and implements object-oriented features with vtables
  • LLVM Representation (Backend/LLVMRep.hs): Custom LLVM IR data structures optimized for Latte with type system mapping and basic block representations

Compilation Optimizations

The compiler implements several advanced optimization techniques in Backend/Optimisation.hs:

  • Global Common Subexpression Elimination (GCSE): Eliminates redundant computations across basic blocks by tracking and replacing duplicate expressions
  • Constant Folding: Evaluates constant expressions at compile time and reduces phi nodes with identical operands
  • Dead Code Elimination: Removes unreachable basic blocks and unused instructions
  • Phi Node Optimization: Simplifies phi nodes while maintaining SSA form for efficient control flow merging
  • Jump Optimization: Removes redundant jumps and simplifies basic block chains

The optimization pipeline runs iteratively until a fixed point is reached, ensuring maximum code improvement.

Example Program

Here's a simple Latte program demonstrating core language features:

// Simple calculator with classes
int main() {
    Calculator calc = new Calculator;
    calc.add(5);
    calc.multiply(3);
    printString("Result: ");
    printInt(calc.getResult());
    
    // Using arrays
    int[] numbers = new int[3];
    numbers[0] = 10;
    numbers[1] = 20; 
    numbers[2] = 30;
    
    int sum = sumArray(numbers, 3);
    printString("Array sum: ");
    printInt(sum);
    
    return 0;
}

int sumArray(int[] arr, int size) {
    int total = 0;
    for (int i : arr) {
        total = total + i;
    }
    return total;
}

class Calculator {
    int result;
    
    void add(int x) {
        result = result + x;
        return;
    }
    
    void multiply(int x) {
        result = result * x;
        return;
    }
    
    int getResult() {
        return result;
    }
}

This example showcases:

  • Classes and object instantiation
  • Method calls and member variables
  • Arrays and for-each loops
  • Functions with parameters and return values
  • Built-in I/O functions (printInt, printString)

Building and Installation

Prerequisites

  • GHC (Glasgow Haskell Compiler)
  • Cabal (Haskell package manager)
  • BNFC (BNF Converter)
  • LLVM toolchain (llvm-as, clang)

Build Steps

  1. Generate Parser:

    make parser
  2. Build Runtime Library:

    make runtime
  3. Compile the Compiler:

    make latc_llvm
  4. Build Everything:

    make all

Cleaning

make clean      # Remove build artifacts
make distclean  # Complete cleanup including executable

Usage

Compiling Latte Programs

./latc_llvm program.lat

This will:

  1. Parse the source file
  2. Perform type checking
  3. Generate optimized LLVM IR (program.ll)
  4. Produce executable bytecode (program.bc)

Command Line Options

./latc_llvm --help           # Display help message
./latc_llvm program.lat      # Compile program.lat

Example Usage

# Compile a simple program
./latc_llvm examples/hello.lat

# Run the compiled program (if LLVM interpreter is available)
lli hello.bc

Running Tests

The project includes a comprehensive test suite:

# Run all tests
python3 run_tests.py

# Run specific test categories
python3 run_tests.py --good lattests/good
python3 run_tests.py --bad lattests/bad

# Test with custom compiler path
python3 run_tests.py --compiler ./latc_llvm

Test Categories

  • good/: Programs that should compile and run successfully
  • bad/: Programs with errors (syntax, type, or runtime)
  • extensions/: Advanced language features (arrays, objects, inheritance)

Runtime Library

The runtime library (lib/runtime.c) provides essential functions:

  • printInt(int) - Print integer values
  • printString(char*) - Print string values
  • readInt() - Read integer from input
  • readString() - Read string from input
  • error() - Runtime error handling
  • Memory management utilities for string operations

Language Features Supported

  • Core Features: Variables, functions, basic I/O, arithmetic and logical operations
  • Control Flow: If-else statements, while loops, for-each loops
  • Data Types: Integers, booleans, strings, arrays
  • Object-Oriented: Classes, inheritance, method overriding, polymorphism
  • Advanced: Type casting, null handling, recursive functions

About

Compiler for Latte programming language - Compiler construction Course 2022/2023

Resources

Stars

0 stars

Watchers

1 watching

Forks

Releases

Packages

Contributors

Languages