シェルスクリプト（POSIX準拠）でBrainf**kインタプリタを作ってみた
次の記事の姉妹版です．Brainf**k（伏字使用，以下BFと略記）の詳細はWikipediaの記事を御参照下さい．
bcコマンドによる実装例の記事にてシェルスクリプトのみの文字変換のコメントをいただきましたので，それらを基に，全体をシェルスクリプト（POSIX準拠）で書き直した次第です．BusyBox for Windows等のシェルでも概ね動きますが，1文字入力,についてはsttyやddを用いているため未対応です．
実装例
次のGitHub Gistでも公開しています．
#!/bin/sh
while IFS= read L; do
T=$T$L
done < "$1"
L=0
while [ "$T" ]; do
case $T in
+*) export "C$L"=0 L=$((L+1));;
-*) export "C$L"=1 L=$((L+1));;
\>*) export "C$L"=2 L=$((L+1));;
\<*) export "C$L"=3 L=$((L+1));;
.*) export "C$L"=4 L=$((L+1));;
,*) export "C$L"=5 L=$((L+1));;
\[*) export "C$L"=6 L=$((L+1));;
\]*) export "C$L"=7 L=$((L+1));;
esac
T=${T#?}
done
P=0
while [ $P != 16384 ]; do
export "A$P"=0
P=$((P+1))
done
N=0
P=0
while [ $N != $L ]; do
case $((C$N)) in
0) export "A$P"=$((A$P+1));;
1) export "A$P"=$((A$P-1));;
2) P=$((P+1));;
3) P=$((P-1));;
4) printf "$(printf '\\%o' $((A$P)))";;
5) stty -icanon
D=$(dd bs=1 count=1 2>/dev/null)
export "A$P"=$(printf '%d' \'$D)
stty icanon;;
6) case $((A$P)) in
0) D=1
while [ $D != 0 ]; do
N=$((N+1))
case $((C$N)) in
6) D=$((D+1));;
7) D=$((D-1));;
esac
done;;
*) ;;
esac;;
7) case $((A$P)) in
0) ;;
*) D=1
while [ $D != 0 ]; do
N=$((N-1))
case $((C$N)) in
6) D=$((D-1));;
7) D=$((D+1));;
esac
done;;
esac;;
esac
N=$((N+1))
done
※Debian GNU/Linux 11のdash 0.5.11での実行確認
$ cat primes.bf
>++++[<++++++++>-]>++++++++[<++++++>-]<++.<.>+.<.>++.<.>++.<.>------..<.>.++.<.>--.++++++.<.>------.>+++[<+++>-]<-.<.>-------.+.<.>-.+++++++.<.>------.--.<.>++.++++.<.>---.---.<.>+++.-.<.>+.+++.<.>--.--.<.>++.++++.<.>---.-----.<.>+++++.+.<.>.------.<.>++++++.----.<.>++++.++.<.>-.-----.<.>+++++.+.<.>.--.>++++++++++.
$ dash bf-intp.sh primes.bf
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
コードの解説
冒頭では，引数で指定されたテキストファイルより各行を読み込み，変数Tに結合しています．
while IFS= read L; do
T=$T$L
done < "$1"
次のコードは，Tの先頭文字によって分岐処理を行い，+-><.,[]であればそれぞれを01234567とし，変数C$Lにexportを用いて設定したのち，変数Lの値（初期値0）を+1しています．これによって，疑似配列C[L]を実現してBFコードを格納しています．なお，01234567と数字にしているのは，その後のコード走査で参照しやすくするためです．また，T=${T#?}はTより先頭文字を削除しています．
L=0
while [ "$T" ]; do
case $T in
+*) export "C$L"=0 L=$((L+1));;
-*) export "C$L"=1 L=$((L+1));;
\>*) export "C$L"=2 L=$((L+1));;
\<*) export "C$L"=3 L=$((L+1));;
.*) export "C$L"=4 L=$((L+1));;
,*) export "C$L"=5 L=$((L+1));;
\[*) export "C$L"=6 L=$((L+1));;
\]*) export "C$L"=7 L=$((L+1));;
esac
T=${T#?}
done
この後，内部配列A[P]相当の初期化を上記C[L]相当と同じ要領で行っています．仕様では内部配列の要素は少なくとも30000個となっていますが，実行環境によってはこの初期化だけでも時間がかかることと，主要なBFサンプルコードがそこまで求めていないことから，さしあたり概ね半分の2^14=16384個の変数A$Pを0に初期化しています．
P=0
while [ $P != 16384 ]; do
export "A$P"=0
P=$((P+1))
done
次は，インタプリタ本体の冒頭です．BFコードの配列相当変数Cに対する添字はNを用い，BFコード読込時に使用した添字LにはBFコードの文字数が入っているため，プログラム停止判定に用いています．
N=0
P=0
while [ $N != $L ]; do
case $((C$N)) in
+-><に対応する処理は，疑似配列を用いていること以外はC言語等の場合と同じです．BFコード格納時と同じく，疑似配列である添字付き変数の値を増減する際にはexportを用い，変数単体の値を増減する際には単純に代入処理をしています．
0) export "A$P"=$((A$P+1));;
1) export "A$P"=$((A$P-1));;
2) P=$((P+1));;
3) P=$((P-1));;
.の出力処理は，printfを用いてA[P]相当内の数値を文字変換して出力しています．なお，フォーマット指定子で\\%oと8進数変換しているのは，printfやechoで文字コードを指定して文字を出力する際には，\に8進数または\xに16進数で指定する必要があり，ここでは8進数を用いて変換出力を行うためです．
4) printf "$(printf '\\%o' $((A$P)))";;
次は，シェルスクリプトで1文字のみをキー入力から読み込む,の処理です．UNIX系のターミナル制御ライブラリtermiosに基づくsttyやバイト単位で読み書きするddを用いています．いずれもPOSIX仕様のコマンドですが，シェルスクリプトの機能ではないため，UNIX系以外のシェル環境ではエラーとなります．なお，printfで指定している'（その前の\はエスケープ）はASCIIコードへの変換を示しています．
5) stty -icanon
D=$(dd bs=1 count=1 2>/dev/null)
export "A$P"=$(printf '%d' \'$D)
stty icanon;;
[]に対応する処理は+-><と同じく，疑似配列を用いていること以外はC言語等の場合と同じです．
6) case $((A$P)) in
0) D=1
while [ $D != 0 ]; do
N=$((N+1))
case $((C$N)) in
6) D=$((D+1));;
7) D=$((D-1));;
esac
done;;
*) ;;
esac;;
7) case $((A$P)) in
0) ;;
*) D=1
while [ $D != 0 ]; do
N=$((N-1))
case $((C$N)) in
6) D=$((D-1));;
7) D=$((D+1));;
esac
done;;
esac;;
参考までに，C言語およびPythonで記述した上記相当のコード例を次に示します．codes[c]がC[N]，array[p]がA[P]，nestがDに相当します．
switch(codes[c]) {
...
case '[':
if (array[p] == 0) {
int nest = 1;
while (nest != 0) {
c++;
if (codes[c] == '[') nest++;
if (codes[c] == ']') nest--;
}
}
break;
case ']':
if (array[p] != 0) {
int nest = 1;
while (nest != 0) {
c--;
if (codes[c] == ']') nest++;
if (codes[c] == '[') nest--;
}
}
break;
c0 = codes[c]
...
elif c0 == '[':
if array[p] == 0:
nest = 1
while nest != 0:
c += 1
if codes[c] == '[': nest += 1
if codes[c] == ']': nest -= 1
elif c0 == ']':
if array[p] != 0:
nest = 1
while nest != 0:
c -= 1
if codes[c] == ']': nest += 1
if codes[c] == '[': nest -= 1
備考
更新履歴
- 2023-01-23：初版公開
Discussion