創建一個Brainfuck解析器，什麼是解析循環運算符的最佳方法？

Question

我創建了一個Brainfuck解析器（用BASIC語言）最終創建了一個解釋器，但我意識到它並不像我第一次想到的那樣直截了當。我的問題是我需要一種方法來精確地解析Brainfuck程序中的匹配循環運算符。這是一個示例方案：

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

循環=結束「[」 =環路的

開始「]」

我需要記錄每個匹配迴路操作的開始和結束點，以便我可以根據需要在源代碼中跳轉。有些循環是獨立的，有些循環是嵌套的。

什麼是解析這個最好的方法是什麼？我想可能是通過源文件創建一個二維數組（或類似的）來記錄每個匹配運算符的開始和結束位置，但是這看起來像是很多'通過源代碼來'和'fro'ing'。這是做這件事的最好方法嗎？

更多信息：Brainfuck homepage

編輯：任何語言的示例代碼不勝感激。

Answer 1

你有沒有使用堆棧數據結構來記錄「跳點」（即指令指針的位置）考慮。

所以基本上，每一次你遇到一個「[」你這個堆棧上推指令指針的當前位置。無論何時遇到「]」，您都將指令指針重置爲當前位於堆棧頂部的值。當循環完成時，將其從堆棧中彈出。

這裏是C中的例子與++ 100的存儲器單元。該代碼遞歸處理嵌套循環，雖然它不精就應該說明概念..

char cells[100] = {0}; // define 100 memory cells 
char* cell = cells;  // set memory pointer to first cell 
char* ip = 0;   // define variable used as "instruction pointer" 

void interpret(static char* program, int* stack, int sp) 
{ 
    int tmp; 
    if(ip == 0)    // if the instruction pointer hasn't been initialized 
     ip = program;  // now would be a good time 

    while(*ip)    // this runs for as long as there is valid brainF**k 'code' 
    { 
     if(*ip == ',') 
      *cell = getch(); 
     else if(*ip == '.') 
      putch(*cell); 
     else if(*ip == '>') 
      cell++; 
     else if(*ip == '<') 
      cell--; 
     else if(*ip == '+') 
      *cell = *cell + 1; 
     else if(*ip == '-') 
      *cell = *cell - 1; 
     else if(*ip == '[') 
     {   
      stack[sp+1] = ip - program; 
      *ip++; 
      while(*cell != 0) 
      { 
       interpret(program, stack, sp + 1); 
      } 
      tmp = sp + 1; 
      while((tmp >= (sp + 1)) || *ip != ']') 
      { 
       *ip++; 
       if(*ip == '[') 
        stack[++tmp] = ip - program; 
       else if(*ip == ']') 
        tmp--; 
      }   
     } 
     else if(*ip == ']') 
     { 
      ip = program + stack[sp] + 1; 
      break; 
     } 
     *ip++;  // advance instruction 
    } 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int stack[100] = {0}; // use a stack of 100 levels, modeled using a simple array 
    interpret(",>,>++++++++[<------<------>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]>>>++++++[<++++++++>-],<.>.", stack, 0); 
    return 0; 
} 

編輯 我只是對代碼又去，我意識到有一個在while循環將錯誤「跳過」解析環路如果指針的值是0。這就是我所做的更改：

while((tmp >= (sp + 1)) || *ip != ']')  // the bug was tmp > (sp + 1) 
{ 
ip++; 
if(*ip == '[') 
    stack[++tmp] = ip - program; 
else if(*ip == ']') 
    tmp--; 
} 

下面是相同的解析器的實現，但不使用遞歸：

