Brainf*ck による言語処理系 第0回

本稿では Brainf*ck をターゲットとした自作高級言語のコンパイラを紹介します。

Brainf*ck はコンパイラがなるべく小さくなる言語として考案された言語です。たった 8 種類の命令しかありませんが、チューリング完全なので他の大抵の言語で計算できるものは計算できます。とはいえ、実用するために設計された言語と比べると可読性や記述性は劣り、大規模で実用的なプログラムを書くのは大変です。そこで、Brainf*ck をターゲットとしたコンパイラを作り、実用的なプログラムを簡単に得られるようにします。このような試みは無論他にも存在しますが、他のものよりかなり実用的になったので、その実行やコンパイラの仕組みについて紹介します。

言語のおおまかな特徴

• 式の値はすべて wrap-around する 8 ビット符号なし整数
• (任意次元の) 多次元配列
• インライン組み込み関数 (getchar, putchar, getint, putint)
• 各種演算 (四則演算、剰余算、比較、boolean、論理演算)
• if, while, for
• スコープ内変数 (制御文の body を抜けたときの変数の削除)

想定する処理系

• セルは uint8
• > 方向 (正方向) に十分に長い配列
• 負番地へのアクセスはエラー

例

例えば以下のコードは 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');
        }
    }
}

以下のような Brainf*ck のコードにコンパイルされます。

7516 bytes (改行込み)

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

実行すると以下のようになります。

実行結果

