DZone Snippets: interpreter code

A solution for the "Interpreter" problem

jmftrindade (Joana M. F. da Trindade) — Tue, 18 Mar 2008 09:26:35 GMT

A solution for the "Interpreter" problem.

Problem description:
http://icpcres.ecs.baylor.edu/onlinejudge/external/100/10033.html

Author: Joana Matos Fonseca da Trindade
Date: 2008.03.16



/* 

 * Solution for the "Interpreter" problem.

 * UVa ID: 10033

 */

#include 



#define MAX_REG 10

#define MAX_RAM 1000



int pointer;

int regArray[MAX_REG];

int ram[MAX_RAM];



/* initialize registers and ram */

int init() {

	int i;

	for (i = 0; i < MAX_REG; i++) {

		regArray[i] = 0;

	}

	for (i = 0; i < MAX_RAM; i++) {

		ram[i] = 0;

	}

	

}



/* decode instruction */

int decode() {

	int command, a1, a2;

	command = ram[pointer] / 100;

	a1 = (ram[pointer] % 100) / 10;

	a2 = ram[pointer] % 10;

	

	switch (command) {

		/* halt */

		case 1 :		

			return 0;

			break;

			

		/* set register a1 to a2 */

		case 2 :

			regArray[a1] = a2;

			pointer++;

			break;

			

		/* add a2 to register a1 */

		case 3 :

			regArray[a1] = (regArray[a1] + a2) % 1000;

			pointer++;

			break;

			

		/* multiply register a1 by a2 */

		case 4 :

			regArray[a1] = (regArray[a1] * a2) % 1000;

			pointer++;

			break;

			

		/* set register a1 to the value of register a2 */

		case 5 : 

			regArray[a1] = regArray[a2];

			pointer++;

			break;

			

		/* add the value of register a2 to register a1 */

		case 6 : 

			regArray[a1] = (regArray[a1] + regArray[a2]) % 1000;

			pointer++;

			break;

			

		/* multiply register a1 by the value of register a2 */

		case 7 :

			regArray[a1] = (regArray[a1] * regArray[a2]) % 1000;

			pointer++;

			break;

			

		/* set register a1 to the value in RAM whose address is in register a2 */

		case 8 :

			regArray[a1] = ram[regArray[a2]];

			pointer++;

			break;			

			

		/* set the value in RAM whose address in in register a2 to that of register a1 */

		case 9 :

			ram[regArray[a2]] = regArray[a1];

			pointer++;

			break;			

			

		/* goto */		

		case 0 :

			if (regArray[a2] != 0) {

				pointer = regArray[a1];

			} else {

				pointer++;

			}

			break;			

			

		default: 

			break;

	}

	return 1;	

}



/* main */

int main (int argc, const char * argv[]) {

	int i, j, cases, num_instr;

	char instr[5];



	scanf("%d", &cases);

	fgets(instr, sizeof(instr), stdin);

	fgets(instr, sizeof(instr), stdin);

	num_instr = 0;

	

	/* for the number of test cases specified */

	for (i = 0; i < cases; i++) {

		init();

		

		pointer = 0;

		

		if (i != 0) {

			printf("\n");

		}

		

		/* read input ram */

		while(fgets(instr, sizeof(instr), stdin) != NULL) {

			if (instr[0] == '\n') {

				break;

			}

			ram[pointer] = (instr[0] - '0') * 100 + (instr[1] - '0') * 10 + (instr[2] - '0');

			pointer++;

		}

		

		/* decode and interpret instructions until halt */

		num_instr = 1;

		pointer = 0;

		while (decode()) {

			num_instr++;

		}	

		

		printf("%d\n",num_instr);	

	}

	

	return 0;

}

Simple integer expression interpreter

scvalex (Alexandru Scvortov) — Thu, 30 Aug 2007 14:45:36 GMT

This is a simple integer expression interpreter.



#include 

#include 

#include 

#include 



char look;

std::map table;



void getChar() {

    look = std::cin.get();

}



void error(const std::string &s) {

    std::cout << std::endl;

    std::cout << "Error: " << s << "." << std::endl;

}



