圖片來源：google 搜索

最近在 Codewars上做練習(xí)辣往，某道題的內(nèi)容是實(shí)現(xiàn)一個(gè) brainFuck（簡稱BF語言） 解釋器（c/python/js等等均可）教硫。動(dòng)手實(shí)踐的過程還是很有趣的涧尿，中間也遇到了各種各樣的問題百新，最終通過測試，代碼也比較接近目前的 JS 高分 solution矮瘟。這篇文章準(zhǔn)備聊聊相關(guān)的一些知識(shí)和實(shí)現(xiàn)的細(xì)節(jié)瞳脓。

“腦洞大開”的語言 —— BF 簡介

BrainFuck（后文以簡寫B(tài)F指代），單是名字就很容易讓人腦洞大開澈侠，有種不可描述的“哲學(xué)”韻味劫侧。所以如果你忍不住 google 一下相關(guān)圖片的話，你會(huì)可能搜到類似下面的圖片：

圖片來源：google 搜索

畫面是不是已經(jīng)很生動(dòng)了哨啃？

BF 字面上的含義已經(jīng)暗示了這是一種不太直觀和容易閱讀的語言烧栋，當(dāng)然，在當(dāng)下也不會(huì)是一種通用語言拳球。她屬于 Esolang（全稱 Esoteric programming language审姓，直譯：深?yuàn)W的編程語言） 的范疇。

BF誕生于上世紀(jì)30年代祝峻，曾運(yùn)用于早期的 PC（Amiga）魔吐，想詳細(xì)了解的童鞋可以瀏覽 維基百科。

BF 在當(dāng)下有什么應(yīng)用場景呢莱找？

我想酬姆，對(duì)一個(gè)吃瓜群眾來說，了解了它奥溺，對(duì)寫作 逼格 和 腦力 的提升是很有用的辞色。BF 具有極簡主義（搞設(shè)計(jì)的童鞋的不妨了解下下）和功能齊全（圖靈完全）的特點(diǎn)，旨在為用戶帶來困惑和挑戰(zhàn)浮定，豐富勞動(dòng)人民的業(yè)余生活相满。

8 種運(yùn)算符及其操作

BF 作為一種極簡的計(jì)算機(jī)語言，僅有8種運(yùn)算符桦卒，分別為: < > + - , . [ ]立美，其功能對(duì)照如下表所示：

BF基于一個(gè)簡單的機(jī)器模型琳省，除了八個(gè)指令迎吵，這個(gè)機(jī)器還包括：一個(gè)以字節(jié)為單位躲撰、被初始化為零的數(shù)組、一個(gè)指向該數(shù)組的指針(初始時(shí)指向數(shù)組的第一個(gè)字節(jié))击费、以及用于輸入輸出的兩個(gè)字節(jié)流拢蛋。

對(duì) BF 比較有意思的比擬可以是這樣的：

1. 如果把機(jī)器內(nèi)存看成是一個(gè)無限長的“小火車”（類似于Array或List的數(shù)據(jù)結(jié)構(gòu)）,每個(gè)車廂（存儲(chǔ)單元）里面的貨物默認(rèn)都是數(shù)字 0，列車上僅有一個(gè)列車員（數(shù)據(jù)指針）蔫巩；
2. <> 相當(dāng)于列車員在車廂間進(jìn)行移動(dòng)谆棱，只有當(dāng)列車員在某節(jié)車廂時(shí)，才能對(duì)車廂的貨物進(jìn)行操作圆仔；
3. +- 相當(dāng)于列車員對(duì)當(dāng)前所在車廂的貨物進(jìn)行增減垃瞧；
4. , 相當(dāng)于列車在裝貨，列車員將當(dāng)前所在車廂的貨物替換為貨運(yùn)站輸入的單批次貨物（一個(gè)字符的ASCII碼）坪郭；
5. . 會(huì)將當(dāng)前車廂里的貨物名稱（單個(gè)字符）輸出來个从；
6. [] 相當(dāng)于列車員在滿足條件的兩節(jié)車廂間來回移動(dòng)；

