next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: Depuración de Errores Sup: Análisis Sintáctico con Parse::Eyapp Ant: Conceptos Básicos para el Err: Si hallas una errata ...


Parse::Eyapp: Un Generador de Analizadores Sintácticos

El generador de analizadores sintácticos Parse::Eyapp es un analizador LALR inspirado en yacc . Parse::Eyapp es una extensión de Parse::Yapp escrita por Casiano Rodriguez-Leon. Puede descargarlo desde CPAN e instalarlo en su máquina siguiendo el procedimiento habitual.

El generador de analizadores sintácticos Parse::Eyapp que estudiaremos en las siguientes secciones funciona de manera similar a un esquema de traducción. Las reglas de producción de la gramática son aumentadas con reglas semánticas. Los símbolos que aparecen en la regla de producción tienen atributos asociados y las reglas semánticas dicen como deben ser computados dichos atributos. Consideremos, por ejemplo, el siguiente fragmento de programa eyapp:

exp:  exp '+' exp         { $_[1] + $_[3] }

que dice que asociado con el símbolo $ exp$ de la regla de producción $ exp \rightarrow exp '+' exp$ tenemos el atributo valor numérico y que para computar el atributo valor de la variable sintáctica $ exp$ en la parte izquierda tenemos que sumar los atributos asociados con los símbolos primero y tercero de la parte derecha.

Por defecto Parse::Eyapp no provee un esquema de traducción ya que - aunque el orden de ejecucíon de las acciones es de abajo-arriba y de izquierda a derecha como en un esquema - no es posible acceder a atributos de nodos que aún no han sido visitados.

Para ilustrar el uso de Parse::Eyapp veamos un ejemplo en el que se implanta una gramática cuyas frases son secuencias (separadas por retornos de carro) de expresiones aritméticas.

Los contenidos del programa eyapp los hemos guardado en un fichero denominado CalcSyntax.eyp

Partes de un Programa Eyapp

Un programa eyapp consta de tres partes:

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 8 separa la cabeza del cuerpo y el de la línea 31 el cuerpo de la cola.

pl@nereida:~/LEyapp/examples$ cat -n CalcSyntax.eyp
 1  # CalcSyntax.eyp
 2  %right  '='
 3  %left   '-' '+'
 4  %left   '*' '/'
 5  %left   NEG
 6  %right  '^'
 7
 8  %%
 9
10  input:  line *  { print "input -> line *\n" }
11  ;
12
13  line:
14    '\n'         { print "line -> \\n\n" }
15    | exp '\n'   { print "line -> exp \\n\n"}
16  ;
17
18  exp:
19      NUM                { print "exp -> NUM ($_[1])\n"; }
20    | VAR                { print "exp -> VAR ($_[1])\n"; }
21    | VAR '=' exp        { print "exp -> VAR '=' exp\n"; }
22    | exp '+' exp        { print "exp -> exp '+' exp\n"; }
..    . ....................................................
29  ;
30
31  %%
32
33  sub _Error {
..    ....................................
41  }
42
..  ......................................
44
45  sub _Lexer {
46      my($parser)=shift;
..      .................
58  }
59
60  sub Run {
61      my($self)=shift;
62
63      $input = shift;
64      return $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
65  }

Las Reglas

Todas las partes derechas de las reglas de producción de una misma variable sintáctica se escriben juntas separadas mediante la barra vertical |.

10  input:  line *  { print "input -> line *\n" }
11  ;
12
13  line:
14    '\n'         { print "line -> \\n\n" }
15    | exp '\n'   { print "line -> exp \\n\n"}
16  ;

En este ejemplo hemos simplificado las acciones semánticas reduciéndolas a mostrar la regla de producción encontrada.

Reglas de Producción Vacías

Un asterisco (como en la línea 10) indica repetición cero o mas veces de la expresión a la que se aplica. De hecho la línea 10 es casi equivalente a:

input:  temp   
;
temp: 
    /* vacio */
  | temp line
;

Observe como en el código anterior hemos codificado la regla de producción $ temp \rightarrow \epsilon$ como:

temp: 
    /* vacio */

Es buena costumbre de programación cuando se tiene una regla de producción que produce vacío ponerla la primera del grupo y añadir un comentario como este. Dado que vacío se representa en Eyapp mediante la cadena vacía es fácil que pase desapercibida. Es por ello que se recomienda que una regla vacía sea siempre la primera y que este comentada como en el ejemplo.

Tratamiento de las Ambiguedades

Hay numerosas ambiguedades en esta gramática. Observe las reglas para los diferentes tipos de expresiones:

