Programemos Cosas

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 n...

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...

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 ...

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.  γ = '', α = LIST ',', β = 'ELEMENT', A = LIST Luego, γA = LIST, es un viable prefix válido. γ = LIST ',', α = '', β = 'a', A = ELEMENT Luego, γA = LIST ',' ELEMENT, es un viable prefix válido. γ = LIST, α = ''...

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...

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 ...

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, ‘,’) => apil...

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, ‘,’) =>...

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 ...