Implementazione di loop di Brainfuck in un interprete

Question

Voglio creare un interprete di Brainfuck (Dannazione di quel nome) nel mio linguaggio di programmazione appena creato per dimostrare che è completo.

Ora, tutto è chiaro finora (<>+-,.) - tranne una cosa: I cicli ([]). Presumo che si conosce il (estremamente difficile) la sintassi BF da qui in poi:

• Come faccio a implementare il BF loop nel mio interprete?

Come potrebbe apparire lo pseudocodice? Cosa devo fare quando l'interprete raggiunge l'inizio di un loop ([) o un loop end (])?

Verificando il ciclo deve continuare o stop non è il problema (current cell==0), ma:

• Quando e dove devo controllare?
• Come sapere dove si trova l'inizio del ciclo?
• Come gestire i cicli annidati?

Come loop possono essere nidificati Suppongo che non sia possibile utilizzare solo una variabile contenente la posizione iniziale del loop corrente.

Ho visto interpreti BF molto piccoli implementati in varie lingue, mi chiedo come siano riusciti a far funzionare gli anelli ma non riescono a capirlo.

Answer 1

Quando si raggiunge [, si verifica il puntatore dati.

Se è falso, è possibile eseguire la scansione per la prossima abbinato] carattere, contando quanti [ si vede e fare in modo che li segnare come si vede ogni ].

Se è vero, è necessario tenere traccia della sua posizione in modo da poter tornare indietro in seguito. Suggerisco di usare una pila. Spingere la posizione del programma corrente sullo stack, quindi quando si raggiunge ], testare il puntatore dati. Se è vero, vai in cima alla posizione del programma in pila. Se è falso, sposta la posizione fuori dallo stack e continua.

Mentre si annidano nei loop interni, lo stack registra in modo pulito il contesto di ciascun ciclo.

Vedere stack (wikipedia). Questo è analogo al modo in cui i programmi di assemblaggio gestiscono le chiamate di funzione.

Answer 2

Come si implementano i loop BF nel mio interprete?

Questo è il punto: dipende interamente dalla lingua. Nel caso di un linguaggio di programmazione basato su stack (o qualsiasi linguaggio che possa utilizzare uno stack), @rjh ha fornito una buona soluzione. Altre lingue utilizzerebbero soluzioni diverse, come la ricorsione (cioè l'uso implicito di una pila).

Answer 3

Dalla cima della mia testa, potrebbero essere alcuni errori in esso, ma qualcosa di simile dovrebbe funzionare:

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

chiamata interpretare con il codice sorgente ck Brainf *. Il puntatore p si trova nella posizione di memoria corrente. Effettua una chiamata ricorsiva quando si individua un [. Torna da questa chiamata ricorsiva quando incontri un].

Answer 4

Preferisco utilizzare una tabella di salto (insieme alla conversione di BF non elaborato in "bytecode"). L'ottimizzazione degli interpreti BF è chiaramente la strada da percorrere!

Answer 5

Ecco la mia versione "ottimizzante" dell'interprete, che precompila i salti di loop.

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 

Fa un funzionamento a secco del codice, tenere traccia delle staffe (in una pila) e contrassegna gli indirizzi in parallelo Goto jump matrice che viene successivamente consultata durante l'esecuzione.

Ho confrontato la velocità di esecuzione sul programma BF di lunga durata (calcolare N cifre di Pi) e questo ha aumentato la velocità 2x rispetto a un'implementazione innocente in cui la sorgente viene scansionata in avanti per uscire [e scansionata all'indietro per eseguire il looping].