1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

Day 21

NITKPC Advent Calendar 2025

@ssuzzukki

わたしがプログラミング言語の処理系を作れるわけないじゃん、ムリムリ！（※ムリじゃなかった！？）

1
Last updated at Posted at 2025-12-20

はじめに

皆さんは自作プログラミング言語に興味はありますか? 私はあります(未だ完成していませんが).
1年ほど前にそんな話をプログラミング研究部でしたところ, 愉快な先輩たちがBrainfuckという愉快な言語を教えてくれました. 今回はそのBrainfuckの処理系を作ってみたいと思います. 初めて知ったその日に私でも書けたほどシンプルで簡単なので皆さんもぜひ挑戦してみてください.

Brainfuckとは？

Brainfuckとはコンパイラがなるべく小さくなるように設計された言語で, なんと命令が8種類しか存在しない. 可読性は著しく低いが驚くことにチューリング完全である. 8つの命令の内容は以下の通り.

命令 内容
+ ポインタが指す値をインクリメント
- ポインタが指す値をデクリメント
> ポインタをインクリメント
< ポインタをデクリメント
. ポインタが指す値をASCII文字として出力
, 入力から1バイト受け取ってポインタが指すメモリに代入
[ ポインタが指す値が0なら対応する ] までスキップ
] ポインタが指す値が0でなければ対応する [ まで戻る

これらの命令で長いメモリの上を動きながら値を書き換えていくだけの言語である.
これが"Hello, World!"と出力するコード.

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

人にはとても読めない⋯と思いきや意外と読めたりもする. 私がBrainfuckを読めるわけないじゃん、ムリムリ！(※ムリじゃなかった！？)
詳しくはWikiとか読んでね.

作るぞ！！

今回はC言語で作る.

その1 ファイルからコードを取り出そう

まずは文字列を格納する配列を作るためにファイルサイズを取得する関数を作る.
一番後ろまで移動して位置を確認. 最後は必ず先頭に戻っておく.

brainfuck.c
#include <stdio.h>

int fsize(FILE *fp){

        fseek(fp, 0, SEEK_END);
        int size = ftell(fp);
        fseek(fp, 0, SEEK_SET);
        return size;
}

次はcalloc関数を使って配列を作り, 一文字ずつ格納する.
Brainfuckで使わない文字はスキップ.

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

char *get_code(FILE *fp){
        char *code;
        int x;
        int i = 0; 

        code = calloc(fsize(fp), sizeof(char));
        while(1){
                x = fgetc(fp);
                if (x == EOF) break;
                if (!((x == '+') || (x == '-') || (x == '[') || (x == ']') || (x == '>') || (x == '<') || (x == ',') || (x == '.'))) continue;
                code[i] = x;
                i++;
        }
        return code;
}

これでファイルからコードが取り出せるようになった.

その2 メモリを用意しよう ～桃色の論理は飛翔する～

C言語ではあとから配列の要素を増やせないの
だから先に要素数を決めないといけない
だからおっきなメモリを用意したんだよ⋯

brainfuck.c
#define MEMORY_SIZE 30000

char *memory = calloc(MEMORY_SIZE, sizeof(char));

クソデカメモリがあれば一旦安心.
callocで0に初期化している.
今度リストを実装して可変長のメモリで再挑戦したい.
作った！！

その3 ポインタを用意しよう

ここでいうポインタはC言語で使うポインタとは違うもの.
「今コードのどこを読んでいるのか」を司るポインタと「今メモリのどこにいるのか」を司るポインタを用意する.

brainfuck.c
int cPointer = 0;
int mPointer = 0;

ついでに初期化もしておこう.

その4 実行部分を作ろう

brainfuck.c
int exec(char *code){
        char *memory = calloc(MEMORY_SIZE, sizeof(char));
        int cPointer = 0;
        int mPointre = 0;

        while(1){
                if (code[cPointer] == '\0') break;
                printf("%c", code[cPointer]);
                cPointer++;
        }
        printf("\n");
        free(memory);
        return 0;
}

int main(int argc, char *argv[]){
        FILE *fp;
        char *code;
        fp = fopen(argv[1], "r");
        if (fp == NULL) return -1;

        code = get_code(fp);
        exec(code);

        free(code);
        return 0;
}

とりあえずこんな感じ.
実行用関数execは今はコードを一文字ずつそのまま出力してるだけ.
main関数はファイル開いてコード取り出してexecにぶち込んでるだけ.

次は各コマンドの処理を書いていく.
とりあえず簡単な4つから.

brainfuck.c
int exec(char *code){                                                                                                           char *memory = calloc(MEMORY_SIZE, sizeof(char));
        int cPointer = 0;
        int mPointer = 0;

        while(1){
                if (code[cPointer] == '\0') break;
                // printf("%c", code[cPointer]);

                if (code[cPointer] == '+') memory[mPointer]++;
                if (code[cPointer] == '-') memory[mPointer]
                if (code[cPointer] == '>') mPointer++;
                if (code[cPointer] == '<') mPointer--;
                cPointer++;
        }
        printf("\n");
        free(memory);
        return 0;
}

コマンドの動作の説明は省略.
次は入出力のコマンド.

brainfuck.c
int exec(char *code){
        char *memory = calloc(MEMORY_SIZE, sizeof(char));                                                                       int cPointer = 0;
        int mPointer = 0;

        while(1){
                if (code[cPointer] == '\0') break;

                if (code[cPointer] == '+') memory[mPointer]++;
                if (code[cPointer] == '-') memory[mPointer]--;
                if (code[cPointer] == '>') mPointer++;
                if (code[cPointer] == '<') mPointer--;
                if (code[cPointer] == ',') memory[mPointer] = fgetc(stdin);
                if (code[cPointer] == '.') fprintf(stdout, "%c", memory[mPointer]);
                cPointer++;
        }
        printf("\n");
        free(memory);
        return 0;
}

最後に最大の鬼門(?)ループを作っていく.

'['はメモリの値が0なら対応する']'までジャンプするコマンド. 括弧が入れ子になっている場合など, コードを順に見て最初に出てきた括弧が必ずしも対応する括弧であるとは限らない.
そこで, カウンターcheckを作り'['が出てきたら+1, ']'が出てきたら-1して, カウンターが0のとき出てきた']'が対応する括弧である, という風に判断する.

brainfuck.c
int check = 0;

while(1){
        check = 0;

        if (code[cPointer] == '\0') break;

        if (code[cPointer] == '+') memory[mPointer]++;
        if (code[cPointer] == '-') memory[mPointer]--;
        if (code[cPointer] == '>') mPointer++;
        if (code[cPointer] == '<') mPointer--;
        if (code[cPointer] == ',') memory[mPointer] = fgetc(stdin);
        if (code[cPointer] == '.') fprintf(stdout, "%c", memory[mPointer]);

        if ((code[cPointer] == '[') && (memory[mPointer] == 0)){
                while(1){
                        cPointer++;
                        if (code[cPointer] == '[') check++;
                        if (code[cPointer] == ']') {
                                if (check == 0) break;
                                check--;
                        }
                }
        }

        cPointer++;
}

']'は逆向きに同じことをやればいい.

brainfuck.c
if ((code[cPointer] == ']') && (memory[mPointer] != 0)){
        while(1){
                cPointer--;
                if (code[cPointer] == '['){
                        if (check == 0) break;
                                check++;
                }
                if (code[cPointer] == ']') check--;
        }
}

なんとこれで処理系は完成です！！！！

あとは軽く調整とか機能の追加とか.

その5 便利な機能を追加しよう

引数を与えず実行したときに標準入力からコードを入力できるようにしよう.

まずはget_code関数を改良して標準入力に対応させよう.
fsize関数はファイル内を移動してサイズを測るので, stdinには対応してない. その他にも区切り文字をEOFと'\n'で使い分ける必要がある.
ちなみに長さは先に取得できないので256固定にする.

brainfuck.c
#define BUFLEN 256

char *get_code(FILE *fp){
        char *code;
        int x;
        int i = 0;
        char fend;

        if (fp == stdin){
                code = calloc(BUFLEN, sizeof(char));
                fend = '\n';
        }else{
                code = calloc(fsize(fp), sizeof(char));
                fend = EOF;
        }
        while(1){
                x = fgetc(fp);
                if (x == fend) break;
                if (!((x == '+') || (x == '-') || (x == '[') || (x == ']') || (x == '>') || (x == '<') || (x == ',') || (x == '.'))) continue;
                code[i] = x;
                i++;
        }
        return code;
}

main関数は引数がないときにコード入力からの実行をひたすら繰り返すことにする.

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

        if (argc == 1){
                while(1){
                        printf("code>> ");
                        code = get_code(stdin);
                        exec(code);
                        free(code);
                }
        }else{
                fp = fopen(argv[1], "r");                                                                                               if (fp == NULL) return -1;
                code = get_code(fp);
                exec(code);
                free(code);
        }

        return 0;
}