18 exp:
19     NUM                { print "exp -> NUM ($_[1])\n"; }
20   | VAR                { print "exp -> VAR ($_[1])\n"; }
21   | VAR '=' exp        { print "exp -> VAR '=' exp\n"; }
22   | exp '+' exp        { print "exp -> exp '+' exp\n"; }
23   | exp '-' exp        { print "exp -> exp '-' exp\n"; }
24   | exp '*' exp        { print "exp -> exp '*' exp\n"; }
25   | exp '/' exp        { print "exp -> exp '/' exp\n"; }
26   | '-' exp %prec NEG  { print "exp -> '-' exp\n"; }
27   | exp '^' exp        { print "exp -> exp '^' exp\n"; }
28   | '(' exp ')'        { print "exp -> '(' exp ')'\n"; }
29 ;

Surgen preguntas como:

La Asociatividad de Terminales y la Ambiguedad

Las declaraciones %left y %right expresan la asociatividad y precedencia de los terminales, permitiendo decidir que árbol construir en caso de ambiguedad.

Los terminales declarados en líneas posteriores tienen mas prioridad que los declarados en las líneas anteriores.

Por defecto, una regla de producción tiene la prioridad del último terminal que aparece en su parte derecha.

Al declarar como asociativo a izquierdas al terminal - hemos resuelto la ambiguedad en 4 -5 -2. Lo que estamos haciendo es indicarle al analizador que a la hora de elegir entre los árboles abstractos $ -(-(4,5),2)$ y $ -(4, -(5,2))$ elija siempre el árbol que se hunde a izquierdas. ¿Como debo interpretar la expresión 4 - 5 * 2? ¿Como (4 - 5) * 2? ¿o bien 4 - (5 * 2)? Al declarar que * tiene mayor prioridad que - estamos resolviendo esta otra fuente de ambiguedad. Esto es así pues * fué declarado en la línea 11 y - en la 10. Por tanto el árbol será -(4, *(5,2)).

La declaración de ^ como asociativo a derechas y con un nivel de prioridad alto resuelve las ambiguedades relacionadas con este operador:

  18  exp:
  ..    ......................................................
  28    | '(' exp ')'        { print "exp -> '(' exp ')'\n"; }

Ejercicio 8.2.1   ¿Como se esta interpretando la expresión -2^2? ¿Cómo (-2)^2? ¿o bien -(2^2)?

Modificación de la Prioridad Implícita de una Regla

Una regla de producción puede ir seguida de una directiva %prec la cual le da una prioridad explícita. Esto puede ser de gran ayuda en ciertos casos de ambiguedad.

26    | '-' exp %prec NEG  { print "exp -> '-' exp\n"; }

¿Cual es la ambiguedad que surge con esta regla? La ambiguedad de esta regla esta relacionada con el doble significado del menos como operador unario y binario: hay frases como -y-z que tiene dos posibles interpretaciones: Podemos verla como (-y)-z o bien como -(y-z). Hay dos árboles posibles. El analizador, cuando este analizando la entrada -y-z y vea el segundo - (después de haber leído -y) deberá escoger uno de los dos árboles. ¿Cuál?. El conflicto puede verse como una ``lucha'' entre la regla exp: '-' exp la cual interpreta la frase como (-y)-z y la segunda aparición del terminal - el cuál ``quiere entrar'' para que gane la regla exp: exp '-' exp y dar lugar a la interpretación -(y-z). En este caso, las dos reglas $ E \rightarrow - E$ y $ E \rightarrow E - E$ tienen, en principio la prioridad del terminal -, el cual fué declarado en la zona de cabecera:

1 # CalcSyntax.eyp
2 %right  '='
3 %left   '-' '+'
4 %left   '*' '/'
5 %left   NEG
6 %right  '^'
7
8 %%

La prioridad expresada explícitamente para la regla por la declaración %prec NEG de la línea 41 hace que la regla tenga la prioridad del terminal NEG y por tanto mas prioridad que el terminal -. Esto hará que eyapp finalmente opte por la regla exp: '-' exp dando lugar a la interpretación (-y)-z.

La Cola

Después de la parte de la gramática, y separada de la anterior por el símbolo %%, sigue la parte en la que se suelen poner las rutinas de apoyo. Hay al menos dos rutinas de apoyo que el analizador sintáctico requiere le sean pasados como argumentos: la de manejo de errores y la de análisis léxico.