$ ./compiler.py factor.txt > factor.bf
$ bfi factor.bf
2 = 2
3 = 3
4 = 2 * 2
5 = 5
6 = 2 * 3
7 = 7
8 = 2 * 2 * 2
9 = 3 * 3
10 = 2 * 5
11 = 11
12 = 2 * 2 * 3
13 = 13
14 = 2 * 7
15 = 3 * 5
16 = 2 * 2 * 2 * 2
17 = 17
18 = 2 * 3 * 3
19 = 19
20 = 2 * 2 * 5
21 = 3 * 7
22 = 2 * 11
23 = 23
24 = 2 * 2 * 2 * 3
25 = 5 * 5
26 = 2 * 13
27 = 3 * 3 * 3
28 = 2 * 2 * 7
29 = 29
30 = 2 * 3 * 5
31 = 31
32 = 2 * 2 * 2 * 2 * 2
33 = 3 * 11
34 = 2 * 17
35 = 5 * 7
36 = 2 * 2 * 3 * 3
37 = 37
38 = 2 * 19
39 = 3 * 13
40 = 2 * 2 * 2 * 5
41 = 41
42 = 2 * 3 * 7
43 = 43
44 = 2 * 2 * 11
45 = 3 * 3 * 5
46 = 2 * 23
47 = 47
48 = 2 * 2 * 2 * 2 * 3
49 = 7 * 7
50 = 2 * 5 * 5
51 = 3 * 17
52 = 2 * 2 * 13
53 = 53
54 = 2 * 3 * 3 * 3
55 = 5 * 11
56 = 2 * 2 * 2 * 7
57 = 3 * 19
58 = 2 * 29
59 = 59
60 = 2 * 2 * 3 * 5
61 = 61
62 = 2 * 31
63 = 3 * 3 * 7
64 = 2 * 2 * 2 * 2 * 2 * 2
65 = 5 * 13
66 = 2 * 3 * 11
67 = 67
68 = 2 * 2 * 17
69 = 3 * 23
70 = 2 * 5 * 7
71 = 71
72 = 2 * 2 * 2 * 3 * 3
73 = 73
74 = 2 * 37
75 = 3 * 5 * 5
76 = 2 * 2 * 19
77 = 7 * 11
78 = 2 * 3 * 13
79 = 79
80 = 2 * 2 * 2 * 2 * 5
81 = 3 * 3 * 3 * 3
82 = 2 * 41
83 = 83
84 = 2 * 2 * 3 * 7
85 = 5 * 17
86 = 2 * 43
87 = 3 * 29
88 = 2 * 2 * 2 * 11
89 = 89
90 = 2 * 3 * 3 * 5
91 = 7 * 13
92 = 2 * 2 * 23
93 = 3 * 31
94 = 2 * 47
95 = 5 * 19
96 = 2 * 2 * 2 * 2 * 2 * 3
97 = 97
98 = 2 * 7 * 7
99 = 3 * 3 * 11
100 = 2 * 2 * 5 * 5
101 = 101
102 = 2 * 3 * 17
103 = 103
104 = 2 * 2 * 2 * 13
105 = 3 * 5 * 7
106 = 2 * 53
107 = 107
108 = 2 * 2 * 3 * 3 * 3
109 = 109
110 = 2 * 5 * 11
111 = 3 * 37
112 = 2 * 2 * 2 * 2 * 7
113 = 113
114 = 2 * 3 * 19
115 = 5 * 23
116 = 2 * 2 * 29
117 = 3 * 3 * 13
118 = 2 * 59
119 = 7 * 17
120 = 2 * 2 * 2 * 3 * 5
121 = 11 * 11
122 = 2 * 61
123 = 3 * 41
124 = 2 * 2 * 31
125 = 5 * 5 * 5
126 = 2 * 3 * 3 * 7
127 = 127
128 = 2 * 2 * 2 * 2 * 2 * 2 * 2
129 = 3 * 43
130 = 2 * 5 * 13
131 = 131
132 = 2 * 2 * 3 * 11
133 = 7 * 19
134 = 2 * 67
135 = 3 * 3 * 3 * 5
136 = 2 * 2 * 2 * 17
137 = 137
138 = 2 * 3 * 23
139 = 139
140 = 2 * 2 * 5 * 7
141 = 3 * 47
142 = 2 * 71
143 = 11 * 13
144 = 2 * 2 * 2 * 2 * 3 * 3
145 = 5 * 29
146 = 2 * 73
147 = 3 * 7 * 7
148 = 2 * 2 * 37
149 = 149
150 = 2 * 3 * 5 * 5
151 = 151
152 = 2 * 2 * 2 * 19
153 = 3 * 3 * 17
154 = 2 * 7 * 11
155 = 5 * 31
156 = 2 * 2 * 3 * 13
157 = 157
158 = 2 * 79
159 = 3 * 53
160 = 2 * 2 * 2 * 2 * 2 * 5
161 = 7 * 23
162 = 2 * 3 * 3 * 3 * 3
163 = 163
164 = 2 * 2 * 41
165 = 3 * 5 * 11
166 = 2 * 83
167 = 167
168 = 2 * 2 * 2 * 3 * 7
169 = 13 * 13
170 = 2 * 5 * 17
171 = 3 * 3 * 19
172 = 2 * 2 * 43
173 = 173
174 = 2 * 3 * 29
175 = 5 * 5 * 7
176 = 2 * 2 * 2 * 2 * 11
177 = 3 * 59
178 = 2 * 89
179 = 179
180 = 2 * 2 * 3 * 3 * 5
181 = 181
182 = 2 * 7 * 13
183 = 3 * 61
184 = 2 * 2 * 2 * 23
185 = 5 * 37
186 = 2 * 3 * 31
187 = 11 * 17
188 = 2 * 2 * 47
189 = 3 * 3 * 3 * 7
190 = 2 * 5 * 19
191 = 191
192 = 2 * 2 * 2 * 2 * 2 * 2 * 3
193 = 193
194 = 2 * 97
195 = 3 * 5 * 13
196 = 2 * 2 * 7 * 7
197 = 197
198 = 2 * 3 * 3 * 11
199 = 199
200 = 2 * 2 * 2 * 5 * 5
201 = 3 * 67
202 = 2 * 101
203 = 7 * 29
204 = 2 * 2 * 3 * 17
205 = 5 * 41
206 = 2 * 103
207 = 3 * 3 * 23
208 = 2 * 2 * 2 * 2 * 13
209 = 11 * 19
210 = 2 * 3 * 5 * 7
211 = 211
212 = 2 * 2 * 53
213 = 3 * 71
214 = 2 * 107
215 = 5 * 43
216 = 2 * 2 * 2 * 3 * 3 * 3
217 = 7 * 31
218 = 2 * 109
219 = 3 * 73
220 = 2 * 2 * 5 * 11
221 = 13 * 17
222 = 2 * 3 * 37
223 = 223
224 = 2 * 2 * 2 * 2 * 2 * 7
225 = 3 * 3 * 5 * 5
226 = 2 * 113
227 = 227
228 = 2 * 2 * 3 * 19
229 = 229
230 = 2 * 5 * 23
231 = 3 * 7 * 11
232 = 2 * 2 * 2 * 29
233 = 233
234 = 2 * 3 * 3 * 13
235 = 5 * 47
236 = 2 * 2 * 59
237 = 3 * 79
238 = 2 * 7 * 17
239 = 239
240 = 2 * 2 * 2 * 2 * 3 * 5
241 = 241
242 = 2 * 11 * 11
243 = 3 * 3 * 3 * 3 * 3
244 = 2 * 2 * 61
245 = 5 * 7 * 7
246 = 2 * 3 * 41
247 = 13 * 19
248 = 2 * 2 * 2 * 31
249 = 3 * 83
250 = 2 * 5 * 5 * 5
251 = 251
252 = 2 * 2 * 3 * 3 * 7
253 = 11 * 23
254 = 2 * 127
255 = 3 * 5 * 17
$

