在解釋器中實現Brainfuck循環

我想在我剛創建的編程語言中構建一個Brainfuck（該死的名字）解釋器來證明它是圖靈完備性的。在解釋器中實現Brainfuck循環

到目前爲止，一切都很清楚（<>+-,.） - 除了一件事情：循環（[]）。我假設你從這裏知道（非常難）BF語法：

如何實現BF在我的翻譯循環？

僞代碼是怎麼樣的？當解釋器達到循環開始（[）或循環結束（]）時，我該怎麼辦？

檢查循環是否應該繼續或停止是沒有問題的（current cell==0），但：

何時何地我都檢查？
如何知道循環開始的位置？
如何處理嵌套循環？

因爲循環可以嵌套，我想我不能只使用包含當前循環開始位置的變量。

我見過用各種語言實現的非常小的BF解釋器，我想知道他們是如何設法讓循環工作，但無法弄清楚。

來源

2010-04-06 sub

Duplicate：http://stackoverflow.com/questions/1055758/creating-a-brainfk-parser-whats-the-best-method-of-parsing-loop-operators – 2010-06-14 21:21:17

當您到達[時，您測試數據指針。

如果是假的，你可以掃描匹配]字符的下，計數有多少[看，並確保您標記它們趕走你看到每個]。

如果確實如此，則需要跟蹤其位置，以便稍後再跳回。我建議使用堆棧。將當前程序位置推入堆棧，然後在達到]時測試數據指針。如果是，則轉到堆棧頂部的程序位置。如果它是錯誤的，從堆棧中彈出並繼續。

當您嵌入到內部循環中時，堆棧將清晰地記錄每個循環的上下文。

請參閱stack (wikipedia)。這類似於彙編程序處理函數調用的方式。

來源

2010-04-06 20:47:32 rjh

我已經建成一個堆棧到我的編程語言，所以這很好：D感謝您的答案 – sub 2010-04-06 20:53:32

如何在解釋器中實現BF循環？

這就是要點 - 完全取決於您的語言。對於基於堆棧的編程語言（或任何可以使用堆棧的語言），@ rjh提供了一個很好的解決方案。其他語言會使用不同的解決方案，例如遞歸（即隱式使用堆棧）。

來源

2010-04-06 20:51:32

從我的頭頂，可能有一些誤差，但這樣的事情應該工作：

char* interpret(char* instructions){ 
    char* c = instructions; 
    while (*c) { 
    if (*c == ".") putchar(*p); 
    else if (*c == ",") *p = getchar(); 
    else if (*c == '+') (*p)++; 
    else if (*c == '-') (*p)--; 
    else if (*c == '<') p--; 
    else if (*c == '>') p++; 
    else if (*c == '[') c = interpret(c+1); 
    else if (*c == ']') { if (*p) c = instructions else return c; } 
    c++; 
    } 
    return 0; 
}

調用具有brainf * CK源代碼的解釋。指針p指向當前的內存位置。發現[。時發出遞歸調用。遇到a時從此遞歸調用返回]。

來源

2010-04-06 20:56:17 Jakob

嗯..只有當它從未遇到過「]」時，因爲如果是這樣，它將返回該字符的位置。但是，即使是由於輸入無效導致的段錯誤也不是很好，不是:)再一次，只是對解決方案的粗略說明，顯然不是完美無瑕的解決方案。 – Jakob 2010-04-06 21:55:58

哦，對了，我錯過了。我刪除了我的評論。 – sepp2k 2010-04-06 22:57:16

我更喜歡使用跳轉表（以及將原始BF轉換爲'字節碼'）。優化BF解釋器顯然是一條可行的路！

來源

2010-05-31 16:01:50 Charles

這是我的「優化」版本的解釋器，預編譯循環跳轉。

def interpret2(code): 
    data = [0] * 5000 # data memory 
    cp = 0    # code pointer 
    dp = 0    # data pointer 
    # pre-compile a jump table 
    stack = [] 
    jump = [None] * len(code) 
    for i,o in enumerate(code): 
     if o=='[': 
      stack.append(i) 
     elif o==']': 
      jump[i] = stack.pop() 
      jump[jump[i]] = i 
    # execute 
    while cp < len(code): 
     cmd = code[cp] 
     if cmd == '>': dp += 1 
     elif cmd == '<': dp -= 1 
     elif cmd == '+': data[dp] += 1 
     elif cmd == '-': data[dp] -= 1 
     elif cmd == '.': stdout.write(chr(data[dp])) 
     elif cmd == ',': data[dp] = ord(stdin.read(1)) 
     elif cmd == '[' and not data[dp]: # skip loop if ==0 
      cp = jump[cp] 
     elif cmd == ']' and data[dp]:  # loop back if !=0 
      cp = jump[cp] 
     cp += 1

它做的代碼的空運行，跟蹤托架（在堆疊）的標記和在平行jump陣列，其執行過程中稍後參考的跳轉地址。

我比較了長時間運行的BF程序（計算Pi的N個數字）的執行速度，並且與源向前掃描退出[並向後掃描循環]的無辜實現相比，這增加了速度2倍。

來源

2010-06-14 21:15:29

在解釋器中實現Brainfuck循環

回答

相關問題