Jazyk Brainfuck a Brainfuck Interpret v C

Mé setkání s tímto zajímavým jazykem a popis implementace jeho interpreteru v jazyce C.

WTF BF?

O programovacím jazyce Brainfuck jsem slyšel již dříve, ale nevěnoval jsem mu pozornost. Až před několika dny mě vlny internetu zanesly na stránku jazyka Brainfuck na Wikipedii. Jazyk na mě zapůsobil, tak jsem se ihned vrhnul do hledání dalších informací o této hříčce mezi programovacími jazyky. Brzy jsem zjistil, že vedle Brainfucku existují další nestandardní jazyky jako jsou například Unlambda, Intercal, Whitespace, Befunge a další. Historii a charakteristiky tohoto jazyka zde nebudu přepisovat, protože ucelené info najdete na anglické wikipedii a poněkud stručnější výcuc se nachází i na té české. Jediné o čem bych se zmínil jsou...

Příkazy jakyka Brainfuck

Brainfuck je minimalistický jazyk o čemž svědčí i počet použitelných příkazů. Je jich celých osm a jejich shrnutí najdete v následující tabulce převzaté z wikipedie:

Příkaz	| Popis
>	posun ukazatele o jednu buňku doprava
<	posun ukazatele o jednu buňku doleva
+	zvýšení hodnoty aktivní buňky o 1 (buňky, nad kterou je ukazatel)
-	snížení hodnoty aktivní buňky o 1
.	výpis hodnoty aktivní buňky na standardní výstup (v drtivé většině případů na obrazovku). Pro výpis se používá hodnota aktivní buňky převedená dle kódování ASCII na znak.
,	uložení hodnoty ze vstupu do aktivní buňky
[	pokud je hodnota aktivní buňky rovna nule, provede přesun ukazatele doprava za odpovídající ]
]	pokud je hodnota aktivní buňky různá od nuly, provede přesun ukazatele doleva před odpovídající [

Programování v BF

Ihned jsem zatoužil po tom, si nějaký ten prográmek v BF napsat. Něco jsem tedy narychlo spatlal a nyní se dostal k problému jak kód přeložit. BF patří mezi interpretované jazyky (přesto jsem viděl i BF compiler), tudíž bylo nanejvýš vhodné si opatřit nějaký Brainfuck interpreter. Těch je na internetu velké množství a při jejich procházení mě to napadlo...

Vlastní BF interpreter

Takto (syntakticky) jednoduchý jazyk má jednoduchý interpreter, proč si ho tedy nevytvořit sám? Na české wikipedii z článku o BF vedou odkazy na BF interpreter v JavaScriptu a v PHP. Má volba tedy byla jasná. Udělám si BF interpreter v jazyce C. Jak jsem si určil, tak jsem také udělal. Kód interpreteru je vskutku jednoduchý a nepřesahuje ani 300 řádků. Avšak dobrý způsob jak si procvičit "céčko". Program jsem nazval prostě a jednoduše Brainfuck Interpreter, zkráceně BFI.

Popis implentace BFI

Nyní bude následovat stručný popis zdrojového kódu interpreteru. Pokud vás programování nebaví můžete tento odstavec přeskočit... btw, pokud vás nebaví programování, tak nemáte na tomto webu vlastně ani co dělat;) Takže zpět k tématu. Program přijímá jeden parametr. Pokud jím je "-h" anebo je program spuštěn bez parametrů, je zobrazena nápověda. V opačném případě by měl parametr představovat soubor se zdrojovým kódem programu v jazyce Brainfuck. Zadání více parametrů je vyhodnoceno jako chyba.

Po zkontrolování parametrů program alokuje paměť pro pásku ( = pole buněk o velikosti jednoho bajtu, nad kterým BF operuje). Ta by podle specifikace měla mít přesně 30 000 bajtů. Z důvodu šetření pamětí však počáteční pásce alokuji prostor 1000 bajtů, který je v případě potřeby dynamicky zvětšen vždy o dalších 1000 bajtů.

Poté je otevřen soubor se zdrojovým kódem a zdrojový kód je nakopírován na vyhrazené místo do paměti. Přístup k jednotlivým operátorům zdrojového kódu BF je tak velmi rychlý.

