Brainf*ck による言語処理系 第5回 〜while, if, スコープ内変数〜

今回は演算ではなく、制御に関する命令を実装します。

• begin_while, end_while
  • スタックトップの値を評価し、0 ならば begin_while から end_while までを実行
  • 実行終了後に再びスタックトップの値を評価し、begin_while に戻る
• begin_if, begin_else, end_if
  • スタックトップの値を評価し、0 ならば begin_else から end_if までを実行、0 以外ならば begin_if から begin_else までを実行
• pop <imm>
  • <imm> 個の領域を配列から削除しデータポインタを <imm> 個左に動かす

while

brainfuck の [] は while と似た制御構造ですが、コンパイラを作るにあたってそのまま使うと以下のような不都合があります。

• [] の前後でデータポインタの位置が変わってはいけない
• [] の対応が取れていなければならない

特に、前者が保証されない場合、while の実行回数に応じてデータポインタ位置が変わってしまい、コンパイラがデータポインタ位置を見失う原因になります。

これを、スタックマシンのアセンブラで保証します。

def begin_while(self):
    assert 0 < self.dp
    self.controlstack += [('while', self.dp)]
    code = '<[[-]'
    self.dp -= 1
    return code

def end_while(self, debug=False):
    assert self.controlstack
    assert self.controlstack[-1][0] == 'while'
    assert self.controlstack[-1][1] == self.dp
    _, dp = self.controlstack.pop()
    code = '<]'
    self.dp = dp - 1
    return code

アセンブラに controlstack というフィールドを追加し、現在のコンテキストを保持します。
また、controlstack で while 開始時のデータポインタ位置を保持し、end_while でチェックすることにより while 前後でデータポインタの位置が変わっていないことを保証します。

以下の疑似コードをコンパイルしたとき、生成される Brainf*ck コードは以下のようになります。

while cond:
    body

push cond
<[[-] ; begin_while
body
push cond
<]    ; end_while

評価に用いた値は破壊され、そこに再び条件を積むことになります。

if

if は必ず else 句付きで使用するものとします。else 句なしの if を使いたいときは単に begin_else の直後に end_if を使用します。

def begin_if(self, debug=False):
    assert 0 < self.dp
    self.controlstack += [('if', self.dp)]
    code = '+<[[-]>->'
    self.dp += 1
    return code + '\n' if debug else code

def begin_else(self, debug=False):
    assert self.controlstack
    assert self.controlstack[-1][0] == 'if'
    assert self.controlstack[-1][1] == self.dp - 1
    _, dp = self.controlstack.pop()
    self.controlstack += [('else', dp)]
    code = '<<]>[->'
    self.dp = dp + 1
    return code + '\n' if debug else code

def end_if(self):
    assert self.controlstack
    assert self.controlstack[-1][0] == 'else'
    assert self.controlstack[-1][1] == self.dp - 1
    _, dp = self.controlstack.pop()
    code = '<]<'
    self.dp = dp - 1
    return code

以下の疑似コードをコンパイルしたとき、生成される Brainf*ck コードは以下のようになります。

if cond:
    then_
else:
    else_

push cond
+<[[-]>-< ; begin_if
then_
<<]>[->   ; begin_else
else_
<]<       ; end_if

else のために、cond の隣に一時領域を設け、1 で初期化します。then 句の最初で一時領域をクリアし、else 句では一時領域を評価します。

スコープ内変数

前述したとおり、while や if では [] の前後でデータポインタが同じ位置である必要があります。即ち、while や if の内部で新しい変数を作ることはできず、新たな変数を作る場合には while や if の前に積んでおく必要があります。

以下のようなコードをコンパイルすることを考えます。

var cond;
while (cond) {
    var a = getint();
    cond = a;
}

このとき、while に入ったときのメモリレイアウトは以下のようになります。

addr	0	1	2	...
data	var cond	var a	cond	...

while の body のコード生成の前に、新たな変数を宣言している部分を探索して、予め領域の確保と変数表への登録を行っておきます。

以下はコンパイラ本体の while のコード生成を行うクラスです。

このメソッドでは以下のことを行います。

• body のスコープ変数を探索、確保、変数表に登録
• 条件をプッシュ
• begin_while
• body を生成
• end_while
• 再び条件をプッシュ
• end_while
• スコープ変数を削除

class StWhile(Statement):
    def __init__(self, cond, body):
        self.cond = cond
        self.body = body

    def string(self, level):
        code = f'{indent(level)}while ({self.cond}) {{\n'
        for st in self.body:
            code += st.string(level + 1) + '\n'
        code += f'{indent(level)}}}'
        return code

    def codegen(self, sm, tables, debug): # while のコード生成を行うメソッド, sm はスタックマシンアセンブラのインスタンス, tables は変数表
        base = sm.dp
        lvars = {} # ローカル変数表
        code = ''
        for st in self.body: # while のスコープ変数を宣言している部分を探索
            if isinstance(st, StInitVariable) or isinstance(st, StInitArray):
                code += st.allocate(sm, tables + [lvars], debug) # 領域の確保と変数表への登録
        size = sm.dp - base # while スコープ変数の合計サイズ
        code += self.cond.codegen(sm, tables + [lvars], debug) # 条件を積む
        code += sm.begin_while(debug)
        for st in self.body: # body の生成
            code += st.codegen(sm, tables + [lvars], debug)
        code += self.cond.codegen(sm, tables + [lvars], debug) # 再び条件を積む
        code += sm.end_while(debug)
        code += sm.pop(size, debug) # スコープ変数を削除
        return code

スコープ変数の削除にあたって、指定したサイズだけ領域をクリアしてデータポインタを左に動かす pop 命令を実装しています。以下のように実装できます。

def pop(self, size):
    self.dp -= size
    return '<[-]' * size

まとめ

今回は while や if といった制御構造と、スコープ変数の扱いについて述べました。

• begin_while, end_while
• begin_if, begin_else, end_if
• pop <imm>

次回は配列と多次元配列について解説します。

リポジトリ

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

記事リンク

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