31  %%
32
33  sub _Error {
34          exists $_[0]->YYData->{ERRMSG}
35      and do {
36          print $_[0]->YYData->{ERRMSG};
37          delete $_[0]->YYData->{ERRMSG};
38          return;
39      };
40      print "Syntax error.\n";
41  }
42
43  my $input;
44
45  sub _Lexer {
46      my($parser)=shift;
47
48      # topicalize $input
49      for ($input) {
50        s/^[ \t]+//;      # skip whites
51        return('',undef) unless $input;
52
53        return('NUM',$1) if s{^([0-9]+(?:\.[0-9]+)?)}{};
54        return('VAR',$1) if s/^([A-Za-z][A-Za-z0-9_]*)//;
55        return($1,$1)    if s/^(.)//s;
56      }
57  }
58
59  sub Run {
60      my($self)=shift;
61
62      $input = shift;
63      return $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
64  }

El Método Run

El método Run ilustra como se hace la llamada al método de análisis sintáctico generado, utilizando la técnica de llamada con argumentos con nombre y pasándole las referencias a las dos subrutinas (en Perl, es un convenio que si el nombre de una subrutina comienza por un guión bajo es que el autor la considera privada):

78  sub Run {
79      my($self)=shift;
80
81      $input = shift;
82      return $self->YYParse( yylex => \&_Lexer, yyerror => \&_Error );
83  }

El Atributo YYData y el Método _Error

El método YYData provee acceso a un hash que contiene los datos que están siendo analizados.

La subrutina de manejo de errores _Error imprime el mensaje de error proveído por el usuario, el cual, si existe, fué guardado en $_[0]->YYData->{ERRMSG}.