しくみ

このコンパイラは以下の図のような仕組みになっています。高級言語を与え、それを普通のアセンブリ程度の抽象度のスタックマシンコードに変換し、そのスタックマシンコードの各命令を Brainf*ck のコードにアセンブルします。なお、今回コンパイラと呼んでいるのは破線で示すシステム全体です。
このような仕組みにより、既存のコンパイラに関する知識が使える上、スタックマシンの各命令は非常にシンプルなため、ある程度簡単にコンパイラを作成できます。

上の素因数分解のコードをデバッグモードでコンパイルすると以下のようになります。

9349 bytes

[
for (var num = 2;(num != 0);num += 1) {
    arr factors[7];
    var div = 2;
    var count = 0;
    putint(num);
    putchar(32);
    putchar(61);
    putchar(32);
    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(32);
            putchar(42);
            putchar(32);
        }else {
            putchar(10);
        }
    }
}
]
lc 0: [-]>
lc 2: [-]++>
sv 0: <<[-]>[-<+>]
push multi dim array (7): [-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>[-]>
lc 0: [-]>
lc 0: [-]>
lv 0: >[-]<<<<<<<<<<<<<<<[->>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<]>>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>]
lc 0: [-]>
neq: <[-<->][-]<[[-]>+<]>[-<+>]
beginwhile: <[[-]
lc 2: [-]++>
sv 12: <<<[-]>>[-<<+>>]
lc 0: [-]>
sv 13: <<[-]>[-<+>]
lv 0: >[-]<<<<<<<<<<<<<<<[->>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<]>>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>]
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lc 100: [-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
ge: [-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]
beginif: +<[[-]>->
lv 14: >[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
lc 100: [-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
div: <<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<+<[-<->>>+>+<<<]>>[-<<+>>]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<<[-]<[-]>>[-<<+>>]<
lc 48: [-]++++++++++++++++++++++++++++++++++++++++++++++++>
add: <[-<+>]
putc: <.[-]
beginelse: [-]<[-]<]>[->
endif: [-]<]<
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lc 10: [-]++++++++++>
ge: [-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]
beginif: +<[[-]>->
lv 14: >[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
lc 100: [-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
mod: <<[->>+>+<<<]>>>[-<<<+>>>]<<[->>+>+<<<]>>>[-<<<+>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<[-<->>+>+<<]>[-<+>]<<[->>+>>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<[-]
lc 10: [-]++++++++++>
div: <<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<+<[-<->>>+>+<<<]>>[-<<+>>]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<<[-]<[-]>>[-<<+>>]<
lc 48: [-]++++++++++++++++++++++++++++++++++++++++++++++++>
add: <[-<+>]
putc: <.[-]
beginelse: [-]<[-]<]>[->
endif: [-]<]<
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lc 10: [-]++++++++++>
mod: <<[->>+>+<<<]>>>[-<<<+>>>]<<[->>+>+<<<]>>>[-<<<+>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<[-<->>+>+<<]>[-<+>]<<[->>+>>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<[-]
lc 48: [-]++++++++++++++++++++++++++++++++++++++++++++++++>
add: <[-<+>]
putc: <.[-]
pop 1: <[-]
lc 32: [-]++++++++++++++++++++++++++++++++>
putc: <.[-]
lc 61: [-]+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
putc: <.[-]
lc 32: [-]++++++++++++++++++++++++++++++++>
putc: <.[-]
lc 0: [-]>
lv 0: >[-]<<<<<<<<<<<<<<<<[->>>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<<]>>>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>>]
sv 14: <<[-]>[-<+>]
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lc 1: [-]+>
neq: <[-<->][-]<[[-]>+<]>[-<+>]
beginwhile: <[[-]
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lv 12: >[-]<<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]
mod: <<[->>+>+<<<]>>>[-<<<+>>>]<<[->>+>+<<<]>>>[-<<<+>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<[-<->>+>+<<]>[-<+>]<<[->>+>>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<[-]
beginif: +<[[-]>->
lv 12: >[-]<<<<<<[->>>>>+>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]
lc 1: [-]+>
add: <[-<+>]
sv 12: <<<<<<[-]>>>>>[-<<<<<+>>>>>]
beginelse: [-]<[-]<]>[->
lv 14: >[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
lv 12: >[-]<<<<<<<[->>>>>>+>+<<<<<<<]>>>>>>>[-<<<<<<<+>>>>>>>]
div: <<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<+<[-<->>>+>+<<<]>>[-<<+>>]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<<[-]<[-]>>[-<<+>>]<
sv 14: <<<<[-]>>>[-<<<+>>>]
lv 12: >[-]<<<<<<[->>>>>+>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]
lv 13: >[-]<<<<<<[->>>>>+>+<<<<<<]>>>>>>[-<<<<<<+>>>>>>]
mds 12 (7): <[-<<<<<<<<+>>>>>>>>]<[-<<<<<<<<+>>>>>>>>]<<<<<<<[<<<[->>>>+<<<<]>[-<+>]<+>>[-<+>]>-[-<+>]<]<<<[-]>>[-<<+>>]<[->+<]>[->>>[-<<<<+>>>>]<<<[->+<]>]>>>>>>>>
lv 13: >[-]<<<<<[->>>>+>+<<<<<]>>>>>[-<<<<<+>>>>>]
lc 1: [-]+>
add: <[-<+>]
sv 13: <<<<<[-]>>>>[-<<<<+>>>>]
endif: [-]<]<
pop 0: 
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lc 1: [-]+>
neq: <[-<->][-]<[[-]>+<]>[-<+>]
endwhile: <]
pop 1: <[-]
lc 0: [-]>
lc 0: [-]>
sv 14: <<[-]>[-<+>]
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lv 13: >[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
lt: [-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>]
beginwhile: <[[-]
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
mdl 12 (7): <[-<<<<<+>>>>>]<<<<<[-<<<[->>>>+<<<<]>>[-<+>]<+>>[-<+>]<]<<<[->+>>+<<<]>[-<+>]>[->>>[-<<<<+>>>>]<<[->+<]<[->+<]>]>>><<[->>>>>+<<<<<]>>>>>>
lv 15: >[-]<<[->+>+<<]>>[-<<+>>]
lc 100: [-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
ge: [-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]
beginif: +<[[-]>->
lv 15: >[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
lc 100: [-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
div: <<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<+<[-<->>>+>+<<<]>>[-<<+>>]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<<[-]<[-]>>[-<<+>>]<
lc 48: [-]++++++++++++++++++++++++++++++++++++++++++++++++>
add: <[-<+>]
putc: <.[-]
beginelse: [-]<[-]<]>[->
endif: [-]<]<
lv 15: >[-]<<[->+>+<<]>>[-<<+>>]
lc 10: [-]++++++++++>
ge: [-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]
beginif: +<[[-]>->
lv 15: >[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
lc 100: [-]++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>
mod: <<[->>+>+<<<]>>>[-<<<+>>>]<<[->>+>+<<<]>>>[-<<<+>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<[-<->>+>+<<]>[-<+>]<<[->>+>>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<[-]
lc 10: [-]++++++++++>
div: <<[->>>+>+<<<<]>>>>[-<<<<+>>>>]<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<+<[-<->>>+>+<<<]>>[-<<+>>]<<<[->>>+>>+<<<<<]>>>>>[-<<<<<+>>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<<[-]<[-]>>[-<<+>>]<
lc 48: [-]++++++++++++++++++++++++++++++++++++++++++++++++>
add: <[-<+>]
putc: <.[-]
beginelse: [-]<[-]<]>[->
endif: [-]<]<
lv 15: >[-]<<[->+>+<<]>>[-<<+>>]
lc 10: [-]++++++++++>
mod: <<[->>+>+<<<]>>>[-<<<+>>>]<<[->>+>+<<<]>>>[-<<<+>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<[-<[-<->>+>+<<]>[-<+>]<<[->>+>>+<<<<]>>>>[-<<<<+>>>>][-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>][-]+<[[-]>-<]>[-<+>]<]<[-]
lc 48: [-]++++++++++++++++++++++++++++++++++++++++++++++++>
add: <[-<+>]
putc: <.[-]
pop 1: <[-]
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lc 1: [-]+>
add: <[-<+>]
lv 13: >[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
neq: <[-<->][-]<[[-]>+<]>[-<+>]
beginif: +<[[-]>->
lc 32: [-]++++++++++++++++++++++++++++++++>
putc: <.[-]
lc 42: [-]++++++++++++++++++++++++++++++++++++++++++>
putc: <.[-]
lc 32: [-]++++++++++++++++++++++++++++++++>
putc: <.[-]
beginelse: [-]<[-]<]>[->
lc 10: [-]++++++++++>
putc: <.[-]
endif: [-]<]<
pop 0: 
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lc 1: [-]+>
add: <[-<+>]
sv 14: <<[-]>[-<+>]
lv 14: >[-]<<[->+>+<<]>>[-<<+>>]
lv 13: >[-]<<<<[->>>+>+<<<<]>>>>[-<<<<+>>>>]
lt: [-]>[-]+>[-]+>[-]<[<<<<[>]>>>[->]<<<<-<->>>>]<[-]<<+<+[-]>[[-]<+>]
endwhile: <]
pop 1: <[-]
lv 0: >[-]<<<<<<<<<<<<<<<[->>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<]>>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>]
lc 1: [-]+>
add: <[-<+>]
sv 0: <<<<<<<<<<<<<<<[-]>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<+>>>>>>>>>>>>>>]
lv 0: >[-]<<<<<<<<<<<<<<<[->>>>>>>>>>>>>>+>+<<<<<<<<<<<<<<<]>>>>>>>>>>>>>>>[-<<<<<<<<<<<<<<<+>>>>>>>>>>>>>>>]
lc 0: [-]>
neq: <[-<->][-]<[[-]>+<]>[-<+>]
endwhile: <]
pop 14: <[-]<[-]<[-]<[-]<[-]<[-]<[-]<[-]<[-]<[-]<[-]<[-]<[-]<[-]

各行はスタックマシンの命令を表しており、行頭のコメントでその行が何をやっているかを示しています。

スタックマシン

スタックマシンはメモリがスタックになっている形式の計算機です。
スタックトップをポップしてその値に対して演算を行い、その結果をスタックにプッシュすることを繰り返します。
例えば、(2 * 3) + 4 は以下のように計算できます。

計算過程

1: 2 をプッシュ
2: 3 をプッシュ
3: スタックトップの 2 数をポップして乗算してプッシュ
4: 4 をプッシュ
5: スタックトップの 2 数をポップして加算してプッシュ

まず、スタックには何も積まれていない状態ではじめます。

addr	0	1	2	3
stack

1 行目ではスタックトップに 2 を積みます。

addr	0	1	2	3
stack	2

2 行目では 3 を積みます。

addr	0	1	2	3
stack	2	3

3 行目では 2 つをポップして乗算して結果をプッシュします。

addr	0	1	2	3
stack	6

さらに 4 行目で 4 を積みます。

addr	0	1	2	3
stack	6	4

5 行目の加算命令を実行すると以下のようになります。

addr	0	1	2	3
stack	10

Brainf*ck でこのようなスタックマシンを実装し、一旦スタックマシン向けのアセンブリを経由することにより、間接的に高級言語から Brainf*ck への変換を実現します。

スタックは Brainf*ck のデータ配列をそのまま用い、命令実行中を除きデータポインタはスタックトップの 1 つ上を指すものとします。

Brainf*ck の根本的な制約

Brainf*ck でスタックマシンを実装にするにあたり最初に直面する根本的な制約が、相対アドレッシングしかできない という点です。

今、2 番地に a という変数が入っているとします。

addr	0	1	2
mem			a

コンパイラはこのことを変数表に記録しています。

variable	pos
a	2

通常、スタックマシンでは直接絶対番地を指定してデータにアクセスする命令が存在します。コンパイラは変数表に登録された変数の番地情報をもとにスタックトップに変数 a をロードすることができます。

しかし、Brainf*ck ではデータポインタを移動するために使えるのは < と > のみであり、基本的には「現在のポインタ位置から定数個離れた位置に移動する」ことしかできません。

そのため、コンパイラは現在のデータポインタがどこに存在するのかを常に追跡しながらコード生成を行う必要があります。以下の状態でデータポインタは 4 番地にあり、コンパイラもそのことを認識しているため、a をロードするには 2 個ポインタを左に動かす必要があることをコンパイラは認識できます。

addr	0	1	2	3	4
mem			a		dp

しかし、以下のようにデータポインタの位置が静的に追跡できなくなると、何個ポインタを進めれば a にたどり着くのかわからないため、もはや変数表を用いて変数ににアクセスすることはできません。

addr	0	1	2	3	4	...	???
mem			a				dp

このような状況を生み出すコードの例として以下が挙げられます。これを実行すると標準入力が \0 の場合 0 番地、そうでない場合は 1 番地で停止します。これではデータポインタの位置が動的に変わり、変数表を用いて移動量を計算できなくなります。

,[>]

このような Brainf*ck のコンパイラにおいて、データポインタからの相対位置を使うために、実行中のデータポインタ位置を全て把握する必要があります。コンパイラがデータポインタの位置を見失う、すなわち生成時にポインタ位置が決まらないような命令は許されません。

まとめ

• スタックマシンを経由して高級言語を Brainf*ck にコンパイルする
• 動的にデータポインタ位置が決まるような命令は実装できない

次回以降の記事で、このスタックマシンに実装されている命令や、このコンパイラの仕組みについてもう少し詳しく解説していきます。

リポジトリ

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

記事リンク

• 第 0 回: Brainf*ck による言語処理系
• 第 1 回: 値のロードとストア
• 第 2 回: 加算, 減算, 乗算
• 第 3 回: bool化, 等値比較
• 第 4 回: 非破壊分岐, 比較, 除算, 剰余算
• 第 5 回: while, if, スコープ内変数
• 第 6 回: 配列, 多次元配列
• 第 7 回: コンパイラと言語仕様