這里要注意的是歪沃，數(shù)組的每個(gè)單元都是一個(gè)字節(jié)大朽氯瘛；- 命令允許溢出沪曙，它可以用 255 個(gè) + 命令來代替奕污。例如，當(dāng)某個(gè)存儲(chǔ)單元的值為 255 時(shí)液走，其執(zhí)行指令 + 的結(jié)果為 0碳默。類似的， 0 執(zhí)行指令 - 的結(jié)果為 255.

與通用語言的類比

據(jù)此育灸，BF的運(yùn)算符與通用語言的類比如下（以C語言為例）：

BF 解釋器的 JS 函數(shù)實(shí)現(xiàn)

代碼奉上：

function brainLuck(code, input) {             // @1
  const inputChars = input.split('');         // @2

  const codes = code.split('');               // @3
  let codeIdx = 0;

  const arr = [];                             // @4
  let arrIdx = 0;
  let outputStr = '';                         // @5

  while (codeIdx < code.length) {             // @6
    const ops = codes[codeIdx];

    const handleLeftBracket = () => {         // @7
      if (~~arr[arrIdx] === 0) {
        let cnt = 1;

        while (cnt) {
          codeIdx++;
          if (codes[codeIdx] === '[') {
            cnt += 1;
          }
          if (codes[codeIdx] === ']') {
            cnt -= 1;
          }
        }
      }
    };

    const handleRightBracket = () => {        // @8
      if (~~arr[arrIdx] !== 0) {
        let cnt = 1;

        while (cnt) {
          codeIdx--;
          if (codes[codeIdx] === ']') {
            cnt += 1;
          }
          if (codes[codeIdx] === '[') {
            cnt -= 1;
          }
        }
      }
    };

    switch (ops) {                            // @9
      case '>':
        arrIdx += 1;
        break;
      case '<':
        arrIdx -= 1;
        break;
      case '+':
        arr[arrIdx] = (~~arr[arrIdx] + 1) % 256;
        break;
      case '-':
        arr[arrIdx] = (~~arr[arrIdx] || 256) - 1;
        break;
      case ',':
        const iptChar = inputChars.shift();
        arr[arrIdx] = iptChar ? iptChar.charCodeAt(0) : arr[arrIdx];
        break;
      case '.':
        outputStr += String.fromCharCode(arr[arrIdx]);
        break;
      case '[':
        handleLeftBracket();
        break;
      case ']':
        handleRightBracket();
        break;
    }

    codeIdx++;                               // @10
  }

  return outputStr;                          // @11
}

實(shí)現(xiàn)思路闡述（與代碼中注釋的序號(hào)對(duì)應(yīng)）：

(1) 我們實(shí)現(xiàn)了一個(gè)函數(shù) brainLuck 用以模擬 BF 語言的解釋執(zhí)行腻窒，函數(shù) brainLuck 的用例如下：

const code = ',+[-.,+]';
const input = 'Parksben' + String.fromCharCode(255);

const output = brainLuck(code, input);
console.log(output); // -> 'Parksben'

(2) 將輸入的字符串切割為單個(gè)字符，暫存進(jìn)數(shù)組 inputChars磅崭；

(3) 將 BF 程序切割為單個(gè)操作符儿子，方便遍歷每個(gè)指令，用 codeIdx 作為下標(biāo)進(jìn)行遍歷砸喻；

(4) 聲明一個(gè)數(shù)組 arr 用以模擬機(jī)器內(nèi)存柔逼，過程產(chǎn)生的數(shù)值存儲(chǔ)到此數(shù)組中；

(5) 用字符串 outputStr 存儲(chǔ)程序的輸出割岛；

(6) 遍歷 BF 運(yùn)算符愉适，對(duì)不同指令進(jìn)行相應(yīng)的操作；

(7) 方法 handleLeftBracket癣漆，用以匹配到與當(dāng)前 [ 對(duì)應(yīng)的 ]（通過操作下標(biāo) codeIdx）维咸；

(8) 方法 handleRightBracket，用以匹配到與當(dāng)前 ] 對(duì)應(yīng)的 [（通過操作下標(biāo) codeIdx）；

(9) 用以處理不同指令的 switch 語句癌蓖；

(10) codeIdx 加一瞬哼，以向前遍歷 codes；

(11) 程序輸出租副；

延伸閱讀

Brainfuck: a Programming Language or a Joke?

丹尼爾·克里斯托法尼的一些 BF 實(shí)例

深?yuàn)W的編程語言 - 維基百科