51  sub _Error {
52          exists $_[0]->YYData->{ERRMSG}
53      and do {
54          print $_[0]->YYData->{ERRMSG};
55          delete $_[0]->YYData->{ERRMSG};
56          return;
57      };
58      print "Syntax error.\n";

El Método _Lexer

A continuación sigue el método que implanta el análisis léxico _Lexer.

45  sub _Lexer {
46      my($parser)=shift;
47
48      # topicalize $input
49      for ($input) {
50        s/^[ \t]+//;      # skip whites
51        return('',undef) unless $input;
52
53        return('NUM',$1) if s{^([0-9]+(?:\.[0-9]+)?)}{};
54        return('VAR',$1) if s/^([A-Za-z][A-Za-z0-9_]*)//;
55        return($1,$1)    if s/^(.)//s;
56      }

El bucle for constituye en este caso una ''frase hecha'': el efecto es hacer que $_ sea un alias de $input. Se simplifica la escritura (obsérvese que no es necesario explicitar el operador de binding en las líneas 50-55, no teniendo que escribir $input =~ s{^([0-9]+(?:\.[0-9]+)?)}{}) y que la computación será mas eficiente al acceder a través de $_ en vez de $input.

El bucle for ($input) se ejecutará mientras la cadena en $input no sea vacía, lo que ocurrirá cuando todos los terminales hayan sido consumidos. sin embargo es un ''falso for'': no hay iteración. El interior del bucle es ejecutado una sola vez en cada llamada.

Eliminamos los blancos iniciales (lo que en inglés se conoce por trimming) y a continuación vamos detectando los números, identificadores y los símbolos individuales.

En primer lugar se comprueba la existencia de datos. Si no es el caso, estamos ante el final de la entrada. Cuando el analizador léxico alcanza el final de la entrada debe devolver la pareja ('',undef).

Ejercicio 8.2.2  
  1. ¿Quién es la variable índice en la línea 49?
  2. ¿Sobre quién ocurre el binding en las líneas 50-54?
  3. ¿Cual es la razón por la que $input se ve modificado aún cuando no aparece como variable para el binding en las líneas 50-54?
  4. Dada la entrada '4 * 3 ' con blancos al final: como termina el analizador léxico. ¿Funciona correctamente en ese caso?

Compilación con eyapp

Construimos el módulo CalcSyntax.pm a partir del fichero CalcSyntax.eyp especificando la gramática, usando elejecutable eyapp:

pl@nereida:~/LEyapp/examples$ eyapp -m CalcSyntax CalcSyntax.eyp
pl@nereida:~/LEyapp/examples$ ls -ltr | tail -3
-rw-r--r-- 1 pl users   1545 2007-10-24 09:03 CalcSyntax.eyp
-rwxr-xr-x 1 pl users    329 2007-10-24 09:05 usecalcsyntax.pl
-rw-r--r-- 1 pl users   7848 2007-10-24 09:36 CalcSyntax.pm
Esta compilación genera el fichero CalcSyntax.pm conteniendo el analizador.

El script eyapp es un frontend al módulo Parse::Eyapp. Admite diversas formas de uso:

La opción -o outfile da el nombre del fichero de salida. Por defecto toma el nombre de la gramática, seguido del sufijo .pm. sin embargo, si hemos especificado la opción -m A::Module::Name el valor por defecto será Name.pm.

La Jerarquía de un Módulo y La Opción -m module

La opción -m module da el nombre al paquete o espacio de nombres o clase encapsulando el analizador. Por defecto toma el nombre de la gramática. En el ejemplo anterior podría haberse omitido. Sin embargo es necesaria cuando se esta desarrollando un módulo con un nombre complejo. Construyamos una distribución con h2xs:

$ h2xs -XA -n Calc::Syntax
Writing Calc-Syntax/lib/Calc/Syntax.pm
Writing Calc-Syntax/Makefile.PL
Writing Calc-Syntax/README
Writing Calc-Syntax/t/Calc-Syntax.t
Writing Calc-Syntax/Changes
Writing Calc-Syntax/MANIFEST
Ahora añadimos el fichero .eyp en el directorio de la librería y producimos el módulo Syntax.pm al compilarlo. Para darle al paquete el nombre Calc::Syntax usamos la opción -m:
$ cd Calc-Syntax/lib/Calc/
$ cp ~/LEyapp/examples/CalcSyntax.eyp .
$ eyapp -m Calc::Syntax  CalcSyntax.eyp
$  head -12 Syntax.pm | cat -n
     1  ###################################################################################
     2  #
     3  #    This file was generated using Parse::Eyapp version 1.081.
     4  #
     5  # (c) Parse::Yapp Copyright 1998-2001 Francois Desarmenien.
     6  # (c) Parse::Eyapp Copyright 2006 Casiano Rodriguez-Leon. Universidad de La Laguna.
     7  #        Don't edit this file, use source file "CalcSyntax.eyp" instead.
     8  #
     9  #             ANY CHANGE MADE HERE WILL BE LOST !
    10  #
    11  ###################################################################################
    12  package Calc::Syntax;
La opción que recomiendo para documentar el módulo es escribir la documentación en un fichero aparte Calc/Syntax.pod.

El Programa Cliente

A continuación escribimos el programa cliente:

$ cd ../..
$ mkdir scripts
$ cd scripts/
$ vi usecalcsyntax.pl
$ cat -n usecalcsyntax.pl
 1  #!/usr/bin/perl -w -I../lib
 2  use strict;
 3  use Calc::Syntax;
 4  use Carp;
 5
 6  sub slurp_file {
 7    my $fn = shift;
 8    my $f;
 9
10    local $/ = undef;
11    if (defined($fn)) {
12      open $f, $fn
13    }
14    else {
15      $f = \*STDIN;
16    }
17    my $input = <$f>;
18    return $input;
19  }
20
21  my $parser = Calc::Syntax->new();
22
23  my $input = slurp_file( shift() );
24  $parser->Run($input);

Ejecución

La ejecución muestra la antiderivación a derechas construida por eyapp:

$ cat prueba.exp
a=2*3

$ usecalcsyntax.pl prueba.exp
exp -> NUM (2)
exp -> NUM (3)
exp -> exp '*' exp
exp -> VAR '=' exp
line -> exp \n
input -> line *

Orden de Ejecución de las Acciones Semánticas

¿En que orden ejecuta YYParse las acciones? La respuesta es que el analizador generado por eyapp construye una derivación a derechas inversa y ejecuta las acciones asociadas a las reglas de producción que se han aplicado. Así, para la frase 2*3 la antiderivación es:

$ NUM + NUM \stackrel{NUM \leftarrow E}{\Longleftarrow} E + NUM \stackrel{NUM \leftarrow E}{\Longleftarrow} E + E \stackrel{E +E \leftarrow E}{\Longleftarrow} E
$

por tanto las acciones ejecutadas son las asociadas con las correspondientes reglas de producción:

  1. La acción asociada con $ E \rightarrow NUM$ :
     NUM                { print "exp -> NUM ($_[1])\n"; }
    
    Esta instancia de exp tiene ahora como atributo 2 (pasado por el analizador léxico).
  2. De nuevo la acción asociada con $ E \rightarrow NUM$ :
     NUM                { print "exp -> NUM ($_[1])\n"; }
    
    Esta nueva instancia de exp tiene como atributo 3.
  3. La acción asociada con $ E \rightarrow E * E$ :
      | exp '*' exp        { print "exp -> exp '*' exp\n"; }
    
Obsérvese que la antiderivación a derechas da lugar a un recorrido ascendente y a izquierdas del árbol:

$\displaystyle E_3(E_1(NUM[2]), *, E_2(NUM[2]))$    

Los subíndices indican el orden de visita de las nodos/producciones.



Subsecciones
next up previous contents index PLPL moodlepserratamodulosperlmonksperldocapuntes LHPgoogleetsiiullpcgull
Sig: Depuración de Errores Sup: Análisis Sintáctico con Parse::Eyapp Ant: Conceptos Básicos para el Err: Si hallas una errata ...
Casiano Rodríguez León
2012-05-22