From: Leandro Lucarella Date: Sat, 23 Aug 2008 01:01:30 +0000 (-0300) Subject: Enunciado e implementación de referencia del ejercicio 1 de 2008-2 X-Git-Url: https://git.llucax.com/personal/documentos.git/commitdiff_plain/c985393b6e6a238ecb71be740ef87d78116085c1?hp=f3d3907a6fe0c5dd15a74d9e9766a0f9dd26b00c Enunciado e implementación de referencia del ejercicio 1 de 2008-2 --- diff --git a/taller/ejercicios/ej1-20082/Makefile b/taller/ejercicios/ej1-20082/Makefile new file mode 100644 index 0000000..47c8921 --- /dev/null +++ b/taller/ejercicios/ej1-20082/Makefile @@ -0,0 +1,33 @@ + +all: ej1.pdf + +ej1.latex: esquema.eps + +%.latex: %.rst + rst2latex --language=es --use-verbatim-when-possible \ + --output-encoding=utf-8 $< > $@ + +%.dvi: %.latex + latex $< + latex $< + +%.pdf: %.dvi + dvipdf $< + +%.eps: %.dot + dot -Tps $< > $@ + +%.png: %.dot + dot -Tpng $< > $@ + +clean-latex: + $(RM) -v *.aux *.log *.out + +clean: clean-latex + $(RM) -v *.png *.eps *.latex *.dvi *~ + +clean-all: clean + $(RM) -v *.pdf + +.PHONY: clean clean-all clean-latex + diff --git a/taller/ejercicios/ej1-20082/ej1.rst b/taller/ejercicios/ej1-20082/ej1.rst new file mode 100644 index 0000000..a3beea7 --- /dev/null +++ b/taller/ejercicios/ej1-20082/ej1.rst @@ -0,0 +1,670 @@ +.. vim: set encoding=utf-8 filetype=rst sw=2 sts=2 et tw=74 : + + +========================================================================== + Taller de Programación I (75.42) +========================================================================== + + +-------------------------------------------------------------------------- + Ejercicio 1 - Mini Protocol Buffers +-------------------------------------------------------------------------- + + + +Objetivo +========================================================================== + +Repasar conceptos vistos en materias anteriores (algoritmos, estructuras +de datos, manejo de memoria, manipulación de archivos, el lenguaje de +programación C). + + +Introducción +========================================================================== + +Hay infinidad de `formatos para representación de datos`__. Según +para que se use, las técnicas varían drásticamente. No es lo mismo +la representación que se utiliza para persistir en disco que para +enviar datos por una red. Incluso las formas de representación pueden +variar para distintos tipos de redes o para distintos medios físicos +(no es lo mismo un disco *flash* que un disco rígido magnético +convencional). Tampoco es lo mismo representar datos para que sean +interpretados solo por la computadora que si tuviera que poder verlos +directamente un usuario. La representación varía también con la +estructura de los datos a representar también. + +__ http://es.wikipedia.org/wiki/Categoría:Protocolos_y_formatos_de_nivel_de_presentación + +Un desafío importante es construir formatos que sirvan de forma genérica +para representar cualquier tipo de dato, definiendo previamente un +*esquema*. Un formato extremadamente popular que hace esto es XML__. +Existen numerosas implementaciones de `parsers`__ XML que permiten +interpretar cualquier tipo de dato dado un `esquema`__ determinado. + +__ http://es.wikipedia.org/wiki/XML +__ http://es.wikipedia.org/wiki/Parser +__ http://es.wikipedia.org/wiki/DTD + +Sin embargo XML tiene varias contras y no siempre es conveniente su uso (a +pesar de que en la industria nadie parezca darse cuenta =), por ejemplo: + +* No es posible representar datos binarios sin *intervención* del usuario + (hay que elegir una codificación *externa* para representar datos + binario). +* Es muy ineficiente en cuanto a espacio. +* Es relativamente lento de interpretar. + +Un formato que resuelve estas desventajas (pero que, por supuesto, +tiene otras) es el propuesto por `Protocol Buffers`__, un proyecto que, +a pesar de su temprana edad, está teniendo mucha adopción (probablemente +por estar auspiciado por Google__). Se trata de un formato binario, muy +eficiente en términos de espacio y muy fácil y veloz para interpretar. + +__ http://code.google.com/p/protobuf/ +__ http://www.google.com/ + +El formato permite representar pares (clave, valor), donde la clave +es un valor numérico siempre y el valor puede ser de varios tipos: +enteros variables o fijos, con signo o sin signo, cadenas de bytes. A +su vez, puede dársele sentido especial a una cadena de bytes para que +represente otro set de pares (clave, valor), formando lo que se conoce +como un *mensaje embebido*, pudiendo construirse mensajes (estructuras +de datos) de una complejidad considerable. + + +Desarrollo +========================================================================== + +Se pide desarrollar un intérprete genérico, pero reducido, de Protocol +Buffers (PB). El programa debe ser capaz de interpretar un archivo +binario con formato de PB (base de datos) y, a partir de otro archivo +(*esquema*), imprimir los datos de forma legible para el usuario. + +.. figure:: esquema.eps + :alt: Esquema de flujo de datos + :align: center + + Esquema de flujo de datos + + +Archivo de esquemas +========================================================================== + +El archivo de esquemas solicitado en este trabajo es considerablemente +más simple que los archivos de `definiciones`__ que utiliza PB. + +__ http://code.google.com/apis/protocolbuffers/docs/proto.html + + +Léxico +-------------------------------------------------------------------------- + +Los siguientes *tokens* (especificados en ABNF_) pueden aparecer en +el archivo:: + + array = identifier "*" + identifier = ALPHA *(ALPHA / DIGIT) + eol = LF + sp = *WSP + +.. _ABNF: http://en.wikipedia.org/wiki/Augmented_Backus–Naur_Form + + +Sintaxis +-------------------------------------------------------------------------- + +La sintaxis del archivo, tomando como base los *tokens* especificados en +la sección anterior), es la siguiente (también especificada en ABNF_):: + + scheme = *eol *message + message = sp identifier sp eol *attribute eol *eol + attribute = sp (identifier / array) WSP sp identifier sp eol + + +Semántica +-------------------------------------------------------------------------- + +Un archivo de esquema está compuesto por 0 o más mensajes (regla +*message*), separados entre sí por una línea vacía. Un mensaje está +representado por un nombre (*identifier*) seguido de 0 o más atributos +(regla *attribute*), separados por un fin de línea. Un atributo a su vez, +se compone de un tipo (*identifier*) y un nombre (*identifier*). Un tipo +a su vez puede ser simple (*identifier*) o un arreglo (*array*), en cuyo +caso se representa con el nombre del tipo terminado con "*". Existen +2 tipos básicos: *int* y *string*. El resto de los tipos deben estar +definidos en el archivo en cualquier orden. + +Cada atributo tiene asociado un *tag* (en el sentido dado por PB) +implícito incremental, comenzando por 1. Dada la definición:: + + Persona + string nombre + string telefono + int edad + +El atributo ``nombre`` tiene el *tag* **1**, ``telefono`` el **2** y +``edad`` el **3**. + +Todos los campos son *requeridos*, excepto aquellos que tengan como tipo +un *array*, que serían *repetidos* (en el sentido dado por PB). + + +Ejemplo +-------------------------------------------------------------------------- + +Vemos como separar en estas 3 etapas la interpretación del siguiente +archivo de esquema:: + + Agenda + Persona* personas + + + Persona + string nombre + int edad + Telefono telefono + + Telefono + string tipo + int numero + +El primer paso es el análisis léxico: separar en *tokens*. Siguiendo lo +propuesto en la sección Léxico_, podemos ir viendo qué *tokens* +encontramos en el archivo (los "_" representan espacios en blanco): + +============= =============== +Contenido Tipo de *token* +============= =============== +"Agenda" identifier +"\n" eol +"__" sp +"Persona*" array +"_" sp +"personas" identifier +"\n" eol +"\n" eol +"\n" eol +"Persona" identifier +"\n" eol +"__" sp +"string" identifier +etc. etc. +============= =============== + +Por ejemplo, si en el archivo apareciera:: + + Agenda + Persona* 1persona + +Esto no sería válido léxicamente, ``1persona`` no es un *token* posible. + +Luego (en realidad generalmente se hace a medida que se van obteniendo los +*tokens*), hay que realizar el análisis sintáctico. Es decir, validar que +estos *tokens* encontrados, tengan el orden correcto y formen +construcciones sintácticas válidas. Para esto aplicamos las reglas de la +sección Sintaxis_. + +Un esquema es una *lista* de mensajes, por lo tanto buscamos un mensaje, +que se compone de un identificador, una nueva línea y una lista de +atributos (vamos verificando que los *tokens* lleguen en el orden +correcto). Un atributo a su vez, es un identificador o array seguido de +otro identificador. + +Con esta información podemos ir armando una representación estructurada +del archivo en memoria (conocida como AST__ o árbol abstracto de sintaxis) +que nos servirá para el próximo paso y para la decodificación de PB. + +__ http://en.wikipedia.org/wiki/Abstract_syntax_tree + +Si en el archivo apareciera:: + + Agenda + Persona* personas no_valido + +Esto sería léxicamente válido (todos los *tokens* son conocidos) pero +sintácticamente inválido, un atributo espera que luego del segundo +identificador solo hayan espacios en blanco o un fin de línea (y +encontramos otro identificador: ``no_valido``). + +Finalmente, una vez construído el AST, queda hacer el análisis semántico. +Es decir, el chequeo de tipos. Hay que verificar que todos los atributos +de todos los mensajes sean de un tipo conocido. + +Si en el archivo de esquema tuvieramos la siguiente definición de +``Agenda`` en vez de la original:: + + Agenda + NoExisto* personas + +Esto sería léxicamente válido, sintácticamente válido, pero semánticamente +inválido (el tipo NoExisto no está definido). + + +Codificación de Protocol Buffers +========================================================================== + +A continuación se explica un *subset* de la `codificación usada por +Protocol Buffers`__, que es lo que debe poder interpretar la aplicación +a desarrollar. La explicación está basada en la documentación de +Protocol Buffers, de manera tal de utilizar los mismos ejemplos para +que sea sencillo para el alumno ampliar los conceptos visitando la +fuente original. + +__ http://code.google.com/apis/protocolbuffers/docs/encoding.html + + +*Varints* de base 128 +-------------------------------------------------------------------------- + +Antes que nada es necesario entender un concepto básico para la +codificación de PB, *varints*. + +*Varints* es un método de serialización de enteros que utiliza uno o más +bytes. Números pequeños utilizan pequeñas cantidades de bytes. + +Cada byte en un *varint*, excepto el último byte, tiene el bit más +significativo (msb__) activado; esto indica que hay más bytes. Los 7 bits +más *bajos* de cada byte son utilizados para guardar, en representación de +complemento a 2, el número en grupos de 7 bits, estando el grupo menos +significativo primero. + +__ http://es.wikipedia.org/wiki/Bit_m%C3%A1s_significativo + +Por ejemplo, esta es la representación del número **1**:: + + 0000 0001 + ^ + msb + +Se puede representar en un solo byte, por lo tanto el msb está +desactivado. El número **130**, levemente más complicado, se representa +de la siguiente forma:: + + 1000 0010 0000 0001 + ^ ^ + msb msb + +¿Cómo saber que es el número **130**? Primero se descarta el msb de cada +byte, ya que sólo nos indica si se ha encontrado el fin de la +representación del número (como se puede ver, está activo solo en el +primer byte ya que hay más de un byte en este *varint*):: + + 1000 0010 0000 0001 + → 000 0010 000 0001 + +Luego hay que invertir los dos grupos de 7 bits porque, como recuedan, los +*varints* guardan el grupo menos significativo primero:: + + 000 0010 000 0001 + → 000 0001 000 0010 + +Finalmente, se concatenan para obtener el resultado final:: + + 000 0001 000 0010 + → 1000 0010 + +Cuyo valor es **130**. + +.. note:: + + Si bien un *varint* no tiene una limitación de tamaño o longitud, + en este trabajo se asumirá un tamaño máximo de 9 bytes (es decir, + se podrán representar enteros de 9*7 = 63 bits, es decir, tendrán + un valor máximo de 2^63-1 = 9.223.372.036.854.775.807), garantizando + de esta manera que cualquier varint entre en un entero de 64 bits + (por ejemplo, el tipo ``uint64_t`` de C99). + + +Estructura de un mensaje +-------------------------------------------------------------------------- + +Como saben, un Protocol Buffer es una serie de pares (clave, valor). La +versión binaria de un mensaje utiliza el *tag* del atributo como clave +(el nombre y tipo de cada atributo solo puede conocerse con precisión +utilizando el esquema del mensaje). + +Cuando un mensaje es codificado, las claves y valores son concatenados en +un flujo de bytes. Las claves se componen en realidad de 2 valores, el +*tag* asociado al atributo y un *wire type*, que provee la información +necesaria para saber el tamaño del valor que acompaña a la clave. + +Protocol Buffers soporta varios *wire types* pero en este ejercicio solo +deberán reconocerse los siguientes: + +======== ========================== ====================================== +Tipo Significado Utilizado para +======== ========================== ====================================== +0 *varint* *int* +2 delimitado por longitud *string*, mensajes embebidos +======== ========================== ====================================== + +Cada clave de un mensaje es un *varint* con el valor:: + + (tag << 3) | wire_type + +En otras palabras, los últimos 3 bits guardan el *wire type*. + +Ante un *wire type* desconocido deberá terminarse la ejecución del +programa con el código de error apropiado (ver `Valores de retorno`_). + + +Valores +-------------------------------------------------------------------------- + +Luego de una clave, viene un valor. Dependiendo del *wire type*, la +codificación de los valores varía. + +*Varint* +~~~~~~~~ + +La representación de un *varint* (*wire type* 0) es, como deben +imaginarse, un *varint*. En esta implementación limitada de Protocol +Buffers solamente el tipo básico *int* es representado con un *varint*. + +Delimitado por longitud +~~~~~~~~~~~~~~~~~~~~~~~ + +La representación de valor delimitado por tamaño (*wire type* 2) se +compone del largo del valor codificado como *varint* seguido por la +cantidad especificada de bytes de datos. + +Por ejemplo, un *string* con valor "testing", se representaría de la +siguiente forma (sólo se muestra el valor, se omite la clave):: + + 0x07 0x74 0x65 0x73 0x74 0x69 0x6e 0x67 + ^^^^ ^^^^ ^^^^ ^^^^ ^^^^ ^^^^ ^^^^ ^^^^ + longitud "t" "e" "s" "t" "i" "n" "g" + +Tanto los atributos de tipo *string* como lo mensajes embebidos se +representan con valores delimitados por tamaño. + +La única forma de distinguir si un valor es un *string* o un mensaje +embebido, es utilizando el esquema del mensaje. + + +Ejemplo de mensaje sencillo +-------------------------------------------------------------------------- + +Ahora que sabemos como se codifican los *varints*, las claves y los +valores, podemos ver un ejemplo de un mensaje simple basado en el +siguiente esquema:: + + Test1 + int a + +La representación de un mensaje de tipo *Test1*, cuyo valor de *a* sea +**150**, es la siguiente:: + + 0x08 0x96 0x01 = 0000 1000 1001 0110 0000 0001 + +Como vimos, un mensaje son pares (clave, valor), por lo tanto sabemos que +lo primero que hay que interpretar es una clave, que a su vez, sabemos +que se representa con un *varint*. Vemos que el primer byte tiene el +msb desactivado, así que el *varint* ocupa un solo byte: 0x08 = 0000 1000 + +Sabemos que los último 3 bits de una clave, son el *wire type*, por lo +tanto en este caso es 000: 0, lo que nos indica que el valor que seguirá +a la clave es otro *varint*. Los restantes 4 bits (desplazados hacia la +derecha 3 lugares, los lugares que ocupaban los bits del *wire type*) +sabemos que almacenan el *tag* del atributo, en este caso 0001 = 1:: + + 0x08 = 0000 1000 + ^-----~~~ + | | wire type = 0 + | | + | tag = 1 + | + msb = 0 + +Ahora decodificamos el valor, que ya sabemos que es un *varint*:: + + 0x96 0x01 = 1001 0110 0000 0001 + ^ ^ + msb msb + +Eliminamos msb, invertimos grupos de 7 bits y concatenamos:: + + 001 0110 000 0001 + → 000 0001 001 0110 + → 1001 0110 = 0x96 + +El resultado es 150. Ahora recordando el esquema del mensaje, observamos +que ``int a`` es el primer atributo del mensaje ``Test1``, por lo tanto le +corresponde el *tag* **1**. Luego, hemos decodificado un mensaje ``Test1`` +cuyo atributo ``a`` tiene el valor **150**. + +Si interpretáramos *tag* para los cuales el mensaje no tuviera un atributo +asociado, simplemente ignoramos ese par (clave, valor) y continuamos +leyendo los siguientes. + + +Ejemplo de mensaje con *arrays* +-------------------------------------------------------------------------- + +Supongamos que agregamos a nuestro esquema anterior el siguiente mensaje:: + + Test2 + int* b + +Si un mensaje de tipo ``Test2`` tuviera como atributo ``b`` dos enteros: +**150** y **1**, su representación sería:: + + 0x08 0x96 0x01 0x08 0x01 + ---- ^^^^^^^^^ ---- ^^^^ + | | | un varint = 1 + | | | + | | `-- clave, nuevamente tag = 1, wire type = 0 + | | + | un varint = 150, igual que en el ejemplo anterior + | + 0000 1010 = 0000 1000 <---- clave + ^-----~~~ + | | wire type = 0 + | | + | tag = 1 + | + msb = 0 + +Como puede observarse, simplemente se repite el *tag* varias veces. Y los +valores se agregan al *array* del atributo que corresponde a ese *tag*. + + +Ejemplo de mensaje compuesto +-------------------------------------------------------------------------- + +Supongamos que agregamos a nuestro esquema anterior el siguiente mensaje:: + + Test3 + Test1 c + +Si un mensaje de tipo ``Test3`` tuviera como atributo ``c`` un mensaje +de tipo ``Test1`` cuyo atributo ``a`` fuera **150**, su representación +sería:: + + 0x0a 0x03 0x08 0x96 0x01 + ---- ~~~~ ^^^^^^^^^^^^^^ + | | igual que el ejemplo del mensaje sencillo + | | + | longitud del mensaje embebido como varint = 3 + | + 0000 1010 = 0000 1010 <---- clave + ^-----~~~ + | | wire type = 2 + | | + | tag = 1 + | + msb = 0 + +El *wire type* es de tipo *delimitado por longitud*, el *tag* es **1** +(``c`` es el primer atributo del mensaje ``Test3``) y el valor de ``c`` es +0x08 0x96 0x01, que coincide con la representación de un mensaje de tipo +``Test1`` cuyo valor para el atributo ``a`` sea **150** sin estar embebido +en otro mensaje. + + +Salida +========================================================================== + +La salida del programa debe tener la siguiente estructura. + +Cada mensaje debe ser impreso por pantalla con el siguiente formato:: + + NombreMensaje + atributo1: valor + atributo2: valor + ... etc. + +Los atributos deben tener una sangría de 2 espacios y deben estar +ordenados por número de *tag* de forma incremental. + +Valores de tipo *int* se imprimen en formato decimal, por ejemplo:: + + Persona + edad: 39 + +Valores de tipo *string* se imprimen entre comillas dobles ``"``, +reemplazando las comillas literales ``"`` por ``\"`` y las ``\`` +literales por ``\\``. Por ejemplo:: + + Persona + nombre: "Thom Yorke" + descripcion: "Cantante + de \"Radiohead\" + \\x es x" + edad: 39 + +Siendo la *descripción* original:: + + Cantante + de "Radiohead" + \x es x + +Los valores de tipo *array* deben representarse como si fueran mensajes, +simulando que su nombre fuera "array" y cada ítem fuera un atributo +con clave numérica, igual al índice del elemento en el *array*. Por +ejemplo, un *array* de 3 *strings* se representaría así:: + + Persona + telefonos: array + 0: "555-4444" + 1: "999-1123" + 2: "113" + +Los valores de tipo *mensaje* serán impresos de la misma manera que un mensaje +regular. Con la sola excepción de que se deberá incrementar el nivel de +sangría por cada nivel de anidamiento. Por ejemplo:: + + Persona + nombre: "Thom Yorke" + edad: 39 + telefonos: array + 0: Telefono + lugar: "Casa" + numero: "555-4444" + 1: Telefono + lugar: "Emergencia" + numero: "911" + direccion: Direccion + calle: "Inglaterra 3452" + piso: 1 + departamento: "B" + + +Invocación +========================================================================== + +El programa debe ser invocado de la siguiente forma:: + + ./ej1 esquema mensaje [pb] + +Dónde: + +esquema + Archivo con el esquema de los datos (obligatorio) +mensaje + Mensaje (que debe estar definido dentro del esquema) que va a + interpretarse +pb + Archivo con **1** mensaje de tipo ``mensaje`` codificado en formato PB + (opcional, si no se especifica, se toma la base de datos de la entrada + estándar *stdin*) + +El resultado debe ser impreso por la salida estándar (*stdout*). + + +Ejemplos de invocación +-------------------------------------------------------------------------- + +:: + + ./ej1 un_esquema UnMensaje una_db > salida + +Lee los datos del archivo ``una_db``, el esquema del archivo +``un_esquema``, interpreta un mensaje de tipo ``UnMensaje`` e imprime +la salida en el archivo ``salida``. + +:: + + ./ej1 un_esquema OtroMensaje < otra_db + +Lee los datos del archivo ``otra_db``, el esquema del archivo +``un_esquema``, interpreta un mensaje de tipo ``OtroMensaje`` e imprime +la salida por *stdout*. + + +Valores de retorno +========================================================================== + +A continuación se presenta una tabla con los códigos de retorno que el +programa debe devolver ante las distintas situaciones: + +====== =================================================================== +Código Situación +====== =================================================================== +0 Ejecución exitosa +1 Parámetros de invocación incorrectos +2 Error al abrir archivo de esquema +3 Error al abrir archivo de PB +4 Error léxico en el archivo de de esquema +5 Error sintáctico en el archivo de de esquema +6 Error semántico en el archivo de de esquema +7 No se encontró el mensaje a interpretar en el archivo de esquema +8 Error al decodificar archivo de PB +9 Otros errores +====== =================================================================== + + +Restricciones de diseño +========================================================================== + +* El ejercicio debe realizarse utilizando `ISO C99`__. +* El programa debe estar correctamente modularizado, separando claramente + la interpretación de archivos de esquema de la interpretación de + archivos de PB y la salida. +* La interpretación de archivos de esquema debe estar bien dividida en + `análisis léxico`__, `análisis sintáctico`__ y `análisis + semántico`__. +* La decodificación de PB debe estar también bien validada, saliendo con + el código de error correspondiente ante cualquier situación inesperada + (*tag* inválido, fin de archivo prematuro, *wire type* desconocido, + etc.). +* No puede asumirse un tamaño máximo de línea ni de identificadores a + leer, ni de cantidad de atributos en un mensaje ni de cantidad de + mensajes en un esquema. +* Puede asumirse que los *tags* vienen ordenados en un archivo de PB. Es + decir, que primero viene el atributo con *tag* **1**, luego el de + *tag* **2**, etc. Si el *tag* **3** fuera de tipo *array*, todos los + *tags* **3** vendrán juntos, y después que el **2** y antes que el + **4**. +* Puede asumirse que van a estar presentes todos los atributos, excepto + los de tipo *array* que podrían no tener elementos (por lo tanto no + existir el *tag* correspondiente en el archivo de PB). +* Se permite (y recomienda) ir imprimiendo la salida a medida que se + interpreta el archivo de PB. + +__ http://es.wikipedia.org/wiki/Lenguaje_de_programaci%C3%B3n_C#C99 +__ http://es.wikipedia.org/wiki/Analizador_l%C3%A9xico +__ http://es.wikipedia.org/wiki/Analizador_sint%C3%A1ctico +__ http://arantxa.ii.uam.es/~alfonsec/docs/compila5.htm + diff --git a/taller/ejercicios/ej1-20082/esquema.dot b/taller/ejercicios/ej1-20082/esquema.dot new file mode 100644 index 0000000..c9d0324 --- /dev/null +++ b/taller/ejercicios/ej1-20082/esquema.dot @@ -0,0 +1,16 @@ + +digraph esquema +{ + rankdir = LR; + node [shape = box, fontsize = 10]; + + scheme -> program; + pb -> program; + program -> output; + + scheme [label = "Archivo de\nEsquema"]; + pb [label = "Archivo de\nProtocol Buffers"]; + program [label = "Programa"]; + output [label = "Salida"]; +} + diff --git a/taller/ejercicios/ej1-20082/tp.py b/taller/ejercicios/ej1-20082/tp.py new file mode 100755 index 0000000..413f2ae --- /dev/null +++ b/taller/ejercicios/ej1-20082/tp.py @@ -0,0 +1,304 @@ +#!/usr/bin/env python +# vim: set encoding=utf8 : + +# Debug +########################################################################## + +DEBUG = False + +def dprint(msg, *args): + if DEBUG: + print msg % args + + +# Lexer +########################################################################## + +SP = 1 +EOL = 2 +ID = 3 +ARR = 4 +EOF = 5 + +tokstr = { + SP: 'SP', + EOL: 'EOL', + ID: 'ID', + ARR: 'ARR', + EOF: 'EOF', +} + +class LexicError(Exception): + pass + +def tokenize(str): + if not str: + dprint('tokenize: %s', tokstr[EOF]) + return (EOF, '', '') + tok = None + val = '' + c = str[0] + if c == '\n': + tok = EOL + val = c + str = str[1:] + elif c.isspace(): + tok = SP + for c in str[1:]: + if not c.isspace(): + break + i = str.find(c) + str = str[i:] + elif c.isalpha(): + tok = ID + for c in str[1:]: + if not c.isalnum(): + break + i = str.find(c) + val = str[:i] + if str[i] == '*': + tok = ARR + i += 1 + str = str[i:] + else: + raise LexicError("unexpected '%s'" % c) + dprint('tokenize: %r', (tokstr[tok], val, str[:20])) + return (tok, val, str) + + +# Parser +########################################################################## + +# "AST" + +class Attr: + def __init__(self, type_name, is_array, name): + self.type_name = type_name + self.is_array = is_array + self.name = name + self.type = None # lo rellena el análisis semántico + def __str__(self): + return repr(self) + def __repr__(self): + type_name = self.type.name + if self.is_array: + type_name += '*' + return 'Attr(%s, %s)' % (type_name, self.name) + +class Message: + def __init__(self, name): + self.name = name + self.attrs = list() + def __str__(self): + return repr(self) + def __repr__(self): + return 'Message(%s, %s)' % (self.name, self.attrs) + +# Fin "AST" + +class SyntaxError(Exception): + pass + +def skip(str, to_skip, current=None, val=''): + if current is None: + current = to_skip + dprint('skip(%r, %s, %s)', str[:20], tokstr[to_skip], tokstr[current]) + while to_skip == current: + (current, val, str) = tokenize(str) + return (current, val, str) + +def parse_attr(str): + (tok, val, str) = tokenize(str) + if tok == EOL: # fin de mensaje + return (None, str) + (tok, val, str) = skip(str, SP, tok, val) + if tok != ID and tok != ARR: + raise SyntaxError('ID or ARR expected, got %s' % tokstr[tok]) + # tipo + is_array = False + if tok == ARR: + is_array = True + type_name = val + # sp + (tok, val, str) = tokenize(str) + if tok != SP: + raise SyntaxError('SP expected, got %s' % tokstr[tok]) + (tok, val, str) = skip(str, SP, tok, val) + # nombre + if tok != ID: + raise SyntaxError('ID expected, got %s' % tokstr[tok]) + attr = Attr(type_name, is_array, val) + (tok, val, str) = skip(str, SP) + if tok != EOL: + raise SyntaxError('EOL expected, got %s' % tokstr[tok]) + return (attr, str) + +def parse_message(str): + (tok, val, str) = skip(str, EOL) + (tok, val, str) = skip(str, SP, tok, val) + if tok == EOF: + return (None, str) + elif tok != ID: + raise SyntaxError('ID expected, got %s' % tokstr[tok]) + msg = Message(val) + dprint('parse_message(): msg = %s', msg) + (tok, val, str) = skip(str, SP) + if tok != EOL: + raise SyntaxError('EOL expected, got %s' % tokstr[tok]) + # ya tengo EOL, vienen atributos (o fin de mensaje) + (attr, str) = parse_attr(str) + while attr: + msg.attrs.append(attr) + (attr, str) = parse_attr(str) + return (msg, str) + +def parse(str): + dprint('parse(): str = %r...', str[:20]) + msgs = list() + (msg, str) = parse_message(str) + while msg: + msgs.append(msg) + (msg, str) = parse_message(str) + dprint('parse(): msg = %s', msg) + dprint('parse(): str = %r...', str[:20]) + return msgs + + +# Semantic Analysis +########################################################################## + +class SemanticError(Exception): + pass + +def search(msgs, type_name): + for msg in msgs: + if msg.name == type_name: + return msg + return None + +def check_types(msgs): + for msg in msgs: + for attr in msg.attrs: + m = search(msgs, attr.type_name) + if m is None: + raise SemanticError('attribute %s in ' \ + 'message %s has an ' \ + 'unknown type %s' % + (attr.name, msg.name, + attr.type_name)) + attr.type = m + + +# Protocol Buffers +########################################################################## + +VARINT = 0 +LENDEL = 2 + +valid_wire_types = (VARINT, LENDEL) + +wirestr = { + VARINT: 'VARINT', + LENDEL: 'LENDEL', +} + +indentation = ' ' + +class DecodeError(Exception): + pass + +def decode_varint(str): + c = ord(str[0]) + n = c & 0x7F + i = 1 + while c & 0x80: # sigue + if i == len(str): + raise DecodeError('unexpected end of stream when ' + 'decoding a varint') + c = ord(str[i]) + n += (c & 0x7F) << (7 * i) + i += 1 + return (n, str[i:]) + +def decode_key(str): + (key, str) = decode_varint(str) + wire_type = key & 0x0000000000000003 + tag = key >> 3 + return (tag, wire_type, str) + +def check_wire_type(msg, attr, wire_type, expected_type): + if wire_type != expected_type: + raise DecodeError('expected wire_type %s for attribute %s of ' + 'message %s, got %s' % (wirestr[expected_type], + attr.name, msg.name, wirestr[wire_type])) + +def decode_attribute(str, msg, indent_level, index=0): + (tag, wire_type, str) = decode_key(str) + if wire_type not in valid_wire_types: + raise DecodeError('unknown wire type %d' % wire_type) + if tag > len(msg.attrs): + raise DecodeError('unknown tag %d for message %s' + % (tag, msg.name)) + attr = msg.attrs[tag-1] + if not attr.is_array: + print "%s%s:" % (indent_level * indentation, attr.name), + if attr.is_array and not index: + print "%s%s: array" % (indent_level * indentation, attr.name) + if attr.is_array: + print "%s%s: %s" % ((indent_level + 1) * indentation, index, + attr.type.name) + index += 1 + if attr.type.name == 'int': + check_wire_type(msg, attr, wire_type, VARINT) + (val, str) = decode_varint(str) + print val + else: + check_wire_type(msg, attr, wire_type, LENDEL) + (length, str) = decode_varint(str) + val = str[:length] + str = str[length:] + if attr.type.name == 'string': # submessage + val = val.replace('\\', '\\\\').replace('"', '\\"') + print '"%s"' % val + else: + if attr.is_array: + decode_array(val, attr.type, indent_level + 1) + else: + decode_message(val, attr.type, indent_level + 1) + return (str, index) + +def decode_array(str, msg, indent_level=1): + index = 0 + while str: + (str, index) = decode_attribute(str, msg, indent_level+1, index) + +def decode_message(str, msg, indent_level=1): + print '%s' % msg.name + index = 0 + while str: + (str, index) = decode_attribute(str, msg, indent_level, index) + + +# Main +########################################################################## + +def main(*args): + msgs = [Message('int'), Message('string')] \ + + parse(file(args[0]).read()) + check_types(msgs) + print msgs + msg = search(msgs, args[1]) + if msg is None: + print "can't find message with name %s in %s" % (args[1], + args[0]) + return 7 + pbfile = sys.stdin + if len(args) > 2: + pbfile = file(args[2]) + decode_message(pbfile.read(), msg) + return 0 + +if __name__ == '__main__': + import sys + sys.exit(main(*sys.argv[1:])) +