Escribiendo un parser de Brainf*ck con BLK|Writting a brainf*ck parser with BLK|Escribindo 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.

At last! at this time BLK can compile a reasonable C subset... well, ok, it needs pointers and structures in order to have something decent, but the former are picky to simulate in a interpreter, and the structures are in the way. The important thing is that the general structure is more or less stable, even inside the prototyping branch, a consecuence is that is open to any participation :), so let's see an example of how to write a little brainf*ck parser.

Por fin! neste momento BLK pode compilar un subset razoable de C... ben, vale, restanlle os punteiros e as estructuras para ter algo decente, pero os primeiros son complicados de simular nun intérprete e as estructuras están en camiño. O importante é que a estructura xeral é relativamente estable, incluso dentro da rama de protipado, unha consecuencia é que está aberta a calquera participación :), así que vexamos un exemplo de como escribir un pequeno parser de 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

The first thing we'll do is to import the bytecode manager and prepare a constant to hold the memory size, in this case it will be a static

O primeiro que faremos será importar o xestor do bytecode e preparar unha constante para soster o tamaño da memoria, que neste caso será unha constante

from bytecode_manager import *

MEM_SIZE = 1024

El parser lo encapsularemos en una clase, con esta forma

The parser will be encapsulaten in a class with the following scheme

Encapsularemos o parser nunha clase coa seguinte 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

Now it comes the class intializer function, it receives the bytecode manager as the only parameter

Agora ven a función para iniciliza-la clase, recibe o xestor 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'

Now we have to prepare a space to hold the code, it gets grouped in frames (which nearly matches the concept of C blocks, they can represent functions, loops or condicionals), at least one is needed in the code to be executable by the interpreter, let's call it '_start'

Agora temos que preparar un espazo para o código, este agrupase en frames (que veñen sendo como bloques de C, podendo representar funcións, bucles ou condicionais), polo menos fai falla un para que o código poda ser executado polo intérprete, chamemoslle '_start'

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

La sintaxis es: Bytecode_manager.add_function(, , )

The syntax is: Bytecode_manager.add_function(, , )

A sintaxe é: 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

Now we can define variables and operations inside that, let's manually create a cursor variable to point the current memory position and assign it the value 0

Alí dentro xa podemos definir variables e operacións, creemos manualmente unha variable cursor para almacenar a posición de memoria na que estamos, e asignemoslle o 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.

Here we have two more functions, the first one, Bytecode_manager.add_variable receives the variable name, it's type, the frame and optionally a comment about the variable as parameters. Bytecode_manager.add_op adds an operation to the frame, the first parameter is the type of operation, the second one, a reference to the variable where the result will be stored, as third the function parámeters (it would be a list if there's more than one), and at last the frame.

Aquí temos duas funcións novas, a primeira é Bytecode_manager.add_variable, recive como parámetro o nome da variable, o seu tipo, o frame e opcionalmente un comentario sobre a variable. Bytecode_manager.add_op añade unha operación o frame, o primeiro parámetro é o tipo de operación, o seguinte unha referencia a variable donde se gardará o resultado, despois os parámetros da función (sería unha lista se fora máis de un), e por último o 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

It's also posible to create a new type to represent our variables, for example an array to keep track of the memory. Types are represented as dictionaries, al least with the attribute 'byte_size' with the obvious use, there are, too, other useful values like 'structure', which tells the size of the dimensions of the type, for example [2, 3] for a 2x3 array

Tamén podemos crear un novo tipo para representar as nosas variables, por exemplo un array para a memoria, os tipos representanse coma diccionarios, necesariamente co atributo 'byte_size' que indica o tamaño en bytes que se adicarán, tamén hay outros atributos que poden usarse, como 'structure', que indica o tamaño das dimensions do tipo, por exemplo [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'

The same can be done with variable references, if they are passed as dictionaries, it's possible to tell in 'pos' which part should be taken into account

O mesmo pasa coas referencias ás variables, se se indican cun diccionario podese especificar en 'pos' unha parte en concreto

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

The rest of the parse function doens't need anything new, just ADD_OP and SUB_OP over the two references we just defined, all less the '[' which will be mentioned next

O resto da función parse non necesita nada novo, só operacións ADD_OP e SUB_OP sobre as dúas referencias

   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

To add a flow contro operation we'll use Bytecode_manager.add_branch, pasing as first parameter the branching type (WHILE_BRANCH, IF_BRANCH, ELSE_BRANCH or DO_WHILE_BRANCH), the second is the condition, if it's different than 0, the conditional is executed or the loop keeps running, the third is the frame, it also optionally accepts two more, one for the operations which take place before the condition is checked and the last one for operations which takes place befere from the second iteration on, this operation returns a frame for the operations which takes place inside it

Para añadir control de fluxo utilizaremos Bytecode_manager.add_branch, pasándolle como primeiro parámetro o tipo de ramificación (WHILE_BRANCH, IF_BRANCH, ELSE_BRANCH ou DO_WHILE_BRANCH), o segundo parñametro é a condición, se é distinto de 0 executará o condicinal ou seguirá no bucle, o terceiro e o frame, ademais permite dous parámetros opcionais máis, o primeir indica as operacións que se executarán cada vez antes de comprobar o condicional, a outra, as que o farán antes de elas pero so a partir da segunda iteración

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

The rest of the code is generic enough to barely need any explanation

O resto do código é suficientemente xenérico como para non necesitar casi ninguha 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

Which does need get mentioned is Bytecode_manager.add_entry_point to point the entry function and Bytecode_manager.save to save the code

O que si que é necesario mencionar é Bytecode_manager.add_entry_point que indica a función pola que entrar, e Bytecode_manager.save para garda-lo código

El código completo está aquí:

The full source code is here:

O código completo está aquí:

brainfuck_parser.py Hasta otra

See you

Vémonos

Blogueando en tres idiomas|Blogging in three languages|Blogueando en tres idiomas » « Recopilación de links