jueves, 16 de febrero de 2017

Notas sobre el artículo L.R. Parsing

El artíuclo al cual se hace referencia aquí, “LR Parsing” de A. V. Aho y J. S. Johnson, ya había sido mencionado en entradas anteriores.

En la notación que usa dicho artículo, se escriben en mayúsculas los símbolos no terminales, en minúsculas los terminales, y entre comillas simples los literales.
La derivación* siguiente sirve de un ejemplo:
SALUDO ‘!’ => hola ‘!’

En donde SALUDO es el símbolo no terminal, hola es el terminal, y ‘!’ el literal.

Las letras griegas (por ejemplo α, β, γ) por su parte, representan cadenas de símbolos de cualesquiera de las 3 categorías (terminales, no terminales y literales) generadas durante el proceso de derivación.
Por ejemplo, de la siguiente derivación:
SALUDO SEÑOR_PÉREZ ‘. ¡Bienvenido!’ => SALUDO NOMBRE pérez ‘. ¡Bienvenido!’
La parte que está a la derecha del => se podría expresar con la ayuda de letras griegas de las siguientes formas:
  • SALUDO α ‘.’ ‘¡Bienvenido!’ 
  • SALUDO β 
  • SALUDO β pérez ‘.’ ‘¡Bienvenido!’ 
  • α β pérez ‘.’ ‘¡Bienvenido!’ 
  • α ‘.’ ‘¡Bienvenido!’ 
  • α 
  • α SALUDO NOMBRE pérez ‘.’ ‘¡Bienvenido!’ 
(En el último ejemplo, a parte de α, la cadena de símbolos es exactamente como la original, lo que significa que α es la cadena vacía, mientras que en el anteúltimo caso, no habiendo más que una α, esta representa a la frase completa.)

Y una sola letra en minúscula, itálica y de forma redondeada (normalmente w) ocupa el lugar de cadenas de símbolos literales, en general la parte de más a la derecha de una frase. Ejemplo:
  • SALUDO NOMBRE pérez ‘. ¡Bienvenido!’ w
  • α NOMBRE pérez ‘. ¡Bienvenido’ w
  • α β ‘. ¡’ w
  • α β ‘. w
  • α β w
(En el primer ejemplo, w es la cadena vacía, de acuerdo a un razonamiento similar al explicado arriba).


Por medio de la simbología introducida, se mostrará una posible definición de algo llamado "viable prefix", sin ocuparnos realmente de definir qué es esto.
Si la parte a la derecha del '=>' tiene la forma α β w, y β representa lo que es diferente con respecto al lado izquierdo, se dice que γ es viable prefix si: γ δ = α β, donde δ puede ser la cadena vacía. 

En otras palabras, el víable prefix siempre empieza bien a la izquierda de la cadena derivada, y se extiende a lo sumo hasta la parte que fue cambiada por la derivación.


*El significado del término derivación queda fuera del alcance de estas notas. Informalmente hablando, se puede reconocer una derivación porque contiene el símbolo '=>'. Una mejor definición se encuentra en “LR Parsing” de A. V. Aho y J. S. Johnson.

miércoles, 15 de febrero de 2017

Desencriptando archivos con clave simétrica de GnuPG con BouncyCastle (OpenPGP)

Si se tiene un archivo ".gpg", es decir, encriptado con GnuPG con la opción --symetric (encriptado simétrico), y se lo quiere desencriptar utilizando BouncyCastle for Java, aquí se presentará un set de herramientas/programas, y el procedimiento para instalarlos y ejecutarlos.

Se requiere Java 8 Development Kit, Maven y conexión a Internet, o en su defecto, a una Intranet donde sea accesible un repositorio Maven local que contenga los artefactos de BouncyCastle y sus dependencias.

El package Bouncy Castle para Java implementa el estándar OpenPGP, al cual la herramienta GnuPG adhiere. Por lo tanto, ambos programas, GnuPG y BouncyCastle, pueden cualquiera de ellas encriptar y desencriptar un archivo que haya sido creado con la otra herramienta.

El package de BouncyCastle Viene con ejemplos de clases stand alone (con el método main()), y son muy simples de invocar desde la línea de comandos, pudiendo ver en el mismo código fuente los parámetros que hay que pasarle según la operación que se quiere realizar. En nuestro caso, la clase de ejemplo a invocar será com.example.PBEFileProcessor, y los parámetros serán (sin comillas) "-d" para desencriptar, el nombre del archivo encriptado con la opción --symetric de gpg, y la contraseña simétrica.

Además, hay otro package que separa estos ejemplos y los empaqueta en un artefacto de Maven. Mientras que el package original (BouncyCastle) está pensado para usarse como librería en un programa que la incluya, este nuevo artefacto Maven sirve para ejecutarse directamente desde línea de comando. Obviamente va a depender de la librería BouncyCastle, ya que mientras que este artefacto es un front end de línea de comando, es la librería quien resuelve la "parte pesada" del trabajo criptográfico.

