stacks in interpreters

[Ed Davis]

I see on many your and other authors
stack-this ,..stack--that

How should look stack-less interpreter?
like mine..even i use some sort of stack for FOR/GOSUB blocks

I'm not really sure what you are asking, sorry.

But maybe an example or two will help?

A simple byte-code interpreter, that uses a stack.  The stack is used to hold values.

Code: [Select]

/*------------------------------------------------------------------------
  Simple expression parser.
  Generates code for a simple virtual machine, and then executes it.
  ed_davis2
  yahoo.com
 ------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

typedef enum {eofsym, number, lparen='(', rparen=')', star='*',
    plus='+', minus='-', slash='/', powsym='^'} Symbol;

typedef enum {o_push, o_neg, o_mul, o_div, o_add, o_sub, o_pow, o_prt} Opcodes;

int code[100], *cp;

enum {False=0, True=1};

char in_str[1000], *in_ptr;
Symbol sym;
int num, ch;

int error(char msg[]) {
    printf(msg);
    exit(2);
    return 0;
}

int interpret(void) {
    int pc, sp;
    int stack[100];

    sp = pc = 0;
    for (;;) {
        Opcodes opcode = code[pc++];
        switch (opcode) {
            case o_push: stack[sp++] = code[pc++]; break;
            case o_add:  --sp; stack[sp - 1] += stack[sp]; break;
            case o_sub:  --sp; stack[sp - 1] -= stack[sp]; break;
            case o_mul:  --sp; stack[sp - 1] *= stack[sp]; break;
            case o_div:  --sp; stack[sp - 1] /= stack[sp]; break;
            case o_pow:  --sp; stack[sp - 1] = pow(stack[sp - 1], stack[sp]); break;
            case o_neg:  --sp; stack[sp - 1] = -stack[sp - 1]; break;
            case o_prt:  return stack[sp - 1];
        }
    }
}

void emit(int op, int n) {
    *cp++ = op;
    *cp++ = n;
}

void emit_op(int op) {
    *cp++ = op;
}

void getsym(void) {
    while ((ch = *in_ptr++) == ' ')
        ;

    if (ch < ' ') sym = eofsym;
    else if (strchr("()*+-/^", ch)) {
        sym = (Symbol)ch;
    } else if (isdigit(ch)) {
        num = 0;
        do {
            num = 10 * num + (ch - '0');
            ch = *in_ptr++;
        } while (isdigit(ch));
        --in_ptr;
        sym = number;
    } else {
        error("unrecognized character");
        sym = eofsym;
    }
}

int accept(Symbol s) {
    if (sym == s) {
        getsym();
        return True;
    }
    return False;
}

int binary_prec(Symbol op) {
    if (op == plus || op == minus) return 1;
    if (op == star || op == slash) return 2;
    if (op == powsym) return 3;
    return error("binary_prec: unknown operator");
}

void expr(int p) {
    Symbol op;

    if (accept(number)) emit(o_push, num);
    else if (accept(minus)) {
        expr(4);
        emit_op(o_neg);
    } else if (accept(lparen)) {
        expr(0);
        if (!accept(rparen))
            error("expecting ')'");
    } else
        error("factor: syntax error");

    while ((sym >= star && sym <= powsym) && binary_prec(sym) >= p) {
        op = sym;
        getsym();
        expr(binary_prec(op) + 1);

        switch (op) {
            case star:   emit_op(o_mul); break;
            case slash:  emit_op(o_div); break;
            case plus:   emit_op(o_add); break;
            case minus:  emit_op(o_sub); break;
            case powsym: emit_op(o_pow); break;
            default: error("expr: unexpected error");
        }
    }
}

int main() {
    for (;;) {
        printf("Enter expression:");
        if (fgets(in_str, sizeof(in_str) - 1, stdin) == NULL || *in_str == '\n')
            break;

        in_ptr = in_str;
        getsym();
        cp = code;
        expr(0);
        emit_op(o_prt);
        printf("%d\n", interpret());
    }
    return 0;
}

A simple pure interpreter, e.g., no pre-processing, just parse and interpret while parsing:

Code: [Select]

/*------------------------------------------------------------------------
  Simple expression parser.
  Interprets as it goes.
  ed_davis2
  yahoo.com
 ------------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

typedef enum {eofsym, number, lparen='(', rparen=')', star='*',
    plus='+', minus='-', slash='/', powsym='^'} Symbol;

enum {False=0, True=1};

char in_str[1000], *in_ptr;
Symbol sym;
int num, ch;

int error(char msg[]) {
    printf(msg);
    exit(2);
    return 0;
}

void getsym(void) {
    while ((ch = *in_ptr++) == ' ')
        ;

    if (ch < ' ') sym = eofsym;
    else if (strchr("()*+-/^", ch)) {
        sym = (Symbol)ch;
    } else if (isdigit(ch)) {
        num = 0;
        do {
            num = 10 * num + (ch - '0');
            ch = *in_ptr++;
        } while (isdigit(ch));
        --in_ptr;
        sym = number;
    } else {
        error("unrecognized character");
        sym = eofsym;
    }
}

int accept(Symbol s) {
    if (sym == s) {
        getsym();
        return True;
    }
    return False;
}

int binary_prec(Symbol op) {
    if (op == plus || op == minus) return 1;
    if (op == star || op == slash) return 2;
    if (op == powsym) return 3;
    return error("binary_prec: unknown operator");
}

int expr(int p) {
    int n;
    Symbol op;

    if (accept(number)) n = num;
    else if (accept(minus)) n = -expr(4);
    else if (accept(lparen)) {
        n = expr(0);
        if (!accept(rparen))
            error("expecting ')'");
    } else
        error("factor: syntax error");

    while ((sym >= star && sym <= powsym) && binary_prec(sym) >= p) {
        op = sym;
        getsym();
        switch (op) {
            case star:   n *= expr(binary_prec(op) + 1); break;
            case slash:  n /= expr(binary_prec(op) + 1); break;
            case plus:   n += expr(binary_prec(op) + 1); break;
            case minus:  n -= expr(binary_prec(op) + 1); break;
            case powsym: n = pow(n, expr(binary_prec(op))); break;
            default: error("expr: unexpected error");
        }
    }
    return n;
}

int main() {
    for (;;) {
        printf("Enter expression:");
        if (fgets(in_str, sizeof(in_str) - 1, stdin) == NULL || *in_str == '\n')
            break;

        in_ptr = in_str;
        getsym();
        printf("%d\n", expr(0));
    }
    return 0;
}

See how similar the code is?  The scanner is the same, and even the parsing is pretty similar.
The difference is that the pure interpreter interprets as it goes along, while the byte code interpreter generates instructions that will be performed later.

Look at the guts of the expression parser, for binary expressions - pure interpreter:

Code: [Select]

    while ((sym >= star && sym <= powsym) && binary_prec(sym) >= p) {
        op = sym;
        getsym();
        switch (op) {
            case star:   n *= expr(binary_prec(op) + 1); break;
            case slash:  n /= expr(binary_prec(op) + 1); break;
            case plus:   n += expr(binary_prec(op) + 1); break;
            case minus:  n -= expr(binary_prec(op) + 1); break;
            case powsym: n = pow(n, expr(binary_prec(op))); break;
            default: error("expr: unexpected error");
        }
    }

And then the byte-code interpreter:

Code: [Select]

    while ((sym >= star && sym <= powsym) && binary_prec(sym) >= p) {
        op = sym;
        getsym();
        expr(binary_prec(op) + 1);

        switch (op) {
            case star:   emit_op(o_mul); break;
            case slash:  emit_op(o_div); break;
            case plus:   emit_op(o_add); break;
            case minus:  emit_op(o_sub); break;
            case powsym: emit_op(o_pow); break;
            default: error("expr: unexpected error");
        }
    }

I hope this helps!

[Aurel]

Hi Ed
and thanks for reply..
Yes nice examples i should try and i will.

My question was about...

what exactly mean stackless interpreter ...like
stackless python ...
I mean how is possible create interpreter or programming language without any kind of stack.?

[ZXDunny]

I mean how is possible create interpreter or programming language without any kind of stack.?

It's not. Your code may work without using a stack, but your compiler will make extensive use of it when converting your code to assembly.

[n00b]

Stackless python just limits its use of the C stack. It will clear everything off the stack at the end of a function call. I was originally doing this on rcbasic v1.0. I changed it because it will produce some unintended results in recursive function calls.

For example, if you create a variable called MyVar with an initial value of 0. Then set MyVar equal to 5 before your recursive call. At the start of the call MyVar is equal to 5 instead of 0 since a new function call does not create a new instance of the variable.

[Aurel]

Well it looks that is possible
using
 continuation-passing style.
i found it here :

https://stackoverflow.com/questions/796211/what-does-it-really-mean-that-a-programming-language-is-stackless

If those guys don't lie..of course