Ir al contenido principal

Escribiendo un parser de Brainf*ck con BLK

¡Por fin! a estas alturas BLK permite compilar un razonable subset de C... bien, vale, faltan punteros y estructuras para tener algo decente, pero los primeros son escabrosos de simular con el intérprete, y las estructuras están en camino. Lo importante es que la estructura general es medianamente estable, aún dentro de la rama de prototipado, una consecuencia es que está abierto a cualquier participación :), así que veamos un ejemplo de como escribir un pequeño parser para brainf*ck.

Lo primero que haremos será importar el gestor de bytecode y preparar una constante para manejar el tamaño de la memoria, que en este caso será estática

from bytecode_manager import *

MEM_SIZE = 1024

El parser lo encapsularemos en una clase, con esta forma

class BrainfuckParser:

code = "" # Unparsed code

_bytecode_manager = None # Bytecode manager

global_frame = None # The global function

Ahora viene la función para inicializar la clase, recibe el gestor de bytecode como único parámetro

def init(self, bytecode_manager):

   self._bytecode_manager = bytecode_manager

Ahora tenemos que preparar un espacio para el código, el código se agrupa en frames (que vienen siendo como bloques en C, pueden representar funciones, bucles o condicionales), al menos uno es necesario para que el código sea ejecutable por el intérprete, llamemosle '_start'

self.global_frame = gframe = bytecode_manager.add_function("_start", void_type, [])

La sintaxis es: Bytecode_manager.add_function(, , )

Ahí dentro ya podemos definir variables y operaciones, creemos manualmente una variable cursor para controlar la posición en memoria, y asignémosle el valor 0

bytecode_manager.add_variable("cursor", int_type, gframe, "Cursor variable")

bytecode_manager.add_op(ASSIGNATION_OP, {"name": "cursor"}, 0, gframe)

Ahí tenemos dos funciones, la primera es Bytecode_manager.add_variable, recibe como parámetros el nombre de la variable, su tipo, el frame y opcionalmente un comentario sobre el uso de la variable. Bytecode_manager.add_op añade una operación al frame, el primer parámetro es el tipo de operación, el segundo una referencia a la variable donde se guardará el resultado, la tercera los parámetros (sería una lista si hay más de uno), y la cuarta el frame.

También podemos crear un nuevo tipo para representar nuestras variables, por ejemplo un array para la memoria, los tipos se representan como diccionarios con al menos el valor 'byte_size' que indica que cantidad de bytes se le dedicarán, además hay otros atributos que se pueden usar, como 'structure', que indica el tamaño de las dimensiones del tipo, por ejemplo [2, 3] para un array de 2x3

   tmp = {"byte-size": 4, "structure": [MEM_SIZE]}

   bytecode_manager.add_variable("mem", tmp, gframe, "Machine memory")

También se puede hacer lo mismo con las referencias a variables, si se indican con un diccionario se puede especificar en 'pos' que parte 'atacar'

def parse_brainfuck(self, frame):

   pointed_ref = {"name":"mem", "pos": ["cursor"]}

   cursor_ref = {"name":"cursor"}

El resto de la función parse no necesita de nada nuevo, solo operaciones ADD_OP y SUB_OP sobre las dos referencias que acabamos de definir, menos el '[' que mencinaremos a continuación

   while self.current < self.code_len:

       current_op = self.code[self.current]

       self.current += 1

       # Print

       if current_op == ".":

           self._bytecode_manager.add_op("putchar", {}, [pointed_ref],

frame, ".")

       # Read

       elif current_op == ",":

           self._bytecode_manager.add_op("getchar", pointed_ref, [],

frame, ",")

       # Inc

       elif current_op == "+":

           self._bytecode_manager.add_op(ADD_OP, pointed_ref,

[pointed_ref, 1], frame, "+")

       # Dec

       elif current_op == "-": self._bytecode_manager.add_op(SUB_OP,

pointed_ref, [pointed_ref, 1], frame, "-")

       # Push

       elif current_op == ">":

            self._bytecode_manager.add_op(ADD_OP, cursor_ref, [cursor_ref,

1], frame, ">")

       # Pop

       elif current_op == "<":

            self._bytecode_manager.add_op(SUB_OP, cursor_ref, [cursor_ref,

1], frame, "<")

       # While

       elif current_op == "[":

           b = self._bytecode_manager.add_branch(WHILE_BRANCH,

pointed_ref, frame)

           self.parse_brainfuck(b)



       # While-end

       elif current_op == "]":

           assert(frame != self.global_frame)

           return

Para añadir una operación de control de flujo utilizaremos Bytecode_manager.add_branch, pasandole como primer parámetro el tipo de ramificación (WHILE_BRANCH, IF_BRANCH, ELSE_BRANCH o DO_WHILE_BRANCH), el segundo parámetro es la condición, si es distinto de 0 se ejecuta el condicional o se sigue en el bucle, el tercero es el frame, además acepta otros dos más, uno para las operaciones que se realizarán antes de comprobar la condición, y el último para las operaciones que se realizaran antes de estas a partir del segundo paso (el paso del 'for'), esta operación devuelve un frame para añadir las operaciones que toman lugar dentro de el

b = self._bytecode_manager.add_branch(WHILE_BRANCH, pointed_ref, frame)

El resto del código es lo suficientemente genérico como para necesitar casi ninguna explicación

def parse(self, f):

   self.code = f.read()



   self.current = 0

   self.code_len = len(self.code)

   self.parse_brainfuck(self.global_frame)

if name=="main":

output = "a.blk"

if len(argv) < 2:

   print "%s " % argv[0]

   exit(0)

try:

   f = open(argv[1], "rt")

except:

   print "Error reading %s" % argv[1]

else:

   bm = BytecodeManager()

   bm.add_entry_point("_start")

   bfp = BrainfuckParser(bm)



   try:

       bfp.parse(f)



   except ParsingException, e:

       print "Parsing exception: %s" % e

       exit(2)



   bm.save(output)

Lo que si que se hace necesario mencionar es Bytecode_manager.add_entry_point que indica la función por la que entrar y Bytecode_manager.save para guardar el código

El código completo está aquí:

brainfuck_parser.py Hasta otra