Почему инструкции [ и ] не работают в этой реализации интерпретатора Brainfrick?

Приведенный ниже код представляет собой черновую реализацию интерпретатора Brainfrick на Java. Спецификации, которые я использую, следующие:

Команды Brainfuck

>   Increment the pointer.

<   Decrement the pointer.

+   Increment the byte at the pointer.

-   Decrement the byte at the pointer.

.   Output the byte at the pointer.

,   Input a byte and store it in the byte at the pointer.

[   Jump forward past the matching ] if the byte at the pointer is zero.

]   Jump backward to the matching [ unless the byte at the pointer is zero.

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

Вопрос: Почему реализация демонстрирует нежелательное поведение?

Редактировать 1: я добавил подход использования счетчика для увеличения при обнаружении открытия [ и уменьшения при достижении a ]. но ошибка все еще сохраняется.

Редактировать 2: код теперь работает нормально, включая циклы, но вывод в терминале Windows показывает вопросительные знаки вместо hello world. что может быть причиной этого?

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;

class Brainfrick {

    public static boolean isValid(char command) {
        switch (command) {
            case '>':
            case '<':
            case '+':
            case '-':
            case '.':
            case ',':
            case '[':
            case ']':
                return true;
            default:
                return false;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String file = System.getProperty("user.dir") + "\\" + args[0];
        //System.out.println(file);
        String content = "";
        try {
            content = Files.readString(Paths.get(file));
        } catch (Exception e) {
            System.out.println("Error reading the file! Printing the stack trace of JVM");
            e.printStackTrace();
            System.exit(-1);
        }
        final char[] commands = content.toCharArray();
        int[] tape = new int[30000];
        int ptr = 0;
        //Stack<Integer> loopStack = new Stack<>();
        int i = 0, ctr = 0;
        while(i < commands.length) {
            char command = commands[i];
            if (!isValid(command)) continue;
            switch (command) {
                case '>':
                    ptr++;
                    i++;
                    break;
                case '<':
                    ptr--;
                    i++;
                    break;
                case '+':
                    tape[ptr]++;
                    i++;
                    break;
                case '-':
                    tape[ptr]--;
                    i++;
                    break;
                case '.':
                    System.out.print((char)tape[ptr]);
                    i++;
                    break;
                case ',':
                    int x = sc.nextInt();
                    sc.nextLine();
                    tape[ptr] = x;
                    i++;
                    break;
                case '[':
                    if (tape[ptr] == 0) {
                         ctr = 0;
                         for(;ctr != 0; ++i){
                            if (commands[i] == '[') ctr+= 1;
                            else if (commands[i] == ']') ctr -= 1;
                        }
                         i++;
                        }
                    i++;
                    break;
                case ']':
                    ctr = 0;
                    if (tape[ptr] != 0) {
                       for(;ctr != 0; --i){
                        if (commands[i] == '[') ctr+= 1;
                            else if (commands[i] == ']') ctr -= 1;
                        }
                    }
                    i++; 
                    break;
                default:
                    continue;
            }
        }
        sc.close();
    }  
} 

как и просили, код, который я пытаюсь запустить, представляет собой некомментированную версию hello world со страницы языка в Википедии.

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

основная проблема в том, что вы ищете не скобку matching, а первую доступную, поэтому вложенные циклы ломаются

Iłya Bursov 05.08.2024 17:15

@IłyaBursov ах, я понимаю, какой будет подход к возможному исправлению? проблема с сопоставлением скобок вложенного цикла была и в Leetcode с использованием стеков, этот сценарий чем-то похож?

Aritro Shome 05.08.2024 17:17

Кроме того, что происходит с ptr, если условия не выполняются? Сейчас ты ничего не делаешь.

General Grievance 05.08.2024 17:18

@GeneralGrivance, насколько мне известно, в спецификациях указано, что [ и ] манипулируют только указателем инструкции, а не указателем памяти.

Aritro Shome 05.08.2024 17:19

исправить? возможно, посчитайте открытие/закрытие [ (приращение) и ] (уменьшение)

user85421 05.08.2024 17:20

@user85421 user85421 как решить, к какому ] или [ перейти?

Aritro Shome 05.08.2024 17:20

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

user85421 05.08.2024 17:22

@user85421 user85421, если возможно, проверьте редактирование один раз, я внедрил предложенные вами изменения, но ошибка все еще сохраняется.

Aritro Shome 05.08.2024 17:40

Разве вам не нужен лексер-парсер дерева, что-то, что, скажем, ANTLR4 может генерировать?

Hovercraft Full Of Eels 05.08.2024 17:53

@HovercraftFullOfEels пытается учиться на практике и понимает, что язык настолько сложен, что ему нужен синтаксический анализатор лексера дерева

Aritro Shome 05.08.2024 17:54

что произойдет, если tape[ptr] не равно нулю для [, т. е. не прыгает, например, 8 для первого [ ? (или если он равен нулю для ])

user85421 05.08.2024 18:06

(отладка должна показать проблему)

user85421 05.08.2024 18:13

Пожалуйста: 1) используйте отладчик; 2) начните тестирование с более простых программ, например, с одним циклом (+++[-]); 3) добавить какую-нибудь трассировку (System.out.print* или логирование)

user85421 05.08.2024 18:18

Подсказка: ctr = 0; for (;ctr !=0;...) никогда не будет зацикливаться (также не рекомендуется инициализировать переменную цикла вне for, если в этом нет необходимости - но это всего лишь соглашение/практика, а не проблема)

user85421 05.08.2024 18:26

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

user85421 07.08.2024 09:08
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
1
15
72
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

в обновленной реализации есть несколько небольших ошибок, поэтому вот один из возможных способов сделать это правильно:

case '[':
    if (tape[ptr] == 0) {
        ctr = 0;
        do {
            ctr += commands[i]=='['?1:0;
            ctr -= commands[i]==']'?1:0;
            i++;
        } while (ctr > 0);
    } else
        i++;
    break;
case ']':
    if (tape[ptr] != 0) {
        ctr = 0;
        do {
            ctr -= commands[i]=='['?1:0;
            ctr += commands[i]==']'?1:0;
            i--;
        } while (ctr > 0);
    }
    i++;
    break;

Другие вопросы по теме