BrainF**k interpreter by Scala (confirmed by 2.10.2)
import scala.annotation.tailrec | |
object BF { | |
class Parser(val str: String) { | |
val cmap = Map( | |
">" -> 'pinc, | |
"<" -> 'pdec, | |
"+" -> 'inc, | |
"-" -> 'dec, | |
"." -> 'out, | |
"," -> 'inp, | |
"[" -> 'jmp, | |
"]" -> 'ret) | |
val parser = s"""[${cmap.keys.map(s => "\\" + s).mkString("|")}]""".r | |
def parse: List[Symbol] = { | |
parser.findAllIn(str).map(s => cmap.getOrElse(s, 'err)).toList | |
} | |
} | |
class Machine(val coms: List[Symbol]) { | |
val commands = coms.zipWithIndex.map(c => (c._2, c._1)) // e.g. (1, 'inc), (2, 'inc), ... | |
val comMap = commands.toMap // e.g. (1 -> 'inc, 2 -> 'inc, ...) | |
val jumpMap = parseJump(commands) // e.g. (9 -> 41, 41 -> 9) | |
def execute: String = { | |
stepExecute(1, 0, 0, Map(), "") | |
} | |
private def parseJump(coms: List[(Int, Symbol)]): Map[Int, Int] = { | |
val sj = coms.collect { case (c, 'jmp) => c } | |
val ej = coms.collect { case (c, 'ret) => c }.reverse | |
if (sj.length != ej.length) throw new Exception("jump couples invalid") | |
sj.zip(ej).toMap ++ ej.zip(sj).toMap | |
} | |
@tailrec | |
private def stepExecute( | |
step: Int, // step index (for debug) | |
cindex: Int, // command index | |
pindex: Int, // pointer index | |
buf: Map[Int, Int], // value buffer | |
result: String): String = { | |
comMap.getOrElse(cindex, 'fin) match { | |
case 'fin => result | |
case 'pinc => stepExecute(step + 1, cindex + 1, pindex + 1, buf, result) | |
case 'pdec => stepExecute(step + 1, cindex + 1, pindex - 1, buf, result) | |
case 'inc => stepExecute(step + 1, cindex + 1, pindex, increment(pindex, buf), result) | |
case 'dec => stepExecute(step + 1, cindex + 1, pindex, decrement(pindex, buf), result) | |
case 'out => stepExecute(step + 1, cindex + 1, pindex, buf, result + output(pindex, buf)) | |
case 'inp => stepExecute(step + 1, cindex + 1, pindex, buf, result) // skip | |
case 'jmp => stepExecute(step + 1, jumpTo(cindex, pindex, buf), pindex, buf, result) | |
case 'ret => stepExecute(step + 1, returnTo(cindex, pindex, buf), pindex, buf, result) | |
case _ => throw new Exception("execute error") | |
} | |
} | |
private def bufValue(pindex: Int, buf: Map[Int, Int]): Int = { | |
buf.getOrElse(pindex, 0) | |
} | |
private def increment(pindex: Int, buf: Map[Int, Int]): Map[Int, Int] = { | |
buf + (pindex -> (bufValue(pindex, buf) + 1)) | |
} | |
private def decrement(pindex: Int, buf: Map[Int, Int]): Map[Int, Int] = { | |
buf + (pindex -> (bufValue(pindex, buf) - 1)) | |
} | |
private def output(pindex: Int, buf: Map[Int, Int]): String = { | |
bufValue(pindex, buf).toChar.toString | |
} | |
private def jumpTo(cindex: Int, pindex: Int, buf: Map[Int, Int]): Int = { | |
val bv = bufValue(pindex, buf) | |
jumpMap.get(cindex) match { | |
case Some(i) if bv == 0 => i | |
case Some(i) => cindex + 1 | |
case None => throw new Exception("jump index error") | |
} | |
} | |
private def returnTo(cindex: Int, pindex: Int, buf: Map[Int, Int]): Int = { | |
val bv = bufValue(pindex, buf) | |
jumpMap.get(cindex) match { | |
case Some(i) if bv != 0 => i | |
case Some(i) => cindex + 1 | |
case None => throw new Exception("jump index error") | |
} | |
} | |
} | |
def execute(str: String): String = { | |
val coms = new Parser(str).parse | |
val machine = new Machine(coms) | |
machine.execute | |
} | |
def main(args: Array[String]) = { | |
val hello = """+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-. | |
------------.<++++++++.--------.+++.------.--------.>+.""" | |
val source = if (args.isEmpty) hello else args(0) | |
println(execute(source)) // => "Hello, world!" | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment