Skip to content

Instantly share code, notes, and snippets.

@SebastianMestre
Last active November 13, 2023 22:04
Show Gist options
  • Save SebastianMestre/b84695d18ec81fee0d141af7f2f249aa to your computer and use it in GitHub Desktop.
Save SebastianMestre/b84695d18ec81fee0d141af7f2f249aa to your computer and use it in GitHub Desktop.
A simple tree-walking interpreter for the tiny language presented in this article https://sebmestre.blogspot.com/2023/11/en-writing-compiler-is-surprisingly_13.html
#include "ast.h"
#include <stdint.h>
uint64_t slots[100];
uint64_t interpret_expression(struct expression* e);
uint64_t interpret_int_literal(struct int_literal* e) {
return e->value;
}
uint64_t interpret_variable(struct variable* e) {
return slots[e->slot];
}
uint64_t interpret_negation(struct negation* e) {
return -interpret_expression(e->target);
}
uint64_t interpret_addition(struct addition* e) {
return interpret_expression(e->left_term) + interpret_expression(e->right_term);
}
uint64_t interpret_expression(struct expression* e) {
switch (e->tag) {
case EXPRESSION_INT_LITERAL:
return interpret_int_literal(&e->as_int_literal);
break;
case EXPRESSION_VARIABLE:
return interpret_variable(&e->as_variable);
break;
case EXPRESSION_NEGATION:
return interpret_negation(&e->as_negation);
break;
case EXPRESSION_ADDITION:
return interpret_addition(&e->as_addition);
break;
}
}
void interpret_statement(struct statement* e);
void interpret_assignment(struct assignment* e) {
slots[e->slot] = interpret_expression(e->value);
}
void interpret_block(struct block* e) {
for (int i = 0; i < e->step_count; ++i) {
interpret_statement(e->steps[i]);
}
}
void interpret_if_else(struct if_else* e) {
if (interpret_expression(e->cond)) {
interpret_statement(e->true_branch);
} else {
interpret_statement(e->false_branch);
}
}
void interpret_while_loop(struct while_loop* e) {
while (interpret_expression(e->cond)) {
interpret_statement(e->body);
}
}
void interpret_statement(struct statement* e) {
switch (e->tag) {
case STATEMENT_ASSIGNMENT:
interpret_assignment(&e->as_assignment);
break;
case STATEMENT_BLOCK:
interpret_block(&e->as_block);
break;
case STATEMENT_IF_ELSE:
interpret_if_else(&e->as_if_else);
break;
case STATEMENT_WHILE_LOOP:
interpret_while_loop(&e->as_while_loop);
break;
}
}
// To make the test fair, we link this against the same file that we used to test the compiler.
uint64_t fib(uint64_t n_arg) {
int n = 0;
int a = 1;
int b = 2;
int c = 3;
struct statement* stmt = block3(
assignment(a, int_literal(1)),
assignment(b, int_literal(1)),
while_loop(variable(n), block4(
assignment(c, addition(variable(a), variable(b))),
assignment(a, variable(b)),
assignment(b, variable(c)),
assignment(n, addition(variable(n), int_literal(-1)))
))
);
slots[n] = n_arg;
interpret_statement(stmt);
return slots[a];
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment