Brainfuck PHP Interpreter

Brainfuck.php

<?php

require_once 'Memory.php';
require_once 'Stack.php';
require_once 'Expressions.php';

class Brainfuck {

    public function run($code, $input, $eof = 0) {
        $memory = new Memory(array_map('ord', str_split($input)), $eof);
        foreach ($this->parse($code) as $op) {
            $op->evaluate($memory);
        }
        return implode('', array_map('chr', $memory->getOutput()));
    }

    protected function parse($code) {
        $code = str_split($code);
        $stack = new Stack();
        $stack->push(new Stack());
        foreach ($code as $op) {
            $op = Expression::factory($op);
            if ($op) {
                if ($op->isTerminal()) {
                    $stack->poke()->push($op);
                } elseif ($op->isOpen()) {
                    $stack->push(new Stack());
                } elseif ($stack->count() > 1) {
                    $children = $stack->pop();
                    while ($child = $children->shift()) {
                        $op->addChild($child);
                    }
                    $stack->poke()->push($op);
                } else {
                    throw new DomainException('Unmatched Closed Tag');
                }
            }
        }
        if ($stack->count() > 1) {
            throw new DomainException('Unmatched Open Tag');
        }
        $commands = $stack->pop();
        $result = array();
        while ($command = $commands->shift()) {
            $result[] = $command;
        }
        return $result;
    }

}

Expressions.php

<?php

Expression::registerExpressions(array(
    'PointerMove',
    'MemoryChange',
    'Loop',
    'IO',
));

abstract class Expression {

    protected static $expressions = array();

    protected $value = '';

    public function __construct($value) {
        $this->value = $value;
    }

    abstract public function evaluate(Memory $memory);

    abstract public static function getTokens();

    public static function registerExpressions(array $classes) {
        foreach ($classes as $class) {
            static::registerExpression($class);
        }
    }

    public static function registerExpression($class) {
        $r = new ReflectionClass($class);
        if (!$r->isSubclassOf(__CLASS__)) {
            throw new LogicException('Improper Expression Class Registered');
        }
        foreach ($class::getTokens() as $token) {
            static::$expressions[$token] = $class;
        }
    }

    public static function factory($value) {
        if (isset(static::$expressions[$value])) {
            $class = static::$expressions[$value];
            return new $class($value);
        }
        return false;
    }

    public function isTerminal() {
        return true;
    }

    public function isOpen() {
        return false;
    }

}

class PointerMove extends Expression {

    public static function getTokens() {
        return array('<', '>');
    }

    public function evaluate(Memory $memory) {
        $memory->move($this->value == '<' ? -1 : 1);
    }

}

class MemoryChange extends Expression {

    public static function getTokens() {
        return array('-', '+');
    }

    public function evaluate(Memory $memory) {
        $memory->increment($this->value == '+' ? 1 : -1);
    }

}

class IO extends Expression {

    public static function getTokens() {
        return array(',', '.');
    }

    public function evaluate(Memory $memory) {
        if ($this->value == '.') {
            $memory->output();
        } else {
            $memory->input();
        }
    }

}

class Loop extends Expression {

    public static function getTokens() {
        return array('[', ']');
    }

    protected $children = array();

    public function addChild(Expression $child) {
        $this->children[] = $child;
    }

    public function evaluate(Memory $memory) {
        while ($memory->current() != 0) {
            foreach ($this->children as $child) {
                $child->evaluate($memory);
            }
        }
    }

    public function isTerminal() {
        return false;
    }

    public function isOpen() {
        return $this->value == '[';
    }
}

Memory.php

<?php

class Memory {
    protected $data = array();
    protected $pointer = 0;
    protected $input = array();
    protected $output = array();
    protected $eof = 0;

    public function __construct(array $input, $eof = 0) {
        $this->input = $input;
        $this->eof = $eof;
    }

    public function getOutput() {
        return $this->output;
    }

    public function current() {
        return isset($this->data[$this->pointer]) ? $this->data[$this->pointer] : 0;
    }

    public function move($amount) {
        if (isset($this->data[$this->pointer]) && $this->data[$this->pointer] == 0) {
            unset($this->data[$this->pointer]);
        }
        $this->pointer += $amount;
    }

    public function increment($size) {
        if (!isset($this->data[$this->pointer])) {
            $this->data[$this->pointer] = 0;
        }
        $this->data[$this->pointer] += $size;
    }

    public function input() {
        if (!empty($this->input)) {
            $this->data[$this->pointer] = array_shift($this->input);
        } else {
            $this->data[$this->pointer] = $this->eof;
        }
    }

    public function output() {
        $this->output[] = $this->current();
    }
}

Stack.php

<?php

class Stack {

    protected $data = array();

    public function count() {
        return count($this->data);
    }

    public function push($element) {
        $this->data[] = $element;
    }

    public function poke() {
        return end($this->data);
    }

    public function pop() {
        return array_pop($this->data);
    }

    public function shift() {
        return array_shift($this->data);
    }
}

test.php

<?php

require_once 'Brainfuck.php';

$bf = new Brainfuck;

$code = '>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[[>[
->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<
]<]<[[<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>
+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-
[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[
>->>>>>]<<[>,>>>]<<[>+>]<<[+<<]<]';
$input = ',[[>+<-],]>.!'.chr(32) . chr(33);
$eof = 0;

echo ord($bf->run($code, $input, $eof)); 

// 65
// Since 32 + 33 == 65