Implementando bucles Brainfuck en un intérprete

Question

Quiero construir un intérprete Brainfuck (Maldito nombre) en mi lenguaje de programación recién creado para demostrar que es completo.

Ahora, todo está claro hasta el momento (<>+-,.) - excepto una cosa: Los bucles ([]). supongo que ya sabe la sintaxis BF (muy duro) de aquí en adelante:

• ¿Cómo implementar los bucles de BF en mi intérprete?

¿Cómo podría ser el pseudocódigo? ¿Qué debo hacer cuando el intérprete llega a un principio de ciclo ([) o un final de ciclo (])?

Comprobación de si el bucle debe continuar o parada no es el problema (current cell==0), pero:

• ¿Cuándo y dónde tengo que comprobar?
• ¿Cómo saber dónde se encuentra el principio del bucle?
• ¿Cómo manejar los bucles anidados?

Como se pueden anidar bucles Supongo que no puedo usar una variable que contenga la posición inicial del bucle de corriente.

He visto muy pequeños intérpretes de BF implementados en varios idiomas, me pregunto cómo lograron hacer que los bucles funcionen, pero no pueden resolverlo.

Answer 1

Al llegar al [, prueba el puntero de datos.

Si es falsa, se puede buscar la siguiente emparejado] carácter, contando cuantas [ ves y asegurarse de que ellos marcan como se ve cada ].

Si es cierto, debe realizar un seguimiento de su posición para poder volver a ella más adelante. Sugiero usar una pila. Presione la posición actual del programa en la pila, luego cuando llegue al ], pruebe el puntero de datos. Si es cierto, vaya a la posición más alta del programa en la pila. Si es falso, saca la posición de la pila y continúa.

Al anidar en bucles internos, la pila registrará limpiamente el contexto de cada bucle.

Ver stack (wikipedia). Esto es análogo a cómo los programas de ensamblaje se ocupan de las llamadas a funciones.

Answer 2

¿Cómo implemento los bucles BF en mi intérprete?

Ese es el punto: depende completamente de su idioma. Para el caso de un lenguaje de programación basado en pila (o cualquier lenguaje que pueda usar una pila), @rjh ha dado una buena solución. Otros idiomas utilizarían soluciones diferentes, como la recursión (es decir, el uso implícito de una pila).

Answer 3

Desde lo alto de la cabeza, puede haber algunos errores en ella, pero algo como esto debería funcionar:

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

llamada interpretar con el código fuente ck brainf *. El puntero p es a la posición actual de la memoria. Haga una llamada recursiva al detectar un [. Regrese de esta llamada recursiva cuando encuentre a].

Answer 4

Prefiero usar una tabla de salto (junto con la conversión de BF en bruto a 'bytecode'). La optimización de los intérpretes de BF es claramente el camino a seguir.

Answer 5

Aquí está mi versión "optimizadora" de intérprete, que precompila los saltos de bucle.

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 

Se hace un recorrido de prueba del código, hacer el seguimiento de los soportes (en una pila) y marca las direcciones Goto en paralelo jump array que más tarde se consulta durante la ejecución.

Comparé la velocidad de ejecución en el programa BF de larga duración (calcule N dígitos de Pi) y esto aumentó la velocidad 2x en comparación con una implementación inocente en la que se escanea la fuente para salir [y se escanea hacia atrás para activar].