Crea tu propio compilador – Parte 5 – Completando el analizador léxico

En el artículo anterior vimos como están estructurados los compiladores, identificando los módulos que los componen.

Como una ayuda, para complementar nuestro entendimiento, el siguiente diagrama (obtenido gracias a Wikipedia) muestra como estas distintas partes se enlazan:

 

Aunque no es común tener un compilador que compile dos lenguajes fuente, sí es posible tener dos compiladores que generen el mismo lenguaje intermedio (como el “bytecode”, generado por Java y diversos compiladores más).

Lo que si se suele usar es partir de un mismo código intermedio para poder generar diversos códigos máquina o simplemente interpretar ese código intermedio.

Ahora, volviendo a nuestro compilador Titan, continuaremos con nuestro analizador léxico.

En el artículo anterior, ya habíamos implementado un código sencillo para la extracción de caracteres, de un archivo de texto pero aún no podíamos identificar tokens, porque para ello necesitamos de funciones de extracción más avanzadas que manejen cadenas.

Primero necesitaremos algunas rutinas de identificación de caracteres:

function IsAlphaUp: integer;
{Indica si el caracter en "srcChar" es alfabético mayúscula.}
begin
   if chr(srcChar)>='A' then begin
     if chr(srcChar)<='Z' then begin
       exit(1);
     end else begin
       exit(0);
     end;
   end else begin
     exit(0);
   end;
end;
function IsAlphaDown: integer;
{Indica si el caracter en "srcChar" es alfabético nimúscula.}
begin
   if chr(srcChar)>='a' then begin
     if chr(srcChar)<='z' then begin
       exit(1);
     end else begin
       exit(0);
     end;
   end else begin
     exit(0);
   end;
end;
function IsNumeric: integer;
{Indica si el caracter en "srcChar" es alfabético nimúscula.}
begin
   if chr(srcChar)>='0' then begin
     if chr(srcChar)<='9' then begin
       exit(1);
     end else begin
       exit(0);
     end;
   end else begin
     exit(0);
   end;
end;

Notar que, debido a las restricciones, estamos haciendo uso de una variable numérica (srcChar) en lugar de una de tipo “char”, lo que facilitaría el código.

Notar también que estas rutinas no serían necesarias si pudiéramos usar conjuntos (una característica útil en el lenguaje Pascal) en nuestro código, pero como estamos restringiendo las funcionalidades del lenguaje, no nos queda otra que implementar el reconocimiento de caracteres de forma “manual”.

Pero estas funciones están muy por debajo de la tarea de extraer tokens (que es lo que hacen los “lexers”), solo identifican caracteres, así que debemos crear otras funciones de mayor nivel que nos acerquen más a los tokens.

Pero antes de entrar en estas rutinas necesitaremos dos variables adicionales:  srcToken y srcToktyp, declaradas de la siguiente forma:

  srcToken : string;  //Token actual
  srcToktyp: integer; // Tipo de token

La variable “srcToken” servirá para guardar el token actual, el último que hemos identificado. Lo mantenemos en una variables para poder hacer comparaciones rápidas.

La variable “srcToktyp” es un número que nos servirá como identificador del tipo de token que tenemos en “srcToken”, y tendrá la siguiente interpretación:

//0-> Fin de línea
//1-> Espacio
//2-> Identificador: “var1”, “VARIABLE”
//3-> Literal numérico: 123, -1
//4-> Literal cadena: “Hola”, “hey”
//5-> Comentario
//9-> Desconocido.

Esta clasificación obedece a la que habíamos planteado para nuestro lenguaje. Es decir, que identificaremos al token mediante el valor de una variable numérica. Esto es común en la mayoría de analizadores léxicos aunque se prefiere usar tipos enumerados, en lugar de simples números, pero ya sabemos que aquí nos hemos impuesto restricciones en el lenguaje.

Ahora para ir avanzando en la identificación y extracción de tokens, necesitamos de rutinas especiales. El enfoque que planteo aquí, es usar una rutina para cada tipo de token que se vaya a procesar, en lugar de usar una sola rutina para identificar a todos los tipos de tokens. De esta forma se simplifica el código de identificación.

Las siguientes funciones utilizan las rutinas vistas en el artículo anterior y las rutinas de identificación que hemos mostrado aquí para explorar líneas e ir extrayendo caracteres (incrementando el índice “idxLine”) de acuerdo al tipo de elemento que manejen:

procedure ExtractIdentifier;
var
  IsToken: integer;  //Variable temporal