ついでに, 対話形式を'q'で抜けられるようにする.

brainfuck.c
char *get_code(FILE *fp){
        char *code;
        int x;
        int i = 0;
        char fend;

        if (fp == stdin){
                code = calloc(BUFLEN, sizeof(char));
                fend = '\n';
        }else{
                code = calloc(fsize(fp), sizeof(char));
                fend = EOF;
        }
        while(1){
                x = fgetc(fp);
                if ((x == 'q') && (i == 0)){
                        code[0] = 'q';
                        break;
                }
                if (x == fend) break;
                if (!((x == '+') || (x == '-') || (x == '[') || (x == ']') || (x == '>') || (x == '<') || (x == ',') || (x == '.'))) continue;
                code[i] = x;
                i++;
        }
        return code;
}

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

        if (argc == 1){
                while(1){
                        printf("code>> ");
                        code = get_code(stdin);
                        if (code[0] == 'q') {
                                free(code);
                                break;
                        }
                        exec(code);
                        free(code);
                }
        }else{
                fp = fopen(argv[1], "r");
                if (fp == NULL) return -1;
                code = get_code(fp);
                exec(code);
                free(code);
        }

        return 0;
}

完成！！！！！！！！

完成したものがこちらになります. 短いですね.

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

#define MEMORY_SIZE 30000
#define BUFLEN 256

