Creazione di un parser di Brainfuck, qual è il metodo migliore per analizzare gli operatori di loop?

Question

Sto creando un parser Brainfuck (in un dialetto BASIC) alla fine per creare un interprete, ma ho realizzato che non è così semplice come ho pensato inizialmente. Il mio problema è che ho bisogno di un modo per analizzare accuratamente gli operatori di loop corrispondenti all'interno di un programma Brainfuck. Questo è un esempio di programma:

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

'[' = inizio ciclo

']' = fine del ciclo

devo registrare il punto di inizio e di fine di ciascun operatore ciclo corrispondente così posso saltare intorno alla fonte, se necessario. Alcuni loop sono soli, alcuni sono nidificati.

Quale sarebbe il modo migliore per analizzare questo? Stavo pensando di spostare il file sorgente creando un array 2D (o simili) che registra le posizioni di inizio e fine di ciascun operatore corrispondente, ma questo sembra un sacco di cose da fare e da fare attraverso la fonte. È questo il modo migliore per farlo?

Maggiori informazioni: Brainfuck homepage

EDIT: codice di esempio in qualsiasi lingua molto apprezzato.

Answer 1

Avete considerato di utilizzare una struttura di dati Stack per registrare "punti di salto" (cioè la posizione del puntatore di istruzioni).

Quindi in pratica ogni volta che si incontra un "[" si spinge la posizione corrente del puntatore di istruzioni su questa pila. Ogni volta che si incontra un "]" si ripristina il puntatore dell'istruzione sul valore attualmente in cima allo stack. Quando un ciclo è completo, lo fai fuori dalla pila.

Ecco un esempio in C++ con 100 celle di memoria. Il codice gestisce cicli annidati in modo ricorsivo e anche se non è raffinato dovrebbe illustrare i concetti ..

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

EDIT Ho appena andato oltre il codice di nuovo e ho capito che c'era un errore nel ciclo while che avrebbe 'saltare' loop analizzata se il valore del puntatore è 0. Questo è dove feci il cambiamento:

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

seguito è un'implementazione dello stesso parser ma senza usare ricorsione:

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

Ogni volta che si trova un '[', spingere la posizione corrente (o un altro token "marker" o un "contesto") su una pila. Quando vieni attraversato da un ']', sei alla fine del ciclo e puoi far scattare il segnalino indicatore dalla pila.

Poiché in BF il '[' verifica già una condizione e potrebbe essere necessario saltare oltre il ']', potrebbe essere necessario avere un indicatore che indica che le istruzioni devono essere saltate nel contesto del loop corrente.

Answer 3

Non ho codice di esempio, ma.

potrei provare a utilizzare una pila, insieme ad un algoritmo simile a questo:

1. (flusso di istruzioni esecuzione)
2. Encounter un [
3. Se il puntatore == 0, quindi continuare a leggere fino a quando non incontra il ']', e non eseguire alcuna istruzione finché non la raggiungi .. Vai al passaggio 1.
4. Se il puntatore! = 0, quindi spingere quella posizione su una pila.
5. Continua l'esecuzione di istruzioni
6. Se si verifica un]
7. Se puntatore == 0, pop il [fuori della pila, e procedere (passo goto 1)
8. Se puntatore! = 0, sbirciatina al in cima allo stack e vai in quella posizione. (Goto step 5)

Answer 4

Python 3.0 esempio dell'algoritmo pila descritto da altri manifesti:.

(Beh, ad essere onesti, questo solo trova parentesi corrispondenti non lo faccio so brainf * ck, quindi cosa fare dopo, non ne ho idea.)

Answer 5

Interessante, solo un paio di giorni fa, stavo scrivendo un interprete brainf * ck in Java.

Uno dei problemi riscontrati era che la spiegazione dei comandi su official page non era sufficiente e non menzionava la parte relativa ai cicli nidificati. Il Wikipedia page on Brainf*ck ha una sottosezione Commands che descrive il comportamento corretto.

Fondamentalmente per riepilogare il problema, la pagina ufficiale indica quando un'istruzione è una [ e la posizione di memoria corrente è 0, quindi passare al successivo ]. Il comportamento corretto è quello di passare alla corrispondente], non alla successiva.

Un modo per ottenere questo comportamento è di tenere traccia del livello di nidificazione. Ho finito per implementare questo con un contatore che teneva traccia del livello di nidificazione.

Quello che segue è parte del ciclo principale dell'interprete:

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

Ecco la leggenda per i nomi delle variabili:

• memory - celle di memoria per i dati.
• p - puntatore alla posizione corrente della cella di memoria.
• inst - un array con le istruzioni.
• pc - contatore di programma; punta all'istruzione corrente.
• nesting - livello di annidamento del loop corrente. nesting di 0 significa che la posizione corrente non è in un ciclo annidato.

Fondamentalmente, quando si incontra un ciclo di apertura [, la posizione di memoria corrente viene controllato per vedere se il valore è 0. In questo caso, viene inserito un ciclo while per passare allo ] corrispondente.

Il modo in cui il nesting viene gestito è la seguente:

1. Se un [ si incontra durante la ricerca per il corrispondente ciclo di chiusura ], la variabile nesting viene incrementato di 1 per indicare che abbiamo inserito un ciclo annidato.

2. Se si verifica un ], e:

   a. Se la variabile nesting è maggiore di 0, la variabile nesting viene decrementata di 1 per indicare che abbiamo lasciato un ciclo nidificato.

   b. Se la variabile nesting è 0, allora sappiamo che è stata rilevata la fine del ciclo, quindi la ricerca della fine del ciclo nel ciclo while viene terminata eseguendo un'istruzione break.

Ora, la parte successiva è quella di gestire la chiusura del ciclo da ]. Analogamente all'apertura del loop, utilizzerà il contatore nesting per determinare il livello di annidamento corrente del loop e provare a trovare l'apertura del loop corrispondente [.

Questo metodo potrebbe non essere il modo più elegante di fare le cose, ma sembra essere orientato alle risorse perché richiede solo una variabile extra da utilizzare come contatore per il livello di annidamento corrente.

(Naturalmente, "risorsa-friendly" sta ignorando il fatto che questo interprete è stato scritto in Java - Volevo solo scrivere del codice rapida e Java è capitato di essere quello che ho scritto in.)

Answer 6

Ed ecco lo stesso codice che ho dato come esempio in precedenza in C++, ma portato su VB.NET. Ho deciso di postarlo qui da quando Gary ha detto che stava cercando di scrivere il suo parser in un dialetto 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

questa domanda è un po 'vecchio, ma volevo dire che le risposte qui mi ha aiutato a decidere il percorso da seguire quando si scrive il mio Brainf ** k interprete. Ecco il prodotto finale:

#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

Il metodo canonico per l'analisi di una grammatica context-free è quello di utilizzare uno stack. Qualcos'altro e stai lavorando troppo e rischiando la correttezza.

Si consiglia di utilizzare un generatore di parser come tazza o yacc, dato che gran parte del lavoro sporco è fatto per te, ma con una lingua semplice come BF, potrebbe essere eccessivo.

Answer 9

Sembra che questa domanda sia diventata un sondaggio "post your bf interpreter".

Quindi, ecco la mia che ho appena ricevuto a lavorare:

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

} 

Questo dovrebbe funzionare. Devi modificarlo un po '. Questo è in realtà un esempio standard di come funziona l'interprete brainfuck. Ho modificato in modo da utilizzare nella mia app, tra parentesi sono gestite c'è:

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