Smallf * CK (простой диалект Brainfuck) интерпретатор бесконечный цикл - PullRequest
Новая
       50

Smallf * CK (простой диалект Brainfuck) интерпретатор бесконечный цикл

0 голосов
/ 06 апреля 2020

Я пытаюсь реализовать интерпретатор Smallf * ck.

Smallfuck - еще более лаконичный диалект Brainfuck c, который работает с битами вместо байтов, имеет ограниченный размер ленты памяти и не имеет команд ввода / вывода. Таким образом, осталось только 5 команд: 

* : flip the current bit;
> : increment the data pointer (move it to the next cell to the right);
< : decrement the data pointer (move it to the next cell to the left);
[ : “begin loop”:
    if the current bit is 1, increment the instruction pointer
    (move it to the next command to the right), otherwise,
    move it to the next command to the right of the matching ] command;
] : “end loop”:
    if the current bit is 0, increment the instruction pointer,
    otherwise move it to the next command to the right of the matching [ command.
    Can also be interpreted as unconditional jump to the matching [ command,
    since [ performs an extra check itself.

Пример ввода: "*>*>*>*>*>*>*>*", "00101100" должен вернуть "11010011"

Моя реализация пока: 

def interpreter(code, tape):
    ptr, cmd_pos = 0, 0
    tape = [int(num) for num in tape]
    while ptr < len(tape) and cmd_pos < len(code):
        if code[cmd_pos] == ">":
            ptr += 1
        elif code[cmd_pos] == "<":
            ptr -= 1
        elif code[cmd_pos] == "*":
            tape[ptr] = 1 if tape[ptr] == 0 else 0
        elif code[cmd_pos] == "[":
            if tape[ptr] == 0:
                found = False
                while not found:
                    cmd_pos += 1
                    if code[cmd_pos] == "]":
                        found = True
        elif code[cmd_pos] == "]":
            found = False
            while not found:
                cmd_pos -= 1
                if code[cmd_pos] == "[":
                    found = True
        cmd_pos += 1
    return ''.join([str(num) for num in tape])

Есть также вопрос codewars, поэтому я делаю это: https://www.codewars.com/kata/58678d29dbca9a68d80000d7/train/python

Я не знаю, что не так с моим кодом ... Основы c все работает, но петли нет. В некоторых тестовых случаях на codewars я создаю бесконечное l oop, и я не знаю почему.

Помощь будет очень полезна, может быть, кому-то даже очень весело реализовать это:

1 Ответ

2 голосов
/ 07 апреля 2020

Вам также необходимо учитывать вложенные циклы. Например, если вы возьмете код «[* [>]]», когда ваша реализация достигнет конца внешнего l oop, он будет искать первый «[» слева от него и продолжит оттуда. Но поскольку это было «]» внешнего l oop, вместо этого оно должно продолжаться на «[» того же внешнего l oop (второе, которое он находит при поиске слева от «]»). Чтобы достичь этого, вы можете, например, подсчитать число «]», с которым вы столкнетесь, глядя влево: 

    elif code[cmd_pos] == "]" and tape[ptr]==1:
        found = False
        nestedLoopCounter = 1
        while not found:
            cmd_pos -= 1
            if code[cmd_pos] == "]":
                nestedLoopCounter+=1
            elif code[cmd_pos] == "[":
                nestedLoopCounter-=1
                if nestedLoopCounter==0:
                    found = True
        cmd_pos-=1

Также обратите внимание, что вам нужно проверить, является ли значение в текущей ячейке первым 1. То же самое относится и к «[». Если вы встречаете начало al oop и текущее значение ячейки равно 0, поэтому вы хотите пропустить l oop, вам нужно найти соответствующий «]», а не только первый, с которым вы столкнулись.

...