C++ Compiler From Scratch
Implemented a multi-stage Datalog compiler and interpreter in C++ for BYU's CS 236 course. Across five linked projects, I built the scanner, parser, relational database evaluator, interpreter, and graph-based rule optimization logic. The work demonstrates data-structure design, parsing, graph traversal, and performance-oriented problem solving.
Overview
This project was completed in BYU CS 236: Discrete Structures. Over the course of the class, I built a Datalog scanner, parser, relational database, interpreter, and optimized rule evaluation pipeline in C++.
More information about the project sequence is available on the course lab page.
Project Components
Data Scanner: Read a text file, identify Datalog tokens, and output the resulting token stream.
Data Parser: Parse a Datalog program and build a structured representation of its contents.
The Relational Database: Use relational operations to evaluate queries from Datalog facts.
The Datalog Interpreter: Add join and union operations to evaluate Datalog rules.
Optimizing Rule Evaluation: Build a dependency graph and apply depth-first search to improve rule evaluation performance.
Timeline
- Duration: January 2025 - April 2025
- Total time: 50 hours