Subsecciones

Análisis Léxico

Comenzaremos con la parte mas sencilla del compilador: el analizador léxico. Habitualmente el término ``análisis léxico'' se refiere al tratamiento de la entrada que produce como salida la lista de tokens. Un token hace alusión a las unidades mas simples que tiene significado. Habitualmente un token o lexema queda descrito por una expresión regular. Léxico viene del griego lexis, que significa ``palabra''. Perl es, sobra decirlo, una herramienta eficaz para encontrar en que lugar de la cadena se produce un emparejamiento. Sin embargo, en el análisis léxico, el problema es encontrar la subcadena a partir de la última posición en la que se produjo un emparejamiento y que es aceptada por una de las expresiones regulares que definen los lexemas del lenguaje dado.

La estructura general del analizador léxico consiste en un bucle en el que se va recorriendo la entrada, buscando por un emparejamiento con uno de los patrones/lexemas especificados y, cuando se encuentra, se retorna esa información al analziador sintáctico. Como no tenemos escrito el analaizador sintáctico simplemente iremos añadiéndo los terminales al final de una lista.

Una iteración del bucle tiene la forma de una secuencia de condicionales en las que se va comprobando si la entrada casa con cada una de las expresiones regulares que definen los terminales del lenguaje. Las condiciones tienen un aspecto similar a este:

     ...
     if (m{\G\s*(\d+)}gc) {
       push @tokens, 'NUM', $1;
     } 
     elsif (m{\G\s*([a-z_]\w*)\b}igc) {
       push @tokens, 'ID', $1;
     } 
     ...

Una expresión como m{\G\s*(\d+)}gc es una expresión regular. Es conveniente que en este punto repase la introducción a las expresiones regulares en [10].

El Operador de Binding

Nótese que, puesto que no se menciona sobre que variable se hace el binding (no se usa ninguno de los operadores de binding =~ y !~): se entiende que es sobre la variable por defecto $_ sobre la que se hace el matching.

Casando a partir del Ültimo Emparejamiento

El ancla \G casa con el punto en la cadena en el que terminó el último emparejamiento.

La expresión regular describiendo el patrón de interés se pone entre paréntesis para usar la estrategia de los paréntesis con memoria (véanse 31.1.4 y 31.1.1).

Las opciones c y g son especialmente útiles para la construcción del analizador.

La opción `g`

Como lo usamos en un contexto escalar, la opción g itera sobre la cadena, devolviendo cierto cada vez que casa, y falso cuando deja de casar. Se puede averiguar la posicion del emparejamiento utilizando la función pos. (véase la sección 31.1.6 para mas información sobre la opción g).

La opción `c`

La opción /c afecta a las operaciones de emparejamiento con /g en un contexto escalar. Normalmente, cuando una búsqueda global escalar tiene lugar y no ocurre casamiento, la posición de comienzo de búsqueda es reestablecida al comienzo de la cadena. La opción /c hace que la posición inicial de emparejamiento permanezca donde la dejó el último emparejamiento con éxito y no se vaya al comienzo. Al combinar esto con el ancla \G, la cuál casa con el final del último emparejamiento, obtenemos que la combinación

                            m{\G\s*(...)}gc

logra el efecto deseado: Si la primera expresión regular en la cadena elsif fracasa, la posición de búsqueda no es inicializada de nuevo gracias a la opción c y el ancla \G sigue recordando donde terminó el ultimo casamiento.

La opción `i`

Por último, la opción i permite ignorar el tipo de letra (mayúsculas o minúsculas).

Repase la sección 31.1.6 para ver algunas de las opciones mas usadas.

Código del Analizador Léxico

Este es el código completo de la subrutina scanner que se encarga del análisis léxico:

 1 package Lexical::Analysis;
 2 sub scanner {
 3   local $_ = shift;
 4   { # Con el redo del final hacemos un bucle "infinito"
 5     if (m{\G\s*(\d+)}gc) {
 6       push @tokens, 'NUM', $1;
 7     } 
 8     elsif (m{\G\s*int\b}igc) {
 9       push @tokens, 'INT', 'INT';
10     } 
11     elsif (m{\G\s*string\b}igc) {
12       push @tokens, 'STRING', 'STRING';
13     } 
14     elsif (m{\G\s*p\b}igc) {
15       push @tokens, 'P', 'P'; # P para imprimir
16     } 
17     elsif (m{\G\s*([a-z_]\w*)\b}igc) {
18       push @tokens, 'ID', $1;
19     } 
20     elsif (m{\G\s*\"([^"]*)\"}igc) {
21       push @tokens, 'STR', $1;
22     } 
23     elsif (m{\G\s*([+*()=;,])}gc) {
24       push @tokens, 'PUN', $1;
25     }
26     elsif (m{\G\s*(\S)}gc) { # Hay un caracter "no blanco"
27       Error::fatal "Caracter invalido: $1\n";
28     }
29     else {
30       last;
31     }
32     redo;
33   }
34 }

