Что не так с моим кодом парсера brainfuck?

Я пытаюсь написать программу на Java, которая может читать, компилировать и запускать исходные файлы brainfuck. (.bf). Я заставил его отлично работать с примером Hello World из Википедии, но он ломается на примере ROT13 (утверждает, что он достиг непревзойденного ], когда он действительно совпал).

Фактический код синтаксического анализатора весь написан в одном файле .JAVA, но сердцевина его (фактический парсер и работающий код) находится в методе ниже, doNow(char). Вот что представляют собой переменные: cells — массив символов для запуска (char[]); pointer — обходной путь Java для указания на адрес в массиве (short); PC — это программный счетчик (int), а loopStack — это стек адресов, соответствующих [s (в основном short[]). Это не проблема, так как они отлично работают в тесте Hello World. Метод, который принимает ввод, автоматически отфильтровывает лишние символы, и я убедился, что он отлично работает при проверке отладки.

Почему этот синтаксический анализатор не выполняет код ROT 13?

Код


Мой парсер, написанный на Java

  /** The array of data */
  private byte[] cells = new byte[Short.MAX_VALUE];
  /** The pointer that is manipulated by the user or program */
  private short pointer = 0;
  /** The program counter, to run compiled programs */
  private int PC = 0;
  /** The compiled commands */
  private ArrayPP<Character> commandBuffer = new ArrayPP<>();
  /** The stack of locations of loop brackets ({@code [}) in the command buffer */
  private ArrayPP<Short> loopStack = new ArrayPP<>();//ArrayPP is my proprietary augmented array object, which also functions as a perfectly working stack.

  public int doNow(char command) throws IOException
  {
    PC++;
    switch (command)
    {
      case '>':
        return ++pointer;
      case '<':
        return --pointer;
      case '+':
        return ++cells[pointer];
      case '-':
        return --cells[pointer];
      case '.':
        System.out.print((char)cells[pointer]);
        return 0;
      case ',':
        return cells[pointer] = (byte)System.in.read();
      case '[':
        if (cells[pointer] == 0)//If we're ready to skip this conditional
        {
          int oldPC = PC;
          try
          {
            while (getCompiledCommand(PC) != ']')//Find the matching ]
              PC++;
            PC++;//Now that we're at the ], skip over it to the next command
          }
          catch (ArrayIndexOutOfBoundsException e)
          {
            throw new NullPointerException("Unmatched '[' at " + oldPC);//If we try to reference a command outside the buffer
          }
        }
        else//if we want to enter this conditional
          loopStack.push(PC - 1);//Add the location of this conditional to the list of conditionals which we are in
        return PC;
      case ']':
        try
        {
          return PC = loopStack.pop();//Move us to the matching [ and remove it from the list of conditionals we're in
        }
        catch (ArrayIndexOutOfBoundsException e)
        {
          throw new NullPointerException("Unmatched ] at " + PC);//If the loop stack is empty
        }
      default:
        throw new AssertionError(command + " is not a valid command.");
    }
  }
  public char getCompiledCommand(int commandIndex)
  {
    return commandBuffer.get(commandIndex);//Look into the buffer of precompiled commands and fetch the one at the given index
  }

Пример Hello World (работает отлично)

+++++ +++++             initialize counter (cell #0) to 10
[                       use loop to set the next four cells to 70/100/30/10
    > +++++ ++              add  7 to cell #1
    > +++++ +++++           add 10 to cell #2 
    > +++                   add  3 to cell #3
    > +                     add  1 to cell #4
    <<<< -                  decrement counter (cell #0)
]                   
> ++ .                  print 'H'
> + .                   print 'e'
+++++ ++ .              print 'l'
.                       print 'l'
+++ .                   print 'o'
> ++ .                  print ' '
<< +++++ +++++ +++++ .  print 'W'
> .                     print 'o'
+++ .                   print 'r'
----- - .               print 'l'
----- --- .             print 'd'
> + .                   print '!'
> .                     print '\n'

Пример ROT 13 (Ввод моей тестовой консоли — M. Прерывается на команде 54 после нескольких итераций цикла)

-,+[                         Read first character and start outer character reading loop
    -[                       Skip forward if character is 0
        >>++++[>++++++++<-]  Set up divisor (32) for division loop
                               (MEMORY LAYOUT: dividend copy remainder divisor quotient zero zero)
        <+<-[                Set up dividend (x minus 1) and enter division loop
            >+>+>-[>>>]      Increase copy and remainder / reduce divisor / Normal case: skip forward
            <[[>+<-]>>+>]    Special case: move remainder back to divisor and increase quotient
            <<<<<-           Decrement dividend
        ]                    End division loop
    ]>>>[-]+                 End skip loop; zero former divisor and reuse space for a flag
    >--[-[<->+++[-]]]<[         Zero that flag unless quotient was 2 or 3; zero quotient; check flag
        ++++++++++++<[       If flag then set up divisor (13) for second division loop
                               (MEMORY LAYOUT: zero copy dividend divisor remainder quotient zero zero)
            >-[>+>>]         Reduce divisor; Normal case: increase remainder
            >[+[<+>-]>+>>]   Special case: increase remainder / move it back to divisor / increase quotient
            <<<<<-           Decrease dividend
        ]                    End division loop
        >>[<+>-]             Add remainder back to divisor to get a useful 13
        >[                   Skip forward if quotient was 0
            -[               Decrement quotient and skip forward if quotient was 1
                -<<[-]>>     Zero quotient and divisor if quotient was 2
            ]<<[<<->>-]>>    Zero divisor and subtract 13 from copy if quotient was 1
        ]<<[<<+>>-]          Zero divisor and add 13 to copy if quotient was 0
    ]                        End outer skip loop (jump to here if ((character minus 1)/32) was not 2 or 3)
    <[-]                     Clear remainder from first division if second division was skipped
    <.[-]                    Output ROT13ed character from copy and clear it
    <-,+                     Read next character
]                            End character reading loop

чтобы было понятно, вот где это ломается:

            >[+[<+>-]>+>>]   Special case: increase remainder / move it back to divisor / increase quotient
                         ^

person Ky Leggiero    schedule 08.10.2012    source источник
comment
@defaultlocale Что не так? Слишком долго? Вам нужны объявления переменных Java? Это не должно иметь значения; проблема связана с опубликованным методом. Но я добавлю их для вас.   -  person Ky Leggiero    schedule 08.10.2012
comment
знает ли getCompiledCommand() о вложенных '['-']'? Если это так, когда вы видите '[', вы переходите к самому первому ']', что неверно, например, [+++[----]+] - первый '[' совпадает с первым ']'. Ваш «Hello world» содержит только одну пару, поэтому он работает.   -  person Dmytro Sirenko    schedule 08.10.2012
comment
@Supuhstar, на самом деле все в порядке. Я надеюсь, что кому-то удастся помочь вам. Но если читатели смогут запустить ваш код, найти проблему будет намного проще.   -  person default locale    schedule 08.10.2012
comment
о, да. Извините. getCompiledCommand(int) просто возвращает символ, загруженный в память из файла или другого источника ввода текста. Он ничего не знает и не имеет условной логики. Хотя я вижу вашу точку зрения. Не могли бы вы опубликовать это как ответ?   -  person Ky Leggiero    schedule 08.10.2012
comment
@Supuhstar, я также думаю, что вы должны вывести и включить сведения об исключении. Трассировка стека, в частности.   -  person default locale    schedule 08.10.2012
comment
@Supuhstar Конечно, уже сделано :)   -  person Dmytro Sirenko    schedule 08.10.2012
comment
@defaultlocale трассировка стека Java очень неинформативна. Это просто Exception in thread "main" java.lang.NullPointerException: Unmatched ] at 54 at bf.BFParser.doNow(BFParser.java:207) Нет трассировки стека BF.   -  person Ky Leggiero    schedule 08.10.2012


Ответы (2)


Вы должны отслеживать вложенность '[]' в ветку case '[': теперь совпадение для первого '[' в [+++[----]+] является первым ']', что нехорошо.

person Dmytro Sirenko    schedule 08.10.2012
comment
Да, я на самом деле поймал это как раз перед тем, как вы опубликовали свой комментарий, указывающий на это. Я все равно приму ваш ответ, но я также опубликовал свое решение: 3 - person Ky Leggiero; 08.10.2012

Проблема


Кажется, проблема заключается в этой строке:

            while (getCompiledCommand(PC) != ']')//Find the matching ]

Это прекрасно работает в программе Hello World, поскольку в ней нет вложенных циклов. Однако с вложенными циклами мы сталкиваемся с проблемой, заключающейся в том, что он попадает в первый встреченный ], который не всегда совпадает с ].

Исправить


Одно из возможных решений — ввести переменную перед циклом while, скажем, loopCount, и увеличивать ее каждый раз, когда встречается [, а затем уменьшать ее, когда встречается ], а loopCount больше 0. Например:

        int loopCount = 0;
        while ((command = getCompiledCommand(PC)) != ']' && loopCount == 0)//Find the matching ]. We can save the return in command because we're done using it.
        {
          if (command == '[')//If we run into a nested loop
            loopCount++;
          else if (command == ']')//If we run into the end of a nested loop
            loopCount--;

          PC++;
        }
person Ky Leggiero    schedule 08.10.2012