Приведенный ниже код представляет собой черновую реализацию интерпретатора 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 со страницы языка в Википедии.
++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
@IłyaBursov ах, я понимаю, какой будет подход к возможному исправлению? проблема с сопоставлением скобок вложенного цикла была и в Leetcode с использованием стеков, этот сценарий чем-то похож?
Кроме того, что происходит с ptr
, если условия не выполняются? Сейчас ты ничего не делаешь.
@GeneralGrivance, насколько мне известно, в спецификациях указано, что [ и ] манипулируют только указателем инструкции, а не указателем памяти.
исправить? возможно, посчитайте открытие/закрытие [
(приращение) и ]
(уменьшение)
@user85421 user85421 как решить, к какому ] или [ перейти?
если ищете замыкание ]
. каждый [
увеличивает счетчик, каждый ]
уменьшает счетчик, если счетчик достигает нуля, вы нашли соответствующее закрытие ]
(аналогично наоборот) ((возможная оптимизация, сохраните результаты для дальнейшего использования))
@user85421 user85421, если возможно, проверьте редактирование один раз, я внедрил предложенные вами изменения, но ошибка все еще сохраняется.
Разве вам не нужен лексер-парсер дерева, что-то, что, скажем, ANTLR4 может генерировать?
@HovercraftFullOfEels пытается учиться на практике и понимает, что язык настолько сложен, что ему нужен синтаксический анализатор лексера дерева
что произойдет, если tape[ptr]
не равно нулю для [
, т. е. не прыгает, например, 8 для первого [
? (или если он равен нулю для ]
)
(отладка должна показать проблему)
Пожалуйста: 1) используйте отладчик; 2) начните тестирование с более простых программ, например, с одним циклом (+++[-]
); 3) добавить какую-нибудь трассировку (System.out.print*
или логирование)
Подсказка: ctr = 0; for (;ctr !=0;...)
никогда не будет зацикливаться (также не рекомендуется инициализировать переменную цикла вне for
, если в этом нет необходимости - но это всего лишь соглашение/практика, а не проблема)
(для ясности: условие (второе выражение) в for()
всегда оценивается перед итерацией цикла, если условие оценивается как ложное, никакая (дальнейшая) итерация не выполняется; это также включает в себя перед первой итерацией, т.е. если условие ложно в самом начале, больше ничего из цикла for не выполняется)
в обновленной реализации есть несколько небольших ошибок, поэтому вот один из возможных способов сделать это правильно:
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;
основная проблема в том, что вы ищете не скобку
matching
, а первую доступную, поэтому вложенные циклы ломаются