next up previous contents index practicapracticaPP2moodleLHPmoodlepserratacpanmodulospauseperlgoogleetsiiullpcgull
Sig: Gramáticas LL(1) Sup: Análisis Sintáctico Predictivo Recursivo Ant: Ejercicio: Calcular los Err: Si hallas una errata ...


Práctica: Construcción de los FIRST y los FOLLOW

He escrito un módulo llamado Grammar que provee la función Grammar::Parse la cual recibe una cadena conteniendo la gramática en formato yacc o yapp y devuelve una referencia a un hash conteniendo la información pertinente para el tratamiento de la gramática. Para instalar el módulo tenga en cuenta que depende del módulo Parse::Yapp.

Para ilustrar el uso vea los ejemplos en el directorio scripts. En concreto veamos el programa grammar.pl.

Grammar/scripts$ cat -n grammar.pl
 1  #!/usr/bin/perl -w -I../lib
 2  use strict;
 3  use Grammar;
 4  use Data::Dumper;
 5
 6  sub usage {
 7    print <<"EOI";
 8  usage:
 9  $0 input_grammar
10  EOI
11    die "\n";
12  }
13
14  usage() unless @ARGV;
15  my $filename = shift;
16
17  local $/ = undef;
18  open FILE, "$filename";
19  my $grammar = <FILE>;
20  my $x = Grammar::Parse($grammar);
21
22  print Dumper($x);
Vamos a darle como entrada la gramática en el fichero aSb.yp conteniendo una gramática:
Grammar/scripts$ cat -n aSb.yp
 1  %%
 2  S:
 3      |   'a' S 'b'
 4  ;
 5  %%

Las gramáticas aceptadas por Grammar::Parse se adaptan a la sintáxis de las gramáticas reconocidas por Parse::Yapp. Una gramática (normalmente con tipo .yp) consta de tres partes: la cabeza, el cuerpo y la cola. Cada una de las partes va separada de las otras por el símbolo %% en una línea aparte. Así, el %% de la línea 1 separa la cabeza del cuerpo. En la cabecera se colocan las declaraciones de terminales (directiva %token), cual es el símbolo de arranque (directiva %start), etc. El cuerpo contiene las reglas de la gramática y las acciones asociadas. Por último, la cola en nuestro caso no es usada y es vacía. En general, la cola contiene las rutinas de soporte al código que aparece en las acciones asi como, posiblemente, rutinas para el análisis léxico y el tratamiento de errores.

La salida de Grammar::Parsees una referencia a un hash cuyas entradas vienen explicadas por los comentarios.

Grammar/scripts$ grammar.pl aSb.yp
$VAR1 = {
    'SYMS' => { 'S' => 2, '\'b\'' => 3, '\'a\'' => 3 }, # Símbolo => línea
    'NULL' => { 'S' => 1 }, # símbolos que se anulan
    'RULES' => [
                 [ 'S', [] ], # S produce vacío
                 [ 'S', [ '\'a\'', 'S', '\'b\'' ] ] # S -> aSb
               ],
    'START' => 'S', # Símbolo de arranque
    'TERM' => [ '\'b\'', '\'a\'' ], # terminales /tokens
    'NTERM' => { 'S' => [ 0, 1 ] }  # índices de las reglas de las variables sintácticas
  };
Usando la estructura devuelta por la función Grammar::Parse escriba un módulo que provea funciones para computar los FIRST y los FOLLOW de las variables sintácticas de la gramática. No olvide escribir la documentación. Incluya una prueba por cada una de las gramáticas que figuran en el directorio scripts del módulo Grammar.


next up previous contents index practicapracticaPP2moodleLHPmoodlepserratacpanmodulospauseperlgoogleetsiiullpcgull
Sig: Gramáticas LL(1) Sup: Análisis Sintáctico Predictivo Recursivo Ant: Ejercicio: Calcular los Err: Si hallas una errata ...
Casiano Rodríguez León
2006-02-21