Crea tu propio compilador – Parte 4 – Creando un analizador léxico

Partes de un compilador

A estas alturas del proyecto, y antes de iniciar el desarrollo del código fuente del compilador, deberíamos tener claro, cuáles son las partes de las que se compone un compilador.

Los compiladores pueden hacerse de tantas formas como se pueden hacer las tortas de chocolate. Eso es lo bueno y lo malo de hacer compiladores. No existe un “Comité Internacional Regulador de las formas en que se hacen los Compiladores” ni nada parecido.

Así, que por favor, dejar de preguntar ¿Cómo se hacen los compiladores? Una mejor pregunta sería, ¿Podría explicarme alguna forma en que se hacen los compiladores?

Por suerte, la mayoría de compiladores presentan módulos más o menos definidos. Algunos de ellos son:

Analizador léxico.- También conocido como “lexer”. Es quien identifica y extrae los llamados “tokens”, que son los elementos mínimos de caracteres con significado coherente para un lenguaje de programación.

Analizador sintáctico.- También conocido como “parser”. Es quien procesa los tokens de acuerdo a las reglas de la gramática del lenguaje de programación (Como dónde es permitido un identificador). Por lo general su resultado termina en lo que se llama “Árbol de sintaxis”

Analizador semántico.- Aunque menos conocido e identificado, este analizador realiza una comprobación de mayor nivel al código fuente, como por ejemplo, si un tipo de datos es válido en la posición donde se encuentra.

Árbol de sintaxis.- Puede haber uno o varios. Es una estructura ramificada que representa al código fuente en cuanto a estructura. Los nodos del árbol pueden representar a funciones o declaraciones. Se usa para realizar el análisis semántico y para la generación de código.

Generador de código intermedio.- Muchos compiladores incluyen este módulo, cuyo principal objetivo es realizar al primera etapa en la generación de código. Se suele usar un código intermedio, para simplificar la generación de código y para facilitar la creación de nuevos generadores de código.

Generador de código.- Es el módulo que crea el código destino Lo ideal es que el código destino sea binario o ejecutable, pero la mayoría de compiladores solo crean código objeto o, inclusive, solo código ensamblador (como vamos a hacer nosotros).

Optimizador de código.- La optimización de código se puede realizar en diversos niveles, como en la etapa previa a la generación de código o en el archivo objeto generado. La idea es obtener un código simplificado, óptimo y/o rápido. Para ellos existen diversas reglas y técnicas aplicables.

Cada uno de estos módulos puede llegar a ser muy complejo y hay investigadores que constantemente están haciendo investigaciones y aportes. Las técnicas para crear compiladores no están escrito en un libro sagrado.

En este artículo iniciaremos con la creación de un sencillo analizador léxico cuyo principal objetivo sea solamente la extracción de tokens.

Cómo escribiremos nuestro compilador

En este artículo, iniciaremos la escritura de código, y como ya hemos mencionado, vamos a tener en consideración algunas reglas básicas al momento de escribir las rutinas del compilador. Estás son:

  • Usaremos el lenguaje Pascal en sus capacidades básicas. No se usarán las capacidades de Object Pascal.
  • Solo usaremos Pascal como lenguaje imperativo y tipado.
  • Solo usaremos dos tipos de datos: Integer y String.
  • Solo usaremos condicionales simples IF .. THEN … ELSE.
  • Solo usaremos los bucles WHILE. No usaremos REPEAT o FOR.
  • No se usarán procedimientos anidados dentro de  otro procedimiento. Ni funciones.
  • No se usarán librerías de terceros. Todo el compilador se implementará desde cero con las funciones nativas del lenguaje  manejo de cadenas y números.
  • No se usarán punteros.
  • El tipo “string” de Pascal que utilizaremos, estará restringido (por convención) a un tamaño máximo de 255 caracteres.
  • Las funciones de manejo de archivos deben ser también las nativas que implementa el lenguaje.
  • Las funciones y procedimientos pueden recibir parámetros pero solo por valor, no por referencia.
  • Al no tener tipos booleanos, se usarán valores enteros para emularlos, tomando en consideración que el valor 0 representa a FALSE.
  • Al no tener tipos “char” se usarán valores enteros.
  • Se usarán expresiones simples de dos o tres operandos.

