Purdue Hackers Interpreters Workshop

If debugging is the process of removing software bugs, then programming must be the process of putting them in.

– Edsger Dijkstra

This repository contains an implementation of the toy PH language written in Python (version 3.13 or above). File map:

• result.py: a Result type implementation taken from https://github.com/rustedpy/result
• parser_combinator.py: a parser combinator library
• ast_.py: contains AST node definitions and the language parser.
• interpreter.py: the whole point.

Link to the workshop slides. Follow along!

PH BNF grammer

Read the *, +, [...], ? symbols in the regex sense:

• *: zero or more of
• +: one or more of
• [a-z] one of the characters inside the square brackets. a-z means a to z.
• ?: zero or one of (more intuitively, "optionally")

A rule is composed of the above and |s, which mean "or".

Example rule interpretations:

• arg_list ::= expr (',' expr)*: An arg_list is composed of an expr, followed by zero or more instances of a comma and another expression.
• atom ::= ident | num | '(' atom ')': An atom is either an ident, a num or an opening brace ( followed by another atom followed by the closing brace ).

ident ::= [a-zA-Z] [a-zA-Z0-9_]*
num ::= [0-9]+
atom ::= ident
       | num
       | '(' atom ')'

arg_list ::= expr (',' expr)*

call ::= ident '(' arg_list? ')'

unary ::= '-' unary
          | call
          | atom

product ::= unary '*' unary
          | unary '/' unary
          | unary

sum ::= product '+' product
      | product '-' product
      | product

expr ::= sum '>=' sum
       | sum '<=' sum
       | sum '<' sum
       | sum '>' sum
       | sum

var_set ::= ident '=' expr
var_decl ::= 'var' ident '=' expr
return ::= 'return' expr

if ::= 'if' '(' expr ')' stmt_block ( 'else' stmt_block )?
while ::= 'while' '(' expr ')' stmt_block

stmt ::= (return | if | while | var_decl | var_set | expr) ';'
stmt_block ::= '{' stmt+ '}'

param_list ::= ident (',' ident)*
fn ::= 'fn' ident '(' param_list? ')' stmt_block

program ::= fn+