void abort(const std::string &s) {

    error(s);

    exit(1);

}



void expected(const std::string &s) {

    abort(s + " Expected");

}



bool isAlpha(char c) {

    return isalpha(c);

}



bool isDigit(char c) {

    return isdigit(c);

}



bool isAlNum(char c) {

    return isalnum(c);

}



bool isAddop(char c) {

    return ((c == '+') || (c == '-'));

}



bool isMulop(char c) {

    return (('*' == c) || ('/' == c));

}



bool isWhite(char c) {

    return ((' ' == c) || ('\t' == c));

}



void skipWhite() {

    while (isWhite(look))

        getChar();

}



void match(char x) {

    if (look != x)

        expected(std::string("\"") + x + "\"");

    else {

        getChar();

        skipWhite();

    }

}



void emit(const std::string &s) {

    std::cout << "\t"  << s;

}



void emitLn(const std::string &s) {

    emit(s);

    std::cout << std::endl;

}



void newLine() {

    if (look == '\n')

        getChar();

}



std::string getName() {

    if (!isAlpha(look))

        expected("Name");



    std::string name;

    while (isAlNum(look)) {

        name += look;

        getChar();

    }

    skipWhite();



    return name;

}



int getNum() {

    int value(0);



    if (!isDigit(look))

        expected("Integer");



    while (isDigit(look)) {

        value = value * 10 + look - '0';

        getChar();

    }

    skipWhite();



    return value;

}



int expression();



int factor() {

    int ret;



    if (look == '(') {

        match('(');

        ret = expression();

        match(')');

    } else if (isAlpha(look)) {

        std::string name = getName();

        if (table.count(name) == 0)

            table.insert(std::pair(name, 0));

        ret = table[name];

    } else

        ret = getNum();



    return ret;

}



int term() {

    int value = factor();



    while (isMulop(look)) {

        if (look == '*') {

            match('*');

            value *= factor();

        } else if (look == '/') {

            match('/');

            value /= factor();

        }

    }



    return value;

}



int expression() {

    int value(0);



    if (!isAddop(look))

        value = term();



    while (isAddop(look)) {

        if (look == '+') {

            match('+');

            value += term();

        } else if (look == '-') {

            match('-');

            value -= term();

        }

    }



    return value;

}



void assignment() {

    std::string name = getName();

    match('=');

    if (table.count(name) == 1)

        table[name] = expression();

    else

        table.insert(std::pair(name, expression()));



    std::cout << name << " = " << table[name] << std::endl;

}



void init() {

    getChar();

    skipWhite();

}



int main(int argc, char *argv[]) {

    init();



    do {

        assignment();

        newLine();

    } while ((look != '.') && (look != '\n'));



    return 0;

}

Simple stack machine interpreter written in Scala

DRMacIver (David R. MacIver) — Sun, 04 Mar 2007 23:00:32 GMT

I wanted to implement a simple stack machine, and I wanted some practice with Scala. The two seemed to combine well.

I'll write up a description of the instruction set when I can be bothered, but it's hopefully pretty self explanatory.



package StackMachine;



import scala.collection.mutable._

import java.io.File;

import java.io.File._;

import java.io.BufferedReader;

import java.io.BufferedReader._ 

import java.io.InputStreamReader;

import java.io.InputStreamReader._;

import java.io.FileInputStream; 

import java.io.FileInputStream._;

import scala.collection.jcl.ArrayList;



class Memory(size : int) {

    private val internalMemory = new Array[int](size);

    

    override def toString : String = internalMemory.toString;    



    def load( location : int) = internalMemory(location % size);

    def store( location : int, value : int) { 

        internalMemory(location % size) = value; }

}



abstract class Instruction;



case class push (value : int) extends Instruction;

case class pop extends Instruction;

case class plus extends Instruction;

case class print extends Instruction;

case class break extends Instruction;

case class dup extends Instruction;

case class goto(instruction : int) extends Instruction;

case class noop extends Instruction;

case class ifCurrent(instruction : int) extends Instruction;

case class minus extends Instruction;

case class store(register : int) extends Instruction;

case class load(register : int) extends Instruction;

case class loadCurrent extends Instruction;

