Реализация циклов Brainfuck в интерпретаторе
Я хочу создать Brainfuck (Чертовски что имя) интерпретатор на моем недавно созданном языке программирования, чтобы доказать, что это - полнота Тьюринга.
Теперь, все ясно до сих пор (<>+-,.) - кроме одной вещи: циклы ([]). Я предполагаю, что Вы знаете (чрезвычайно твердый) синтаксис BF отсюда на:
- Как я реализую циклы BF в своем интерпретаторе?
Как псевдокод мог быть похожим? Что должно я делать, когда интерпретатор достигает начала цикла ([) или конец цикла (])?
При проверке, должен ли цикл продолжиться или остановка не является проблемой (current cell==0), но:
- Когда и где я должен проверить?
- Как знать, где начало цикла расположено?
- Как обработать вложенные циклы?
Поскольку циклы могут быть вложены, я предполагаю, что не могу только использовать переменную, содержащую стартовую позицию токовой петли.
Я видел, что очень маленькие интерпретаторы BF, реализованные на различных языках, интересно, как они сумели получить работу циклов, но не могут понять это.
5 ответов
Достигнув [, вы проверяете указатель данных.
Если это ложь, вы можете сканировать следующий совпадающий ] символ, подсчитывая, сколько [ вы видите, и отмечая их, когда видите каждый ] .
Если это правда, вам нужно отслеживать его положение, чтобы вы могли вернуться к нему позже. Предлагаю использовать стек. Поместите текущую позицию программы в стек, затем, когда вы достигнете ] , проверьте указатель данных. Если это правда, перейти к самой верхней позиции программы в стеке. Если это false, вытащить позицию из стека и продолжить.
По мере вложения во внутренние циклы стек будет четко записывать контекст каждого цикла.
См. Стек (википедия) . Это аналогично тому, как программы сборки обрабатывают вызовы функций.
Наверное, в нем могут быть какие-то ошибки, но должно работать что-то вроде этого:
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 указывает на текущую позицию в памяти. Выполняйте рекурсивный вызов при обнаружении [. Вернитесь из этого рекурсивного вызова при обнаружении].
Как реализовать циклы BF в моем интерпретаторе?
В том-то и дело - это полностью зависит от вашего языка. В случае языка программирования на основе стека (или любого языка, который может использовать стек), @rjh дал хорошее решение. Другие языки будут использовать другие решения, такие как рекурсия (т.е. неявное использование стека).
Я предпочитаю использовать таблицу переходов (наряду с преобразованием сырого BF в "байткод"). Оптимизация BF-интерпретаторов - это, несомненно, путь вперед!
Вот моя "оптимизирующая" версия интерпретатора, которая предварительно компилирует переходы цикла.
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 раза по сравнению с невинной реализацией, в которой исходный текст сканируется вперед для выхода [ и сканируется назад для цикла на ].