MacHack 1998/MacHack 1998.toast/Programming Contest/~Solutions Submitted/Problem 10 - Three and One/Solution.cp

Text File | 1998-06-19 | 7.2 KB | 389 lines | [TEXT/CWIE]

/*
Problem 10 - Interpreter

Write an interpreter for this simple 32-bit integer language with 26 registers
labeled A-Z.

type RegisterArray = array[0..25] of SInt32;

procedure Interpret( source: Handle; var result: RegisterArray );

source consists of a number of lines of the form:

[<label>:][<tab><instruction><tab><operand-list>]<cr>

<label> is a sequence of at least two alphanumerics (0-9a-zA-Z_)
(casesensitive).
<operand-list> is a sequence of operators seperated by commas
other than the tabs and crs, no white space is allowed.

<instruction> (and appropriate operands are:

MOVE    <value>,<register>            (set <register> to <value>)
ADD     <value1>,<value2>,<register>  (set <register> to <value1>+<value2>)
SUB     <value1>,<value2>,<register>  (set <register> to <value1>-<value2>)
JMP     <label>                       (jump to line labeled with <label>)
JEQ     <value1>,<value2>,<label>     (jump to <label> if <value1> = <value2>)
JLE     <value1>,<value2>,<label>     (jump to <label> if <value1> <= <value2>)
JSR     <label>                       (jump to subroutine at <label>)
RTS                                   (return from subroutine)
PUSH    <value>                       (push value on to stack)
POP     <register>                    (pop value from stack)

<register> is a single uppercase letter in the range A..Z
<number> is an optional minus sign followed by decimal digits
<value> is a <register> or a <number>

Note that the data stack and subroutine stack are independent stacks.  A RTS is
used to stop the program (that is, consider that you have JSRed to the initial
line of the source handle).  For example:

    PUSH    10
    JSR    setA
    JSE setB
    RTS
setA:
    POP    A
    RTS
setB:    MOVE    A,B
    RTS

Interpret takes the source handle and JSRs to it, presetting the registers
according to the register array.  When the code returns, the register array is
set to the final value of all the registers.  Both subroutine and data stacks
should be large (at least 1000 entries each).
*/

#include "Solution.h"
#include <map>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <stack>
#include <ctype.h>

// Fill in your solution and then submit this folder

// Team Name: Three and One!

struct Instruction {
    virtual void Execute() const = 0;
};

__MSL_FIX_ITERATORS__(Instruction*);

std::map<std::string, int instruction> labels;
std::vector<Instruction*> program;
RegisterArray registers;
int pc;
std::stack<int> callStack;
std::stack<int> valueStack;
bool done;

struct Value {
    int Evaluate() const;
    bool reg;
    int valueOrRegister;
};

void
SkipCommasSpacesTabs(std::istream& s)
{
    while (1) {
        char character = s.get();
        if (character != ',' && character != ' ' && character != 9) {
            s.putback(character);
            return;
        }
    }
}

int
ReadRegister(std::istream& s)
{
    SkipCommasSpacesTabs(s);
    return toupper(s.get()) - 'A';
}

std::string
ReadLabel(std::istream& s)
{
    SkipCommasSpacesTabs(s);
    std::string label;
    s >> label;
    return label;
}

Value
ReadValue(std::istream& s)
{
    SkipCommasSpacesTabs(s);

    Value v;

    char character = toupper(s.get());
    if (character >= 'A' && character <= 'Z') {
        v.valueOrRegister = character - 'A';
        v.reg = true;
        return v;
    }

    s.putback(character);
    s >> v.valueOrRegister;
    v.reg = false;
    return v;
}

int
Value::Evaluate() const
{
    if (!reg)
        return valueOrRegister;
    return registers[valueOrRegister];
}

struct MOVE : Instruction {
    MOVE(istream&);
    virtual void Execute() const;
    Value value;
    int reg;
};

struct ADD : Instruction {
    ADD(istream&);
    virtual void Execute() const;
    Value value1;
    Value value2;
    int reg;
};

struct SUB : Instruction {
    SUB(istream&);
    virtual void Execute() const;
    Value value1;
    Value value2;
    int reg;
};

struct JMP : Instruction {
    JMP(istream&);
    virtual void Execute() const;
    std::string label;
};

