lunes, 13 de marzo de 2017

Ejercicio LR Parsing sección 6.2, "Constructing the Collection of Accessible Sets of Items"

Ejercicio propuesto por el enunciado

The reader should verify that these two items 
[ACCEPT → LIST .]
[LIST → LIST . ',' ELEMENT]
are the only items valid for the viable prefix LIST.

La verificación será realizada a partir de los items generados por la gramática
ACCEPT → LIST
LIST → LIST ',' ELEMENT
LIST → ELEMENT
ELEMENT → 'a'
ELEMENT → 'b'
estableciendo γ y α a valores apropiados según cada ítem y comprobando que los 2 del enunciado son los únicos que validan los datos del enunciado contra la definición de valid item. La tabla siguiente comprende la resolución del ejercicio según lo explicado.

Ítem
γ
α
β
A
γ.A
¿γA válido? / ¿Hay alguna forma de hacer γα=LIST para γA?
ACCEPT → ⋅ LIST
LIST
''
LIST
ACCEPT
LIST ACCEPT
no / sí
ACCEPT → LIST ⋅
''
LIST
''
ACCEPT
ACCEPT
sí / sí
LIST → ⋅ LIST ',' ELEMENT
LIST
''
LIST ',' ELEMENT
LIST
LIST LIST
no / sí
LIST → LIST ⋅ ',' ELEMENT
''
LIST
',' ELEMENT
LIST
LIST
sí / sí
LIST → LIST ',' ⋅ ELEMENT
''
LIST ','
ELEMENT
LIST
LIST
sí / no
LIST → LIST ',' ELEMENT ⋅
''
LIST ',' ELEMENT
''
LIST
LIST
sí / no
LIST → ⋅ ELEMENT
LIST
''
ELEMENT
LIST
LIST LIST
no / sí
LIST → ELEMENT ⋅
''
ELEMENT
''
LIST
LIST
sí / no
ELEMENT → ⋅ 'a'
LIST
''
'a'
ELEMENT
LIST ELEMENT
no / sí
ELEMENT → 'a' ⋅
''
'a'
''
ELEMENT
ELEMENT
sí / no
ELEMENT → ⋅ 'b'
LIST
''
'b'
ELEMENT
LIST ELEMENT
no / sí
ELEMENT → 'b' ⋅
''
'b'
''
ELEMENT
ELEMENT
sí / no



miércoles, 1 de marzo de 2017

Ejercicio propuesto en el artículo "LR Parsing" en la sección 6.1, "Sets of Items"

Nada mejor que hacer los ejercicios propuestos por el texto que uno lee para afianzar conocimientos. En este caso, se trata del ejercicio del artículo LR Parsing, A.V. Aho & S. C. Johnson, propuesto en la sección 6.1, "Sets of Items", bajo el enunciado:

The reader can (and should) verify that the state corresponding to the viable prefix LIST ',' is associated with the set of items:
[LIST → LIST ',' . ELEMENT]
[ELEMENT → . 'a']
[ELEMENT→ . 'b']



Por definición, dado un viable prefix γα, compuesto por cualquier cadena derivable a partir de γ seguido de cualquier cadena derivable de α, cualquier ítem de la forma [A → α.β] es válido si γA es un viable prefix.



  1.  γ = '', α = LIST ',', β = 'ELEMENT', A = LIST
    Luego, γA = LIST, es un viable prefix válido.
  2. γ = LIST ',', α = '', β = 'a', A = ELEMENT
    Luego, γA = LIST ',' ELEMENT, es un viable prefix válido.
  3. γ = LIST, α = '', β = 'b', A = ELEMENT
    Luego, γA = LIST ',' ELEMENT, es un viable prefix válido.


Bueno, a lo mejor el ejercicio completo debe constar de las comprobaciones con todos los items de la gramática.

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.