Внедрение контуров Brainfuck в интерпретаторе

Question

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

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

• Как реализовать БФ петлю в моем переводчике?

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

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

От верхней части головы, могут быть некоторые ошибки в нем, но что-то, как это должно работать:

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 * исходного кода ск. Указатель p находится в текущей позиции памяти. Выполняйте рекурсивный вызов при обнаружении [. Вернитесь из этого рекурсивного вызова при встрече с].

Answer 4

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

Answer 5

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

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 

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

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