タスク概要

Brainfuck の処理系を作る。

Brainfuck は非常に小さな言語で、その仕様は Rosetta code のページや Wikipedia にも書いてある。それによるとプログラムコードは {'>', '<', '+', '-', '.', ',', '[', ']'} のみで構成され、チューリング完全、らしい。

方針

以下の順序で処理を行う。

Brainfuck のソースをファイルから読み込む
命令列にコンパイル
実行

f:id:mtXTJocj:20190506194524p:plain

Brainfuck のソースをファイルから読み込む

コマンドラインで指定したファイルの内容を一度にメモリ上に読みこむ。

    let mut buf = String::new();                                                  
    match File::open(&args[1]) {                                              
        Ok(mut f) => {                                                        
            f.read_to_string(&mut buf).expect("cannot read file.");           
        }                                                                     
        Err(e) => {                                                           
            println!("{}", e);                                                
            return;                                                           
        }                                                                     
    }

命令列にコンパイル

通常、言語処理系を作るとなると、まず lexcal analyzer を用いてソースの文字列をトークン列に変換することから始める。
ところが Brainfuck の場合、全ての構成要素が 1 文字からなっているため、1 文字 = 1 トークンという関係が成立し、1 文字ずつ読み込むことがほぼそのまま lexcal analysis になる。
唯一異なる点はコメントで、前述の 8 文字以外の文字は全てコメントになる。

そして、Brainfuck は 1 トークン(1 文字)が 1 命令に対応しているため、これもそのまま命令列にすることができる。

今回は enum で命令を定義しているため、トークンをこの enum に変換することがコンパイルの作業となる。対応は以下の通り。

トークン	命令
>	IncrementPointer
<	DecrementPointer
+	IncrementValue
-	DecrementValue
.	Output
,	Input
[	BranchIfZero(usize)
]	BranchIfNotZero(usize)

表にないトークン(文字)が現れた場合にはコメントとみなし読み飛ばせば良い。
シンプルな一対一対応で、説明する点といったら Branch に関する 2 命令のみで十分だと思う。この 2 命令は条件に応じて分岐するため、分岐先を usize の形で持っておく必要がある。

上記の対応に従って一文字ずつそのまま対応する enum に置き換える。ただし、分岐命令に関してはその分岐先を調べなくてはならない。要は '[' と ']' の対応を取ることになる。
カッコの対応といえばスタックだ。'[' が出てきたら、その場所をスタックに push する。']' が出てきたらスタックから pop する。これで ']' が出現した時に対応する '[' の場所が分かる。

            '[' => {                                                            
                stack.push(program.len());                           
                                  [f:id:mtXTJocj:20190506194524p:plain] //略                                
            }                                                                   
            ']' => {                                                            
                let dst = stack.pop().expect("']' appeared before '['");        
                                  //略
                program.push(Instruction::BranchIfNotZero(dst));                
            }

program は Vec で、分岐先の指定にはこの Vec のインデックスを用いる。なので、

program.len()

がその場所にあたる。

一方、'[' が出現した時点ではまだ対応する ']' は分からず、']' が出現した時にはじめて分岐先を知ることができる。なので、最初は仮の命令(今回は BranchIfZero(0))を配置しておき、']' が現れた時に書き換える。

            '[' => {                                                            
                                 //略                                  
                program.push(Instruction::BranchIfZero(0));                     
            }                                                                   
            ']' => {                                                            
                                 //略   
                program[dst] = Instruction::BranchIfZero(program.len());        
                                 //略     
            }

結局、ここでやっていることといえばコメントの削除と分岐先の計算くらいだね。

実行

命令列が得られたら、あとは先頭から順に実行していくだけ。本当にそのままなので execute() を見れば分かると思う。

余談

Brainfuck に関しては名前とおおよそのところしか知らなかった。そのせいか、Rosetta code にある Brainfuck の説明でチューリングマシンに似ているという記述を読んだ時に、命令列もデータと一緒にメモリ上に置いて実行時に書き換えられるものだと思ってしまった。

mtXTJocj’s blog

Execute Brain****

タスク概要

方針

Brainfuck のソースをファイルから読み込む

命令列にコンパイル

実行

余談