// ファイルサイズ確認用関数
int fsize(FILE *fp){

        fseek(fp, 0, SEEK_END);
        int size = ftell(fp);
        fseek(fp, 0, SEEK_SET);

        return size;
}

// ファイルからコードを取り出す関数
char *get_code(FILE *fp){
        char *code;
        int x;
        int i = 0;
        char fend;

        if (fp == stdin){
                code = calloc(BUFLEN, sizeof(char));
                fend = '\n';
        }else{
                code = calloc(fsize(fp), sizeof(char));
                fend = EOF;
        }
        while(1){
                x = fgetc(fp);
                if ((x == 'q') && (i == 0)){
                        code[0] = 'q';
                        break;
                }
                if (x == fend) break;
                if (!((x == '+') || (x == '-') || (x == '[') || (x == ']') || (x == '>') || (x == '<') || (x == ',') || (x == '.'))) continue;
                code[i] = x;
                i++;
        }
        return code;
}




// Brainfuckを実行する関数
int exec(char *code){
        char *memory = calloc(MEMORY_SIZE, sizeof(char));
        int cPointer = 0;
        int mPointer = 0;
        int check = 0;

        while(1){
                check = 0;

                if (code[cPointer] == '\0') break;

                if (code[cPointer] == '+') memory[mPointer]++;
                if (code[cPointer] == '-') memory[mPointer]--;
                if (code[cPointer] == '>') mPointer++;
                if (code[cPointer] == '<') mPointer--;
                if (code[cPointer] == ',') memory[mPointer] = fgetc(stdin);
                if (code[cPointer] == '.') fprintf(stdout, "%c", memory[mPointer]);

                if ((code[cPointer] == '[') && (memory[mPointer] == 0)){
                        while(1){
                                cPointer++;
                                if (code[cPointer] == '[') check++;
                                if (code[cPointer] == ']') {
                                        if (check == 0) break;
                                        check--;
                                }
                        }
                }
                if ((code[cPointer] == ']') && (memory[mPointer] != 0)){
                        while(1){
                                cPointer--;
                                if (code[cPointer] == '[') {
                                        if (check == 0) break;
                                        check++;
                                }
                                if (code[cPointer] == ']') check--;
                        }
                }

                cPointer++;
        }
        printf("\n");
        free(memory);
        return 0;
}

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

        if (argc == 1){
                while(1){
                        printf("code>> ");
                        code = get_code(stdin);
                        if (code[0] == 'q') {
                                free(code);
                                break;
                        }
                        exec(code);
                        free(code);
                }
        }else{
                fp = fopen(argv[1], "r");
                if (fp == NULL) return -1;
                code = get_code(fp);
                exec(code);
                free(code);
        }

        return 0;
}

