3 заметки с тегом

bf

Интерпретатор Brainfuck на языке R

В качестве упражнения написал тривиальный интерпретатор «Брейнфака» на языке «Эр», никаких оптимизаций, кроме преподсчёта переходов. Даже на версию без поддержки вложенных циклов ушло прилично времени — некоторые вещи у меня пока со скрипом идут. Зато воспользовался разными структурами данных и сделал класс на RC (в языке «Эр» три встроенных способа работы с классами).

Brainfuck на AppleScript

Для развлечения написал интерпретатор языка Brainfuck на AppleScript.

Особенности: для ввода программы используется текстовое поле, которое выглядит как однострочное, но на деле понимает многострочный текст. Операция «,» у меня с буфером, это значит, что при запросе можно вводить сразу строку, при надобности интерпретатор сам будет брать оттуда значения. Если их не хватит, запросит ещё.

AppleScript медленный язык, следовательно и получившийся интерпретатор медленный (никаких оптимизаций я не делал), лучше всего на нём запускать небольшие программы. Например, «Hello, world»:

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

Не уверен, что нигде не ошибся (всё-таки время четвёртый час ночи), но даже вложенные циклы на программах, которые я прогонял, работают нормально. 

#!/usr/bin/osascript
-- AppleScript Brainfuck interpreter
-- Evgeny Stepanischev 1 Jul 2011 http://bolknote.ru

set Cells to {}
repeat 30000 times
    set end of Cells to 0
end repeat

display dialog "Enter your BF program" default answer ""
set Bf to text items of text returned of result

set Pointer to 1
set CmdPointer to 1
set Output to ""
set Input to {}
set Stack to {}

repeat while CmdPointer ≤ (count of Bf)
    set Cmd to item (CmdPointer) of Bf
    
    if Cmd is equal to ">" then
        set Pointer to Pointer + 1
        if Pointer > 30000 then set Pointer to 1
        
    else if Cmd is equal to "<" then
        set Pointer to Pointer - 1
        if Pointer < 1 then set Pointer to 30000
        
    else if Cmd is equal to "+" then
        set Val to (item (Pointer) of Cells) + 1
        if Val is greater than 255 then set Val to 0
        copy Val to item (Pointer) of Cells
        
    else if Cmd is equal to "-" then
        set Val to (item (Pointer) of Cells) - 1
        if Val is less than 0 then set Val to 255
        copy Val to item (Pointer) of Cells
        
    else if Cmd is equal to "." then
        set Output to Output & (ASCII character item (Pointer) of Cells)
        
    else if Cmd is equal to "," then
        if Output ≠ "" then
            display alert Output
            set Output to ""
        end if
        
        if Input is {} then
            display dialog "Enter one or more characters" default answer ""
            set Res to text returned of result
            
            set item (Pointer) of Cells to ASCII number of character 1 of Res
            
            try
                set Input to rest of text items of Res
            end try
            
        else
            set item (Pointer) of Cells to ASCII number of item 1 of Input
            set Input to rest of Input
        end if
        
    else if Cmd is equal to "[" then
        if item (Pointer) of Cells = 0 then
            set CmdPointer to CmdPointer + 1
            set Deep to 1
            
            repeat while CmdPointer ≤ (count of Bf)
                set Cmd to item (CmdPointer) of Bf
                
                if Cmd is equal to "[" then
                    set Deep to Deep + 1
                else if Cmd is equal to "]" then
                    set Deep to Deep - 1
                    
                    if Deep is 0 then exit repeat
                end if
                
                set CmdPointer to CmdPointer + 1
                
            end repeat
        else
            set Stack to (CmdPointer - 1) & Stack
        end if
    else if Cmd is equal to "]" then
        if item (Pointer) of Cells ≠ 0 then
            copy item (1) of Stack to CmdPointer
        end if
        set Stack to rest of Stack
    end if
    
    set CmdPointer to CmdPointer + 1
end repeat

if Output ≠ "" then
    display alert Output
end if

Brainfuck

Как-то очень давно я наткнулся в сети на язык с названием Brainfuck. Его идея, так подходящая к его названию, так меня захватила, что я в своё время создал оптимизирующий компилятор программ Brainfuck в JavaScript, выполненный в виде минишелла и работающий прямо в браузере. Язык интересен тем, что содержит всего восемь конструкций, но позволяет писать программу любой сложности, правда скорость выполнения...

Дело давнее, но около месяца назад, поддавшись какому-то невнятному импульсу, я вернулся к идее оптимизирующего компилятора. Поскольку, в данный момент язык-фаворит для меня PHP, мне захотелось, руководствуясь теми же принципами, написать компилятор Brainfuck в PHP, что я и сделал.

Модуль к PHP написан в формате PEAR, т. е. его можно либо использовать непосредственно, либо исталлировать в составе PEAR.

Нельзя сказать, что я компилятор проводит глубокую оптимизацию, но, например, код «[->+>++<<][>+>[-]<<-][>+<[-]]" будет преобразован в

<?php
$in = array(0, $id = 0);
$d = array_fill(-65535, 65535, $di = 0);

$d[$di+1]+= $d[$di];
$d[$di+2]+= $d[$di]*2;
$d[$di] = 0;

$d[$di+1]+= $d[$di];
if ($d[$di]) $d[$di+2] = 0;
$d[$di] = 0;

$d[$di+1]+= $d[$di];
$d[$di] = 0;

В сам PEAR-репозиторий я его выкладывать не буду — даже по моим меркам это не слишком полезная штука, да и вряд ли за него проголосуют (все модули на PEAR подвергаются процедуре голосования, прежде чем попадут в репозиторий).