Compiler From Scratch using C++

Description

BYU CS 236 Discrete Math Projects. Over the course of this class we built a Datalog Scanner, Parser, Relational Database, Datalog interpreter and then optimized the rule evaluation. More information can be found here. Descriptions that are included below are taken verabutum from the class website. Projects build upon each other.

Objectives

Data Scanner (Project 1): Write a scanner that reads a sequence of characters from a text file, identifies the datalog language tokens found in the file, and outputs each token.

Data Parser (Project 2): Write a parser that reads a datalog program from a text file, builds a data structure that represents the datalog program, and outputs the contents of the datalog program data structure.

The Relational Database (Project 3): Write an interpreter that uses relational database operations to evaluate the queries in a Datalog Program. For this project, use only the facts to evaluate the queries. (The evaluation of rules will be added in the next project.)

The Datalog Interpreter (Project 4): Add join and union operations to the relational database from the last project and use the new operations to evaluate the rules in a Datalog program.

Optimizing Rule Evaluation (Project 5): Build the dependency graph for the rules in a Datalog program and use depth-first search on the graph to improve the evaluation of the rules.

Timeline

Duration: Jan 2025 - Apr 2025

Total time: 50 hours

Technical Skills

C++

Gained greater profeciency in C++