domingo, 30 de abril de 2017

Notas finales sobre el artículo de Aho y Johnson

Esto viene a ser un cierre a una serie de escritos en torno a un artículo titulado L.R. Parsing, autoría de A.V. Aho y S.C. Johnson. Varias de ellas son glosas y otras ejercicios resueltos. Al pie se detallan las referencias.

Notas finales:
Entre right parse y righmost derivation puede establecerse una relación, entendida como que cada una de las reescrituras de una right derivación se emparentan con cada uno de los estadíos de un right parse de modo que los símbolos de dicho estadío son prefijo de la cadena reescrita, y lo que no es prefijo, es una cadena de símbolos terminales igual al input que falta incorporar al right parse en ese estadío. Además, dicho prefijo no es cualquiera, sino que es siempre un viable prefix.

La closure operation tiene un operando y un resultado, ambos definidos bajo el nombre de "ítem". El hecho de que para esta operación se exija que los símbolos del lookahead set previo estén concatenados a la cadena de cuya derivación se extraerá el nuevo lookeahead set tiene un significado importante. Algunas derivaciones podrían realizarse que sean válidas en forma aislada pero que no pudieran formar una right sentential form en el lugar desde donde se están generando. Concatenando a estas derivaciones los símbolos del lookahead set previo queda en evidencia su falta de sentido, y por otro lado, la validez de las derivaciones que sí la tienen.

Artículos anteriores de esta serie:
Ejercicio de La Sección 6.4, "Computing Lookahead Sets"
Ejercicio LR Parsing Sección 6.2, "Constructing the Collection of Accessible Set of Items"
Ejercicio Propuesto En El Artículo LR Parsing En La Sección 6.1, "Sets Of Items"
Notas Sobre El Artículo L.R. Parsing
Parseo Simple
Otro Ejercicio del Artículo L.R. Parsing
Ejercicios del Artículo L.R. Parsing

lunes, 10 de abril de 2017

Ejercicio de la sección 6.4 computing lookahead sets

The reader should verify that the complete collection of sets of items for G₁ is:

I₀: [ACCEPT → ⋅ LIST], {'$'}
[LIST → ⋅ LIST ',' ELEMENT], {',', '$'}
[LIST→ ⋅ ELEMENT], {',', '$'}
[ELEMENT → ⋅ 'a'], {',', '$'}
[ELEMENT →  ⋅ 'b'], {',', '$'}
I₁: [ACCEPT → LIST ⋅ ], {'$'}
[LIST → LIST ⋅ ',' ELEMENT], {',', '$'}
I₂: [LIST → ELEMENT ⋅ ], {',', '$'}
I₃: [ELEMENT → 'a' ⋅ ], {',', '$'}
I₄: [ELEMENT → 'b' ⋅ ], {',', '$'}
I₅: [LIST → LIST ',' ⋅ ELEMENT], {',', '$'}
[ELEMENT → ⋅ 'a'], {',', '$'}
[ELEMENT → ⋅ 'b'], {',', '$'}
I₆: [LIST → LIST ',' ELEMENT ⋅ ], {',', '$'}



Teniendo en cuenta que hay 2 formas de generar los sets de items, se elegirá uno teniendo en cuenta lo siguiente.
Una de las formas tiene más que ver con las definiciones de viable prefix y valid item, y la otra con un símbolo especial (ACCEPT) que expande la gramática con una nueva regla, una operación llamada closure que completa los items de cada set. Ambas tienen en cuenta uno y sólo un símbolo de desplazamiento en el cálculo de cada nuevo estado, El 2do. método es más natural a lo realizado por un parser en ejecución: partir de un estado, desplazar un símbolo y cambiar a un nuevo estado. El 1er. método requiere una cadena auxiliar para usarla de viable prefix al aplicar la definición de valid item. Es auxiliar en el sentido de que sólo forma parte del proceso de construcción pero no del parser construido.
Finalmente, por simplicidad se elegirá el 2do. método para este ejercicio.
Los sets de items I₀, I₁, I₂, I₃ e I₄ ya fueron calculados en la sección 6.2, de la cual el cálculo de los lookehead sets no formaba parte. También fueron calculados, en la sección 6.4, los lookahead sets para I₀ e I₃, más allá de que este último sea referido en dicha sección como I₂, cosa que aquí no tiene importancia.
Dando por hecho los sets de items y lookahead sets mencionados, se procederá a completar la collección, aplicando las definiciones de las secciones 6.2 y 6.4.

El único ítem de I₁ surge de desplazarse a través de LIST sobre el ítem [ACCEPT → ⋅ LIST] {$} y conservando su lookahead set al no haber closure operation aplicable. Como resultado se tiene:
I₁: [ACCEPT → LIST ⋅ ], {'$'}

Para I₂ el razonamiento por ende es el mismo lookahead set que el del ítem del cual procede, que es [LIST→ ⋅ ELEMENT], {',', '$'}. Según esto:
I₂: [LIST → ELEMENT ⋅ ], {',', '$'}

Lo mismo pasa con el único ítem de I₄ (I₃, como se dijo, se da por hecho), cuyo antecesor es [ELEMENT →  ⋅ 'b'], {',', '$'}, y 'b' el símbolo "atravesado" (a través del cual nos desplazamos), siendo pues:
I₄: [ELEMENT → 'b' ⋅ ], {',', '$'}

Se resolverá un nuevo set de items por medio de GOTO(I₁, ','):
Desplazándose a través de un símbolo ',' sobre un ítem de I₁ único donde esto tiene sentido se genera el ítem [LIST → LIST ',' ⋅ ELEMENT], {',', '$'}. Siendo que no hay símbolos entre ELEMENT y el final de la regla, su lookahead set tiene el mismo potencial de formar right sentential form en presencia de esta instancia de ELEMENT como así de todas sus derivaciones por derecha, de modo que el lookahead set no cambia. Conociendo la closure operation sobre ELEMENT, el estado completo queda:
[LIST → LIST ',' ⋅ ELEMENT], {',', '$'}
[ELEMENT → ⋅ 'a'], {',', '$'}
[ELEMENT → ⋅ 'b'], {',', '$'}
Que viene a ser I₅.

GOTO(I₅, ELEMENT) da como resultado exactamente I₆, no habiendo ni closure operation que valga ni posibilidad de que el lookahead set sea modificado, por razonamientos similares a los seguidos hasta aquí.

Por más GOTO(I,X) que se intente, ya no queda forma de expandir la colección de sets de items. Queda pues verificado el enunciado.

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.