BFコンパイラー in C++ DouKaku?

BFコンパイラー

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

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

Dan the Brainf.ucker

see: Brainfuck - Wikipedia

以下のように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!

post comment

Posted feedbacks - C++

C++→Cの変化球． Xbyakを使ってオブジェクトコードを出力． ./bf hello.bf なら即実行 ./bf hello.bf 1 > a.c でx86 32bit用Cコードを生成します．これでも32bit x86ならMac/Win/Linuxで動作します． gccの場合は-fno-operator-namesをつけてコンパイルしてください．

see: Xbyak

/*
    出力例
#include <stdio.h>
static int stack[32768];
static const unsigned char code[] = {
0x55,0x56,0x57,0x8b,0x74,0x24,0x10,0x8b,0x7c,0x24,0x14,0x8b,0x6c,0x24,0x18,0x83,
...
};
main()
{
    ((void (*)(void*, void*, int *))code)((void*)putchar, (void*)getchar, stack);
}

*/
#include "xbyak/xbyak.h"
#include <stdio.h>
#include <stack>
#include <fstream>

struct Brainfuck : public Xbyak::CodeGenerator {
    Brainfuck(std::istream& is) : CodeGenerator(10000)
    {
        push(ebp); // stack
        push(esi);
        push(edi);
        const int _P = 4 * 3;
        mov(esi, ptr[esp + _P + 4]);
        mov(edi, ptr[esp + _P + 8]);
        mov(ebp, ptr[esp + _P + 12]);
        int labelNo = 0;
        std::stack<int> keepLabelNo;
        char label[32];
        char c;
        while (is >> c) {
            switch (c) {
            case '+': inc(dword [ebp]); break;
            case '-': dec(dword [ebp]); break;
            case '.': push(dword [ebp]); call(esi); pop(eax); break;
            case ',': call(edi); mov(dword [ebp], eax); break;
            case '>': add(ebp, 4); break;
            case '<': sub(ebp, 4); break;
            case '[':
                sprintf(label, "B%d", labelNo); L(label);
                mov(eax, dword [ebp]);
                test(eax, eax);
                sprintf(label, "F%d", labelNo); jz(label, T_NEAR);
                keepLabelNo.push(labelNo++);
                break;
            case ']':
                {
                    int no = keepLabelNo.top(); keepLabelNo.pop();
                    sprintf(label, "B%d", no); jmp(label);
                    sprintf(label, "F%d", no); L(label);
                }
                break;
            default:
                break;
            }
        }
        pop(edi);
        pop(esi);
        pop(ebp);
        ret();
    }
};

void dump(const Xbyak::uint8 *code, size_t size)
{
    puts("#include <stdio.h>\nstatic int stack[32768];\nstatic const unsigned char code[] = {");
    for (size_t i = 0; i < size; i++) {
        printf("0x%02x,", code[i]); if ((i % 16) == 15) putchar('\n');
    }
    puts("\n};");
#ifdef __linux__
    puts("#include <unistd.h>");
    puts("#include <sys/mman.h>");
#endif
    puts("main()\n{");
#ifdef __linux__
    puts("\tlong pageSize = sysconf(_SC_PAGESIZE) - 1;");
    puts("\tmprotect((void*)code, (sizeof(code) + pageSize) & ~pageSize, PROT_READ | PROT_EXEC);");
#endif
    puts(
        "\t((void (*)(void*, void*, int *))code)((void*)putchar, (void*)getchar, stack);\n"
        "}"
    );
}

int main(int argc, char *argv[])
{
    if (argc == 1) {
        fprintf(stderr, "bf filename.bf [0|1]\n");
        return 1;
    }
    std::ifstream ifs(argv[1]);
    int mode = argc == 3 ? atoi(argv[2]) : 0; 
    Brainfuck bf(ifs);
    if (mode == 0) {
        static int stack[32768];
        ((void (*)(void*, void*, int *))bf.getCode())((void*)putchar, (void*)getchar, stack);
    } else {
        dump(bf.getCode(), bf.getSize());
    }
    return 0;
}

にしおさんに倣って，若干最適化コードを生成するようにしました．素数計算のだと3割ぐらい出力コード長が短くなるようです．

+       int getContinuousChar(std::istream& is, char c)
+       {
+               int count = 1;
+               char p;
+               while (is >> p) {
+                       if (p != c) break;
+                       count++;
+               }
+               is.unget();
+               return count;
+       }

+#if 0
        case '+': inc(dword [ebp]); break;
        case '-': dec(dword [ebp]); break;
        case '>': add(ebp, 4); break;
        case '<': sub(ebp, 4); break;
#else
       case '+':
       case '-':
               {
                       int count = getContinuousChar(is, c);
                       if (count == 1) {
                               c == '+' ? inc(dword [ebp]) : dec(dword [ebp]);
                       } else {
                               add(dword [ebp], (c == '+' ? count : -count));
                       }
               }
               break;
       case '>':
       case '<':
               {
                       int count = getContinuousChar(is, c);
                       add(ebp, 4 * (c == '>' ? count : -count));
               }
               break;
#endif

#include <iostream>
#include <fstream>
#include <cctype>
using namespace std;

#define REP(n) for (size_t i = 0; i < n; ++i)

void compile(istream& in, ostream& out)
{
    size_t indent = 0;

#define OUTPUT(s) REP(indent) out << "\t"; out << s << endl;

    OUTPUT("#include <stdio.h>");
    OUTPUT("#include <mem.h>");
    OUTPUT("");
    OUTPUT("int main()");
    OUTPUT("{");
    ++indent;
    OUTPUT("unsigned char buf[33000], *p = buf;");
    OUTPUT("memset(buf, 0, sizeof(buf));");
    OUTPUT("");

    char c;

    while (in.get(c))
    {
        if (isspace(c))
        {
            // pass
        }
        else if (c == '<')
        {
            OUTPUT("--p;");
        }
        else if (c == '>')
        {
            OUTPUT("++p;");
        }
        else if (c == '+')
        {
            OUTPUT("++*p;");
        }
        else if (c == '-')
        {
            OUTPUT("--*p;");
        }
        else if (c == '.')
        {
            OUTPUT("putchar(*p);");
        }
        else if (c == ',')
        {
            OUTPUT("*p = getchar();");
        }
        else if (c == '[')
        {
            OUTPUT("while (*p)");
            OUTPUT("{");
            ++indent;
        }
        else if (c == ']')
        {
            --indent;
            OUTPUT("}");
        }
    }

    --indent;
    OUTPUT("}");

#undef OUTPUT
}

int main(int argc, char* argv[])
{
    if (argc != 2)
    {
        cerr << "usage: name" << endl;

        return -1;
    }

    compile(ifstream(argv[1]), cout);
}

DouKaku?

BFコンパイラー

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq