Interpreter

An interpreter for code in Backus-Naur Form.

🎥 Watch the project video

Table of Contents

1. About The Project
2. Getting Started
3. Usage
4. Contributors
5. Connect
6. License
7. Acknowledgments

About The Project

This program was developed as the culminating project for CS460: Programming Languages at Sonoma State University during the Fall 2024 semester. Collaboratively created by a team of five students, this project presents an interpreter designed to process and execute code written in Backus-Naur Form (BNF), a C-like programming language. The interpreter interprets the input in BNF, analyzes its structure and logic, and executes the corresponding computations to generate the desired output. This project exemplifies advanced concepts in parsing, syntax analysis, data structures, and interpreter design.

The interpreter was constructed through a modular design, composed of several key components that work in sequence to process the input code. These components include:

1. Comment Removal: Eliminates non-executable comments to prepare the input for further processing.

2. Tokenization: Breaks the input into meaningful tokens, such as keywords, identifiers, and symbols, forming the building blocks of the program.

3. Recursive Descent Parsing: Analyzes the tokenized input based on the defined BNF grammar, ensuring syntactical correctness while building a structural representation of the code. Generates a Concrete Syntax Tree (CST) representing program strucutre.

4. Symbol Table Generation: Creates a mapping of variables, functions, and other symbols to their corresponding definitions and values, enabling efficient lookup during execution.

5. Abstract Syntax Tree (AST) Generation: Constructs a tree representation of the program that encapsulates its logical structure and relationships, serving as the foundation for execution.

Each component builds on the outputs of the previous stage, concluding in a fully functional interpreter capable of processing complex inputs and producing correct results. This layered approach highlights the importance of modularity and abstraction in software engineering and programming language design.

This repository contains additional functionality to further integrate these components and enable the interpreter's functionality.

Getting Started

The interpreter is compatible with Windows, MacOS, and Linux.

Dependencies

This project utlizes ncurses when run on MacOS / Linux. This library can be insalled via:

MacOS

brew install ncurses

Linux

sudo apt-get install libncurses-dev

Running The Program

MacOS / Linux

1. Clone the repo

git clone https://github.com/Pip-Install-Party/Interpreter.git

2. Run the makefile

make

3. Run the executable

./interpreter.x

Windows

1. Clone the repo

git clone https://github.com/Pip-Install-Party/Interpreter.git

2. Run the makefile

 make

3. Run the executable

 ./interpreter.exe

File Output

Output will be written to Output.txt in the working directory.

Usage

The interpreter is capable of producing output for code written in Backus-Naur Form. The program may also work with some programs written in C, however differences in reserved words (such as string) may lead to unexpected output.

See getting-started.

Testing

This program contains a series of files that can be used to test the interpreter. The program's interface will prompt you to make a selection from the available test files.

In addition to interpretting code, this program also lets you test its various components. Upon starting the program, the interface will display a series of components to select from. The following components can be selected:

1. Comment Removal
2. Tokenization
3. Recursive Descent Parser
4. Symbol Table
5. Abstract Syntax Tree
6. Interpreter

The results from the selected component will print to Output.txt.

Contributors

Five students worked together to construct the interpreter.

Connect With Us

Blake Marshall - LinkedIn
Brandon Robinson - LinkedIn
Holden Ea - LinkedIn
Jacob Sellers - LinkedIn
Rolando Yax - LinkedIn

License

Distributed under the MIT License. See LICENSE. for more information.

Acknowledgments

Test files were provided by Robert Bruce.

(back to top)