BFコンパイラー DouKaku?

「どう書く?」でまだ出ていないのが不思議なお題。それがBF処理系。ここでは、BFで書かれたソースを、同じ言語に変換するコンパイラーを募集します。

私自身、すでにPerlとJavaScriptに関しては http://blog.livedoor.jp/dankogai/archives/50545151.html でやっているのですが、他の言語バージョンも是非見たいので。

Dan the Brainf.ucker

ひさびさの一番かな？

入力を文字列にしたい場合なんかは
Console.withInを使うとできます。

import scala.io.Source.fromFile

object BF{
  def main(args:Array[String]) = {
    if(args.size == 0) print("scala BF [sourcecode filename]")
    else
    args.foreach{f=> (new Machine).interpret(fromFile(f).mkString("")) }
  }
}

object Machine {
  final val MEM = 0xffffff
  final val VAL = 0xff
}

class Machine{
  var _p = 0
  val _mem = new Array[int](Machine.MEM)
  def p_=(v:int) = _p = v&Machine.MEM
  def p = _p
  def mem_=(v:int) = _mem(p)=v&Machine.VAL
  def mem = _mem(p)

  def abort = error("Missing corresponding parenthesis.")

  def interpret(code:String):unit = interpret(code.toArray)
  def interpret(code:Array[char]):unit = {
    val (s,m) = ((List[int](), List[(int,int)]()) /: code.zipWithIndex){
      (r,c) => c._1 match {
        case '[' => (c._2::r._1, r._2)
        case ']' => r._1 match {
          case x::xs => (xs, (x,c._2)::(c._2,x)::r._2)
          case _ => abort
        }
        case _   => r
    }}
    if(s.size > 0) abort
    val parenMap = Map(m:_*)

    var i = -1;while({i=i+1;i<code.size}) code(i) match {
      case '>' => p = p+1
      case '<' => p = p-1
      case '+' => mem = mem+1
      case '-' => mem = mem-1
      case '.' => print(mem.asInstanceOf[char])
      case ',' => mem = readChar.asInstanceOf[int]
      case '[' if mem == 0 => i = parenMap(i)
      case ']' if mem != 0 => i = parenMap(i)
      case _   => ()
    }
  }
}