Se puede notar que existen restricciones fuertes en cuanto a lo que podemos (y lo queno podemos) usar del lenguaje. Esto constituye un desafío adicional a la hora de escribir el compilador, pero nos servirá para:

  • En el futuro, poder traducir el compilador del Pascal al propio lenguaje del compilador.
  • Facilitar la explicación del compilador, al tener un código sencillo y no tener que explicar conceptos avanzados del lenguaje.

Habiendo dejado en claro las restricciones al momento de escribir el código, pasamos entonces al primer módulo del compilador.

Nuestro Analizador Léxico

En comparación con los compiladores profesionales, nuestro analizador léxico parecerá un juego de niños, pero no por eso dejará de ser funcional.

Para entender mejor los analizadores léxicos, sugiero leer mi artículo http://blog.pucp.edu.pe/blog/tito/2016/12/19/jugando-con-palabras-analizadores-lexicos/

Nuestro “lexer” será simplemente un conjunto de procedimientos y funciones que nos permitirán reconocer los diversos tipos de tokens con los que trabajaremos en nuestro lenguaje de programación.

Por simplicidad solo definiremos los siguientes tipos de tokens:

  • Espacios.
  • Saltos de línea.
  • Identificadores
  • Literales cadena
  • Literales Numéricos
  • Tokens desconocidos

Con estos tokens es suficiente para representar a todos los elementos de nuestro lenguaje.

Los espacios son los que corresponden al carácter #32 (del código ASCII), pero también podría incluirse a las tabulaciones.

Los saltos de línea son los delimitadores de línea, y en Windows se representan por dos caracteres: #10 y #13.

Los identificadores se definieron en el artículo anterior, cuando creamos el lenguaje.

Los literales cadena son caracteres delimitados por comillas dobles, como “Hola” o “esto es una cadena”.

Los literales numéricos son caracteres numéricos como: 123 o 002. De momento no consideraremos números con decimales o en coma flotante.

Todos los otros tokens serán considerados como desconocidos, pero también tendrán un tipo. En este grupo caerán los símbolos como “+”, “-” o “:”.

De vuelta con Lazarus

En el segundo artículo habíamos dejado el entorno de Lazarus listo para empezar a trabajar. Ahora vamos a continuar creando un archivo que será nuestro primer programa en nuestro lenguaje Titan.

Creemos un archivo llamado “input.tit”, que debe ser un archivo de texto y pongamos el siguiente contenido:

Este archivo no es un código coherente, sino simplemente una buena muestra para probar nuestro analizador léxico, porque contiene todos los elementos sintácticos .

Este archivo lo debemos poner en la la misma carpeta en donde tenemos nuestro proyecto de Lazarus, de modo que en nuestra carpeta de trabajo tenemos ya varios archivos:

 

Como nuestra intención es leer los tokens de un archivo fuente, empezaremos con la rutina para leer líneas de un archivo de texto.  Abrimos el proyecto titan.lpi y escribimos el siguiente código:

{Proyecto de un compilador con implementación mínima.}
program titan;
var
  inFile   : Text;    //Archivo de entrada
  srcLine  : string[255]; //Línea leída actualmente
begin
  AssignFile(inFile, 'input.tit');
  Reset(inFile);
  while not eof(inFile) do begin
    readln(inFile, srcLine);
    writeln(srcLine);
  end;
  Close(inFile);
  ReadLn;
end.

Este es el esquema típico de un programa para lectura de archivos en Pascal. Si lo ejecutamos veremos el contenido del archivo “input.tit” en la consola.

Pero esto está lejos de ser un analizador léxico, porque solo extrae líneas y las líneas no se consideran tokens en nuestra definición. Sin embargo este código será la base de nuestro analizador léxico, que funcionará también leyendo líneas del archivo fuente.

Nuestro lexer se alimentará de las líneas de texto de un archivo, así que para ganar velocidad, y por simplicidad (ya que no podemos usar características avanzadas del lenguaje) usaremos una variable cadena para almacenar cada línea que vayamos leyendo del archivo. A esta variable la llamaremos “srcLine”:

 srcLine : string[255]; //Línea leída actualmente

Ahora esta línea debe ser explorada carácter por carácter, así que necesitaremos acceder a ella como arreglo y necesitaremos también un índice, o puntero, para ir leyendo cada carácter de la “srcLine”. A ese índice lo llamaremos “idxLine”:

 idxLine : integer;

También necesitaremos dos variables más para manejar el archivo de entrada (código fuente) y el archivo de salida (archivo en ensamblador) que generará nuestro compilador:

Ahora teniendo ya estas variables, podemos implementar algunas funciones básicas de lo que será nuestro “lexer”:

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
  idxLine:=1;    //Apunta a primer carácter
end;

Estas funciones manejan el desplazamiento a través del archivo de entrada (NextLine), y la verificación de los límites del archivo (EndOfLine y EndOfFile).

Esto es importante porque conforme vayamos haciendo la exploración, se puede dar el caso que hayamos llegado al final del archivo, en cuyo caso ya no tiene sentido seguir explorando. La verificación de fin de línea (EndOfLine) es usada para saber cuando debemos leer la siguiente línea, aunque esto solo se ve a niveles bajos del “lexer” (funciones más básicas) porque a niveles más altos, el cambio de línea es algo que se realiza de forma transparente.

Notar que las funciones EndOfLine y EndOfFile deberían devolver valores booleanos, pero aquí están devolviendo números, para cumplir con las restricciones del lenguaje que podemos usar. Una de ellas es, precisamente, que solo podemos usar datos de tipo “integer” y “string”, aunque podemos usar también enteros sin signo o de menor capacidad, sin perder la esencia de la restricción.

La lógica de estas funciones es simple así que no creo que el lector tenga problemas en la interpretación. Poner atención en la forma en que se pasa a una nueva línea, reiniciando el índice “idxLine” a 1, para empezar a explorar desde el primer carácter.

Una mejora que podríamos hacer para este código es incluir un contador de líneas procesadas para poder saber en qué línea se produce un error. Para ello debemos agregar una variable, a la que llamaremos “srcRow” y nuestro procedimiento NextLine quedaría:

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;

Pero aún con estas rutinas, todavía no tenemos la capacidad de identificar y extraer tokens. Aún tenemos que escribir rutinas de mayor nivel (que se crean usando otras rutinas más simples).

Existe un par de rutinas que están presentes casi en todos los analizadores léxicos, y son las que se encargan de explorar la entrada carácter por carácter. Aquí las definiremos así:

procedure ReadChar;
{Lee el carácter actual y actualiza "srcChar".}
begin
   srcChar := ord(srcLine[idxLine]);
end;

procedure NextChar;
{Incrementa "idxLine". Pasa al siguiente carácter.}
begin
   idxLine := idxLine + 1;  //Pasa al siguiente carácter
end;

Para leer el carácter actual (al que apunta “idxLine”)  usaremos el procedimiento ReadChar(). Observar que el caracter actual se devuelve en la variable global “srcChar”, que es numérica. También se pudo retornar como resultado de la función, sin problemas, pero aquí se está tratando de usar la forma más simple de trabajar. Pero el cambio es trivial.

La rutina NextChar() solo incrementa el índice para apuntar al siguiente carácter, pero se deduce que por seguridad, hay que estar siempre comparando si se llega al final de la línea. Intentar explorar más allá, generará un error en tiempo de ejecución.

Con estas rutinas ya podríamos crear un bucle para ir explorando caracteres de una línea y tendría la forma:

  while EndOfLine=0 do begin
    ReadChar; //Lee en "scrChar"
    //Hace algo con "scrChar"
    NextChar;  //Toma caracter
  end;

Notar la forma en que se compara el valor booelano (entero) que devuelve EndOfLine().

Este bucle, solo funcionaría bien para una línea y se podría usar para extraer sus tokens, pero lo que buscamos es algo más general que nos permita extraer tokens de varias líneas de una forma cómoda y algo transparente.

Si ahora juntamos todas las rutinas mostradas, tendríamos algo así:

{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

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;
begin
  //Abre archivo de entrada
  AssignFile(inFile, 'input.tit');
  Reset(inFile);
  NextLine;  //Lee primera línea en "srcLine"s
  while EndOfLine=0 do begin
      ReadChar; //Lee en "scrChar"
      write(chr(srcChar)); //Hace algo con "scrChar"
      NextChar;  //Toma caracter
    end;
  Close(inFile);
  ReadLn;
end.

Este código solo nos mostrará carácter por carácter, el contenido de la primera línea del archivo de entrada. Aunque no es un “lexer” porque no extrae tokens sino caracteres, conviene estudiarlo (y ejecutarlo) para seguir adelante con el desarrollo con buen entendimiento.

En el siguiente artículo terminaremos de implementar el analizador léxico y lo probaremos con el archivo que estamos preparando.

 

Puntuación: 0 / Votos: 0

Deja un comentario

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