Relación de corutina con el Analizador Sintáctico

Si decidieramos establecer una relación de corutina con el analizador léxico los condicionales se pueden programar siguiendo secuencias con esta estructura:

      return ('INT', 'INT') if (m{\G\s*int\b}igc);

Manejo de Errores

Para completar el analizador solo quedan declarar las variables usadas y las subrutinas de manejo de errores:

######## global scope variables
our @tokens = ();
our $errorflag = 0;

package Error;

sub error($) {
  my $msg = shift;
  if (!$errorflag) {
    warn "Error: $msg\n";
    $errorflag = 1;
  }
}

sub fatal($) {
  my $msg = shift;
  die "Error: $msg\n";
}

El uso de our es necesario porque hemos declarado al comienzo del módulo use strict. El pragma use strict le indica al compilador Perl que debe considerar como obligatorias un conjunto de reglas de buen estilo de programación. Entre otras restricciones, el uso del pragma implica que todas las variables (no-mágicas) deben ser declaradas explícitamente (uso de my, our, etc.) La declaración our se describe en [10].

Ejercicio: La opción `g`

Explique cada una de las líneas que siguen:

$ perl -wde 0
main::(-e:1):   0
  DB<1> $x = "ababab"
  DB<2> $x =~ m{b}g; print "match= ".$&." pos = ".pos($x)
match= b pos = 2
  DB<3> $x =~ m{b}g; print "match= ".$&." pos = ".pos($x)
match= b pos = 4
  DB<4> $x =~ m{b}g; print "match= ".$&." pos = ".pos($x)
match= b pos = 6
  DB<5> print "falso" unless $x =~ m{b}g
falso

Ejercicio: Opciones `g` y `c` en Expresiones Regulares

Explique cada una de las conductas que siguen

¿Porqué en la línea 18 se casa con la primera b?

  DB<5> $x = "bbabab"
  DB<6> $x =~ m{a}g; print "match= ".$&." pos = ".pos($x)
match= a pos = 3
  DB<7> $x =~ m{b}g; print "match= ".$&." pos = ".pos($x)
match= b pos = 4
  DB<8> $x =~ m{c}g; print "match= ".$&." pos = ".pos($x)
Use of uninitialized value in concatenation (.) 
  DB<18> $x =~ m{b}g; print "match= ".$&." pos = ".pos($x)
match= b pos = 1

¿Porqué en la línea 27 se casa con la última b?

  DB<23> $x = "bbabab"
  DB<24> $x =~ m{a}g; print "match= ".$&." pos = ".pos($x)
match= a pos = 3
  DB<25> $x =~ m{b}g; print "match= ".$&." pos = ".pos($x)
match= b pos = 4
  DB<26> $x =~ m{c}gc
  DB<27> $x =~ m{b}g; print "match= ".$&." pos = ".pos($x)
match= b pos = 6

¿Porqué en la línea 5 se produce casamiento y en la línea 8 no?

  DB<3> $x = "bcbabab"
  DB<4> $x =~ m{b}gc; print "match= ".$&." pos = ".pos($x)
match= b pos = 1
  DB<5> $x =~ m{a}gc; print "match= ".$&." pos = ".pos($x)
match= a pos = 4

  DB<6> $x = "bcbabab"
  DB<7> $x =~ m{b}gc; print "match= ".$&." pos = ".pos($x)
match= b pos = 1
  DB<8> $x =~ m{\Ga}gc; print "match= ".$&." pos = ".pos($x)
Use of uninitialized value in concatenation 
match=  pos = 1

Ejercicio: El orden de las expresiones regulares

¿Que ocurriría en la subrutina scanner si el código en las líneas 17-19 que reconoce los identificadores se adelanta a la línea 8? ¿Que ocurriría con el reconocimiento de las palabras reservadas como INT? ¿Seguiría funcionando correctamente el analizador?

