Реализация циклов Brainfuck в интерпретаторе - PullRequest
Новая
       30

Реализация циклов Brainfuck в интерпретаторе

9 голосов
/ 07 апреля 2010

Я хочу создать интерпретатор Brainfuck (Черт возьми, имя) на моем недавно созданном языке программирования, чтобы доказать его полноту по Тьюрингу.

Теперь все ясно (<>+-,.) - за исключением одного: петли ([]). Я предполагаю, что вы знаете (чрезвычайно жесткий) синтаксис BF с этого момента:

  • Как реализовать циклы BF в моем интерпретаторе?

Как может выглядеть псевдокод? Что мне делать, когда интерпретатор достигает начала цикла ([) или конца цикла (])?

Проверка, должен ли цикл продолжаться или останавливаться, не является проблемой (current cell==0), но:

  • Когда и где я должен проверить?
  • Как узнать, где находится начало цикла?
  • Как обращаться с вложенными циклами?

Поскольку циклы могут быть вложенными, я полагаю, что я не могу просто использовать переменную, содержащую начальную позицию текущего цикла.

Я видел очень маленькие интерпретаторы BF, реализованные на разных языках, мне интересно, как им удалось заставить циклы работать, но я не могу понять это.

Ответы [ 5 ]

8 голосов
/ 07 апреля 2010

Когда вы достигаете [, вы проверяете указатель данных.

Если значение равно false, вы можете отсканировать следующий соответствующий ] символ, подсчитав, сколько [ вы видите, и убедившись, что вы отметили их, как видите каждый ].

Если это правда, вам нужно отслеживать его положение, чтобы вы могли вернуться к нему позже. Я предлагаю использовать стек. Вставьте текущую позицию программы в стек, затем, когда вы достигнете ], проверьте указатель данных. Если это правда, перейдите на самую верхнюю позицию программы в стеке. Если значение равно false, вытолкните позицию из стека и продолжайте.

Когда вы вкладываетесь во внутренние циклы, стек будет чистым образом записывать контекст каждого цикла.

См. стек (Википедия) . Это аналогично тому, как программы на ассемблере обрабатывают вызовы функций.

5 голосов
/ 15 июня 2010

Вот моя «оптимизирующая» версия интерпретатора, которая предварительно компилирует скачки цикла. 

def interpret2(code):
    data = [0] * 5000   # data memory
    cp = 0              # code pointer
    dp = 0              # data pointer
    # pre-compile a jump table
    stack = []
    jump = [None] * len(code)
    for i,o in enumerate(code):
        if o=='[':
            stack.append(i)
        elif o==']':
            jump[i] = stack.pop()
            jump[jump[i]] = i
    # execute
    while cp < len(code):
        cmd = code[cp]
        if   cmd == '>': dp += 1
        elif cmd == '<': dp -= 1
        elif cmd == '+': data[dp] += 1 
        elif cmd == '-': data[dp] -= 1 
        elif cmd == '.': stdout.write(chr(data[dp]))
        elif cmd == ',': data[dp] = ord(stdin.read(1))
        elif cmd == '[' and not data[dp]: # skip loop if ==0
            cp = jump[cp]
        elif cmd == ']' and data[dp]:     # loop back if !=0
            cp = jump[cp]
        cp += 1

Он выполняет пробный прогон кода, отслеживая скобки (в стеке) и помечает адреса goto параллельно массиву jump, к которому позже обращаются при выполнении.

Я сравнил скорость выполнения в долго выполняющейся программе BF (вычислим N цифр числа Пи), и это увеличило скорость в 2 раза по сравнению с невинной реализацией, в которой источник сканируется вперед для выхода [ и сканируется назад для включения цикла ].

1 голос
/ 07 апреля 2010

Из головы может быть несколько ошибок, но примерно так должно работать: 

char* interpret(char* instructions){
  char* c = instructions;
  while (*c) {
    if (*c == ".") putchar(*p);
    else if (*c == ",") *p = getchar();
    else if (*c == '+') (*p)++;
    else if (*c == '-') (*p)--;
    else if (*c == '<') p--;
    else if (*c == '>') p++;
    else if (*c == '[') c = interpret(c+1);
    else if (*c == ']') { if (*p) c = instructions else return c; }
    c++;
  }
  return 0;
}

Вызовите интерпретацию с исходным кодом brainf * ck. Указатель p указывает на текущую позицию в памяти. Сделайте рекурсивный вызов при обнаружении [. Возврат из этого рекурсивного вызова при обнаружении].

1 голос
/ 07 апреля 2010

Как реализовать циклы BF в моем интерпретаторе?

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

0 голосов
/ 31 мая 2010

Я предпочитаю использовать таблицу переходов (вместе с преобразованием необработанного BF в 'байт-код').Оптимизация переводчиков BF - это верный путь!

...