Создание синтаксического анализатора Brainfuck, каков лучший метод парсинга операторов цикла?

Question

Создание синтаксического анализатора Brainfuck, каков лучший метод парсинга операторов цикла?

Самое простое решение - использовать $stateChangeStart и event.preventDefault() для отмены изменения состояния, когда пользователь не аутентифицирован, и перенаправить его в состояние auth , которое является страницей входа в систему.

angular
  .module('myApp', [
    'ui.router',
  ])
    .run(['$rootScope', 'User', '$state',
    function ($rootScope, User, $state) {
      $rootScope.$on('$stateChangeStart', function (event, toState, toParams, fromState, fromParams) {
        if (toState.name !== 'auth' && !User.authenticaded()) {
          event.preventDefault();
          $state.go('auth');
        }
      });
    }]
  );

5

parsing loops brainfuck

задан Jeremy Banks 29 January 2013 в 19:36

6 ответов

Interesting enough, just a couple days ago, I was writing a brainf*ck interpreter in Java.

One of the issues I was having was that the explanation of the commands at the official page was insufficient, and did not mention the part about nested loops. The Wikipedia page on Brainf*ck has a Commands subsection which describes the correct behavior.

Basically to summarize the problem, the official page says when an instruction is a [ and the current memory location is 0, then jump to the next ]. The correct behavior is to jump to the corresponding ], not the next one.

One way to achieve this behavior is to keep track of the level of nesting. I ended up implementing this by having a counter which kept track of the nesting level.

The following is part of the interpreter's main loop:

do {
  if (inst[pc] == '>') { ... }
  else if (inst[pc] == '<') { ... }
  else if (inst[pc] == '+') { ... }
  else if (inst[pc] == '-') { ... }
  else if (inst[pc] == '.') { ... }
  else if (inst[pc] == ',') { ... }
  else if (inst[pc] == '[') {
    if (memory[p] == 0) {
      int nesting = 0;

      while (true) {
        ++pc;

        if (inst[pc] == '[') {
          ++nesting;
          continue;
        } else if (nesting > 0 && inst[pc] == ']') {
          --nesting;
          continue;
        } else if (inst[pc] == ']' && nesting == 0) {
          break;
        }
      }
    }
  }
  else if (inst[pc] == ']') {
    if (memory[p] != 0) {
      int nesting = 0;

      while (true) {
        --pc;

        if (inst[pc] == ']') {
          ++nesting;
          continue;
        } else if (nesting > 0 && inst[pc] == '[') {
          --nesting;
          continue;
        } else if (inst[pc] == '[' && nesting == 0) {
          break;
        }
      }
    }
  }
} while (++pc < inst.length);

Here is the legend for the variable names:

memory -- the memory cells for the data.
p -- pointer to the current memory cell location.
inst -- an array holding the instructions.
pc -- program counter; points to the current instruction.
nesting -- level of the nesting of the current loop. nesting of 0 means that the current location is not in a nested loop.

Basically, when a loop opening [ is encountered, the current memory location is checked to see if the value is 0. If that is the case, a while loop is entered to jump to the corresponding ].

The way the nesting is handled is as follows:

If an [ is encountered while seeking for the corresponding loop closing ], then the nesting variable is incremented by 1 in order to indicate that we have entered a nested loop.
If an ] is encountered, and:

a. If the nesting variable is greater than 0, then the nesting variable is decremented by 1 to indicate that we've left a nested loop.

b. If the nesting variable is 0, then we know that the end of the loop has been encountered, so seeking the end of the loop in the while loop is terminated by executing a break statement.

Now, the next part is to handle the closing of the loop by ]. Similar to the opening of the loop, it will use the nesting counter in order to determine the current nesting level of the loop, and try to find the corresponding loop opening [.

This method may not be the most elegant way to do things, but it seems like it is resource-friendly because it only requires one extra variable to use as a counter for the current nesting level.

(Of course, "resource-friendly" is ignoring the fact that this interpreter was written in Java -- I just wanted to write some quick code and Java just happened to be what I wrote it in.)

2