今回は、これまでに解説したスタックマシンを用いたコンパイラが受理する言語について説明します。

言語仕様

本言語はシンプルな構文を持ち、制御構造、変数・配列の宣言、入出力用の組み込み関数などを備えます。
各文はセミコロンで区切られ、プログラムはグローバルスコープで実行されます。

コメント (C と同じ)

行コメント
- 各行の // 以降はコメント
ブロックコメント
- /* と */ に囲まれた領域はコメント

型

全ての式の値は実行系における各セルの型と同じで、配列の各要素も同様です。基本的には unit8 (wrap-around) を想定しています。

式

主要な式の種類と例、説明を以下に示します。

種類	例	説明
リテラル	`2`, `'a'`, `'+'`	整数、文字などの定数
変数・配列の要素	`num`, `mat[i][j]`	宣言済みの変数や配列要素の値の参照
演算	`i * 5 + j`, `num + i`, `!flag`	演算子を含む計算
標準入力受取	`getint()`, `getchar()`	組み込み関数呼び出し

演算子を以下の表に示します。上から順に高い優先度を持ちます。

優先度	演算子	種類	説明
1	`()`, 変数, リテラル	primary	プライマリ、括弧・グループ化
2	`+`, `-`, `!`	unary	単項正負、単項論理否定
3	`*`, `/`, `%`	multiplicative	乗算、除算、剰余算
4	`+`, `-`	additive	加減算
5	`>`, `<`, `>=`, `<=`	relational	比較演算
6	`==`, `!=`	equality	等値・不等値比較
7	`&`	logical and	論理積
8	`\|`	logical or	論理和

C と異なり、論理積と論理和に短絡評価 (ショートサーキット) はありません。全ての項が評価されます。
また、ビットワイズの論理積と論理和は存在しません。

排他的論理和は != とほとんど等価なため、^ は存在しません。

文

変数宣言

キーワード var を使用して変数を宣言します。変数は 0 で初期化されます。

var i;

宣言時に代入を行うこともできます。

var j = 10;

配列宣言

キーワード arr を使用して静的サイズの一次元または多次元配列を宣言します。各要素は 0 で初期化されます。

arr vec[8];
arr mat[4][4];

配列のサイズには、(変数を含まない) 式を指定できます。変数の参照を含む場合はエラーになります。

arr grid[9 * 9]; // ok
var a = 10;
arr err[a]; // error!

代入

変数や配列要素に対して = を用いて値を代入できます。

i = 255;
mat[0][0] = 10;

左辺値になることができるのは変数と配列の要素だけです。配列を左辺値にすることはできません。

arr lhs[4][4];
lhs[0][0] = 5; // ok
lhs = 100; // error!
lhs[0] = 10; // error!

四則演算と剰余演算による複合代入が可能です。

var a = 0;
a += 10;
a -= 5;
a *= 3;
a /= 2;
a %= 100;

制御文

if 文

条件に応じた分岐処理を行います。

if (hoge) {
    putchar('h');
    putchar('o');
    putchar('g');
    putchar('e');
} else {
    putchar('p');
    putchar('o');
    putchar('y');
    putchar('o');
}

else 句は省略できます。

if (hoge) {
    putchar('h');
    putchar('o');
    putchar('g');
    putchar('e');
}

for 文

C と同様に、初期化子、条件式、再初期化子を用いたループ処理を行います。

for (var i = 'a'; i <= 'z'; i += 1) {
    putchar(i);
}

while 文

C と同様の while 文です。

// GCD(a, b)
var a = getint();
var b = getint();
while (a != 0) {
    b %= a;
    var c = b;
    b = a;
    a = c;
}
putint(b);

変数スコープ

各制御文の中は局所スコープを形成します。変数は宣言されたブロック内でのみ有効です。内部での宣言は外側と独立したローカル変数となります。

for (var i = 0; i < 5; i += 1) {
    putint(i);
    putchar(' ');
    for (var i = 0; i < 5; i += 1) {
        putint(i);
    }
    putchar('\n');
}
/*
0 01234
1 01234
2 01234
3 01234
4 01234
*/