begin
  srcToken := '';
  srcToktyp := 2;
  IsToken := 1;
  while IsToken=1 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Pasa al siguiente
    if EndOfLine=1 then begin     //No hay más caracteres
      exit;
    end;
    ReadChar;  //Lee sigte. en "srcChar"
    IsToken := IsAlphaUp or IsAlphaDown;
    IsToken := IsToken or IsNumeric;
  end;
end;
procedure ExtractSpace;
var
  IsToken: integer;  //Variable temporal
begin
  srcToken := '';
  srcToktyp := 1;
  IsToken := 1;
  while IsToken=1 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Pasa al siguiente
    if EndOfLine=1 then begin     //No hay más caracteres
      exit;
    end;
    ReadChar;  //Lee sigte. en "srcChar"
    IsToken := ord(srcChar = ord(' '));
  end;
end;
procedure ExtractNumber;
var
  IsToken: integer;  //Variable temporal
begin
  srcToken := '';
  srcToktyp := 3;
  IsToken := 1;
  while IsToken=1 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Pasa al siguiente
    if EndOfLine=1 then begin     //No hay más caracteres
      exit;
    end;
    ReadChar;  //Lee sigte. en "srcChar"
    IsToken := IsNumeric;
  end;
end;
procedure ExtractString;
var
  IsToken: integer;  //Variable temporal
begin
  srcToken := '';
  srcToktyp := 4;
  IsToken := 1;
  while IsToken=1 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Pasa al siguiente
    if EndOfLine=1 then begin     //No hay más caracteres
      exit;
    end;
    ReadChar;  //Lee sigte. en "srcChar"
    IsToken := ord(srcChar <> ord('"'));
  end;
  NextChar;  //Toma la comilla final
  srcToken := srcToken + '"';   //Acumula
end;
procedure ExtractComment;
begin
  srcToken := '';
  srcToktyp := 5;
  while EndOfLine=0 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Toma caracter
  end;
end;

Observar que las rutinas de exploración de caracteres se parece al mismo esquema que vimos en el artículo anterior, pero ahora hemos agregado condicionales adicionales para filtrar los caracteres correspondientes.

Algunas partes del código tienen apariencia extraña porque se están simplificando las expresiones para cumplir con la limitación de usar expresiones sencillas.

Si bien estas rutinas se han definido de forma que se adapten a nuestro lenguaje, el lector bien puede hacer las modificaciones que considere necesario para adaptarlas a su lenguaje, si tiene diferencias sustanciales (y no solo identificadores diferentes) al que yo he propuesto.

Todas las rutinas cumplen con dejar el resultado en “srcToken” y actualizan “srcToktyp”. Pero estas rutinas no identifican al token en sí, sino que requieren que se haga una identificación previa para ir revisando los caracteres siguientes e ir discriminando si pertenecen o no al tipo de token que manejan. Se podría decir que estas funciones procesan los “caracteres siguientes”.

Lo que nos faltaría es una rutina, que pueda hacer la primera identificación, en base al primer caracter (o dos primeros), qué tipo de token se nos presenta. Esta identificación es simple, porque por ejemplo, un carácter numérico nos indicará que el token que sigue es de tipo 3 (literal numérico), y debemos pasar el tratamiento a la rutina correspondiente.

La siguiente rutina hace precisamente este trabajo:

procedure NextToken;
//Lee un token y devuelve el texto en "srcToken" y el tipo en "srcToktyp".
//Mueve la posición de lectura al siguiente token.
begin
   srcToktyp := 9;  //Desconocido por defecto
   if EndOfFile=1 then begin
     srcToken := '';
     srcToktyp := 0;  //Fin de línea
     exit;
   end;
   if EndOfLine=1 then begin
     srcToken := '';
     srcToktyp := 0;  //Fin de línea
     NextLine;
   end else begin
     //Hay caracteres por leer en la línea
     ReadChar;  //Lee en "srcChar"
     if IsAlphaUp=1then begin
       ExtractIdentifier;
       exit;
     end;
     if IsAlphaDown=1 then begin
       ExtractIdentifier;
       exit;
     end;
     if srcChar = ord('_') then begin
       ExtractIdentifier;
       exit;
     end;
     if IsNumeric=1 then begin
       ExtractNumber;
       exit;
     end;
     if srcChar = ord(' ') then begin
       ExtractSpace;
       exit;
     end;
     if srcChar = ord('"') then begin
       ExtractString;
       exit;
     end;
     if srcChar = ord('/') then begin
       if NextCharIsSlash = 1 then begin
         ExtractComment;
         exit;
       end;
     end;
     srcToken := chr(srcChar);   //Acumula
     srcToktyp := 9;
     NextChar;  //Pasa al siguiente
   end;