Nakonec probíhá samotné parsování zdrojového kódu. To je díky nízkému počtu operátorů jazyka BF možno realizovat pomocí konstrukce switch. Pro každý operátor se vykoná daná operace v příslušené větvi switche. Implementace jednotlivých operací byla triviální až na příkazy cyklu '[' a ']', kde bylo nutné brát ohled na vnořené cykly. Nakonec bych ještě podotknul, že "zapamatovávání si" počátku cyklů (nutné pro vnořené cykly) je realizováné formou zásobníku, pro který byly implementovány dvě funkce pushující a popující hodnotu na/ze zásobníku.

Programy v jazyce Brainfuck

Zde jsou k dispozici dva prográmky v jazyce Brainfuck, na kterých si můžete vyzkoušet BFI. Prvním je klasické Hello World, druhý vytiskne kompletní text známe anglické písničky/říkanky. Budu rád, pokud se v komenentářích podělíte o své případné výtvory v tomto zajímavém jazyce.

Hello.bf

Bottles.bf

BFI download

A nyní mi už zbývá snad jen přidat odkaz na zdrojový kód BFI. Přeji příjemné BF programování:)

bfi.tar.gz

bfi.zip

Předcházející článek: Jsem šachovým mistrem Evropy

Následující článek: XSS aneb Švejnar ne na Hrad

Přidej svůj komentář

Master
Nice!
24.1.2008 1:03:01		81.19.45.*

GeniuS	genius(zavinac)yw.sk
A cim to mam skompilovat?
25.1.2008 20:37:02		78.98.204.*

Stoyan
GeniuS: Omfg, ty mas jeste odvahu sem psat? A navic takova otazka... (skoda ze tu nemam smajlika s ocima v sloup). Uz z nazvu clanku je patrne, ze se jedna o "ceckovsky" zdrojak, tzn ze pouzijes C compiler. Jelikoz muj kod dodrzuje vsechny standardy (norma C99), muzes teoreticky pouzit jakykoliv. Ja doporuciji GCC.
25.1.2008 20:42:35		195.47.46.*