Maven por su parte, puede pensarse de alguna manera como un asistente para instalar aplicaciones Java.

Los pasos a seguir serían:

Bajar el package openpgp-bc-examples, simplemente buscar la opción para descargarse un .zip. Descomprimirlo.
También descargarse un .zip de BouncyCastle para Java. Descomprimirlo.
En la página de openpgp-bc-examples explica cómo se hizo para extraer los ejemplos en un package separado, en el párrafo titulado "How this repository was created". Siguiendo de esa explicación el criterio de renombrar la declaración del "package" de Java, hay que pasar de BouncyCastle, todos los archivos que están en pg/src/main/java/org/bouncycastle/openpgp/examples a la carpeta com/examples de openpgp-bc-examples.

Ya se puede instalar y ejecutar la aplicación, siguiendo los pasos que se explican en la misma página openpgp-bc-examples, con la particularidad de que si se desconoce cómo direccionar, estando bajo Windows, el archivo "classpath.txt" ahí mostrado, se puede abrir con un notepad y copiar su contenido en la línea de comando de la ejecución.

Si el sistema tiene otras versiones de Java Development Kit además de la 8, y esta no es la predeterminada, bastará con setear, solamente en la sesión de línea de comando abierta, las variables JAVA_HOME y PATH con los valores apropiados. La forma bajo Windows sería: set JAVA_HOME=path a Java 8, y set PATH=path a Java8/bin;%PATH%

La invocación tendrá esta forma:
java -classpath <path openpgp-bc-examples>/target/<jar open-bc-examples> com.example.PBEFileProcessor -d archivo_encriptado.gpg Contraseña

Para no tener que pasar la contraseña por línea de comando, habría que modificar el programa Java para que use un método más seguro para la lectura de contraseñas. El apéndice D de la especificación de Java Cryptographic Architecture tiene un programa de ejemplo de lectura de contraseñas que se podría utilizar para tal fin. Habría que incorporarlo de alguna forma dentro de los programas del package com.example. Dentro de la misma especificación de Java Crtptographic Architecture, hay ejemplos de cómo usarlo, en la sección Example Codes, subsección Using Password-Based Encryption.

Espero que sirva.

viernes, 10 de febrero de 2017

Parseo simple



El siguiente ejercicio proviene del mismo lugar que uno publicado unos días atrás. Los datos del ejercicio que se mantienen igual, no se vuelven a exponer. En particular, la Parsing Action y Goto table son los mismos que en dicho artículo.


Lo que cambia es el input string, y obviamente el seguimiento del parser, manteniéndose iguales la pa (parsing action), la goto (goto table) y las reglas gramaticales.


Input string: a,,b
Acción
Raíces del árbol de derivación (y estado asociado)*
Input remanente
Inicialización: 0
(0)
a,,b $end
pa(0, ‘a’) => apilar
(0), ‘a’
,,b $end
goto(0, ‘a’) => 3
(0), ‘a’ (3)
,,b $end
pa(3, ‘,’) => reducir (3)
(0), ‘ELEMENT’
,,b $end
goto(0, ‘ELEMENT’) => 2
(0), ‘ELEMENT’ (2)
,,b $end
pa(2, ‘,’) => reducir (2)
(0), ‘LIST’
,,b $end
goto(0, ‘LIST’) => 1
(0), ‘LIST’ (1)
,,b $end
pa(1, ‘,’) => apilar
(0), ‘LIST’ (1), ‘,’
,b $end
goto(1, ‘,’) => 5
(0), ‘LIST’ (1), ‘,’ (5)
,b $end
pa(5, ‘,’) => error
(0), ‘LIST’ (1), ‘,’ (5)
,b $end

* Solamente el estado inicial (0) no está asociado a ninguna raíz.

lunes, 6 de febrero de 2017

Otro ejercicio del artículo "LR Parsing"

El siguiente ejercicio proviene del mismo lugar que uno publicado unos días atrás. Los datos del ejercicio que se mantienen igual, no se vuelven a exponer. En particular, la Parsing Action y Goto table son los mismos que en dicho artículo.
Lo que cambia es el input string, y obviamente el seguimiento del parser, manteniéndose iguales la pa (parsing action), la goto (goto table) y las reglas gramaticales.

