Brainfuck コンパイラの自作 第3回 - 構文解析（Parsing）の実装
1. はじめに
前回は字句解析（Lexing）を実装し、Brainfuck のコードをトークンのリストに変換しました。
今回は 構文解析（Parsing） を行い、特に [ と ] の対応関係を管理する ジャンプテーブル を作成します。
2. 構文解析（Parsing）とは？
構文解析（Parsing）は、字句解析で得たトークンを解析し、文法的な誤りを検出・管理するプロセス です。
Brainfuck における構文解析
Brainfuck の構文解析では、特に ループ構造（[ ]）の対応関係 を管理することが重要です。
処理内容
- トークンリストの読み取り
[と]のペアを管理するジャンプテーブルの作成- エラー処理（対応しない
[]があれば警告）
3. 構文解析の実装
プロジェクト構成
brainfuck_compiler/ ├── main.cpp （エントリポイント） ├── lexer.cpp （字句解析） ├── lexer.hpp ├── parser.cpp （構文解析） ├── parser.hpp ├── Makefile
1. parser.hpp（Parser クラスの定義）
#ifndef PARSER_HPP #define PARSER_HPP #include <vector> #include <unordered_map> class Parser { public: explicit Parser(const std::vector<char>& tokens); bool parse(); // 構文解析を実行 std::unordered_map<int, int> getJumpTable() const; private: std::vector<char> tokens; std::unordered_map<int, int> jumpTable; // `[` `]` のペア }; #endif
2. parser.cpp（Parser クラスの実装）
#include "parser.hpp" #include <stack> #include <iostream> Parser::Parser(const std::vector<char>& tokens) : tokens(tokens) {} // 構文解析（ループの対応関係をチェック） bool Parser::parse() { std::stack<int> loopStack; for (int i = 0; i < tokens.size(); i++) { if (tokens[i] == '[') { loopStack.push(i); } else if (tokens[i] == ']') { if (loopStack.empty()) { std::cerr << "構文エラー: 余分な ']' が " << i << " 番目にあります。\n"; return false; } int openPos = loopStack.top(); loopStack.pop(); jumpTable[openPos] = i; jumpTable[i] = openPos; } } if (!loopStack.empty()) { std::cerr << "構文エラー: 対応しない '[' があります。\n"; return false; } return true; } // ジャンプテーブルを取得 std::unordered_map<int, int> Parser::getJumpTable() const { return jumpTable; }
3. main.cpp（Parser のテスト）
#include <iostream> #include <fstream> #include "lexer.hpp" #include "parser.hpp" int main(int argc, char* argv[]) { if (argc < 2) { std::cerr << "使い方: " << argv[0] << " <brainfuckファイル>\n"; return 1; } std::ifstream file(argv[1]); if (!file) { std::cerr << "ファイルを開けませんでした: " << argv[1] << "\n"; return 1; } std::string code((std::istreambuf_iterator<char>(file)), std::istreambuf_iterator<char>()); // 字句解析 Lexer lexer(code); std::vector<char> tokens = lexer.tokenize(); // 構文解析 Parser parser(tokens); if (!parser.parse()) { std::cerr << "構文解析に失敗しました。\n"; return 1; } // ジャンプテーブルの表示 std::unordered_map<int, int> jumpTable = parser.getJumpTable(); std::cout << "ジャンプテーブル:\n"; for (const auto& pair : jumpTable) { std::cout << pair.first << " -> " << pair.second << "\n"; } return 0; }
4. 実行方法
1. コンパイル
g++ main.cpp lexer.cpp parser.cpp -o bf_parser
2. テスト用 Brainfuck コード（loop_test.bf）
+[->++<].
このコードは以下の処理を行います：
1. + : 1 をメモリにセット
2. [ : ループ開始
3. - : 1 を 0 にする（ループ終了）
4. > : 次のセルへ移動
5. ++ : 2 をセット
6. < : 先頭セルに戻る
7. ] : ループ終了
8. . : ASCII コード 2 (STX) を出力
3. 実行
./bf_parser loop_test.bf
4. 出力結果
ジャンプテーブル: 1 -> 6 6 -> 1
この結果から、[ が 1 番目、対応する ] が 6 番目にあることが分かります。
5. まとめと次回の予定
今回の成果
✅ 構文解析（Parsing）の基本を実装
✅ [ ] の対応関係を管理するジャンプテーブルを作成
✅ 構文エラーを検出できるようにした
次回予定
次回は、C 言語コードの生成 を行い、Brainfuck のコードを C に変換し、コンパイルして実行できるようにします。
- > < + - . , の C 変換
- [ ] のループ処理を C コードで実装
- generator.cpp の作成
次に学ぶべきこと
- Brainfuck のコード変換
- C 言語でのメモリ管理
- シンプルなコード生成のテクニック
参考リンク - Brainfuck Wikipedia - コンパイラ構築の基本 - C++ の std::unordered_map
次回もお楽しみに！
