Brainfuck

Brainfuck

Brainfuck是一種極小化的計算機語言,它是由Urban Müller在1993年創建的。由於fuck在英語中是髒話,這種語言有時被稱為brainf*ck或brainf**k,甚至被簡稱為BF。

基本信息

簡介

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

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

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

這種語言,是一種按照“Turing complete(圖靈完備)”思想設計的語言,它的主要設計思路是:用最小的概念實現一種“簡單”的語言,BrainF**k 語言只有八種符號,所有的操作都由這八種符號的組合來完成。

字元標識

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

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

(按照更節省時間的簡單說法,"]"也可以說成“向後跳轉到對應的"["狀態”。這兩解釋是一樣的。)

(第三種同價的說法,"["意思是"向前跳轉到對應的"]"",]意思是"向後跳轉到對應的[指令的次一指令處,如果指針指向的位元組非零。")

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

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

當前位置清零

[-] 將當前指針的值歸零

之前位置清零

[[-]<] 將當前指針以及之前的指針歸零

字元I/O

,. 從鍵盤讀取一個字元並輸出到螢幕上。

簡單的循環

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

指針維護

>,[.>,] 通過移動指針保存所有的輸入,供後面的程式使用。

加法

[->+<]

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

條件指令

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

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

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

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

加法

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

這個程式對兩個一位數做加法,並輸出結果(如果結果也只有一位數的話):4+3

7 (現在程式開始有點複雜了。我們要涉及到數組中單元的內容了,比如[0]、[1]、[2]之類。)

第一個輸入的數字被放在在[0]中,從中減去48來把它從ASCⅡ碼值48到57轉換為數值0到9:這是通過在[1]中放入6,然後按照[1]中的次數讓一個循環從[0]中多次減去8來完成的(當加上或減去一個大的數值時,這是常用的辦法)。下一步,加號被讀入[1]中;然後,第二個數字被輸入,覆蓋掉加號。

下面的循環[<+>-]執行最重要的工作:通過把第二個數字移動到第一個裡面讓它們相加,並把[1]清空。這裡的每次循環都把[0]增一併從[1]中減一;最終,在[1]被置零的多次循環中,[1]中的值就被轉移到了[0]中。現在,[1]中是我們輸入的換行符(這個程式里,我們沒有設定對輸入錯誤的檢查機制)。

然後,指針被移回到指向[0],並輸出它的內容([0]裡面現在是 a + (b + 48) 的值,因為我們沒有修改b的值,這等於 (a + b) + 48,也就是我們想要輸出的ASCⅡ值)。然後,把指針指向[1],裡面保存著前面輸入的換行符;輸出換行符,程式結束。

乘法

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

和前一個程式類似,不過這次是乘法而不是加法。

第一個輸入的數字被放入[0],星號和第二個數字被放入[1],然後兩個數值都被校正:減去48。

現在,程式進入了主循環。我們的基本思想是:每次從[0]中減去一,同時把[1]的值加入到保存乘積的[2]中。在實際操作中,第一個內層循環把[1]的值同時轉移到[2]和[3]中,同時[1]清零(這是我們複製數字的基該方法)。下一個內層循環把[3]中的值重新放回到[1],並清零[3]。然後從[0]中減一,結束外層循環。在退出這個循環時,[0]中為零,[1]仍然是輸入的第二個數值,[2]則是這兩個數值的和。(要是想保存第一個數,我們可以在外層循環中每次給[4]加一,最後把[4]移回[0]。)在結果中加48,並把換行符讀入[3],輸出ASCII碼的乘積,然後輸出剛才保存的換行符。

除法

,>,>++++++[-<--------<-------->>]

從簡單儲存2個數字元到[0]和[1],並各自減去48

<<[ 這是一個主循環,在被除數,也就是[0]的值為0後循環跳出

>[->+>+<<] 從單元1中複製除數的值到[2]和[3],設[1]為0

>[-<<- 被除數[1]減去除數[2],結果將儲存在[0],並且[2]將歸0

[>]>>>[<[>>>-<<<[-]]>>]<<] 如果被除數[0]為0,跳出循環

>>>+ 加1值商到[5]

<<[-<<+>>] 從[3]複製除數到[1]

<<<] 移動指針到[0]

>[-]>>>>[-<<<<<+>>>>>] 從[5]複製商到[0] (這步不是必須的,但會更清楚)

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

相關詞條

相關搜尋

熱門詞條

聯絡我們