case class storeCurrent extends Instruction;

case class ifEmpty(instruction : int) extends Instruction;



object Instruction{

    def parse (value : String) = {

        if (value.startsWith("#")) noop()

        else {

        val split = splitString(value);

        val instruction = split._1.toLowerCase;

        val args = split._2;



        instruction match {

            case "pop"          => pop()

            case "plus"         => plus()

            case "print"        => print()

            case "push"         => push(args(0)) 

            case "break"        => break()

            case "dup"          => dup()

            case "goto"         => goto(args(0))

            case "ifstack"      => ifCurrent(args(0))

            case "store"        => store(args(0))

            case "load"         => load(args(0))

            case ""             => noop()

            case "minus"        => minus()

            case "ifempty"      => ifEmpty(args(0))

            case "loadcurrent"  => loadCurrent()

            case "storecurrent" => storeCurrent()

            case  _             => throw new Exception("Couldn't parse " + value)}}}



    private def splitString (value : String) = {

        val strings = value.split("\\s");

        

        Tuple2[String, List[int]](strings(0), 

            for {

                val i <- List.range(1, strings.length);

                strings(i) != ""}

            yield Integer.parseInt(strings(i)))

    }

}



class Machine(memorySize : int, states : Array[Instruction]) {

    val stack = new Stack[int]();

    val memory = new Memory(memorySize);

    var position = 0;

    

    private def advance { position = position + 1; }

    private def goto (instruction : int) { position = instruction - 1};    



    private def execute (instruction : Instruction) = 

        instruction match {

            // Stack manipulation

            case push(value)            => { stack += value; 

                                             advance; }

            case pop()                  => { stack.pop; 

                                             advance; }

            case dup()                  => { stack += stack.top; 

                                             advance; }

            

            // Arithmetic

            case plus()                 => { stack += (stack.pop + stack.pop); 

                                             advance; }

            

            case minus()                => { val second = stack.pop;

                                             val first = stack.pop;

                                             stack.push(if (second > first) 0 else (first - second));

                                             advance; }

            // Control flow

            // Our instructions are labelled from 1. Why? Laziness - vim does it that way.

            case goto(instruction)      => goto(instruction);

            case noop()                 => { advance; }

            

            case ifCurrent(instruction)   => { if (stack.pop == 0) goto(instruction); 

                                             else advance; }

            case ifEmpty(instruction)   => { if (stack.isEmpty) goto(instruction);

                                             else advance; }



            // Memory manipulation

            case load(register)         => { stack.push(memory.load(register));      

                                             advance; }                                   

            case store(register)        => { memory.store(register, stack.pop); 

                                             advance; }                                         

            case loadCurrent()          => { stack.push(memory.load(stack.pop)); 

                                             advance;}

            case storeCurrent()         => { val value = stack.pop;

                                             val register = stack.pop;

                                             memory.store(register, value);

                                             advance;}

            

            // IO instructions

            case print()                => { Console.println(stack.top); 

                                             advance; }

        };



    def run(){

        while (position < states.length){

            execute(states(position));

        }

    } 



    def execute (instructions : Iterable[Instruction]) : Unit = { 

        for (val instruction <- instructions)

        yield execute(instruction : Instruction);

        ();}

}



object Main{

    def main (args : Array[String]){

        if (args.length > 0){

            val file = new File(args(0));

            val reader = new BufferedReader(new InputStreamReader(new FileInputStream(file)));    



            var line = reader.readLine();

            

            val instructions = new ArrayList[Instruction]();



            while (line != null) {

                val instruction = Instruction.parse(line);

                instructions.add(instruction); 

                 

                

                line = reader.readLine();

                }



            val machine = new Machine(32, instructions.toArray);

            

            for (val i <- List.range(1, args.length))

            yield { machine.stack.push(Integer.parseInt(args(i))); }

            

            machine.run();

            

            Console.print("\n\n");

            Console.println("Machine terminated with:");

            Console.println("     Memory: " + machine.memory);

            Console.println("     Stack: " + machine.stack);

            Console.print("\n\n");

        }

        else Console.println("Please supply a file name");                

    }    

}

bf.py