可読性捨てたらもっと短くなりそう.

だからこれからもたくさん見せてね ぶれいんちゃんのファック⋯ ぶれいんざふぁっくを！

実際に使ってみよう.
例文1

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.

例文2

>+++++++++++[<++++++>-]<.>++++++[<++++++++>-]<.>+>++++++[<++++++++++++++++>-]<.++++++++.+++++.>>++++++[<+++++++++++++++++>-]<.>+++++[<+++>-]<.>>+++++++++++[<+++++++++>-]<.++++++++.

例文3

>+++++++[<++++++++++++>-]<.>++++++++++[<++>-]<.>+>++++++[<++++++++++++++++>-]<.>+++++++++++++[<+>-]<.>++>+++++++[<+++++++++++++++>-]<.>>++++[<++++++++>-]<.+>+++++++++++[<++++++++>-]<.>+>+++++++++++[<++++++++++>-]<.++++++.>>++++[<++++++++>-]<.>++++++++++[<+++++++>-]<.+++++++++.+++.>>++++[<++++++++>-]<.+>+++++++++[<+++++++++>-]<.>+>++++++++++[<++++++++++>-]<.>+>++++++[<++++++++++++++++>-]<.+++.+++++.+++++.>+>++++++[<+++++++++++++++++>-]<.>>+++++++++++[<+++>-]<.
解答
  1. Hello World!
  2. Brainfuck
  3. Thank you for reading!

おまけ(リスト使用版)

最低限使える程度のリストを作ったので可変長のメモリで挑戦.

桃ちゃん⋯
リストはゴムのように伸びるよ⋯

その1 リストを導入しよう

ここで作ったリストを導入する. まずはこれを書き加えよう.

#include <stdlib.h>

typedef struct list list;
struct list{
        char data;
        list *prev;
        list *next;
};

list *Next(list *l1){
        if(l1->next == NULL){
                struct list *l2 = (list *)malloc(sizeof(list));
                l1->next = l2;
                l2->prev = l1;
                l2->next = NULL;
                return l2;
        }else{
                return l1->next;
        }
}

list *Prev(list *l){
        return l->prev;
}

void Free(list *l){
        if(l->next == NULL){
                free(l);
        }else{
                Free(Next(l));
                free(l);
        }
}

その2 リストの関数をちょっと改良しよう

0で初期化されるよう改良.

brainfuck2.c
list *Next(list *l1){
        if(l1->next == NULL){
                struct list *l2 = (list *)malloc(sizeof(list));
                l1->next = l2;
                l2->prev = l1;
                l2->next = NULL;
                l2->data = 0;
                return l2;
        }else{
                return l1->next;
        }
}

その3 exec()を改良しよう

ほとんどmemory[mPointer]をmPointer->dataに書き換えるだけ. あとは定義とかFree()とか.

brainfuck2.c
int exec(char *code){
        struct list *memory = (list *)malloc(sizeof(list));
        memory->data = 0;
        memory->prev = NULL;
        memory->next = NULL;
        int cPointer = 0;
        struct list *mPointer = (list *)malloc(sizeof(list));
        mPointer = memory;
        int check = 0;

        while(1){
                check = 0;

                if (code[cPointer] == '\0') break;

                if (code[cPointer] == '+') (mPointer->data)++;
                if (code[cPointer] == '-') (mPointer->data)--;
                if (code[cPointer] == '>') mPointer = Next(mPointer);
                if (code[cPointer] == '<') mPointer = Prev(mPointer);
                if (code[cPointer] == ',') (mPointer->data) = fgetc(stdin);
                if (code[cPointer] == '.') fprintf(stdout, "%c", mPointer->data);

                if ((code[cPointer] == '[') && (mPointer->data == 0)){
                        while(1){
                                cPointer++;
                                if (code[cPointer] == '[') check++;
                                if (code[cPointer] == ']') {
                                        if (check == 0) break;
                                        check--;
                                }
                        }
                }
                if ((code[cPointer] == ']') && (mPointer->data != 0)){
                        while(1){
                                cPointer--;
                                if (code[cPointer] == '[') {
                                        if (check == 0) break;
                                        check++;
                                }
                                if (code[cPointer] == ']') check--;
                        }
                }

                cPointer++;
        }
        printf("\n");
        Free(memory);
        return 0;
}

