Brainfuckのアセンブラー

ある寒い5月1日は退屈でしたが、このすばらしい言語、Brainfuckの勉強を始めることにしました。

通訳は すでに 何 度も Habréに 掲載さ れ ています。

しかし、別のインタープリターを作成するのではなく、言語自体とそのアルゴリズムをもう少し深く研究したかったのです。 したがって、brainfuckの高レベル言語のコンパイラをモグラ塚から作ることが決定されました 。

しかし、本当の頭脳はすぐに始まりました。ifステートメントの欠如、セルへのランダムアクセスの欠如、その他の多くの問題がすぐに思いつきました。 高水準言語でしばらく待たなければならず、まずは、高水準言語がコンパイルされるアセンブラーを作成しました。

catでのアセンブラーの実装について。

主な部品の実装

便宜上、テープはいくつかの部分に分割されました。

• 登録
• スタック
• 一時セルとフラグセル
• 残りのメモリ-配列と文字列の保存に使用

トランスレータは、ゼロで満たされたテープのゼロセルでプログラムが開始されると想定します。 テープをループする必要があります。

登録

これは、アセンブラーの最も重要な部分です。 ほとんどの場合、相互作用する必要があるのは彼らです。 あなたはレジスターに数字を入れることができます（brainfuck'eの数字は255に制限されていることに注意してください）、それらに他のレジスターの数字と値を追加し、他のレジスターの数字と値を減算し、他のレジスターで乗算し、他のレジスターで除算して互いに比較することができます。

トランスレータは4つのレジスタを使用します：ax、bx、cx、dx-x86アセンブラとの類推により、それぞれが単一のメモリセルで表されます。

例：

mov ax 5 //   ax 5 mov bx 6 //   bx 6 sub ax bx //   ax 255 mov cx 12 mov dx 2 mul cx dx //  cx  24 mov dx 10 div cx dx //   :  cx - 2,  dx - 4
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

スタック

ゼロセルの左側で、スタックが始まります。 ほぼsi-lineの原則に基づいて保存され、どのようなサイズでもかまいませんが、メモリがループし、スタックに配置された非常に多くの要素が他のデータを損なう可能性があることを覚えておく必要があります。

スタックに値を追加したり、スタックから値を削除したりするために、次のようなプッシュコマンドとポップコマンドがあります。

 push ax push 5 pop bx pop cx
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、Cライン形式のストレージには1つの欠点があります。ゼロはスタックの最上部のインジケータとして機能するため、スタックにゼロを置くことはできません。 もちろん、通常のスタックを整理することはできましたが、その長さは256要素に制限されていました。

一時セルとフラグセル

一時的なセルは、複雑な操作の中間計算に使用されます。 比較操作では3つのフラグセルが使用されますが、これについては以下で詳しく説明します。

配列

配列は、インデックスによってアクセスできるセルの範囲です。

 array test 10 //    test    set test 0 42 //       42 get test 0 ax //   ax   
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ところで、インデックスは、たとえばユーザー入力を含むレジスタにすることができますが、255を超えるインデックスを持つ要素にアクセスすることはできません。

行

文字列はstringキーワードで宣言されます：

 string hello "Hello, World!" //   hello puts hello //  
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

行は配列のセクションに配置され、プログラムの起動時に初期化されます。

文字列は配列のように扱うことができます：

 get hello 0 ax put ax //  'H'
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

基本構造

入出力

3つのI / O操作があります。

 take ax //    ax    put ax //  ,    ax puts str //     str
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ところで、putsコマンドは、通常の配列（最初のゼロまで）を出力できます。

サイクル構成

原則として、アセンブラージャンプも編成できますが、これはややhemoであるため、サイクルはBASICサイクルに似ています。

 while ax //  while      // do smth. endwhile
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このループは、axレジスタがゼロになるまで何かをします。

比較

比較はアセンブラースタイルで行われます。 何かを比較するには、cmpコマンドをレジスタに適用する必要があります。

 mov ax 2 mov bx 1 cmp ax bx
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このコマンドの後、フラグセルの値が変更されます。 それらの3つがあります：平等、それ以上。 最初のレジスタが2番目のレジスタと等しい場合、等値フラグはゼロに設定され、1番目のレジスタが小さい場合、2番目のフラグはゼロに設定され、大きい場合は3番目に設定されます。

比較結果は次のように使用できます。

 cmp ax bx //          ne //   //   ,     end nl //   // do end ng //   // do end eq //  // do end lt //  // do end gt //  // do end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

おわりに

アセンブラは単純な構文で作成されており、プログラムを作成することはできますが、自動生成を目的としています。 翻訳者はRubyで書かれており、 こちらから入手できます 。 そこで、プログラムの例を見て、独自のプログラムを書くことができます。

便利なリンク

Brainfuckのアルゴリズム -そこから乗算と除算のアルゴリズムを使用しました。



BFDevは便利なBrainfuck-IDEであり、すべてのプログラムがテストされています。



BrainFixは、 brainfuckで放送される高レベル言語です。 そこから、コンパイル時に不明なインデックスを持つ配列要素にアクセスするためのアルゴリズムが採用されました。