Input string: a,ba
Acción
Raíces del árbol de derivación (y estado asociado)*
Input remanente
Inicialización: 0
(0)
a,ba $end
pa(0, ‘a’) => apilar
(0), ‘a’
,ba $end
goto(0, ‘a’) => 3
(0), ‘a’ (3)
,ba $end
pa(3, ‘,’) => reducir (3)
(0), ‘ELEMENT’
,ba $end
goto(0, ‘ELEMENT’) => 2
(0), ‘ELEMENT’ (2)
,ba $end
pa(2, ‘,’) => reducir (2)
(0), ‘LIST’
,ba $end
goto(0, ‘LIST’) => 1
(0), ‘LIST’ (1)
,ba $end
pa(1, ‘,’) => apilar
(0), ‘LIST’ (1), ‘,’
ba $end
goto(1, ‘,’) => 5
(0), ‘LIST’ (1), ‘,’ (5)
ba $end
pa(5, ‘b’) => apilar
(0), ‘LIST’ (1), ‘,’ (5), ‘b’
a $end
goto(5, ‘b’) => 4
(0), ‘LIST’ (1), ‘,’ (5), ‘b’ (4)
a $end
pa(4, ‘a’) => error
(0), ‘LIST’ (1), ‘,’ (5), ‘b’
a $end

 * Solamente el estado inicial (0) no está asociado a ninguna raíz.

viernes, 3 de febrero de 2017

Ejercicios del artículo "LR Parsing",

A continuación, un ejercicio propuesto por el artículo LR Parsing, de A.V. Aho y S. C. Johnson


pa (Parsing Action)

Siguiente símbolo de entrada
Estado
'a'
'b'
','
'$'
0
shift
shift
error
error
1
error
error
shift
accept
2
error
error
Red. 2
Red 2
3
error
error
Red. 3
Red. 3
4
error
error
Red. 4
Red. 4
5
shift
shift
error
error
6
error
error
Red. 1
Red 1
Ejemplo: pa(5, ‘b’)= shift;  pa(4, 'a')= error

Nota de traducción: shift=apilar; Red.=reducir

Reglas gramaticales
(1) LIST --> LIST ',' ELEMENT
(2) LIST --> ELEMENT
(3) ELEMENT --> 'a'
(4) ELEMENT --> 'b'


goto (Goto table)

Label of new root
Estado de más a la derecha
LIST
ELEMENT
‘a’
‘b’
‘,’
0
1
2
3
4

1




5
2





3





4





5

6
3
4

6





Ejemplo: goto(0, LIST)= 1;   goto(1, ',')= 5
Los espacios vacíos nunca deberían ser consultados por el parser.



Input string: a,b,a
Acción
Raíces del árbol de derivación (y estado asociado)*
Input remanente
Inicialización: 0
(0)
a,b,a $end
pa(0, ‘a’) => apilar
(0), ‘a’
,b,a $end
goto(0, ‘a’) => 3
(0), ‘a’ (3)
,b,a $end
pa(3, ‘,’) => reducir (3)
(0), ‘ELEMENT’
,b,a $end
goto(0, ‘ELEMENT’) => 2
(0), ‘ELEMENT’ (2)
,b,a $end
pa(2, ‘,’) => reducir (2)
(0), ‘LIST’
,b,a $end
goto(0, ‘LIST’) => 1
(0), ‘LIST’ (1)
,b,a $end
pa(1, ‘,’) => apilar
(0), ‘LIST’ (1), ‘,’
b,a $end
goto(1, ‘,’) => 5
(0), ‘LIST’ (1), ‘,’ (5)
b,a $end
pa(5, ‘b’) => apilar
(0), ‘LIST’ (1), ‘,’ (5), ‘b’
,a $end
goto(5, ‘b’) => 4
(0), ‘LIST’ (1), ‘,’ (5), ‘b’ (4)
,a $end
pa(4, ‘,’) => reducir (4)
(0), ‘LIST’ (1), ‘,’ (5), ‘ELEMENT’
,a $end
goto(5, ‘ELEMENT’) => 6
(0), ‘LIST’ (1), ‘,’ (5), ‘ELEMENT’ (6)
,a $end
pa(6, ‘,’) => reducir (1)
(0), ‘LIST’
,a $end
goto(0, ‘LIST’) => 1
(0), ‘LIST’ (1)
,a $end
pa(1, ‘,’) => apilar
(0), ‘LIST’ (1), ‘,’
a $end
goto(1, ‘,’) => 5
(0), ‘LIST’ (1), ‘,’ (5)
a $end
pa(5, ‘a’) => apilar
(0), ‘LIST’ (1), ‘,’ (5), ‘a’
$end
goto(5, ‘a’) => 3
(0), ‘LIST’ (1), ‘,’ (5), ‘a’ (3)
$end
pa(3, $end) => reducir (3)
(0), ‘LIST’ (1), ‘,’ (5), ‘ELEMENT’
$end
goto(5, ‘ELEMENT’) => 6
(0), ‘LIST’ (1), ‘,’ (5), ‘ELEMENT’ (6)
$end
pa(6, $end) => reducir (1)
(0), ‘LIST’
$end
goto(0, ‘LIST’) => 1
(0), ‘LIST’ (1)
$end
pa(1, $end) => accept
(0), ‘LIST’ (1)
$end


* Solamente el estado inicial, [0], no está asociado a ninguna raíz.