Ejercicio: Regexp para cadenas

En la rutina scanner. ¿Es legal que una cadena correspondiente al terminal STR contenga retornos de carro entre las comillas dobles?

Ejercicio: El `or` es vago

Explique el resultado de la siguiente sesión con el depurador:

lhp@nereida:~/Lperl/src/topdown/PL0506/03lexico/PL-Tutu/lib/PL/Lexical$ perl -de 0
  DB<1> 'bb' =~ m{b|bb}; print $&
  b
  DB<2> 'bb' =~ m{bb|b}; print $&
  bb

Perl convierte la expresión regular en un NFA. A diferencia de lo que ocurre en otras herramientas, el NFA no es convertido en un DFA. El NFA es entonces simulado. ¿Que está ocurriendo en la simulación?

Práctica: Números de Línea, Errores, Cadenas y Comentarios

Extienda el analizador léxico para que:

Reescriba la expresión regular para las cadenas de manera que acepte comillas dobles escapadas \" en el interior de una cadena. Por ejemplo en "esta \"palabra\" va entre comillas".
Analice esta solución ¿Es correcta?:
```
 DB<1> $stringre = qr{"(\\.|[^\\"])*"}
 DB<2> print $& if '"esta \"palabra\" va entre comillas"' =~ $stringre
 "esta \"palabra\" va entre comillas"
```
Consuma comentarios a la Perl: cualesquiera caracteres después de una almohadilla hasta el final de la línea (# ...).

Consuma comentarios no anidados a la C (/* ... */.). Repase las secciones sobre expresiones regulares no ``greedy'' (p. ej. sección 31.1.1) y la sección 31.1.1. Recuerde que, en una expresión regular, la opción /s hace que el punto '.' empareje con un retorno de carro \n. Esto es, el punto ``casa'' con cualquier carácter.

Observe el siguiente ejemplo:

pl@nereida:~/src/perl/testing$ cat -n ccomments.pl
 1  #!/usr/bin/perl -w
 2  use strict;
 3
 4  sub showmatches {
 5   my ($x, $re) = @_;
 6
 7    for (my $i = 0; $x =~ /$re/gsx; $i++) {
 8      print "matching $i: $1\n";
 9      $i++;
10    }
11  }
12
13  my $x = <<'EOC';
14  if (x) {
15    /* a comment */ return x + 1; /* another comment */
16  }
17  else {
18    return x + 2; /* a last comment */
19  }
20  EOC
21
22  print "\n************************\n";
23
24  my $greedy = q{ (
25           /\*  # Abrir comentario
26           .*   # Consumir caracteres (greedy)
27           \*/  # Cerrar comentario
28           )
29  };
30  print "Greedy:\n";
31  showmatches($x, $greedy);
32
33  print "\n************************\n";
34
35  my $lazy = q{ (
36           /\*  # Abrir comentario
37           .*?  # Consumir caracteres (lazy)
38           \*/  # Cerrar comentario
39           )
40  };
41  print "Lazy:\n";
42  showmatches($x, $lazy);

Cuando se ejecuta produce:

pl@nereida:~/src/perl/testing$ ccomments.pl

************************
Greedy:
matching 0: /* a comment */ return x + 1; /* another comment */
}
else {
  return x + 2; /* a last comment */

************************
Lazy:
matching 0: /* a comment */
matching 2: /* another comment */
matching 4: /* a last comment */

Explique la conducta.

Números en punto flotante (como -1.32e-04 o .91). El siguiente ejemplo intenta ayudarle en la búsqueda de la solución:

lhp@nereida:~$ perl -de 0
  DB<1> print "Si" if  ('.5' =~ m{\d+})
Si
  DB<2> print "Si" if  ('.5' =~ m{^\d+})

  DB<3> print "Si" if  '0.7' =~ m{^\d+(\.\d+)?(e[+-]?\d+)?$}
Si
  DB<4> print "Si" if  '.7' =~ m{^\d+(\.\d+)?(e[+-]?\d+)?$}

  DB<5> print "Si" if  '1e2' =~ m{^\d+(\.\d+)?(e[+-]?\d+)?$}
Si
  DB<6> print "Si " while  'ababa' =~ m{a}g
Si Si Si
  DB<7> print "@a" if @a = 'ababa' =~ m{(a)}g
a a a

¿Sabría decir porque la respuesta al primer comando del depurador es si?.

Tenga presente el posible conflicto entre los terminales INT y FLOAT. Si la entrada contiene 3.5 el terminal debería ser (FLOAT, '3.5') y no (INT, 3), ('.', '.'), (INT, 5).
En esta práctica si lo desea puede instalar y usar el módulo Regexp::Common mantenido por Abigail el cual provee expresiones regulares para las situaciones mas comunes: números, teléfonos, IP, códigos postales, listas, etc. Puede incluso usarlo para encontrar soluciones a las cuestiones planteadas en esta práctica:
```
nereida:~/doc/casiano/PLBOOK/PLBOOK> perl -MRegexp::Common -e 'print "$RE{num}{int}\n"'
(?:(?:[+-]?)(?:[0123456789]+))
```
Podemos hacer uso directo del hash %RE directamente en las expresiones regulares aprovechando que estas interpolan las variables en su interior:
```
nereida:/tmp> cat -n prueba.pl
     1  #!/usr/bin/perl -w
     2  use strict;
     3  use Regexp::Common;
     4
     5  my $input = <>;
     6
     7  print "$&\n" if $input =~ /^$RE{num}{real}$/;
nereida:/tmp> ./prueba.pl
23.45
23.45
nereida:/tmp> ./prueba.pl
jshdf
nereida:/tmp>
```

Para mejorar la calidad de los mensajes de error extienda el par (terminal, valor) devuelto por el scanner a un par (terminal, [valor, número de línea ]) cuya segunda componente es un array anónimo conteniendo el valor y el número de línea en el que aparece el terminal.

El siguiente extracto de un analizador léxico muestra como hacerlo:

sub _Lexer {

  return('', undef) unless defined($input);

  #Skip blanks
      $input=~m{\G((?:
              \s+       # any white space char
          |   \#[^\n]*  # Perl like comments
          )+)}xsgc
    and do {
        my($blanks)=$1;

        #Maybe At EOF
            pos($input) >= length($input)
        and return('', undef);
        $tokenend += $blanks =~ tr/\n//;
    };
    
    $tokenbegin = $tokenend;

      $input=~/\G(and)/gc
    and return($1, [$1, $tokenbegin]);

      $input=~/\G(?:[A-Za-z_][A-Za-z0-9_]*::)*([A-Za-z_][A-Za-z0-9_]*)/gc
    and do {
      return('IDENT', [$1, $tokenbegin]);
    };

    ....................

        $input=~/\G{/gc
    and do {
        my($level,$from,$code);

        $from=pos($input);

        $level=1;
        while($input=~/([{}])/gc) {
                substr($input,pos($input)-1,1) eq '\\' #Quoted
            and next;
                $level += ($1 eq '{' ? 1 : -1)
            or last;
        }
            $level
        and  _SyntaxError("Not closed open curly bracket { at $tokenbegin");
        $code = substr($input,$from,pos($input)-$from-1);
        $tokenend+= $code=~tr/\n//;
        return('CODE', [$code, $tokenbegin]);
    };


    #Always return something
      $input=~/\G(.)/sg
    and do {
      $1 eq "\n" and ++$tokenend;
      return ($1, [$1, $tokenbegin]);
    };
    #At EOF
    return('', undef);
}

El operador tr ha sido utilizado para contar los retornos de carro (descrito en la sección 31.5). El operador, ademas de reemplazar devuelve el número de carácteres reeemplazados o suprimidos:

$cuenta = $cielo =~ tr/*/*/; # cuenta el numero de estrellas en cielo

Para aprender soluciones alternativas consulte perldoc -q 'substring'.

Mejore sus mensajes de error ahora que lleva la cuenta de los números de línea. En vez de usar las rutinas error y fatal introducidas en la sección anterior escriba una sola rutina que recibe el nivel de severidad del error (parámetro $level en el siguiente ejemplo) y ejecuta la acción apropiada. El código de _SyntaxError ilustra como hacerlo:

sub _SyntaxError {
  my($level,$message,$lineno)=@_;

  $message= "*".
      [ 'Warning', 'Error', 'Fatal' ]->[$level].
      "* $message, at ".
      ($lineno < 0 ? "eof" : "line $lineno")." at file $filename\n";

      $level > 1
  and die $message;

  warn $message;

  $level > 0 and ++$nberr;

      $nberr == $max_errors
  and die "*Fatal* Too many errors detected.\n"
}

Casiano Rodríguez León
2013-04-23