mcandre (Andrew Pennebaker) — Mon, 19 Feb 2007 00:52:20 GMT

// Brainfuck Interpreter



#!/usr/bin/env python



"""A Brainfuck interpreter"""



__author__="Andrew Pennebaker (andrew.pennebaker@gmail.com)"

__date__="18 Nov 2005 - 27 Feb 2006"

__copyright__="Copyright 2006 Andrew Pennebaker"

__license__="GPL"

__version__="0.5"

__URL__="http://snippets.dzone.com/posts/show/3536"



from aio import chomp



import sys

from getopt import getopt



tape=[0]*100

address=0



def sublevel(toplevel):

	i=0



	# until a balanced-bracket code block is found, add a character



	while toplevel[0:i+1].count("[")!=toplevel[0:i+1].count("]"): i+=1



	return toplevel[1:i]



def run(instructions):

	global tape

	global address



	position=0

	while position		cmd=instructions[position]



		if cmd=="<": address-=1

		elif cmd==">": address+=1

		elif cmd=="+": tape[address]+=1

		elif cmd=="-": tape[address]-=1

		elif cmd==".": sys.stdout.write(chr(tape[address]))

		elif cmd==",":

			try: tape[address]=ord(sys.stdin.read(1))

			except: tape[address]=-1

		elif cmd=="[":

			level=sublevel(instructions[position:])

			while tape[address]!=0: run(level)



			position+=len(level)+1



		position+=1



def usage():

	print "Usage: %s [options] " % (sys.argv[0])

	print "--help (usage)"



	sys.exit()



def main():

	systemArgs=sys.argv[1:] # ignore program name



	live=False



	optlist=[]

	args=[]



	try:

		optlist, args=getopt(systemArgs, None, ["help"])

	except Exception, e:

		usage()



	live=len(args)<1



	for option, value in optlist:

		if option=="--help":

			usage()



	if live:

		print "--BF Interpreter 0.5--"

		print "  Type exit to exit."



		line="not exit"

		while line!="exit":

			sys.stdout.write("% ")

			line=chomp(sys.stdin.readline())



			if line.count("[")!=line.count("]"):

				raise "Unbalanced brackets"

			else:

				run(line)

	else:

		src=args[0]



		srcfile=open(src, "r")

		code="".join(srcfile.readlines())

		srcfile.close()



		if code.count("[")!=code.count("]"):

			raise "Unbalanced brackets"

		else:

			run(code)



if __name__=="__main__":

	try:

		main()

	except KeyboardInterrupt, e:

		pass

Math Parser //JavaScript Class

jonasraoni (Jonas Raoni Soares Silva) — Thu, 15 Jun 2006 20:34:52 GMT

This class is able to parse math expressions and also run user defined functions.

On JavaScript there's the "eval" function, that can do such things well, but this code objective was just to give me fun or a new challenge =)~

[UPDATED CODE AND HELP CAN BE FOUND HERE]

Usage:



x = new MathProcessor;

try{alert(x.parse("1+2-(3*4) + medium(2,3) - frac( 2.2231)"));}

catch(e){alert(e);}

It's possible to add more functions to the class, just add them into the "methods" property ;]

Well, that's it :)



//+ Jonas Raoni Soares Silva

//@ http://jsfromhell.com/classes/math-processor [v1.0]



MathProcessor = function(){ //v1.0

    var o = this;

    o.o = {

        "+": function(a, b){ return +a + b; },

        "-": function(a, b){ return a - b; },

        "%": function(a, b){ return a % b; },

        "/": function(a, b){ return a / b; },

        "*": function(a, b){ return a * b; },

        "^": function(a, b){ return Math.pow(a, b); },

        "~": function(a, b){ return Math.sqrt(a, b); }

    };

    o.s = { "^": 3, "~": 3, "*": 2, "/": 2, "%": 1, "+": 0, "-": 0 };

    o.u = {"+": 1, "-": -1}, o.p = {"(": 1, ")": -1};

};