end;

Este procedimiento permite, ahora sí, leer el archivo fuente y determinar a que tipo de token pertenece el caracter actual para luego ir extrayendo los caracteres que corresponden a ese token, devolviendo el token en “srcToken” y el tipo en “srcToktyp”.

Con cada llamada que se haga a NextToken(), se tendrá un nuevo token en “srcToken”, mientras no se llegue al final del archivo.

La identificación de comentarios, tiene un nivel de complicación adicional por cuanto se requiere de dos caracteres “//” para una identificación confiable y no confundir con el operador de división. Para ello se ha implementado la función NextCharIsSlash () que permite “echar un vistazo” al siguiente caracter, porque si se llama dos veces a ReadChar() y se encontrara que no se tiene el símbolo “//” ya no habría forma de volver atrás, para continuar con una exploración normal.

Lógicamente existen muchas formas de enfrentar este problema, pero lo que aquí planteo es solo una solución práctica basada en mi experiencia como desarrollador.

El siguiente código integra todas las rutinas vistas anteriormente y ahora sí podemos decir que tenemos ya a nuestro analizador léxico completo incluyendo a la función NextCharIsSlash():

{Proyecto de un compilador con implementación mínima para ser autocontenido.}
program titan;
var
  //Manejo de código fuente
  inFile   : Text;    //Archivo de entrada
  outFile  : Text;    //Archivo de salida
  idxLine  : integer;
  srcLine  : string[255]; //Línea leída actualmente
  srcRow   : integer;  //Número de línea áctual
  srcChar  : byte;      //Caracter leído actualmente

  srcToken : string;
  srcToktyp: integer; // Tipo de token:
                      //0-> Fin de línea
                      //1-> Espacio
                      //2-> Identificador: "var1", "VARIABLE"
                      //3-> Literal numérico: 123, -1
                      //4-> Literal cadena: "Hola", "hey"
                      //5-> Comentario
                      //9-> Desconocido.
function EndOfLine: integer;
begin
  if idxLine > length(srcLine) then exit(1) else exit(0);
end;
function EndOfFile: integer;
{Devuelve TRUE si ya no hay caracteres ni líneas por leer.}
begin
  if eof(inFile) then begin
    if EndOfLine<>0 then exit(1) else exit(0);
  end else begin
    exit(0);
  end;
end;
procedure NextLine;
//Pasa a la siguiente línea del archivo de entrada
begin
  if eof(inFile) then exit;
  readln(inFile, srcLine);  //Lee nueva línea
  inc(srcRow);
  idxLine:=1;    //Apunta a primer caracter
end;
procedure ReadChar;
{Lee el caracter actual y actualiza "srcChar".}
begin
   srcChar := ord(srcLine[idxLine]);
end;
procedure NextChar;
{Incrementa "idxLine". Pasa al siguiente caracter.}
begin
   idxLine := idxLine + 1;  //Pasa al siguiente caracter
end;
function NextCharIsSlash: integer;
{Incrementa "idxLine". Pasa al siguiente caracter.}
begin
  if idxLine > length(srcLine)-1 then exit(0);
  if srcLine[idxLine+1] = '/' then exit(1);
  exit(0);
end;
function IsAlphaUp: integer;
{Indica si el caracter en "srcChar" es alfabético mayúscula.}
begin
   if chr(srcChar)>='A' then begin
     if chr(srcChar)<='Z' then begin
       exit(1);
     end else begin
       exit(0);
     end;
   end else begin
     exit(0);
   end;
end;
function IsAlphaDown: integer;
{Indica si el caracter en "srcChar" es alfabético nimúscula.}
begin
   if chr(srcChar)>='a' then begin
     if chr(srcChar)<='z' then begin
       exit(1);
     end else begin
       exit(0);
     end;
   end else begin
     exit(0);
   end;
end;
function IsNumeric: integer;
{Indica si el caracter en "srcChar" es alfabético nimúscula.}
begin
   if chr(srcChar)>='0' then begin
     if chr(srcChar)<='9' then begin
       exit(1);
     end else begin
       exit(0);
     end;
   end else begin
     exit(0);
   end;
end;
procedure ExtractIdentifier;
var
  IsToken: integer;  //Variable temporal
begin
  srcToken := '';
  srcToktyp := 2;
  IsToken := 1;
  while IsToken=1 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Pasa al siguiente
    if EndOfLine=1 then begin     //No hay más caracteres
      exit;
    end;
    ReadChar;  //Lee sigte. en "srcChar"
    IsToken := IsAlphaUp or IsAlphaDown;
    IsToken := IsToken or IsNumeric;
  end;