char cells[100] = {0}; 
void interpret(static char* program) 
{ 
    int cnt;    // cnt is a counter that is going to be used 
          //  only when parsing 0-loops 
    int stack[100] = {0}; // create a stack, 100 levels deep - modeled 
          //  using a simple array - and initialized to 0 
    int sp = 0;   // sp is going to be used as a 'stack pointer' 
    char* ip = program; // ip is going to be used as instruction pointer 
          // and it is initialized at the beginning or program 
    char* cell = cells; // cell is the pointer to the 'current' memory cell 
          //  and as such, it is initialized to the first 
          //  memory cell 

    while(*ip)    // as long as ip point to 'valid code' keep going 
    { 
     if(*ip == ',') 
      *cell = getch(); 
     else if(*ip == '.') 
      putch(*cell); 
     else if(*ip == '>') 
      cell++; 
     else if(*ip == '<') 
      cell--; 
     else if(*ip == '+') 
      *cell = *cell + 1; 
     else if(*ip == '-') 
      *cell = *cell - 1; 
     else if(*ip == '[') 
     {   
      if(stack[sp] != ip - program) 
       stack[++sp] = ip - program; 

      *ip++; 

      if(*cell != 0) 
       continue; 
      else 
      {     
       cnt = 1; 
       while((cnt > 0) || *ip != ']') 
       { 
        *ip++; 
        if(*ip == '[') 
        cnt++; 
        else if(*ip == ']') 
        cnt--; 
       } 
       sp--; 
      } 
     }else if(*ip == ']') 
     {    
      ip = program + stack[sp]; 
      continue; 
     } 
     *ip++; 
    } 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    // define our program code here.. 
    char *prg = ",>++++++[<-------->-],[<+>-]<."; 

    interpret(prg); 
    return 0; 
} 

Answer 2

每次找到一個「[」，按當前位置（或另一種「標記」令牌或「上下文」）的堆疊上的時間。當你來到一個']'時，你處於循環的結尾，你可以從棧中彈出標記記號。

由於BF的「[」已檢查的條件和可能需要跳過去的「]」，你可能希望有一個標誌，指示說明應在電流回路上下文被跳過。

Answer 3

我沒有示例代碼，但是。

我可能會嘗試使用堆棧，伴隨着這樣的算法：

1. （執行指令流）
2. 遇到[
3. 如果指針== 0，然後繼續讀，直到你遇到']'，不要執行任何指令，直到達到它。轉到步驟1.
4. 如果指針！= 0，則將該位置推入堆棧。
5. 繼續執行指令
6. 如果遇到]
7. 如果指針== 0，彈出[從堆棧，並且繼續進行（步驟轉到1）
8. 如果指針！= 0，在偷看在堆棧頂部，然後轉到那個位置。 （轉到步驟5）通過其他海報中描述的堆棧算法的

Answer 4

的Python

3.0例子：

（當然，是誠實的，但是這僅發現匹配括號我不知道brainf * ck，接下來該怎麼做，我不知道。）

Answer 5

有趣的是，就在兩天前，我正在用Java編寫一個brainf * ck解釋器。

我遇到的問題之一是official page上的命令解釋不夠，並沒有提到有關嵌套循環的部分。 Wikipedia page on Brainf*ck有一個描述正確行爲的Commands小節。

基本上總結問題，該負責人表示頁的指令時是[和當前存儲位置是0，然後跳轉到下一個]。正確的行爲是跳轉到對應的]，而不是下一個。

實現此行爲的一種方法是跟蹤嵌套的級別。我最終通過一個跟蹤嵌套級別的計數器來實現這一點。

以下是翻譯的主循環的一部分：

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); 

下面是變量名的傳說：

• memory - 存儲單元的數據。
• p - 指向當前內存單元位置的指針。
• inst - 一個包含指令的數組。
• pc - 程序計數器;指向當前的指令。
• nesting - 當前循環的嵌套級別。 0表示當前位置不在嵌套循環中。

基本上，當遇到循環開口[時，當前存儲器位置進行檢查，看是否該值0。如果是這種情況，則輸入while循環跳轉到相應的]。

嵌套的處理方式如下：

1. 如果同時尋求相應環路的閉合]遇到[，則nesting變量由1爲了表明我們有遞增進入一個嵌套循環。

2. 如果遇到]和：

   一個。如果nesting變量大於0更大，那麼nesting變量由1遞減，表明我們已經留下了一個嵌套循環。

   b。如果nesting變量是0，那麼我們就知道了循環的結束已經遇到過，所以尋求在while循環的循環結束時通過執行break聲明終止。現在