MathProcessor.prototype.parse = function(e){

    for(var n, x, o = [], s = [x = this.RPN(e.replace(/ /g, "").split(""))]; s.length;)

        for((n = s[s.length-1], --s.length); n[2]; o[o.length] = n, s[s.length] = n[3], n = n[2]);

    for(; (n = o.pop()) != undefined; n[0] = this.o[n[0]](isNaN(n[2][0]) ? this.f(n[2][0]) : n[2][0], isNaN(n[3][0]) ? this.f(n[3][0]) : n[3][0]));

    return +x[0];

};



MathProcessor.prototype.methods = {

    "div": function(a, b){ return parseInt(a / b); },

    "frac": function(a){ return a - parseInt(a); },

    "sum": function(n1, n2, n3, n){ for(var r = 0, a, l = (a = arguments).length; l; r += a[--l]); return r; },

    "medium": function(a, b){ return (a + b) / 2; }

};



MathProcessor.prototype.error = function(s){

    throw new Error("MathProcessor: " + (s || "Erro na expressão"));

}



MathProcessor.prototype.RPN = function(e){

    var _, r, c = r = [, , , 0];

    if(e[0] in this.u || !e.unshift("+"))

        for(; e[1] in this.u; e[0] = this.u[e.shift()] * this.u[e[0]] + 1 ? "+" : "-");

    (c[3] = [this.u[e.shift()], c, , 0])[1][0] = "*", (r = [, , c, 0])[2][1] = r;

    (c[2] = this.v(e))[1] = c;

    (!e.length && (r = c)) || (e[0] in this.s && ((c = r)[0] = e.shift(), !e.length && this.error()));

     while(e.length){

        if(e[0] in this.u){

            for(; e[1] in this.u; e[0] = this.u[e.shift()] * this.u[e[0]] + 1 ? "+" : "-");

            (c = c[3] = ["*", c, , 0])[2] = [-1, c, , 0];

        }

        (c[3] = this.v(e))[1] = c;

        e[0] in this.s && (c = this.s[e[0]] > this.s[c[0]] ?

            ((c[3] = (_ = c[3], c[2]))[1][2] = [e.shift(), c, _, 0])[2][1] = c[2]

            : r == c ? (r = [e.shift(), , c, 0])[2][1] = r

            : ((r[2] = (_ = r[2], [e.shift(), r, ,0]))[2] = _)[1] = r[2]);

    }

    return r;

};



MathProcessor.prototype.v = function(e){

    if("0123456789.".indexOf(e[0]) + 1){

        for(var i = -1, l = e.length; ++i < l && "0123456789.".indexOf(e[i]) + 1;);

        return [+e.splice(0,i).join(""), , , 0];

    }

    else if(e[0] == "("){

        for(var i = 0, l = e.length, j = 1; ++i < l && (e[i] in this.p && (j += this.p[e[i]]), j););

        return this.RPN(l = e.splice(0,i), l.shift(), !j && e.shift());

    }

    else{

        var i = 0, c = e[0].toLowerCase();

        if((c >= "a" && c <= "z") || c == "_"){

            while(((c = e[++i].toLowerCase()) >= "a" && c <= "z") || c == "_" || (c >= 0 && c <= 9));

            if(c == "("){

                for(var l = e.length, j = 1; ++i < l && (e[i] in this.p && (j += this.p[e[i]]), j););

                return [e.splice(0,i+1).join(""), , , 0];

            }

        }

    }

    this.error();

}



MathProcessor.prototype.f = function(e){

    var i = 0, n;

    if(((e = e.split(""))[i] >= "a" && e[i] <= "z") || e[i] == "_"){

        while((e[++i] >= "a" && e[i] <= "z") || e[i] == "_" || (e[i] >= 0 && e[i] <= 9));

        if(e[i] == "("){

            !this.methods[n = e.splice(0, i).join("")] && this.error("Função \"" + n + "\" não encontrada"), e.shift();

            for(var a = [], i = -1, j = 1; e[++i] && (e[i] in this.p && (j += this.p[e[i]]), j);)

                j == 1 && e[i] == "," && (a.push(this.parse(e.splice(0, i).join(""))), e.shift(), i = -1);

            a.push(this.parse(e.splice(0,i).join(""))), !j && e.shift();

        }

        return this.methods[n].apply(this, a);

    }

};