end;
procedure ExtractSpace;
var
  IsToken: integer;  //Variable temporal
begin
  srcToken := '';
  srcToktyp := 1;
  IsToken := 1;
  while IsToken=1 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Pasa al siguiente
    if EndOfLine=1 then begin     //No hay más caracteres
      exit;
    end;
    ReadChar;  //Lee sigte. en "srcChar"
    IsToken := ord(srcChar = ord(' '));
  end;
end;
procedure ExtractNumber;
var
  IsToken: integer;  //Variable temporal
begin
  srcToken := '';
  srcToktyp := 3;
  IsToken := 1;
  while IsToken=1 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Pasa al siguiente
    if EndOfLine=1 then begin     //No hay más caracteres
      exit;
    end;
    ReadChar;  //Lee sigte. en "srcChar"
    IsToken := IsNumeric;
  end;
end;
procedure ExtractString;
var
  IsToken: integer;  //Variable temporal
begin
  srcToken := '';
  srcToktyp := 4;
  IsToken := 1;
  while IsToken=1 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Pasa al siguiente
    if EndOfLine=1 then begin     //No hay más caracteres
      exit;
    end;
    ReadChar;  //Lee sigte. en "srcChar"
    IsToken := ord(srcChar <> ord('"'));
  end;
  NextChar;  //Toma la comilla final
  srcToken := srcToken + '"';   //Acumula
end;
procedure ExtractComment;
begin
  srcToken := '';
  srcToktyp := 5;
  while EndOfLine=0 do begin
    srcToken := srcToken + chr(srcChar);   //Acumula
    NextChar;  //Toma caracter
  end;
end;
procedure NextToken;
//Lee un token y devuelve el texto en "srcToken" y el tipo en "srcToktyp".
//Mueve la posición de lectura al siguiente token.
begin
   srcToktyp := 9;  //Desconocido por defecto
   if EndOfFile=1 then begin
     srcToken := '';
     srcToktyp := 0;  //Fin de línea
     exit;
   end;
   if EndOfLine=1 then begin
     srcToken := '';
     srcToktyp := 0;  //Fin de línea
     NextLine;
   end else begin
     //Hay caracteres por leer en la línea
     ReadChar;  //Lee en "srcChar"
     if IsAlphaUp=1then begin
       ExtractIdentifier;
       exit;
     end;
     if IsAlphaDown=1 then begin
       ExtractIdentifier;
       exit;
     end;
     if srcChar = ord('_') then begin
       ExtractIdentifier;
       exit;
     end;
     if IsNumeric=1 then begin
       ExtractNumber;
       exit;
     end;
     if srcChar = ord(' ') then begin
       ExtractSpace;
       exit;
     end;
     if srcChar = ord('"') then begin
       ExtractString;
       exit;
     end;
     if srcChar = ord('/') then begin
         if NextCharIsSlash = 1 then begin
         ExtractComment;
         exit;
       end;
     end;
     srcToken := chr(srcChar);   //Acumula
     srcToktyp := 9;
     NextChar;  //Pasa al siguiente
   end;
end;
begin
  //Abre archivo de entrada
  AssignFile(inFile, 'input.tit');
  Reset(inFile);
  NextLine;  //Para hacer la primera lectura.
  while EndOfFile<>1 do begin
    NextToken;
    writeln(srcToken);
  end;
  Close(inFile);
  ReadLn;
end.

Este código de más de 200 líneas será nuestro analizador léxico. Aún hay rutinas que iremos completando y tal vez unas leves modificaciones, pero de cualquier forma, serán cambios menores.

Si archivo de entrada contiene el texto mostrado:

Al ejecutar nuestro programa, veremos que nos muestra en pantalla todos los tokens que tenemos en nuestro archivo fuente:

Cada línea de la salida, representa un token y es la salida esperada. Un detalle notorio es que el token que representa el comentario, el primero, no es exacto en cuanto al contenido del comentario. Este comportamiento no nos afecta porque no se espera procesar los comentarios. Estos son solo útiles para el que escribe el programa, no para el compilador, así que serán descartados.

Notar que los saltos de línea también se consideran como tokens, aunque sin representación. Lo mismo ocurre con los espacios. Estos si contienen caracteres de espacio pero  lógicamente no son visibles en el terminal.

Los otros tokens sí se extraen de manera natural y tienen la apariencia esperada.

En la siguiente parte de esta serie veremos algunas rutinas complementarias del “lexer” y como podemos usarlas para hacer un análisis sintáctico y hasta empezaremos generando código sencillo.

Puntuación: 5 / Votos: 1

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *