jueves, 1 de diciembre de 2011

miniSL parte 17 - El analizador léxico

Hasta aquí hemos visto la semántica de nuestro lenguaje script mínimo. A partir de ahora, empezamos con el reconocedor sintáctico. Debido a que nuestro lenguaje tiene una sintaxis no trivial, nos ocupará bastante tiempo describirlo. (Una sintaxis trivial es la del LISP)

Generalmente los reconocedores sintácticos se separan en dos partes (por ejemplo, el clásico LEX&YACC). La primera llamada analizador léxico (scanner o lexer) reconoce varios caracteres del fichero de entrada (por ejemplo 3, 5 y 6) y nos devuelve un elemento significativo llamado token (el número 356). La segunda parte es el analizador sintáctico propiamente dicho (llamado parser) que acepta los tokens y devuelve un AST. Veremos esta segunda parte más adelante y nos centramos en la generación de tokens.

En miniSL hay varios tipos de token que se listan en la enumeración TOKEN_TYPE.
enum TOKEN_TYPE { T_NONE, T_RAW, T_LITERAL, T_SYMBOL, T_NAME };
El tipo T_NONE indica que no se han reconocido los caracteres. Usamos T_RAW cuando el token es un único carácter (por ejemplo, una llave { o una coma , ). Es importante saber aquí que el final de fichero, un carácter llamado EOF, también se guarda en un token de tipo T_RAW. El tipo de token T_LITERAL indica o bien un número, o bien una cadena, en general una celda literal. Guardaremos el valor que corresponda en una celda del tipo adecuado. El token de tipo T_SYMBOL es un identificador formado por símbolos tales como +, <= o !=. Finalmente, T_NAME se usa para identificadores alfanuméricos como x, map o iterator. Tanto los tokens de tipo T_SYMBOL como los T_NAME guardan el identificador en una celda de tipo STRING_LIT.

La información del tipo de token y la información relativa al token se guardan en la estructura TOKEN que es la siguiente.
struct TOKEN
 {
  TOKEN() : type(T_NONE) {}
  TOKEN(TOKEN_TYPE t, CELL* d) : type(t), data(d) {}
  TOKEN(ISTREAM::int_type r) : type(T_RAW), raw(r) {}

  TOKEN_TYPE type;
  union
  {
   CELL* data;
   ISTREAM::int_type raw;
  };
 };
Los constructores fuerzan que cuando el TOKEN sea de tipo T_RAW, la información relacionada es un único carácter guardado en la variable miembro raw. En los otros tipos lo guardaremos en la celda apuntada por la variable miembro data. Esta estructura no es muy segura porque podríamos colar un T_RAW en el constructor que toma una celda. Vigilaremos que eso no ocurra.

Ahora queda leer los caracteres y generar el token correspondiente. De eso se encarga la función ReadToken(). La función ReadToken() devuelve el siguiente token leído y lo consume. De esta forma, cada vez que llamemos a ReadToken() avanzaremos por el fichero hasta obtener el carácter de fin de fichero EOF. Sin embargo, muchas veces no querremos avanzar por el fichero. Querremos únicamente saber cuál es el siguiente token, sin consumirlo. De esto se encarga la función PeekToken().

Nota: “Peek” en inglés significa “ojear” en el sentido de mirar a hurtadillas.

Script::TOKEN Script::PeekToken(ISTREAM& i)
{
 if(m_Ahead.type!=T_NONE)
  return m_Ahead;

 m_Ahead=ReadToken(i);
 return m_Ahead;
}
El funcionamiento de PeekToken() es muy simple porque se basa en ReadToken(). Primero, comprueba si ya hemos leído el siguiente token que se ha guardado en m_Ahead. Esta no es más que una variable miembro en la clase Script (para los que no recuerden la clase Script, ver la parte séptima).
TOKEN m_Ahead;
Si m_Ahead guarda ya el token leído, lo devuelve. Si m_Ahead no contiene el token leído, lo lee con ReadToken() y lo guarda en m_Ahead para siguientes PeekToken()s. De esta manera, llamar a PeekToken() varias veces, sólo llama a ReadToken() la primera vez y usa m_Ahead el resto.

¿Por qué es importante saber cómo funciona PeekToken() antes de saber cómo funciona ReadToken()? Muy sencillo. Si m_Ahead contiene un token y llamamos a ReadToken(), hay que vaciar m_Ahead. De esta forma se consume.
Script::TOKEN Script::ReadToken(ISTREAM& i)
{
 if(m_Ahead.type!=T_NONE)
 {
  TOKEN t=m_Ahead;
  m_Ahead.type=T_NONE;
  return t;
 }
A partir de este momento empieza, realmente la lectura de caracteres dentro de ReadToken(). La primera acción es saltarse el espacio en blanco. Nuestra sintaxis va a ignorar los espacios en blanco.
SkipWhitespace(i);
Luego, vamos a ojear el siguiente carácter. Podréis comprobar que no he inventado nada nuevo al llamar PeekToken() a mi función ya que la biblioteca estándar de C++ llama a esta función peek().
ISTREAM::int_type c=i.peek();
Según sea ese carácter, decidiremos leer un token de un tipo o de otro. Si es una doble comilla, será una cadena.
if(c=='"')     return TOKEN(T_LITERAL, &ReadString(i, false));
Si es un símbolo ASCII extendido, lo examinaremos. Para eso usamos la comparación c<256.
if(c<256)
 {
  if(isalpha(c) || c=='_') return ReadName(i);
  if(isdigit(c))    return TOKEN(T_LITERAL, &ReadNumber(i));
  if(CELL::IsSymbol(c))  return TOKEN(T_SYMBOL, &ReadSymbol(i));
Hasta aquí todo sencillo. Si es un carácter alfanumérico, lo leemos como un nombre. Si es un dígito, como un número. Si es un símbolo, como símbolo.

Pero ahora vamos a añadir una puerta trasera que ya ha sido muy útil. De hecho, nos ha permitido imprimir de manera uniforme los identificadores. Básicamente consiste en poner una arroba delante de una cadena. Entonces, en vez de cadena tomamos ese token como un identificador. Será lo mismo escribir mi_variable que @”mi_variable”. También añadiremos la sintaxis de arroba seguido de símbolo con la misma idea. Será lo mismo escribir 3+5 que @+(3,5).
if(c=='@') //Symbol or string as name
  {
   i.get();
   if(i.peek()=='"')    return TOKEN(T_NAME, &ReadString(i, true));
   if(CELL::IsSymbol(i.peek())) return TOKEN(T_NAME, &ReadSymbol(i));
   throw L"Expecting a symbol or a string after @";
  }
 }
Si el carácter no es ASCII extendido, será probablemente el carácter EOF así que lo guardamos como un token T_RAW. Además, si ninguna de las condiciones anteriores se dio, será un carácter ASCII extendido no usado por otro tipo de token. Deberá ser T_RAW también.
//Raw one-character token
 return TOKEN(i.get());
} 
Nota: Esto no funciona con UTF-8 que sería lo suyo. Introduciríamos una complejidad que sobrepasa los objetivos de este pequeño lenguaje de script.

Y ya hemos leído el token. Ahora queda examinar todas esas funciones de ayuda que hemos utilizado. Empezaremos con SkipWhitespace() en la siguiente parte y seguiremos con ReadString() y demás más adelante.