，接下來的部分是由]處理循環的結束。類似於環的開通，它將使用nesting計數器，以確定循環的當前嵌套級別，並試圖找到相應的環狀開口[。

這種方法可能不是最優雅的方式做事情，但現在看來似乎是資源友好，因爲它只需要一個額外的變量作爲當前嵌套級別的計數器使用。

（當然，「資源型」是忽略這個解釋器Java編寫的事實 - 我只是想要寫一些簡單的代碼和Java正好是我寫它）。

Answer 6

這裏的代碼與我之前在C++中的例子相同，但移植到了VB.NET。我決定在這裏發佈它，因爲加里提到他試圖用BASIC語言編寫他的解析器。

Public cells(100) As Byte 

Sub interpret(ByVal prog As String) 
    Dim program() As Char 

    program = prog.ToCharArray() ' convert the input program into a Char array 

    Dim cnt As Integer = 0  ' a counter to be used when skipping over 0-loops          
    Dim stack(100) As Integer  ' a simple array to be used as stack 
    Dim sp As Integer = 0   ' stack pointer (current stack level) 
    Dim ip As Integer = 0   ' Instruction pointer (index of current instruction) 
    Dim cell As Integer = 0  ' index of current memory 

    While (ip < program.Length) ' loop over the program 
     If (program(ip) = ",") Then 
      cells(cell) = CByte(AscW(Console.ReadKey().KeyChar)) 
     ElseIf (program(ip) = ".") Then 
      Console.Write("{0}", Chr(cells(cell))) 
     ElseIf (program(ip) = ">") Then 
      cell = cell + 1 
     ElseIf (program(ip) = "<") Then 
      cell = cell - 1 
     ElseIf (program(ip) = "+") Then 
      cells(cell) = cells(cell) + 1 
     ElseIf (program(ip) = "-") Then 
      cells(cell) = cells(cell) - 1 
     ElseIf (program(ip) = "[") Then 
      If (stack(sp) <> ip) Then 
       sp = sp + 1 
       stack(sp) = ip 
      End If 

      ip = ip + 1 

      If (cells(cell) <> 0) Then 
       Continue While 
      Else 
       cnt = 1 
       While ((cnt > 0) Or (program(ip) <> "]")) 
        ip = ip + 1 
        If (program(ip) = "[") Then 
         cnt = cnt + 1 
        ElseIf (program(ip) = "]") Then 
         cnt = cnt - 1 
        End If 
       End While 
       sp = sp - 1 
      End If 
     ElseIf (program(ip) = "]") Then 
      ip = stack(sp) 
      Continue While 
     End If 
     ip = ip + 1 
    End While 
End Sub 

Sub Main() 
    ' invoke the interpreter 
    interpret(",>++++++[<-------->-],[<+>-]<.") 
End Sub 

Answer 7

這個問題是有點老了，但我想說的是，答案在這裏幫我決定寫我自己的Brainf **畝解釋時採取的路線。這是最終產品：

#include <stdio.h> 

char *S[9999], P[9999], T[9999], 
    **s=S, *p=P, *t=T, c, x; 

int main() { 
    fread(p, 1, 9999, stdin); 
    for (; c=*p; ++p) { 
     if (c == ']') { 
      if (!x) 
       if (*t) p = *(s-1); 
       else --s; 
      else --x; 
     } else if (!x) { 
      if (c == '[') 
       if (*t) *(s++) = p; 
       else ++x; 
      } 

      if (c == '<') t--; 
      if (c == '>') t++; 
      if (c == '+') ++*t; 
      if (c == '-') --*t; 
      if (c == ',') *t = getchar(); 
      if (c == '.') putchar(*t); 
     } 
    } 
} 

Answer 8

解析上下文無關語法的規範方法是使用堆棧。除此之外，你正在努力工作並冒着正確的風險。

