--- /dev/null
+.. 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
+
--- /dev/null
+#!/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:]))
+
projects / personal / documentos.git / commitdiff