struct-prog-lang: A Small Language Interpreter (Python)

A tokenizer, recursive-descent parser, and tree-walking evaluator for a tiny dynamic language, with a final project that adds callable functions and a math standard library.

Overview

This is an interpreter for a small dynamic language, built in Python across a Kent State course in the structure of programming languages. Source text runs through three stages. A tokenizer turns characters into tagged tokens. A recursive-descent parser turns the token stream into an abstract syntax tree built from nested Python dictionaries. A tree-walking evaluator visits that tree and produces values.

The language supports integer and float arithmetic, comparison and boolean operators, variables, if/else, while, and print. The course builds it up one topic at a time, from a single-integer evaluator in topic-01 to a grammar-verified parser in topic-06.

My final project extends that base. I added a function-call syntax to the grammar, wired it through the parser into a call AST node, and implemented a math standard library in the evaluator. I also added a do ... while loop and a small course-specific statement.

My Contributions

The final project lives in final-project/. It starts from the topic-06 interpreter and adds the following. Everything here is my own work for the course.

Function-call syntax and the call AST node

I extended the factor grammar rule so an identifier followed by ( is parsed as a function call instead of a bare variable. In parser.py, parse_factor now checks whether the token after an identifier is an open paren. If it is, it reads a comma-separated argument list, parsing each argument as a full expression, and emits a node:

{"tag": "call", "name": func_name, "args": [ ...argument ASTs... ]}

To make commas work in argument lists, I added a , token to tokenizer.py.

Math standard library in the evaluator

In evaluator.py I added a call branch that evaluates each argument and dispatches on the function name. I implemented these functions by hand rather than calling Python's math module, so the rounding and sign behavior is explicit:

• pow(base, exp) and sqrt(x)
• cbrt(x) and root(x, n), both with correct handling of negative inputs for odd roots
• floor(x) and ceil(x), written to behave correctly for negative numbers
• factorial(n), with a guard for negative input
• gcf(a, b, ...), a variadic greatest-common-factor using the Euclidean algorithm

sqrt, cbrt, and root snap their result to the nearest integer when floating-point error puts them within 1e-9 of a whole number, so sqrt(9) returns 3 rather than 2.9999999999.

do ... while loop

I added a do_while_statement grammar rule, a parse_do_while_statement function, and a do_while evaluator branch. The body runs once before the condition is checked, which while alone cannot express. I added a do keyword token for this.

sopatz statement

A small course-specific statement. It parses to a {"tag": "sopatz"} node, and evaluating it injects _kentid_ into the environment. I added the sopatz keyword token and a parse_sopatz_statement function.

Test programs

dw_math.t drives the do-while loop and every math function. homework2.t exercises if, the sopatz statement, and identifier lookup. Each module also keeps its own test_* suite, and parser.py cross-checks every grammar rule against a parsing function that carries the same rule in its docstring.

Attribution

This repository is a fork of the course interpreter framework sopatz/struct-prog-lang. The incremental topic-01 through topic-06 folders are the course scaffold, which I built by following the course as the instructor introduced each topic. The final-project/ folder is my extension and is my own academic work. The final-project/ parser, evaluator, tokenizer, and runner are identical to my topic-06 checkpoint plus the additions described above.

Architecture

flowchart LR
    SRC["Source text<br/>(.t program)"] --> TOK["Tokenizer<br/>tokenize()"]
    TOK -->|"list of token dicts<br/>{tag, value, position}"| PARSE["Parser<br/>parse() (recursive descent)"]
    PARSE -->|"AST<br/>(nested dicts/lists)"| EVAL["Evaluator<br/>evaluate(ast, environment)"]
    EVAL -->|"values + print output"| OUT["Result"]

Loading

Getting Started

You need Python 3. There are no third-party dependencies.

Run a .t program by passing its path to the runner from inside final-project/:

cd final-project
python runner.py homework2.t
python runner.py dw_math.t

runner.py reads the file, tokenizes it, parses it to an AST, and evaluates it. Output appears on stdout from print statements.

Run the per-module test suites directly:

python tokenizer.py
python parser.py
python evaluator.py

Repository Layout

struct-prog-lang/
├── topic-01-integers/            # course: evaluate a single integer
├── topic-02-expressions/         # course: arithmetic expressions
├── topic-03-environments/        # course: variables and environments
├── topic-04-assignments/         # course: assignment statements
├── topic-05-control_structures/  # course: if / while / print
├── topic-06-grammar-verification/# course: grammar-checked parser
└── final-project/                # my final project
    ├── tokenizer.py              #   + do, sopatz, comma tokens
    ├── parser.py                 #   + function-call factor, do-while, sopatz
    ├── evaluator.py              #   + call dispatch, math library, do-while
    ├── runner.py                 #   entry point: file -> tokens -> AST -> eval
    ├── homework2.t               #   if / sopatz test program
    ├── dw_math.t                 #   do-while + math library test program
    └── trivial                   #   shell wrapper around runner.py

The topic-* folders are the course progression and show the interpreter growing one feature at a time. The final-project/ folder is where I took the finished base and extended it.

Roadmap

Ideas I would pursue if I kept building on this:

• Move the math functions out of the evaluator switch into a registered function table so adding a function does not mean editing the evaluator.
• Add user-defined functions to the language itself, with their own parameter scope.
• Add string and array values, which the tokenizer and grammar do not yet model.
• Replace the per-module test_* functions with a single pytest suite.

License & Credits

No LICENSE file ships with this repository or its upstream at the time of writing, so no license terms are stated here. The interpreter framework and the topic-* course progression come from the Kent State Structure of Programming Languages course and its instructor repository, sopatz/struct-prog-lang. The additions in final-project/ are my own academic work. If you reuse anything here, credit the course framework to sopatz and check with the course before assuming any license.