お題を見て「BF→言語Ａへのトランスレータを言語Ａで製作する」のだと思ったんですけど、お手本見るとなんかちょっと違う感じがしたので全部やってみました (^-^;; BF ソースファイルから C# ソースと実行ファイルを生成してそれを実行します。

using System;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.IO;
using System.Reflection;
using Microsoft.CSharp;
static class BFCompiler {
    public static void Main(String[] args) {
        if (0 < args.Length && File.Exists(args[0])) {
            using(StringWriter sw = new StringWriter())
            using(StreamReader sr = new StreamReader(args[0])) {
                Stack<string> labels = new Stack<string>();
                int label_num = 0;
                sw.WriteLine("using System; static class BF {");
                sw.WriteLine("public static void Main() {");
                sw.WriteLine("byte[] m = new byte[256]; int p = 0;");
                foreach(char c in sr.ReadToEnd()) {
                    switch(c) {
                        case '+': sw.WriteLine("m[p]++;"); break;
                        case '-': sw.WriteLine("m[p]--;"); break;
                        case '>': sw.WriteLine("p++;"); break;
                        case '<': sw.WriteLine("p--;"); break;
                        case '.': sw.WriteLine("Console.Write((char)m[p]);"); break;
                        case ',': sw.WriteLine("m[p] = (byte)Console.Read();"); break;
                        case '[': {
                            string ll = "L" + (label_num++);
                            labels.Push(ll);
                            sw.WriteLine("if (m[p] == 0) goto {0}_END;", ll);
                            sw.WriteLine("{0}_START:;", ll);
                            break;
                        }
                        case ']': {
                            string ll = labels.Pop();
                            sw.WriteLine("if (m[p] != 0) goto {0}_START;", ll);
                            sw.WriteLine("{0}_END:;", ll);
                            break;
                        }
                    }
                }
                sw.WriteLine("}}");
                Generate(Path.GetFileNameWithoutExtension(args[0]), sw.ToString());
            }
        }
        else {
            Console.WriteLine("usage: bfc [sourcefile]");
        }
    }
    private static void Generate(string filename, string cs_code) {
        // ソースファイル生成
        using (StreamWriter sw = new StreamWriter(filename + ".cs")) {
            sw.Write(cs_code);
        }
        // 実行ファイル生成
        CompilerParameters param = new CompilerParameters();
        param.OutputAssembly = filename + ".exe";
        param.GenerateExecutable = true;
        CompilerResults rs = new CSharpCodeProvider().CompileAssemblyFromSource(param, cs_code);
        // 実行
        rs.CompiledAssembly.GetType("BF").GetMethod("Main").Invoke(null, null);
    }
}

以下のようにonelinerで可能です。ただしLanguage::BF 0.03が必要です。 CodeRepos経由で、

svn co svn.coderepos.org/share/lang/perl/Language-BF
cd Language-BF/trunk
perl Makefile.PL
make install

するか、CPANにVersion 0.03が現れるのをお待ち下さい。

Dan the Brainf.cker

perl -MLanguage::BF \
  -e 'print Language::BF->new_from_file(shift)->as_perl' t/hello.bf \
  | perl
Hello World!

>お題を見て「BF→言語Ａへのトランスレータを言語Ａで製作する」のだと思ったんですけど

それであっていると思いますよ。お手本は「Language::BF->new_from_file(shift)->as_perl」というコードで「t/hello.bf」というBrainf*ckで書かれたコードを読んでPerlに変換し、その出力をさいごの「| perl」でもう一度Perlに食わせて実行させているわけです。

perl -MLanguage::BF \
-e 'print Language::BF->new_from_file(shift)->as_perl' t/hello.bf \
| perl
Hello World!

SiroKuroさんがおっしゃっているお手本は
http://blog.livedoor.jp/dankogai/archives/50545151.html  

のほうだと思います。投稿時間を見てみるとわかります。

僕もURLの方だけみて勘違いしてました･･･
今から書き直します(^^;

ひねり無し。
python bf.py -o hello.py hello.bf  みたいな感じで使います。

import sys
from getopt import getopt

def encode(bfcode):
    depth = code = 0
    pycode = []
    stack = []
    
    f = file(default['-o'], 'w')
    
    pycode.append('import sys')
    pycode.append('tape, ptr, code = {}, 0, 0')
    
    while code != len(bfcode):
        c = bfcode[code]
        
        if c == '>':
            pycode.append('\t' * depth + 'ptr += 1')
        elif c == '<':
            pycode.append('\t' * depth + 'ptr -= 1')
        elif c == '+':
            pycode.append('\t' * depth + 'tape[ptr] = tape.get(ptr, 0) + 1')
        elif c == '-':
            pycode.append('\t' * depth + 'tape[ptr] = tape.get(ptr, 0) - 1')
        elif c == ',':
            pycode.append('\t' * depth + 'tape[ptr] = sys.stdin.read(1)')
        elif c == '.':
            pycode.append('\t' * depth + 'sys.stdout.write(chr(tape.get(ptr, 0)))')
        elif c == '[':
            pycode.append('\t' * depth + 'while tape.get(ptr, 0):')
            stack.append(depth)
            depth += 1
        elif c == ']':
            depth = stack.pop()
        
        code += 1
    
    file(default['-o'], 'w').write('\n'.join(pycode))


if __name__ == '__main__':
    default = {'-o': 'a.py'}
    optlist, args = getopt(sys.argv[1:], 'o:', [])
    if args:
        default.update(optlist)
        encode(''.join(file(args[0]).readlines()))

簡単の為、標準出力を使用。

#include <stdio.h>
#include <stdlib.h>

int main(int arg_c, char **arg_v) {
    FILE *fp;
    int c;

    if (*++arg_v == NULL) {
        fprintf(stderr, "usage: bfc [source file]\n");
        exit(EXIT_FAILURE);
    }
    if ((fp = fopen(*arg_v, "r")) == NULL) {
        fprintf(stderr, "file open error.\n");
        exit(EXIT_FAILURE);
    }
    
    puts("#include <stdio.h>");
    puts("#include <stdlib.h>");
    puts("int main(void) {");
    puts(" char *s, *p;");
    puts(" p = s = (char *)calloc(1024, 1);");
    
    while ((c = getc(fp)) != EOF) {
        switch (c) {
            case '>': puts(" ++p;"); break;
            case '<': puts(" --p;"); break;
            case '+': puts(" ++*p;"); break;
            case '-': puts(" --*p;"); break;
            case '.': puts(" putchar(*p);"); break;
            case ',': puts(" *p = getchar();"); break;
            case '[': puts(" while (*p) {"); break;
            case ']': puts(" }"); break;
            default: break;
        }
    }
    
    puts(" free(s);");
    puts("}");
    
    fclose(fp);
}

あ、ごめんなさい。yuin さんの仰るとおり、弾さんのブログを見ての疑問でした。弾さんのブログだと普通に実行してるみたいでしたので……。んで、トランスレートかな？コンパイルかな？実行かな？と迷ったので全部やってみた感じです。どれか１つはあってると思いたい (^-^;;

出力のインデント処理と配列の長さを引数で調整できるようにしてみました。
./bf2c hello.bf > hello.c
または
./bf2c hello.bf 128 > hello.c
のように使います。

#include <stdio.h>
#include <stdlib.h>

char *code[] = { "sp++;", "sp--;", "(*sp)++;", "(*sp)--;", "putchar(*sp);",
                 "*sp = getchar();", "while(*sp){", "}" };

int main( int argc, char *argv[] ){
   int c,i,j,n=0;
   int indent = 1;
   int length;
   FILE *fp;

   if( argc < 2 ){
      fprintf(stderr,"Usage: %s sourcefile\n", argv[0] );
      return EXIT_FAILURE;
   }
   if( (fp = fopen( argv[1], "r" )) == NULL ){
      fprintf(stderr,"Error: %s cannot opened\n", argv[1] );
      return EXIT_FAILURE;
   }
   if( !argv[2] || (length = atoi( argv[2] )) <= 0 ){
      length = 256;
   }

   puts("#include <stdio.h>");
   puts("#include <stdlib.h>");
   printf("#define DATA_LEN %d\n", length);
   puts("char code[DATA_LEN];");
   puts("int main (void){");
   puts("   char *sp = code;");
   while( (c=fgetc( fp )) != EOF ){
      switch(c){
      case '>': i = 0; break;
      case '<': i = 1; break;
      case '+': i = 2; break;
      case '-': i = 3; break;
      case '.': i = 4; break;
      case ',': i = 5; break;
      case '[': i = 6; indent++; break;
      case ']': i = 7; indent--; break;
      default:
         /* skip other characters */
         continue;
      }
      for( j = 0; j < (indent+(i==6?-1:0)); j++ ){
         printf("   ");
      }
      printf("%s\n", code[i] );
   }
   puts("   return EXIT_SUCCESS;");
   puts("}");
   fclose(fp);
   return EXIT_SUCCESS;
}

コードをラベルと命令の列みたいなのにして、
prog の中へ放り込みます。

(defun compile-bf (str &optional (size 30000) (offset 0))
  (let ((tags ()))
    (flet ((translate (c)
             (case c
               (#\> '((incf ptr)))
               (#\< '((decf ptr)))
               (#\+ '((setf *ptr (logand (1+ *ptr) #xff))))
               (#\- '((setf *ptr (logand (1- *ptr) #xff))))
               (#\. '((write-char (code-char *ptr))))
               (#\, '((setf *ptr (char-code (read-char)))))
               (#\[ (let ((t1 (gensym)) (t2 (gensym)))
                      (setf tags (list* t1 t2 tags))
                      `(,t1 (if (= *ptr 0) (go ,t2)))))
               (#\] (let ((t1 (pop tags)) (t2 (pop tags)))
                      `((if (/= *ptr 0) (go ,t1)) ,t2))))))
      `(symbol-macrolet ((*ptr (aref array ptr)))
         (prog ((array ,(make-array size :initial-element 0))
                (ptr ,offset))
           ,@(loop for c across str append (translate c)))))))

;;; test
(eval (compile-bf "+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.
+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+."))

はっきりしなくてごめんなさい。にしおさんが言う通り。

コンパイラー(トランスレーター)
  BF ====> 言語A
      言語A

というのが本来の趣旨で、そしてBFの場合こちらの方が

インタープリター(ランタイム)
  BF => 言語Aで書かれた実行環境

よりもずっと実装が簡単なので。
ちなみにLanguage::BFはどちらの機能も持っています。

Dan the Brainf.cker

題意を読み間違えてたので。

こっちのほうがかなり楽です。

import scala.io.Source.fromFile

object BFC{
  def main(args:Array[String]) = {
    if(args.size == 0){
      println("Usage:scala BFC [sourcecode filename]")
    }else{
      println("""
        object Machine {
          final val MEM = 0xffffff
          final val VAL = 0xff
        }

        class Machine{
          var _p = 0
          val _mem = new Array[int](Machine.MEM)
          def p_=(v:int) = _p = v&Machine.MEM
          def p = _p
          def mem_=(v:int) = _mem(p)=v&Machine.VAL
          def mem = _mem(p)

          def eval = {
      """)
      val code = fromFile(args(0)).mkString("").toList
      if(code.count('['==_) != code.count(']'==_)) {
        error("Missing corresponding parenthesis.")
      }
      code.foreach(c=>println(c match {
        case '>' => "p = p+1"
        case '<' => "p = p-1"
        case '+' => "mem = mem+1"
        case '-' => "mem = mem-1"
        case '.' => "print(mem.asInstanceOf[char])"
        case ',' => "mem = readChar.asInstanceOf[int]"
        case '[' => "while(mem != 0){"
        case ']' => "}"
        case _   => ""
      }))
      println("}};(new Machine).eval;")
    }
  }
}

ケースが嫌いな私は、以下のように書き換えてしまいました。機能的には#3955と互換ですが、出力されたCコードのコンパイルには差し支えないのでインデントは省略しました。

Dan the Brainf.cker

#include <stdio.h>
#include <stdlib.h>

int main( int argc, char *argv[] ){
    int c;
    char *code[256];
    int length;
    FILE *fp;

    if( argc < 2 ){
        fprintf(stderr,"Usage: %s sourcefile\n", argv[0] );
        return EXIT_FAILURE;
    }
    if( (fp = fopen( argv[1], "r" )) == NULL ){
        fprintf(stderr,"Error: %s cannot opened\n", argv[1] );
        return EXIT_FAILURE;
    }
    if( !argv[2] || (length = atoi( argv[2] )) <= 0 ){
        length = 256;
    }

    for (c = 0; c < 256; c++) code[c] = NULL;
    code['>'] = "sp++;";
    code['<'] = "sp--;";
    code['+'] = "(*sp)++;";
    code['-'] = "(*sp)--;";
    code['.'] = "putchar(*sp);";
    code[','] = "*sp = getchar();";
    code['['] = "while(*sp){";
    code[']'] = "}";

    puts("#include <stdio.h>");
    puts("#include <stdlib.h>");
    printf("#define DATA_LEN %d\n", length);
    puts("char code[DATA_LEN];");
    puts("int main (void){");
    puts("   char *sp = code;");
    while( (c=fgetc( fp )) != EOF ) if (code[c]) printf("%s\n", code[c]); 
    puts("   return EXIT_SUCCESS;");
    puts("}");
    fclose(fp);
    return EXIT_SUCCESS;
}

ひねりなし。
配列の値がbyte型を越える場合についてはとりあえず考慮しない方向で…

class BF
  def compile(str)
    depth = 0
    code = []
    code << "mem = [0]"
    code << "ptr = 0"
    str.each_byte do |ch|   
      if ch == ?>
        code << "\t" * depth + "ptr += 1; mem[ptr] = 0 if ptr >= mem.size"
      elsif ch == ?<
        code << "\t" * depth + "(ptr == 0)? mem.unshift(0) : ptr -= 1"
      elsif ch == ?+
        code << "\t" * depth + "mem[ptr] += 1"
      elsif ch == ?-
        code << "\t" * depth + "mem[ptr] -= 1"
      elsif ch == ?.
        code << "\t" * depth + "putc(mem[ptr])"
      elsif ch == ?,
        code << "\t" * depth + "mem[ptr] = STDIN.getc"
      elsif ch == ?[
        code << "\t" * depth + "while(mem[ptr] != 0) do"
        depth += 1
      elsif ch == ?]
        depth -= 1
        code << "\t" * depth + "end"
      end
    end
   code.join "\n"
  end
end

eval BF.new.compile("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.") # => Hello World!

自己ツッコミ。
このままだと"～[]～" のようなBFコードがあった際にwhile文のところで文法エラーを起こすので、
']'が出た時にはpassをダミーで放り込んだ方がよさそうです。


あと、最初間違えてインタプリタを書いてしまった名残で変なやり方になっていました。

def encode(bfcode):
-   depth = code = 0 
+   depth = 0
    pycode = []
    stack = []
    
    f = file(default['-o'], 'w')
    
    pycode.append('import sys')
-   pycode.append('tape, ptr, code = {}, 0, 0')
+   pycode.append('tape, ptr = {}, 0')
    

-     while code != len(bfcode):
-        c = bfcode[code]
+     for c in bfcode:
        if c == '>':
            pycode.append('\t' * depth + 'ptr += 1')
        elif c == '<':
            pycode.append('\t' * depth + 'ptr -= 1')
        elif c == '+':
            pycode.append('\t' * depth + 'tape[ptr] = tape.get(ptr, 0) + 1')
        elif c == '-':
            pycode.append('\t' * depth + 'tape[ptr] = tape.get(ptr, 0) - 1')
        elif c == ',':
            pycode.append('\t' * depth + 'tape[ptr] = sys.stdin.read(1)')
        elif c == '.':
            pycode.append('\t' * depth + 'sys.stdout.write(chr(tape.get(ptr, 0)))')
        elif c == '[':
            pycode.append('\t' * depth + 'while tape.get(ptr, 0):')
            stack.append(depth)
            depth += 1
        elif c == ']':
+           pycode.append('\t' * depth + 'pass')
            depth = stack.pop()

-    code += 1

久しぶりに投稿します。
-v optimize=1 とするとオプティマイズされます（笑

helloworld.bf:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

% awk -f bf2awk.awk helloworld.bf > helloworld.awk
% awk -f helloworld.awk 
Hello World!

helloworld.awk:
BEGIN {
  ix = 0
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  while (st[ix]) {
    ix++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    ix++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    st[ix]++
    ix++
    st[ix]++
    st[ix]++
    st[ix]++
    ix++
    st[ix]++
    ix--
    ix--
    ix--
    ix--
    st[ix]--
  }
  ix++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  ix++
  st[ix]++
  printf("%c", st[ix])
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  printf("%c", st[ix])
  st[ix]++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  ix++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  ix--
  ix--
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  ix++
  printf("%c", st[ix])
  st[ix]++
  st[ix]++
  st[ix]++
  printf("%c", st[ix])
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  printf("%c", st[ix])
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  st[ix]--
  printf("%c", st[ix])
  ix++
  st[ix]++
  printf("%c", st[ix])
  ix++
  printf("%c", st[ix])
}

% awk -v optimize=1 -f bf2awk.awk helloworld.bf > helloworld-optimized.awk
% awk -f helloworld-optimized.awk 
Hello World!

helloworld-optimized.awk:
BEGIN {
  ix = 0
  st[ix] += 10
  while (st[ix]) {
    st[++ix]++
    st[ix] += 6
    st[++ix]++
    st[ix] += 9
    st[++ix]++
    st[ix] += 2
    st[++ix]++
    ix -= 4
    st[ix]--
  }
  st[++ix]++
  st[ix]++
  printf("%c", st[ix])
  st[++ix]++
  printf("%c", st[ix])
  st[ix] += 7
  printf("%c", st[ix])
  printf("%c", st[ix])
  st[ix] += 3
  printf("%c", st[ix])
  st[++ix]++
  st[ix]++
  printf("%c", st[ix])
  ix -= 2
  st[ix] += 15
  printf("%c", st[ix])
  printf("%c", st[++ix])
  st[ix] += 3
  printf("%c", st[ix])
  st[ix] -= 6
  printf("%c", st[ix])
  st[ix] -= 8
  printf("%c", st[ix])
  st[++ix]++
  printf("%c", st[ix])
  printf("%c", st[++ix])
}

BEGIN {
    read_buf = ""
    if (optimize) reset_last()

    indent = ""
    indent_print("BEGIN {")

    indent_incr()
    indent_print("ix = 0")
}
{
    gsub(/#.*$/,""); # comment
    gsub(/[^\[\]<>+\-.,]/,""); if (/^$/) next

    N = split($0, op, "")
    for (i=1; i<=N; i++) {
        if (op[i] == ">") {
            if (optimize) {
                if (last_inst == "ix") {
                    last_arg++
                } else {
                    out_last()
                    set_last("ix", 1)
                }
            } else {
                indent_print("ix++")
            }
        } else if (op[i] == "<") {
            if (optimize) {
                if (last_inst == "ix") {
                    last_arg--
                } else {
                    out_last()
                    set_last("ix", -1)
                }
            } else {
                indent_print("ix--")
            }
        } else if (op[i] == "+") {
            if (optimize) {
                if (last_inst == "st[ix]") {
                    last_arg++
                } else {
                    s = set_incr_decr("st[ix]")
                    if (last_inst) out_last()
                    set_last(s, 1)
                }
            } else {
                indent_print("st[ix]++")
            }
        } else if (op[i] == "-") {
            if (optimize) {
                if (last_inst == "st[ix]") {
                    last_arg--
                } else {
                    s = set_incr_decr("st[ix]")
                    if (last_inst) out_last()
                    set_last(s, -1)
                }
            } else {
                indent_print("st[ix]--")
            }
        } else if (op[i] == ".") {
            if (optimize) {
                s = set_incr_decr("printf(\"%c\", st[ix])")
                if (last_inst) out_last()
                indent_print(s)
            } else {
                indent_print("printf(\"%c\", st[ix])")
            }
        } else if (op[i] == ",") {
            if (optimize) {
                s = set_incr_decr("st[ix] = getchar()")
                if (last_inst) out_last()
                indent_print(s)
            } else {
                indent_print("st[ix] = getchar()")
            }
        } else if (op[i] == "[") {
            if (optimize) {
                s = set_incr_decr("while (st[ix]) {")
                if (last_inst) out_last()
                indent_print(s)
                indent_incr()
            } else {
                indent_print("while (st[ix]) {")
                indent_incr()
            }
        } else if (op[i] == "]") {
            if (optimize) out_last()
            indent_decr()
            indent_print("}")
        } else {
            ;
        }
    }
}
END {
    if (optimize) out_last()
    indent_decr()
    indent_print("}")
}

function getchar(  ch)
{
    if (read_buf ~ /^$/) getline read_buf
    ch = substr(read_buf,1,1)
    read_buf = substr(read_buf,2)
    return ch
}
function indent_incr()
{
    indent = "  " indent
}
function indent_decr()
{
    indent = substr(indent, 3)
}
function indent_print(line)
{
    print indent line
}
function set_last(inst,arg)
{
    last_inst = inst
    last_arg = arg
}
function reset_last()
{
    last_inst = ""
    last_arg = 0
}
function out_last(  diff)
{
    if (last_inst ~ /ix/) {
        if (last_arg > 1)
            diff = " += " last_arg
        else if (last_arg == 1)
            diff = "++"
        else if (last_arg == 0)
            diff = ""
        else if (last_arg == -1)
            diff = "--"
        else if (last_arg < -1)
            diff = " -= " (0 - last_arg)

        if (diff) indent_print(last_inst diff)
    }
    last_inst = ""
}
function set_incr_decr(s)
{
    if (last_inst == "ix") {
        if (last_arg == 1) { gsub(/ix/, "++ix", s); last_inst = "" }
        else if (last_arg == -1) { gsub(/ix/, "--ix", s); last_inst = "" }
    }
    return s
}

これまたif文の羅列を置き換える方向で書き換えてみました。
Cと違ってHashが気軽に使えるのがうれしい。
next unless が使えるのもPerl Mongerとしてはうれしい。
    str.unpack("C*").map{|c| c.chr}.each do |ch|
は、単に{}とdo endを両方使ってみたかったから。
Dan the Occasional Rubyist

class BF
  @@opcode = {
    '>' => "ptr += 1; mem[ptr] = 0 if ptr >= mem.size",
    '<' => "(ptr == 0)? mem.unshift(0) : ptr -= 1",
    '+' => "mem[ptr] += 1",
    '-' => "mem[ptr] -= 1",
    '.' => "putc(mem[ptr])",
    ',' => "mem[ptr] = STDIN.getc",
    '[' => "while(mem[ptr] != 0) do",
    ']' => "end"
  }
  def compile(str)
    code = ["mem = [0]", "ptr = 0"]
    str.unpack("C*").map{|c| c.chr}.each do |ch|
      next unless @@opcode[ch]
      code << @@opcode[ch]
    end
   code.join "\n"
  end
end

Squeak Smalltalk で。

| bf st op in |
bf := FileStream fileNamed: 'hello.bf'.
in := FileStream fileNamed: 'in.txt'.
in binary.
st := WriteStream with: '| ss | ss := ReadWriteStream with: #(0). ss reset'.
[(op := bf next) notNil] whileTrue: [
    st nextPutAll: (op caseOf: {
        [$>] -> ['. ss next. ss atEnd ifTrue: [ss nextPut: 0; back]'].
        [$<] -> ['. ss back'].
        [$+] -> ['. ss nextPut: ss peek + 1; back'].
        [$-] -> ['. ss nextPut: ss peek - 1; back'].
        [$.] -> ['. Transcript show: (ss peek asCharacter)'].
        [$,] -> ['. ss nextPut: ', in next printString,' value; back'].
        [$[] -> ['. [ss peek isZero] whileFalse: ['].
        [$]] -> [']']} otherwise: [''])].
bf close.  in close.
World findATranscript: nil.
Compiler evaluate: st contents

おぉ、なるほど。勉強になります。

a2p的にもきれいなawkコードを吐きますねwww

Dan the Cyberpolyglot

1 2	% awk -f bfcc.awk helloworld.bf \| a2p \| perl Hello, World!

optimize=1 の時に while(st[ix]) の直前に ix++ や ix-- が来ると while(st[++ix]) のように誤ったオプティマイズが行われるバグを修正

--- bf2awk.awk.orig    2007-11-14 00:43:07.000000000 +0900
+++ bf2awk.awk    2007-11-14 01:46:46.000000000 +0900
@@ -77,15 +77,9 @@
                 indent_print("st[ix] = getchar()")
             }
         } else if (op[i] == "[") {
-            if (optimize) {
-                s = set_incr_decr("while (st[ix]) {")
-                if (last_inst) out_last()
-                indent_print(s)
-                indent_incr()
-            } else {
-                indent_print("while (st[ix]) {")
-                indent_incr()
-            }
+            if (optimize) out_last()
+            indent_print("while (st[ix]) {")
+            indent_incr()
         } else if (op[i] == "]") {
             if (optimize) out_last()
             indent_decr()

オプティマイズ時に
++ix
st[ix]++
st[ix]++
st[ix]++
が
st[++ix]++
st[ix] += 2
となっていたのを
st[++ix] += 3
のようにちゃんとまとめるように修正するパッチ

--- bf2awk.awk.orig    2007-11-14 00:43:07.000000000 +0900
+++ bf2awk.awk    2007-11-14 01:55:50.000000000 +0900
@@ -38,7 +38,7 @@
             }
         } else if (op[i] == "+") {
             if (optimize) {
-                if (last_inst == "st[ix]") {
+                if (last_inst ~ /^st\[/) {
                     last_arg++
                 } else {
                     s = set_incr_decr("st[ix]")
@@ -50,7 +50,7 @@
             }
         } else if (op[i] == "-") {
             if (optimize) {
-                if (last_inst == "st[ix]") {
+                if (last_inst ~ /^st\[/) {
                     last_arg--
                 } else {
                     s = set_incr_decr("st[ix]")

BFによるBFコンパイラーは、これほど簡単です:-)

種明かしは、こちら。

本来であれば、,[.,]でもOKなのですが、これだとEOFが処理できません。

Dan the Brainf.cker

,+[-.,+]

これまたifの羅列をHashに置き換え。ただし、pythonの場合、[]は少し特別扱いが必要。こちらはindent不要とは行かないので。あと、関数名やインターフェースも好みにあわせて変えました。

Dan the Novice Snake Tamer

#!/usr/bin/env python
import sys
from getopt import getopt

def bf2py(bfcode):
    depth = 0
    opcode = {
        '>':'ptr += 1',
        '<':'ptr -= 1',
        '+':'tape[ptr] = tape.get(ptr, 0) + 1',
        '-':'tape[ptr] = tape.get(ptr, 0) - 1',
        ',':'tape[ptr] = sys.stdin.read(1)',
        '.':'sys.stdout.write(chr(tape.get(ptr, 0)))',
        '[':'while tape.get(ptr, 0):',
        ']':'pass'
    }
    pycode = []
    stack = []
    
    pycode.append('import sys')
    pycode.append('tape, ptr = {}, 0')
    
    for c in bfcode:
        if opcode.has_key(c):
            pycode.append( '\t' * depth + opcode[c])
            if c == '[':
                stack.append(depth)
                depth += 1
            elif c == ']':
                depth = stack.pop()
     
    return '\n'.join(pycode)

if __name__ == '__main__':
    defout = 'a.py'
    optlist, args = getopt(sys.argv[1:], 'o:', [])
    if args:
        pysrc = bf2py(''.join(file(args[0]).readlines()));
        file(defout or ops

DouKaku?

BFコンパイラー

Posted feedbacks - Flatten