完成！！！！！！！！

これで改良終わりです. 実際に例文を試すと同じ結果になるのがわかります.

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

#define BUFLEN 256

// リスト関係
typedef struct list list;
struct list{
        char data;
        list *prev;
        list *next;
};

list *Next(list *l1){
        if(l1->next == NULL){
                struct list *l2 = (list *)malloc(sizeof(list));
                l1->next = l2;
                l2->prev = l1;
                l2->next = NULL;
                l2->data = 0;
                return l2;
        }else{
                return l1->next;
        }
}

list *Prev(list *l){
        return l->prev;
}

void Free(list *l){
        if(l->next == NULL){
                free(l);
        }else{
                Free(Next(l));
                free(l);
        }
}




// ファイルサイズ確認用関数
int fsize(FILE *fp){

        fseek(fp, 0, SEEK_END);
        int size = ftell(fp);
        fseek(fp, 0, SEEK_SET);

        return size;
}

// ファイルからコードを取り出す関数
char *get_code(FILE *fp){
        char *code;
        int x;
        int i = 0;
        char fend;

        if (fp == stdin){
                code = calloc(BUFLEN, sizeof(char));
                fend = '\n';
        }else{
                code = calloc(fsize(fp), sizeof(char));
                fend = EOF;
        }
        while(1){
                x = fgetc(fp);
                if ((x == 'q') && (i == 0)){
                        code[0] = 'q';
                        break;
                }
                if (x == fend) break;
                if (!((x == '+') || (x == '-') || (x == '[') || (x == ']') || (x == '>') || (x == '<') || (x == ',') || (x == '.'))) continue;
                code[i] = x;
                i++;
        }
        return code;
}




// Brainfuckを実行する関数
int exec(char *code){
        struct list *memory = (list *)malloc(sizeof(list));
        memory->data = 0;
        memory->prev = NULL;
        memory->next = NULL;
        int cPointer = 0;
        struct list *mPointer = (list *)malloc(sizeof(list));
        mPointer = memory;
        int check = 0;

        while(1){
                check = 0;

                if (code[cPointer] == '\0') break;

                if (code[cPointer] == '+') (mPointer->data)++;
                if (code[cPointer] == '-') (mPointer->data)--;
                if (code[cPointer] == '>') mPointer = Next(mPointer);
                if (code[cPointer] == '<') mPointer = Prev(mPointer);
                if (code[cPointer] == ',') (mPointer->data) = fgetc(stdin);
                if (code[cPointer] == '.') fprintf(stdout, "%c", mPointer->data);

                if ((code[cPointer] == '[') && (mPointer->data == 0)){
                        while(1){
                                cPointer++;
                                if (code[cPointer] == '[') check++;
                                if (code[cPointer] == ']') {
                                        if (check == 0) break;
                                        check--;
                                }
                        }
                }
                if ((code[cPointer] == ']') && (mPointer->data != 0)){
                        while(1){
                                cPointer--;
                                if (code[cPointer] == '[') {
                                        if (check == 0) break;
                                        check++;
                                }
                                if (code[cPointer] == ']') check--;
                        }
                }

                cPointer++;
        }
        printf("\n");
        Free(memory);
        return 0;
}

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

        if (argc == 1){
                while(1){
                        printf("code>> ");
                        code = get_code(stdin);
                        if (code[0] == 'q') {
                                free(code);
                                break;
                        }
                        exec(code);
                        free(code);
                }
        }else{
                fp = fopen(argv[1], "r");
                if (fp == NULL) return -1;
                code = get_code(fp);
                exec(code);
                free(code);
        }

        return 0;
}

おわりに

以前Rubyで書いたものは入力の処理ができていなかったりアンダーフローができなかったりしたので, 今回はちゃんとしたものを書けてよかった. この記事を書いている間にもリストを実装して改良できて成長を感じたので, 今後もC言語でなにか作って投稿したい.

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?