simple stackmachine example (no parser)

stackmachine.c

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define LENGTH(a) (sizeof (a) / sizeof (a)[0])

enum {
        OP_NAME,
        OP_VARDECL,
        OP_VARLOC,
        OP_VARLOAD,
        OP_VARSTORE,
        OP_VALUE,
        OP_DUP,
        OP_POP,
        OP_ADD,
        OP_SUB,
        OP_MUL,
        OP_DIV,
        OP_LOAD,
        OP_STORE,
        OP_AND,
        OP_OR,
        OP_LT,
        OP_LE,
        OP_EQ,
        OP_JMP,
        OP_JMPIF,
        OP_PRINT,
        OP_DEBUG,
        ENUM_COUNT_OP,
};

struct Obj {
        int type;  // OP_??
        union {
                int value;
                char *name;
                int loc_addr;
                int pc;  // code position
                char *msg;  // debug message
        };
};

struct VarDecl {
        int name;
        int loc;
};

static int stack[1024];
static int size;
static int mem[1024];
static int firstvar = LENGTH(mem);  // index into mem: first cell that is variable
static struct VarDecl vars[64];
static int nvars;


static char strpool[1024];
static int strpoolsize;
static int strptr[256];
static int strptrsize;

static int intern_string(const char *str)
{
        int i, len;
        for (i = 0; i < strptrsize; i++)
                if (strcmp(str, strpool + strptr[i]) == 0)
                        return i;
        len = strlen(str);
        assert(strpoolsize + len + 1 <= LENGTH(strpool));
        assert(strptrsize < LENGTH(strptr));
        memmove(strpool + strpoolsize, str, len + 1);
        strpoolsize += len + 1;
        return strptrsize++;
}


static void push_var(int name, int loc)
{
        assert(nvars < LENGTH(vars));
        vars[nvars].name = name;
        vars[nvars].loc = loc;
        nvars++;
}

static void pop_var(void)
{
        assert(nvars > 0);
        nvars--;
}

static int lookup_var(int name)
{
        int j;
        for (j = 0; j < nvars; j++)
                if (vars[j].name == name)
                        break;
        assert(j < nvars);
        return vars[j].loc;
}

static int getmem(int a)
{
        assert(0 <= a);
        assert(a < LENGTH(mem));
        return mem[a];
}

static void setmem(int a, int x)
{
        assert(0 <= a);
        assert(a < LENGTH(mem));
        mem[a] = x;
}

static void push(int x)
{
        assert(size < LENGTH(stack));
        stack[size++] = x;
}

static int pop(void)
{
        assert(size > 0);
        return stack[--size];
}

static void interpret(struct Obj *obj, int nobj)
{
        int i, j, x, y;

        size = 0;
        nvars = 0;
        for (i = 0; i < nobj; i++) {
                switch (obj[i].type) {
                case OP_NAME:
                        push(intern_string(obj[i].name));
                        break;
                case OP_VARDECL:
                        x = pop();
                        push_var(x, --firstvar);
                        break;
                case OP_VARLOC:
                        x = pop();
                        push(lookup_var(x));
                        break;
                case OP_VARLOAD:
                        x = pop();
                        push(getmem(lookup_var(x)));
                        break;
                case OP_VARSTORE:
                        y = pop();
                        x = pop();
                        setmem(lookup_var(y), x);
                        break;
                case OP_VALUE:
                        push(obj[i].value);
                        break;
                case OP_DUP:
                        x = pop();
                        push(x);
                        push(x);
                        break;
                case OP_POP:
                        pop();
                        break;
                case OP_ADD:
                        y = pop();
                        x = pop();
                        push(x + y);
                        break;
                case OP_SUB:
                        y = pop();
                        x = pop();
                        push(x - y);
                        break;
                case OP_MUL:
                        y = pop();
                        x = pop();
                        push(x * y);
                        break;
                case OP_DIV:
                        y = pop();
                        x = pop();
                        push(x / y);
                        break;
                case OP_LOAD:
                        push(getmem(pop()));
                        break;
                case OP_STORE:
                        y = pop();
                        x = pop();
                        setmem(y, x);
                        break;
                case OP_AND:
                        y = pop();
                        x = pop();
                        push(x && y);
                        break;
                case OP_OR:
                        y = pop();
                        x = pop();
                        push(x || y);
                        break;
                case OP_LT:
                        y = pop();
                        x = pop();
                        push(x < y);
                        break;
                case OP_LE:
                        y = pop();
                        x = pop();
                        push(x <= y);
                        break;
                case OP_EQ:
                        y = pop();
                        x = pop();
                        push(x <= y);
                        break;
                case OP_JMP:
                        i = pop();
                        assert(0 <= i && i < nobj);
                        break;
                case OP_JMPIF:
                        x = pop();
                        if (x) {
                                i = obj[i].pc;
                                assert(0 <= i && i < nobj);
                                // HACK: decrement one more since it gets
                                // incremented next iteration...
                                i -= 1;
                        }
                        break;
                case OP_PRINT:
                        for (j = 0; j < size; j++)
                                printf(" %d", stack[j]);
                        printf("\n");
                        break;
                case OP_DEBUG:
                        printf("Dbg (stack %d): %s\n", size, obj[i].msg);
                        break;
                default:
                        assert(0 && "case missing!");
                        break;
                }
        }
}

int main(void)
{
        struct Obj testprog[] = {
#define NAME(n) { OP_NAME, { .name = n } }
#define VARDECL { OP_VARDECL }
#define VARLOC { OP_VARLOC }
#define VARLOAD { OP_VARLOAD }
#define VARSTORE { OP_VARSTORE }
#define LOAD { OP_LOAD }
#define STORE { OP_STORE }
#define VALUE(v) { OP_VALUE, { .value = v } }
#define DUP { OP_DUP }
#define ADD { OP_ADD }
#define MUL { OP_MUL }
#define LT { OP_LT }
#define JMP { OP_JMP }
#define JMPIF(i) { OP_JMPIF, { .pc = i } }
#define PRINT { OP_PRINT }
#define DEBUG(s) { OP_DEBUG, { .msg = s } }
                NAME("x"), VARDECL,
                VALUE(3), NAME("x"), VARSTORE,
                VALUE(1), VALUE(2), ADD,
                NAME("x"), VARLOAD, MUL,
                DUP, VALUE(28), LT, JMPIF(8),
                PRINT,
        };
        interpret(&testprog[0], LENGTH(testprog));
        return 0;
}