Saltar ó contido principal

Escribindo un parser de brainf*ck con BLK

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.

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

Encapsularemos o parser nunha clase coa seguinte forma

class BrainfuckParser:

code = "" # Unparsed code

_bytecode_manager = None # Bytecode manager

global_frame = None # The global function

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

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, [])

A sintaxe é: Bytecode_manager.add_function(, , )

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)

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

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

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

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

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)

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

O código completo está aquí:

brainfuck_parser.py

Vémonos