Processing_BF.phps
<?
/* vim: set expandtab tabstop=4 softtabstop=4 shiftwidth=4: */
/**
*
* Optimizing compilator from Brainf*ck to PHP
*
* PHP versions 4 and 5
*
* LICENSE: This source file is subject to version 3.0 of the PHP license
* that is available through the world-wide-web at the following URI:
* http://www.php.net/license/3_0.txt. If you did not receive a copy of
* the PHP License and are unable to obtain it through the web, please
* send a note to license@php.net so we can mail you a copy immediately.
*
* @category Processing
* @package Processing_BF
* @author Evgeny Stepanischev <imbolk@gmail.com>
* @copyright 2005 Evgeny Stepanischev
* @license http://www.php.net/license/3_0.txt PHP License 3.0
* @version CVS: $Id:$
* @link http://pear.php.net/package/System_SharedMemory
*/
// {{{ class Processing_BF
class Processing_BF
{
// {{{ compile()
/**
* Program compling
* @param string $str BF program code
* @param string $input input data of BF program
*
* @return string PHP code
*
*/
function compile($str, $input = '')
{
return $this->addHeader($this->toPHP($str), $input);
}
// }}}
// {{{ addHeader()
/**
* Add standart header to compiled BF program
* @param string $str compiled BF program
* @param string $input input data of BF program
*
* @return string PHP code
*
*/
function addHeader($str, $input = '')
{
$str = "\$d = array_fill(-65535, 65535, \$di = 0);\n" . $str;
// If input isn't empty we convert it to array of charcodes
$codes = $input == '' ?
array(0) :
array_map('ord', preg_split('//', $input, -1, PREG_SPLIT_NO_EMPTY));
// End of string in BF
$codes[] = '$id = 0';
return '$in=array(' . implode(', ', $codes) . ');' . $str;
}
// }}}
// {{{ toPHP()
/**
* Compile program to PHP
* @param string $str BF program code
*
* @return string PHP code
*
*/
function toPHP($str)
{
return $this->_compile($this->_prepare);
}
// }}}
// {{{ _prepare()
/**
* Preparing to compiling and starting.
* @param string $str program code
*
* @return string prepared program code
*
*/
function _prepare($str)
{
// Remove trash chars
$str = preg_replace('/[^\-\+\[\]><\,\.]/', '', $str);
// Escaping opcodes
$trans = array
(
'[<]' => 'l',
'[>]' => 'r',
'[-]' => 'c',
'[+]' => 'c',
'+' => 'P',
'-' => 'M',
'<' => 'm',
'>' => 'p',
'[' => 'L',
']' => 'R',
);
$str = strtr($str, $trans);
// repeating opcodes
return preg_replace_callback('/([PMpm])(\\1{1,98})/', array(&$this, '_prepare_callback'), $str);
}
// }}}
// {{{ _dir_op
/**
* Complex opcodes transformation
* @param string $dir move direction
* @param int $shift number of movement
* @param int $col number for sub or add
* @param string $op operation - sub (M) or add (P)
*
* @return string prepared program code
*
*/
function _dir_op($dir, $shift, $col, $op)
{
$dir = $dir == 'm' ? '-' : '+';
$shift = $shift ? (int) $shift : 1;
$shift = '$di'.$dir.intval($shift);
if ($op == 'c') {
$op = '=0';
} else {
$op = $op == 'M' ? '-' : '+';
if ($col) {
$op = $op.'='.(int) $col;
} else {
$op = $op.$op;
}
}
return '$d['.$shift.']'.$op.';';
}
// }}}
// {{{ _op()
/**
* Simple opcodes transformation
* @param int $repeat operation repeat factor
* @param int $op opcode
* @param int $idx optional data index string
*
* @return string prepared program code
*
*/
function _op($repeat, $op, $idx = false)
{
$idx = $idx === false ? '$d[$di]' : '$d['.$idx.']';
if ($repeat = (int) $repeat) {
switch ($op) {
case 'M':
return $idx.'-='.$repeat.';';
case 'P':
return $idx.'+='.$repeat.';';
case 'c':
return $idx.'=0;';
case 'm':
return '$di-='.$repeat.';';
case 'p':
return '$di+='.$repeat.';';
}
} else {
switch ($op) {
case 'M':
return $idx.'--;';
case 'P':
return $idx.'++;';
case 'c':
return $idx.'=0;';
case 'm':
return '--$di;';
case 'p':
return '++$di;';
}
}
}
// }}}
// {{{ _cycles_op
/**
* Cycles optimization
* @param string $str string to optimization
*
* @return string prepared program code
*
*/
function _cycles_op($str)
{
// Is loop entry point concur with exit point?
$brack = array('m' => 0, 'p' => 0);
preg_replace('/(\d{2}|)([mp])/e', '$brack[$2] += "$1" ? "$1" : 1', $str);
if ($brack['m'] != $brack['p']) {
return 'L'.$str.'R';
}
// Execution emulation
$out = '';
$pos = 0;
$start = false;
$clear_end = true;
$len = strlen($str);
for ($i = 0; $i<$len; $i++) {
if (is_numeric($str{$i})) {
$num = intval(substr($str, $i++, 2));
$op = $str{++$i};
} else {
$num = 1;
$op = $str{$i};
}
if ($pos > 0) {
$pos = '+' . (int) $pos;
} elseif (!$pos) {
$pos = '';
}
switch ($op) {
case 'm':
$pos -= $num;
break;
case 'p':
$pos += $num;
break;
case 'M':
case 'P':
if ($start || $pos) {
$op = $op == 'M' ? '-' : '+';
$num = $num == 1 ? '' : '*'.$num;
$out .= '$d[$di'.$pos.']'.$op.'=$d[$di]'.$num.';';
} else {
$start = $pos == 0;
}
break;
case 'c':
if ($pos) {
$out .= 'if ($d[$di]) $d[$di'.$pos.']=0;';
} else {
$out .= '$d[$di]=0;';
$start = true;
$clear_end = false;
}
}
}
if ($start) {
if ($clear_end) {
$out .= '$d[$di]=0;';
}
return $out;
}
return 'L'.$str.'R';
}
// }}}
// {{{ _compile()
/**
* Main complile routine
* @param string $str program data
*
* @return string PHP program code
*
*/
function _compile($str)
{
$repl = array
(
// [>>>+<<-<]
'/L([MPmpc\d]+)R/e' => '$this->_cycles_op("$1")',
// <+++>, <[-]>, <--->
'/(\d{2}|(?<!\d))(m)(\d{2}|)([McP])\\1p/e' => '$this->_dir_op("$2", "$1", "$3", "$4")',
// >+++<, >[-]<. >---<
'/(\d{2}|(?<!\d))(p)(\d{2}|)([McP])\\1m/e' => '$this->_dir_op("$2", "$1", "$3", "$4")',
// ++>>, <<<-
'/(\d{2}|(?<!\d))([MP])([mp])/e' => '$this->_op("$1", "$2", "$3" == "m" ? \'$di--\' : \'$di++\')',
// <<+, >>>-, >>>[-]
'/(\d{2}|(?<!\d))([pm])(\d{2}|)([PMc])/e' => '$this->_op("$3", "$4", rtrim($this->_op("$1", "$2"), ";"))',
// ++, ---, [-], [<], [>], <<<, >>>
'/(\d{2}|)([MPmplrc])/e' => '$this->_op("$1", "$2")',
);
$str = preg_replace(array_keys($repl), array_values($repl), $str);
$trans = array(
'.' => 'flush(print chr($d[$di]));',
'l' => 'for (;$d[$di];--$di);',
'r' => 'for (;$d[$di];++$di);',
',' => 'if (isset($in{$id})) $d[$di] = $in{$id++}; else exit;',
'L' => 'while ($d[$di]) {',
'R' => '}',
);
return strtr($str, $trans);
}
// }}}
// {{{ _prepare_callback()
/**
* Callback for repeating opcodes replacement
*
* @param array $m preg_replace match array
*
* @return string special opcode string
*
*/
function _prepare_callback($m)
{
// sq. length
$len = strlen($m[2]) + 1;
if ($len < 10) {
$len = '0' . $len;
}
return $len.$m[1];
}
// }}}
}
// }}}
?>