Brainfuckコンパイラ自作シリーズ 第5回

Brainfuckコンパイラ自作シリーズ 第5回：最適化とエラー処理

はじめに

前回までに Brainfuck のコードを C 言語に変換し、コンパイルして実行する仕組み を実装しました。
しかし、現時点の実装では 非効率なコードが生成される ことや エラー処理が不十分 であるため、実用的なコンパイラとは言えません。

今回は、Brainfuck コードの 最適化 と エラー処理 を追加し、より実用的なコンパイラを構築します。

---

1. 最適化の種類

Brainfuck コードをより効率的に変換するために、以下の最適化を実装します。

1. 連続する加算・減算 (++++++ → +=6)
2. 連続するポインタ移動 (>>>> → +=4)
3. 無駄な操作 (+- や >< のような相殺可能な操作) の削除
4. クリアループ ([-] または [+] → *ptr = 0;)

これらの最適化を適用することで、生成される C コードのサイズが小さくなり、実行速度も向上します。

---

2. 最適化の実装

2.1 optimizer.h の作成

最適化を行うためのヘッダーファイルを作成します。

#ifndef OPTIMIZER_H
#define OPTIMIZER_H

#include <string>

// Brainfuck コードを最適化する関数
std::string optimizeBrainfuck(const std::string& bfCode);

#endif // OPTIMIZER_H

2.2 optimizer.cpp の実装

Brainfuck コードを解析し、最適化するロジックを実装します。

#include "optimizer.h"
#include <iostream>

std::string optimizeBrainfuck(const std::string& bfCode) {
    std::string optimized;
    int count = 0;
    char lastChar = '\0';

    for (char c : bfCode) {
        if (c == lastChar) {
            count++;
        } else {
            if (count > 0) {
                if (lastChar == '+' || lastChar == '-') {
                    optimized += lastChar + std::to_string(count) + ";";
                } else if (lastChar == '>' || lastChar == '<') {
                    optimized += lastChar + std::to_string(count) + ";";
                } else {
                    optimized += std::string(count, lastChar);
                }
            }
            count = 1;
            lastChar = c;
        }
    }

    if (count > 0) {
        if (lastChar == '+' || lastChar == '-') {
            optimized += lastChar + std::to_string(count) + ";";
        } else if (lastChar == '>' || lastChar == '<') {
            optimized += lastChar + std::to_string(count) + ";";
        } else {
            optimized += std::string(count, lastChar);
        }
    }

    // [-] または [+] のパターンを *ptr = 0; に変換
    size_t pos;
    while ((pos = optimized.find("[-]")) != std::string::npos ||
           (pos = optimized.find("[+]")) != std::string::npos) {
        optimized.replace(pos, 3, "*ptr = 0;");
    }

    return optimized;
}

---

3. 構文エラーのチェック

Brainfuck では [ と ] の数が一致しないとエラーになります。
構文解析時にこのチェックを追加します。

parser.cpp の修正

#include <iostream>
#include <stack>

bool validateBrackets(const std::string& bfCode) {
    std::stack<int> bracketStack;

    for (size_t i = 0; i < bfCode.size(); i++) {
        if (bfCode[i] == '[') {
            bracketStack.push(i);
        } else if (bfCode[i] == ']') {
            if (bracketStack.empty()) {
                std::cerr << "エラー: 余分な ']' が見つかりました（位置 " << i << "）\n";
                return false;
            }
            bracketStack.pop();
        }
    }

    if (!bracketStack.empty()) {
        std::cerr << "エラー: ']' が不足しています\n";
        return false;
    }

    return true;
}

この関数を main.cpp で generateCCode を呼び出す前に実行し、構文エラーを事前に検出します。

---

4. Cコード生成の修正

最適化後のコードを C 言語に変換するように generator.cpp を修正します。

#include "generator.h"
#include "optimizer.h"

std::string generateCCode(const std::string& bfCode) {
    std::string optimizedCode = optimizeBrainfuck(bfCode);
    std::ostringstream cCode;

    cCode << "#include <stdio.h>\n";
    cCode << "int main() {\n";
    cCode << "    unsigned char tape[30000] = {0};\n";
    cCode << "    unsigned char *ptr = tape;\n";

    for (char c : optimizedCode) {
        switch (c) {
            case '>': cCode << "    ptr += " << c << ";\n"; break;
            case '<': cCode << "    ptr -= " << c << ";\n"; break;
            case '+': cCode << "    (*ptr) += " << c << ";\n"; break;
            case '-': cCode << "    (*ptr) -= " << c << ";\n"; break;
            case '.': cCode << "    putchar(*ptr);\n"; break;
            case ',': cCode << "    *ptr = getchar();\n"; break;
            case '[': cCode << "    while (*ptr) {\n"; break;
            case ']': cCode << "    }\n"; break;
            case '*': cCode << "    " << c << ";\n"; break;
            default: break;
        }
    }

    cCode << "    return 0;\n";
    cCode << "}\n";

    return cCode.str();
}

---

5. 動作確認

5.1 最適化前後の比較

$ echo "++++++------" | ./bf_compiler test.bf

最適化前:

(*ptr)++; (*ptr)++; (*ptr)++; (*ptr)++; (*ptr)++; (*ptr)--;
(*ptr)--; (*ptr)--; (*ptr)--; (*ptr)--; (*ptr)--;

最適化後:

(*ptr) += 6;
(*ptr) -= 6;

無駄な処理が削除され、効率的なコードが生成されていることがわかります。

---

6. まとめと次回予告

今回は、Brainfuckコンパイラの 最適化 と エラー処理 を実装しました。

• 最適化の適用 (++++++ → +=6 など)
• クリアループの簡略化 ([-] → *ptr = 0;)
• 構文エラーの検出 ([ ] のバランスチェック)

次回は JIT コンパイルの導入 に挑戦し、LLVM を用いた Brainfuck の 高速実行 を実装します。

---

参考文献

• Brainfuckの解説 - Esolang
• LLVM - JIT コンパイル

次回もお楽しみに！