您可能需要使用一個解析器生成像杯或YACC，因爲有很多骯髒的工作是爲你做，但作爲BF一樣簡單的語言，它可能是矯枉過正。

Answer 9

它看起來像這個問題已經成爲「後你的BF解釋」調查。

因此，這裏是我的，我剛工作：

#include <assert.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <string.h> 
#include <sys/mman.h> 
#include <sys/types.h> 
#include <sys/stat.h> 
#include <fcntl.h> 
#include <unistd.h> 

void error(char *msg) { 
    fprintf(stderr, "Error: %s\n", msg); 
} 

enum { MEMSIZE = 30000 }; 

char *mem; 
char *ptr; 
char *prog; 
size_t progsize; 

int init(char *progname) { 
    int f,r; 
    struct stat fs; 
    ptr = mem = calloc(MEMSIZE, 1); 
    f = open(progname, O_RDONLY); 
    assert(f != -1); 
    r = fstat(f, &fs); 
    assert(r == 0); 
    prog = mmap(NULL, progsize = fs.st_size, PROT_READ, MAP_PRIVATE, f, 0); 
    assert(prog != NULL); 
    return 0; 
} 

int findmatch(int ip, char src){ 
    char *p="[]"; 
    int dir[]= { 1, -1 }; 
    int i; 
    int defer; 
    i = strchr(p,src)-p; 
    ip+=dir[i]; 
    for (defer=dir[i]; defer!=0; ip+=dir[i]) { 
     if (ip<0||ip>=progsize) error("mismatch"); 
     char *q = strchr(p,prog[ip]); 
     if (q) { 
      int j = q-p; 
      defer+=dir[j]; 
     } 
    } 
    return ip; 
} 

int run() { 
    int ip; 
    for(ip = 0; ip>=0 && ip<progsize; ip++) 
     switch(prog[ip]){ 
     case '>': ++ptr; break; 
     case '<': --ptr; break; 
     case '+': ++*ptr; break; 
     case '-': --*ptr; break; 
     case '.': putchar(*ptr); break; 
     case ',': *ptr=getchar(); break; 
     case '[': /*while(*ptr){*/ 
        if (!*ptr) ip=findmatch(ip,'['); 
        break; 
     case ']': /*}*/ 
        if (*ptr) ip=findmatch(ip,']'); 
        break; 
     } 

    return 0; 
} 

int cleanup() { 
    free(mem); 
    ptr = NULL; 
    return 0; 
} 

int main(int argc, char *argv[]) { 
    init(argc > 1? argv[1]: NULL); 
    run(); 
    cleanup(); 
    return 0; 
} 

Answer 10

package interpreter; 

import java.awt.event.ActionListener; 

import javax.swing.JTextPane; 

public class Brainfuck { 

    final int tapeSize = 0xFFFF; 
    int tapePointer = 0; 
    int[] tape = new int[tapeSize]; 
    int inputCounter = 0; 

    ActionListener onUpdateTape; 

    public Brainfuck(byte[] input, String code, boolean debugger, 
      JTextPane output, ActionListener onUpdate) { 
     onUpdateTape = onUpdate; 
     if (debugger) { 
      debuggerBF(input, code, output); 
     } else { 
      cleanBF(input, code, output); 
     } 
    } 