Tom@sQo
ahoj, aj ja som spravil davnejsie(cez letne prazdniny) kompiler v pythone ;) chcel som ho sem napisat, ale neviem ho najst ;( kazdopadne, co sa zopar zaujimavych programov tyka, tak odporucam: http://esoteric.sange.fi/brainfuck/bf-source/prog/
30.1.2008 23:00:08		88.212.21.*

GeniuS	genius(zavinac)yw.sk
Ja pouzivam dev c++ a tam to neslo preto sa pytam
31.1.2008 11:56:52		212.89.232.*

Bagy
Nehrajes nahodou hackits.de ? Tam toti tahle brainf-ck sifra taky je, tam jsem se ji naucil ++++++++[->++++++++<]>++.<++++++[->++++++<]>++++++++++++.<++++[->----<]>-.+ +++++++.+++++.--------.<+++[->+++<]>++++++.<++++[->----<]>--.++++++++.----- -.-.<
3.2.2008 11:01:17		85.160.108.*

nuguien	ooznam(zavinac)seznam.cz
to mi nechce fungovat nevim cim to je pls vi nekdo cim to muze bejt ze mi to na XPcku nejde zkusil sem to Hello.bf
5.2.2008 17:33:51		195.122.213.*

nuguien	ooznam(zavinac)seznam.cz
dam to do exe a nefunguje to
5.2.2008 17:50:30		195.122.213.*

Stoyan
nuguien: Uznavam ze jsem to do clanku nenapsal, ale hned pri letmem pohledu do zdrojaku by melo byt i zacatecnikovi v C jasne pouziti tohoto programu ktere je: Linux: ./bfi Hello.bf Windows: bfi.exe Hello.bf Tzn, ze program se spousti z konzole a jako svuj jediny parametr prijima nazev souboru s BF zdrojakem. Bagy: Brainfuck neni sifra, ale "plnohodnotny" programovaci jazyk.
5.2.2008 18:00:07		195.47.46.*

nuguien	ooznam(zavinac)seznam.cz
Dik stoyane
5.2.2008 19:03:16		195.122.213.*

nuguien	ooznam(zavinac)seznam.cz
uz mi to funguje.neni to totiz pro lamy
6.2.2008 18:12:54		213.192.7.*

nuguien	ooznam(zavinac)seznam.cz
upozornuju ze ty co neumi nic tak ani tady z tich prgramu nevytvari
6.2.2008 18:14:29		213.192.7.*

mr.Crow
Stoyane, já tě trumfnu, já se pustím do interpretu pro whitespace http://cs.wikipedia.org/wiki/Whitespace ...nejvtipnější jazyk ze všech
12.2.2008 23:32:35		213.211.34.*

ulkas
2 mr.Cow skus radsej lolcode, ten je najvtipnejsi
13.2.2008 14:36:02		195.168.209.*

Harvie
Vy ste teda linuxaci ;P dam vam radu: su mv bfi /usr/bin/ exit echo '#!/usr/bin/bfi' > newzdrojak.bf cat oldzdrojak.bf >> newzdrojak.bf chmod +x newzdrojak.bf ./newzdrojak.bf #tahle se to dela na linuxu!
17.4.2008 15:49:24		213.220.241.*

iza	xsehnalm(zavinac)seznam.cz
Please, může mi to někdo přeložit do řeči čísel? Nejsem programátor a tohle mi fakt nic neříká Díky moc se>++++++++++[<++++++++++>-]<++++.>+++[<++++>- ]<..----.>+++++++[<------->-]<-----.>+++[<-- ->-]<--..>++++++++[<+++++++++>-]<...>>++++++ [<+++++++>-]<++++.<>[-]++[<---->-]<.-.>+++[< --->-]<-.>+++[<++++>-]<++.>+++[<---->-]<-.++ +++.>>++++++[<+++++++>-]<++++.<+++++.+++.>[- ]+++[<--->-]<--.>>++++++[<+++++++>-]<+++++.< .----.>.-.<+++++++.>[-]+++[<--->-]<.>+++++[< +++++>-]<.-.>+++[<---->-]<--.>+++[<++++>-]<+ +.>>++++++[<+++++++>-]<+++++.>>+++[<+++>-]<+.
1.11.2008 8:42:24		89.24.225.*

Stoyan
Harvie: jj, toto je ciste *nix reseni. iza: Na to nemusis byt ani programator, staci ti pouze popis prikazu jazyka brainfuck a trocha prirozene inteligence
2.11.2008 18:04:24		195.47.46.*

PP
Stoyan: Zkusil jsem neco slozitejsiho naprogramovat v brainfucku, 'if (x==0) ...;' ale interpret to prestal zvladat. Pravdepodobne je chyba ve smyckach [] Nasleduje vypis programu, ktery prubezne vypisuje ladici informace na obrazovku. ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ > ++++++++++ > ++++ >>> + <<<<< // test 1 // tisk pozice a promennych . >> ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- <<<<<.>.< // konec tisku pozice a promennych >>[>+>+<<-]>>[<<+>>-]<<<< // test 2 // tisk pozice a promennych . >> ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- <<<<<.>.< // konec tisku pozice a promennych >>>[[-]>>-]<<<<< // test 3 // tisk pozice a promennych . >> ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- <<<<<.>.< // konec tisku pozice a promennych >>>>>+-[-]<<<<< // test 4 // tisk pozice a promennych . >> ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- > ++++++++++ ++++++++++ ++++++++++ ++++++++++ ++++++++ . ---------- ---------- ---------- ---------- -------- <<<<<.>.< // konec tisku pozice a promennych
5.2.2009 15:20:27		79.97.1.*

Stoyan
PP: Vidim, ze sis s tim celkem vyhral. Dnes uz bych ten interpret napsal uplne jinak. Stejne mi to nedalo a ten zdrojak jsem debugoval. Byla tam opravdu hloupa chyba. Muzes si stahnout novou verzi.
6.2.2009 9:38:20		195.47.46.*

PP
Stoyan: diky za novou verzi, ale jsou tam dalsi chyby, viz >>[[-]>>]<<<<< kazdopadne jsem si hezky zabrainfuckoval
6.2.2009 23:06:44		79.97.1.*

Nový komentář

Nick:	160" />	Smajlíci:
Web:
Email:
Komentář:
Opište prosím číslo 160 (ochrana proti SPAMu)
	* Pole Komentář podporuje BBCode tagy

© Stoyan, 2006 - 2010