組み込み関数

組み込み関数を利用して入出力を行います。

getint(): 入力された文字列を 10 進数で解釈
getchar(): 入力を 1 文字として解釈
putint(expr): expr を評価した値を 10 進数で出力
putchar(expr): expr を評価した値を文字として出力

未定義動作

配列のインデックスが範囲内かどうかは、コンパイル時、実行時ともにチェックされません。配列の範囲外にアクセスすると、他の変数を破壊したり負番地へのアクセスが発生する可能性があるため、プログラマの責任でこれを行ってはいけません。

コンパイラの使い方

compiler.py がコンパイラの実行ファイルです。ソースファイルを指定するとコンパイル結果の Brainf*ck のコードを標準出力します。どこかにリダイレクトして使用します。

$ git clone https://github.com/void-hoge/brainfuck.git
$ cd brainfuck
$ ./compiler data/for.txt
[-]>[-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++><<[-]>[-<+>]>[-]<<[->+>+<<]>>[-<<+>>][-]+++++++++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+++++++++++++++++++++++++++>[-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+
[-]<+[[-]>+<]>[-<+>][-]+<[[-]>-<]>[-<+>]<[[-]>[-]<<[->+>+<<]>>[-<<+>>]<.[-]>[-]<
<[->+>+<<]>>[-<<+>>][-]+><[-<+>]<<[-]>[-<+>]>[-]<<[->+>+<<]>>[-<<+>>][-]++++++++
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++>[-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]
<[-]<<+[-]<+[[-]>+<]>[-<+>][-]+<[[-]>-<]>[-<+>]<]<[-][-]++++++++++><.[-]

$ ./compiler data/for.txt > data/for.bf
$

interpreter.py は Brainf*ck のインタプリタです。停止時にデータポインタ位置、メモリの状態、実行ステップ数を出力します。また、@ でブレークポイントを設定できます。

$ ./interpreter.py data/for.bf
abcdefghijklmnopqrstuvwxyz
(0, [0, 0, 0, 0, 0, 0, 0], 237677)
$

付属の interpreter.py は遅いので、高速な処理系を一つ持っておくことを推奨します。

参考: https://kmyk.github.io/blog/blog/2016/03/21/brainfuck-on-services/

例

小文字アルファベット

小文字のアルファベットを順に出力します。

ソースコード

for (var i = 'a'; i <= 'z'; i += 1) {
    putchar(i);
}
putchar('\n');

FizzBuzz

2 から 255 までの値で FizzBuzz します。

ソースコード

for (var num = 1; num != 0; num += 1){
    var fizz = num % 3 == 0;
    var buzz = num % 5 == 0;
    var nofizzbuzz = !(fizz | buzz);
    if (nofizzbuzz) {
        putint(num);
    }
    if (fizz) {
        putchar('f');
        putchar('i');
        putchar('z');
        putchar('z');
    }
    if (buzz) {
        putchar('b');
        putchar('u');
        putchar('z');
        putchar('z');
    }
    putchar('\n');
}
putchar('\n');

最大公約数

標準入力から与えられた 2 数の最大公約数を返します。

ソースコード

var a = getint();
var b = getint();
putchar('G');
putchar('C');
putchar('D');
putchar('(');
putint(a);
putchar(',');
putchar(' ');
putint(b);
putchar(')');
putchar(' ');
putchar('=');
putchar(' ');
while (a != 0) {
    b %= a;
    var c = b;
    b = a;
    a = c;
}
putint(b);
putchar('\n');

素因数分解

2 から 255 までの値を素因数分解した結果を出力します。

ソースコード

for (var num = 2; num != 0; num += 1) {
    arr factors[7];
    var div = 2;
    var count = 0;
    putint(num);
    putchar(' ');
    putchar('=');
    putchar(' ');

    for (var target = num; target != 1;) {
        if (target % div) {
            div += 1;
        } else {
            target /= div;
            factors[count] = div;
            count += 1;
        }
    }
    for (var i = 0; i < count; i += 1) {
        putint(factors[i]);
        if (i + 1 != count) {
            putchar(' ');
            putchar('*');
            putchar(' ');
        } else {
            putchar('\n');
        }
    }
}

素数判定

2 から 255 までの値が素数かどうか判定し、それぞれ素数ならば報告します。

ソースコード

arr table[8];
table[0] = 2;
table[1] = 3;
table[2] = 5;
table[3] = 7;
table[4] = 11;
table[5] = 13;
table[6] = 17;
table[7] = 19;

for (var num = 2; num != 0; num += 1) {
    var flag = 1;
    for (var i = 0; flag & i < 6 & table[i] * table[i] <= num; i += 1) {
        if (num % table[i] == 0) {
            flag = 0;
        }
    }
    if (flag) {
        putint(num);
        putchar(' ');
        putchar('i');
        putchar('s');
        putchar(' ');
        putchar('a');
        putchar(' ');
        putchar('p');
        putchar('r');
        putchar('i');
        putchar('m');
        putchar('e');
        putchar(' ');
        putchar('n');
        putchar('u');
        putchar('m');
        putchar('b');
        putchar('e');
        putchar('r');
        putchar('!');
        putchar('\n');
    }
}

転置

5x5 の行列を転置します。

ソースコード

arr mda[5][5];

for (var i = 0; i < 5; i += 1) {
    for (var j = 0; j < 5; j += 1) {
        mda[i][j] = i * 5 + j + 'a';
    }
}

for (var i = 0; i < 5; i += 1) {
    for (var j = 0; j < 5; j += 1) {
        putchar(mda[i][j]);
    }
    putchar('\n');
}
putchar('\n');
for (var i = 0; i < 5; i += 1) {
    for (var j = i + 1; j < 5; j += 1) {
        var tmp = mda[j][i];
        mda[j][i] = mda[i][j];
        mda[i][j] = tmp;
    }
}
for (var i = 0; i < 5; i += 1) {
    for (var j = 0; j < 5; j += 1) {
        putchar(mda[i][j]);
    }
    putchar('\n');
}

数独ソルバー

標準入力から与えられた 9x9 の数独を解きます。

ソースコード

arr grid[9][9];

// 入力例
// .2.71..6.......4.5.3..9..2.5....46..8.43..........7849..9.7...12.6.........2.....
// .7..6..3....58.2...5...7.8.9....3.26........12.8...7..3..6...1...9........6..4..7
// .1......2594.6..3...29.5......3..7.9.....1..4..5..7.8..........7..1.41......891..

// 問題入力
for (var i = 0; i < 9; i += 1) {
    for (var j = 0; j < 9; j += 1) {
        var c = getchar();
        if (c == '.') {
            grid[i][j] = 0;
        } else {
            grid[i][j] = c - '0';
        }
    }
}

// 問題表示
for (var i = 0; i < 9; i += 1) {
    if (i % 3 == 0) {
        putchar('+');
        for (var j = 0; j < 3; j += 1) {
            putchar('-');
            for (var k = 0; k < 3; k += 1) {
                putchar('-');
                putchar('-');
            }
            putchar('+');
        }
        putchar('\n');
    }
    for (var j = 0; j < 9; j += 1) {
        if (j % 3 == 0) {
            putchar('|');
            putchar(' ');
        }
        if (grid[i][j] == 0) {
            putchar(' ');
        } else {
            putint(grid[i][j]);
        }
        putchar(' ');
    }
    putchar('|');
    putchar('\n');
}
putchar('+');
for (var i = 0; i < 3; i += 1) {
    putchar('-');
    for (var j = 0; j < 3; j += 1) {
        putchar('-');
        putchar('-');
    }
    putchar('+');
}
putchar('\n');

// 前処理
arr emptycells[2][9 * 9];
var numempty = 0;
for (var row = 0; row < 9; row += 1) {
    for (var col = 0; col < 9; col += 1) {
        if (grid[row][col] == 0) {
            emptycells[0][numempty] = row;
            emptycells[1][numempty] = col;
            numempty += 1;
        }
    }
}

// メイン処理
arr triednumbers[9 * 9];
var k = 0;
while (k != 255 & k < numempty) {
    var row = emptycells[0][k];
    var col = emptycells[1][k];
    var found = 0;
    var num = triednumbers[k] + 1;
    while (num <= 9 & !found) {
        var safe = 1;
        var x = 0;
        while (x < 9 & safe) {
            if (grid[row][x] == num) {
                safe = 0;
            }
            x += 1;
        }
        x = 0;
        while (x < 9 & safe) {
            if (grid[x][col] == num) {
                safe = 0;
            }
            x += 1;
        }
        if (safe) {
            var startrow = row - row % 3;
            var startcol = col - col % 3;
            var i = 0;
            while (i < 3 & safe) {
                var j = 0;
                while (j < 3 & safe) {
                    if (grid[startrow + i][startcol + j] == num) {
                        safe = 0;
                    }
                    j += 1;
                }
                i += 1;
            }
        }
        if (safe) {
            grid[row][col] = num;
            triednumbers[k] = num;
            found = 1;
            k += 1;
        } else {
            num += 1;
        }
    }
    if (!found) {
        grid[row][col] = 0;
        triednumbers[k] = 0;
        k -= 1;
    }
}
// メイン処理ここまで

if (k == numempty) { // 解を発見
    // 解を表示
    for (var i = 0; i < 9; i += 1) {
        if (i % 3 == 0) {
            putchar('+');
            for (var j = 0; j < 3; j += 1) {
                putchar('-');
                for (var k = 0; k < 3; k += 1) {
                    putchar('-');
                    putchar('-');
                }
                putchar('+');
            }
            putchar('\n');
        }
        for (var j = 0; j < 9; j += 1) {
            if (j % 3 == 0) {
                putchar('|');
                putchar(' ');
            }
            if (grid[i][j] == 0) {
                putchar(' ');
            } else {
                putint(grid[i][j]);
            }
            putchar(' ');
        }
        putchar('|');
        putchar('\n');
    }
    putchar('+');
    for (var i = 0; i < 3; i += 1) {
        putchar('-');
        for (var j = 0; j < 3; j += 1) {
            putchar('-'); putchar('-');
        }
        putchar('+');
    }
    putchar('\n');
} else { // 解なし
    putchar('n');
    putchar('o');
    putchar(' ');
    putchar('s');
    putchar('o');
    putchar('l');
    putchar('u');
    putchar('t');
    putchar('i');
    putchar('o');
    putchar('n');
    putchar('\n');
}

ABC394 A

https://atcoder.jp/contests/abc394/submissions/63187799

ソースコード

for (var c = getchar(); c != '\n'; c = getchar()) {
    if (c == '2') {
        putchar(c);
    }
}
putchar('\n');

ABC394 B

https://atcoder.jp/contests/abc394/submissions/63188475

ソースコード

var n = getint();
arr strs[50][51];

for (var i = 0; i < n; i += 1) {
    var len = 0;
    for (var c = getchar(); c != '\n'; c = getchar()) {
        strs[i][len + 1] = c;
        len += 1;
    }
    strs[i][0] = len;
}

arr result[50][51];

for (var i = 0; i < n; i += 1) {
    var len = strs[i][0];
    result[len - 1][0] = len;
    for (var j = 0; j < len; j += 1) {
        result[len - 1][j + 1] = strs[i][j + 1];
    }
}

for (var i = 0; i < 50; i += 1) {
    var len = result[i][0];
    if (len - 1 == i) {
        for (var j = 0; j < len; j += 1) {
            putchar(result[i][j + 1]);
        }
    }
}
putchar('\n');

リポジトリ

https://github.com/void-hoge/brainfuck

記事リンク