4

我正在尝试用 Java 编写一个程序,它可以读取、编译和运行Brainfuck源文件 ( .bf)。我已经让它与 Wikipedia 的 Hello World 示例一起正常工作,但它在 ROT13 示例中中断(声称它]在实际匹配时达到了无与伦比的)。

实际的解析器代码都写在一个.JAVA文件中,但它的核心(真正的大脑解析器和运行代码)在下面的方法中,doNow(char). 以下是变量的含义:cells是要运行的字符数组 ( char[]);pointer是指向数组中地址的 Java 解决方法 ( short);PC是程序计数器 ( int),并且loopStack是对应于[s 的地址堆栈(基本上是 a 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
                         ^
4

2 回答 2

5

您应该跟踪 '[' 案例分支中的 '[]' 嵌套:现在,第一个 '[' 的匹配[+++[----]+]是第一个 ']',这是不好的。

于 2012-10-08T05:29:45.413 回答
4

问题


看来问题出在这一行:

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

这在 Hello World 程序中运行良好,因为它没有嵌套循环。但是,对于嵌套循环,我们会遇到第一个遇到的问题],这并不总是匹配的]

使固定


一种可能的解决方法是在 while 循环之前引入一个变量,例如loopCount,并在每次遇到 a 时将其递增,然后在遇到 a 且大于 0[时将其递减。例如:]loopCount

        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++;
        }
于 2012-10-08T05:32:23.867 回答