struct JEQ : Instruction {
    JEQ(istream&);
    virtual void Execute() const;
    Value value1;
    Value value2;
    std::string label;
};

struct JLE : Instruction {
    JLE(istream&);
    virtual void Execute() const;
    Value value1;
    Value value2;
    std::string label;
};

struct JSR : Instruction {
    JSR(istream&);
    virtual void Execute() const;
    std::string label;
};

struct RTS : Instruction {
    RTS();
    virtual void Execute() const;
};

struct PUSH : Instruction {
    PUSH(istream&);
    virtual void Execute() const;
    Value value;
};

struct POP : Instruction {
    POP(istream&);
    virtual void Execute() const;
    int reg;
};

MOVE::MOVE(istream& s)
{
    value = ReadValue(s);
    reg = ReadRegister(s);
}

void MOVE::Execute() const
{
    registers[reg] = value.Evaluate();
}

ADD::ADD(istream& s)
{
    value1 = ReadValue(s);
    value2 = ReadValue(s);
    reg = ReadRegister(s);
}

void ADD::Execute() const
{
    registers[reg] = value1.Evaluate() + value2.Evaluate();
}

SUB::SUB(istream& s)
{
    value1 = ReadValue(s);
    value2 = ReadValue(s);
    reg = ReadRegister(s);
}

void SUB::Execute() const
{
    registers[reg] = value1.Evaluate() - value2.Evaluate();
}

JMP::JMP(istream& s)
{
    label = ReadLabel(s);
}

void JMP::Execute() const
{
    pc = labels[label];
}

JEQ::JEQ(istream& s)
{
    value1 = ReadValue(s);
    value2 = ReadValue(s);
    label = ReadLabel(s);
}

void JEQ::Execute() const
{
    if (value1.Evaluate() == value2.Evaluate())
        pc = labels[label];
}

JLE::JLE(istream& s)
{
    value1 = ReadValue(s);
    value2 = ReadValue(s);
    label = ReadLabel(s);
}

void JLE::Execute() const
{
    if (value1.Evaluate() <= value2.Evaluate())
        pc = labels[label];
}

JSR::JSR(istream& s)
{
    label = ReadLabel(s);
}

void JSR::Execute() const
{
    callStack.push(pc);
    pc = labels[label];
}

RTS::RTS()
{
}

void RTS::Execute() const
{
    if (callStack.empty())
        done = true;
    else {
        pc = callStack.top();
        callStack.pop();
    }
}

PUSH::PUSH(istream& s)
{
    value = ReadValue(s);
}

void PUSH::Execute() const
{
    valueStack.push(value.Evaluate());
}

POP::POP(istream& s)
{
    reg = ReadRegister(s);
}

void POP::Execute() const
{
    registers[reg] = valueStack.top();
    valueStack.pop();
}

pascal void Interpret( Handle s,  RegisterArray result )
{
    labels.clear();
    program.clear();
    callStack = stack<int>();
    valueStack = stack<int>();
    BlockMove(result, registers, sizeof(registers));

    HLock(s);
    int size = GetHandleSize(s);
    std::string source(*s, size);
    HUnlock(s);
    std::istringstream in(source);

    // read a line
    std::string line;
    char macNL = 13;
    while (getline(in, line, macNL)) {
        std::istringstream l(line);
        std::string opcode;
        l >> opcode;
        if (opcode[opcode.length() - 1] == ':') {
            // label
            opcode.erase(opcode.length() - 1);
            labels[opcode] = program.size();
            l >> opcode;
        }

        if (opcode == "MOVE")
            program.push_back(new MOVE(l));
        else if (opcode == "ADD")
            program.push_back(new ADD(l));
        else if (opcode == "SUB")
            program.push_back(new SUB(l));
        else if (opcode == "JMP")
            program.push_back(new JMP(l));
        else if (opcode == "JEQ")
            program.push_back(new JEQ(l));
        else if (opcode == "JLE")
            program.push_back(new JLE(l));
        else if (opcode == "JSR")
            program.push_back(new JSR(l));
        else if (opcode == "RTS")
            program.push_back(new RTS());
        else if (opcode == "PUSH")
            program.push_back(new PUSH(l));
        else if (opcode == "POP")
            program.push_back(new POP(l));
    }

    pc = 0;
    done = false;

    while (!done)
        program[pc++]->Execute();

    BlockMove(registers, result, sizeof(registers));
}