本頁使用了標題或全文手工轉換

Brainfuck

維基百科,自由的百科全書
跳至導覽 跳至搜尋

Brainfuck,是一種極小化的程序語言,它是由Urban Müller在1993年創造的。由於fuck英語中是髒話,這種語言有時被稱為Brainf*ckBrainf***,或被簡稱為BF

概述[編輯]

Müller的目標是建立一種簡單的、可以用最小的編譯器來實現的、符合圖靈完全思想的編程語言。這種語言由八種運算符構成,為Amiga機器編寫的編譯器(第二版)只有240個字節大小。[1]

就象它的名字所暗示的,Brainfuck程序很難讀懂。儘管如此,Brainfuck圖靈機一樣可以完成任何計算任務。雖然Brainfuck的計算方式如此與眾不同,但它確實能夠正確運行。

這種語言基於一個簡單的機器模型,除了指令,這個機器還包括:一個以字節為單位、被初始化為零的數組、一個指向該數組的指針(初始時指向數組的第一個字節)、以及用於輸入輸出的兩個字節流

下面是這八種狀態的描述,其中每個狀態由一個字符標識:

字符 含義
> 指針加一
< 指針減一
+ 指針指向的字節的值加一
- 指針指向的字節的值減一
. 輸出指針指向的單元內容(ASCII碼
, 輸入內容到指針指向的單元(ASCII碼)
[ 如果指針指向的單元值為零,向後跳轉到對應的]指令的次一指令處
] 如果指針指向的單元值不為零,向前跳轉到對應的[指令的次一指令處

按照更節省時間的簡單說法,]也可以說成「向前跳轉到對應的[狀態」。這兩解釋是一樣的。

第三種同價的說法,[意思是「向後跳轉到對應的]」,]意思是「向前跳轉到對應的[指令的次一指令處,如果指針指向的字節非零。」

Brainfuck程序可以用下面的替換方法翻譯成C語言(假設ptrchar *類型):

Brainfuck C
> ++ptr;
< --ptr;
+ ++*ptr;
- --*ptr;
. putchar(*ptr);
, *ptr = getchar();
[ while (*ptr) {
] }

例子[編輯]

Hello World![編輯]

一個在屏幕上打印Hello World!的程序:

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++.
>.+++.------.--------.>+.>.

目前位置歸零[編輯]

[-]

字符I/O[編輯]

,.

從鍵盤讀取一個字符並輸出到屏幕上。

簡單的循環[編輯]

,[.,]

這是一個連續從鍵盤讀取字符並回顯到屏幕上的循環。注意,這裡假定0表示輸入結束,事實上有些系統並非如此。以-1和「未改變」作為判斷依據的程序代碼分別是,+[-.,+],[->+>-<<]>[-<+>]>[[-]<<.[->>+<<],[->+>-<<]>[-<+>]>]

指針維護[編輯]

>,[.>,]

通過移動指針保存所有的輸入,供後面的程序使用。

加法[編輯]

[->+<]

把當前位置的值加到後面的單元中(破壞性的加,它導致左邊的單元被歸零)。

條件指令[編輯]

,----------[----------------------.,----------]

這個程序會把從鍵盤讀來的小寫字符轉換成大寫。按回車鍵退出程序。

首先,我們通過,讀入第一個字符並把它減10(10 在大多數情況下為換行符 LF 的值)。如果用戶按的是回車鍵,循環命令([)就會直接跳轉到程序的結尾:因為這時第一個字節已經被減到了零。如果輸入的字符不是換行符(假設它是一個小寫字符),程序進入循環。在這裡我們再減去剩下的22,這樣總共減掉32:這是ASCII碼中小寫字符和大寫字符的差值。

下面我們把它輸出到屏幕。然後接收下一個輸入字符,並減去10。如果它是換行符,退出循環;否則,再回到循環的開始,減去22並輸出……當循環退出時,因為後面已經沒有其他的指令,程序也隨之終止。

加法器 add(summand, addend, *sum)[編輯]

>>[-]>[-]<<<        // clear cell #2 and #3
[->>+>+<<<]         // transfer cell #0 to #2 and #3
>
    >>[-<<<+>>>]<<  // transfer cell #3 to #0
    [->+>+<<]       // transfer cell #1 to #2 and #3
    >>[-<<+>>]<<    // transfer cell #3 to #1
<

該代碼以 cell #3 作為臨時變量,將保存在 cell #0 和 cell #1 中的兩個整數相加,

結果保存在 cell #2;同時維持原來的兩個存儲單元數值不變,方便以後使用。

代碼運行前,設定指針指向 cell #0,

第一步,先將 cell #2 和 cell #3 清空,確保不會有髒數據影響運算結果;

第二步,將 cell #0 的數值轉移到 cell #2 和 cell #3,隨後利用 cell #3 這個來恢復 cell #0 的值;

第三步,將 cell #1 的數值轉移到 cell #2 和 cell #3,隨後利用 cell #3 這個來恢復 cell #1 的值;

最後,指針歸位(回到初始位置,即指向 cell #0),方便後續運算。

乘法器 multiply(multiplicand, multiplier, *product)[編輯]

>>[-]>[-]>[-]<<<<       // clear cell #2 and #3 and #4
[->
    [->+>+<<]           // add cell #1 to #2
    >>
        [-<<+>>]        // move cell #3 back to #1
        >+<             // copy cell #0 to #4
    <<
<]
>>>>[-<<<<+>>>>]<<<<    // move cell #4 back to #0

跟上面的「加法器」類似,這個「乘法器」將保存在 cell #0 和 cell #1 的兩個整數相乘,結果保存在 cell #2;同時維持原來的兩個存儲單元數值不變,方便以後使用。

更多代碼解析請參見 https://github.com/moky/BrainFuck

注釋[編輯]

  • 注意,這裡數組的每個單元都是一個字節大小;-命令允許溢出,它可以用255個+命令來代替。同樣,如果數組單元是有限、循環的<可以用29999個>命令代替。每個修改動作都可以被分解為最多7條指令。可是,兩個連在一起的修改動作將會破壞「圖靈完全」,因為這會把可能的內存狀態限制到有限個數。(更確切的說,從這個角度看,現代的計算機依然不是完全意義上的「圖靈完全」)

參考資料[編輯]

  1. ^ dev/lang/brainfuck-2.lha. Aminet. [2013-10-30]. (原始內容存檔於2005-11-06). 

外部連結[編輯]