    private void debuggerBF(byte[] input, String code, JTextPane output) { 
     for (int i = 0; i < code.length(); i++) { 
      onUpdateTape.actionPerformed(null); 
      switch (code.charAt(i)) { 
      case '+': { 
       tape[tapePointer]++; 
       break; 
      } 
      case '-': { 
       tape[tapePointer]--; 
       break; 
      } 
      case '<': { 
       tapePointer--; 
       break; 
      } 
      case '>': { 
       tapePointer++; 
       break; 
      } 
      case '[': { 
       if (tape[tapePointer] == 0) { 
        int nesting = 0; 

        while (true) { 
         ++i; 

         if (code.charAt(i) == '[') { 
          ++nesting; 
          continue; 
         } else if (nesting > 0 && code.charAt(i) == ']') { 
          --nesting; 
          continue; 
         } else if (code.charAt(i) == ']' && nesting == 0) { 
          break; 
         } 
        } 
       } 
       break; 
      } 
      case ']': { 
       if (tape[tapePointer] != 0) { 
        int nesting = 0; 

        while (true) { 
         --i; 

         if (code.charAt(i) == ']') { 
          ++nesting; 
          continue; 
         } else if (nesting > 0 && code.charAt(i) == '[') { 
          --nesting; 
          continue; 
         } else if (code.charAt(i) == '[' && nesting == 0) { 
          break; 
         } 
        } 
       } 
       break; 
      } 
      case '.': { 
       output.setText(output.getText() + (char) (tape[tapePointer])); 
       break; 
      } 
      case ',': { 
       tape[tapePointer] = input[inputCounter]; 
       inputCounter++; 
       break; 
      } 
      } 
     } 
    } 

    private void cleanBF(byte[] input, String code, JTextPane output) { 
     for (int i = 0; i < code.length(); i++) { 
      onUpdateTape.actionPerformed(null); 
      switch (code.charAt(i)) { 
      case '+':{ 
       tape[tapePointer]++; 
       break; 
      } 
      case '-':{ 
       tape[tapePointer]--; 
       break; 
      } 
      case '<':{ 
       tapePointer--; 
       break; 
      } 
      case '>':{ 
       tapePointer++; 
       break; 
      } 
      case '[': { 
       if (tape[tapePointer] == 0) { 
        int nesting = 0; 

        while (true) { 
         ++i; 

         if (code.charAt(i) == '[') { 
          ++nesting; 
          continue; 
         } else if (nesting > 0 && code.charAt(i) == ']') { 
          --nesting; 
          continue; 
         } else if (code.charAt(i) == ']' && nesting == 0) { 
          break; 
         } 
        } 
       } 
       break; 
      } 
      case ']': { 
       if (tape[tapePointer] != 0) { 
        int nesting = 0; 

        while (true) { 
         --i; 

         if (code.charAt(i) == ']') { 
          ++nesting; 
          continue; 
         } else if (nesting > 0 && code.charAt(i) == '[') { 
          --nesting; 
          continue; 
         } else if (code.charAt(i) == '[' && nesting == 0) { 
          break; 
         } 
        } 
       } 
       break; 
      } 
      case '.':{ 
       output.setText(output.getText()+(char)(tape[tapePointer])); 
       break; 
      } 
      case ',':{ 
       tape[tapePointer] = input[inputCounter]; 
       inputCounter++; 
       break; 
      } 
      } 
     } 
    } 

    public int[] getTape() { 
     return tape; 
    } 

    public void setTape(int[] tape) { 
     this.tape = tape; 
    } 

    public void editTapeValue(int counter, int value) { 
     this.tape[counter] = value; 
    } 

} 

這應該工作。你需要修改它。 這實際上是一個標準的例子，它是如何使用brainfuck解釋器的。我修改了它在我的應用程序中使用，括號在這裏處理：

case '[': { 
    if (tape[tapePointer] == 0) { 
     int nesting = 0; 

     while (true) { 
      ++i; 

      if (code.charAt(i) == '[') { 
       ++nesting; 
       continue; 
      } 
      else if (nesting > 0 && code.charAt(i) == ']') { 
       --nesting; 
       continue; 
      } 
      else if (code.charAt(i) == ']' && nesting == 0) { 
       break; 
      } 
     } 
    } 
    break; 
} 
case ']': { 
    if (tape[tapePointer] != 0) { 
     int nesting = 0; 

     while (true) { 
      --i; 

      if (code.charAt(i) == ']') { 
       ++nesting; 
       continue; 
      } 
      else if (nesting > 0 && code.charAt(i) == '[') { 
       --nesting; 
       continue; 
      } 
      else if (code.charAt(i) == '[' && nesting == 0) { 
       break; 
      } 
     } 
    } 
    break; 
}