Jugando con Palabras – Analizadores Léxicos I

Una de las necesidades comunes en computación, es el procesamiento de textos, sea a nivel visual, para mostrarlo, o a nivel léxico, para interpretar las palabras que contiene. Cuando se procesa un texto a nivel léxico, se dice que el programa que realiza el procesamiento, es un analizador léxico.

En este artículo, propondré la creación de un analizador léxico elemental, usando Lazarus como IDE y Object Pascal como lenguaje de programación.

Una analizador léxico o lexer (anglicismo equivalente), es un programa que lee un texto de entrada, para ir extrayendo sus elementos constitutivos, a los que se les llama tokens o fichas. En otras palabras, un analizador léxico es el programa que divide un texto en sus elementos constitutivos, a los que se les llama tokens.

Los analizadores léxicos o lexers, constituyen la base de los compiladores e intérpretes de código fuente, de modo que cada compilador o intérprete, incluye al menos un lexer, para realizar su trabajo.

Un lexer es entonces un programa que troza texto, con algún fin en particular. Dicho fin es, por lo general, servir como base a otro programa llamado analizador sintáctico, para que este pueda realizar su trabajo.

Entonces podemos entender a un lexer, como un programa que toma caracteres (lo que constituye a un texto) y devuelve tokens, como se indica en la siguiente figura;

Quizá el primer pensamiento que viene a la mente, cuando se habla de trozar o dividir un texto, podría ser: partirlo en palabras. Y efectivamente, las palabras pueden ser también buenos tokens. Sin embargo, el concepto de token más usado, es algo más que una simple palabra. Un token es un componente léxico, que está formado por uno o más símbolos (caracteres). Un token puede ser:

• Un identificador -> Conjunto de caracteres alfabético o alfanumérico. Lo más parecido a una palabra en lenguaje humano.
• Un espacio-> Los tokens también pueden ser espacios en blanco, que a su vez pueden incluir tabulaciones o saltos de línea.
• Un símbolo-> Que puede ser un punto, guión, punto y coma, etc. Los símbolos son elementos clave, en los lenguajes de programación, porque definen expresiones.

Como suele pasar, no hay un estándar universal sobre lo que debe considerarse o no como un token, ya que esta definición dependerá del tipo de lenguaje que deseamos analizar. Sin embargo, la mayoría de definiciones coinciden, en diversas implementaciones.

Pasemos ahora a crear nuestra implementación básica de lo que sería nuestro analizador léxico, en Lazarus:

unit Unit2;
{$mode objfpc}{$H+}
interface
uses  Classes, SysUtils;
Const
  FIN_CON = #0;    //Fin de contexto

Type
  { TContexto }
  {Define al objeto contexto, que es una abstracción para leer datos de entrada.}
  TContexto = class
    lin      : string;   //Línea de texto
    col      : Integer;  //columna actual
    //Métodos de lectura
    Function IniCont:Boolean;
    Function FinCont:Boolean;
    Function VerCar:Char;
    Function CogCar:Char;
    Function VerCarSig: Char;
    Function CapBlancos:Boolean;
    procedure CurPosIni;
    procedure CurPosFin;
    function CogIdentif(var s: string): boolean;
  public
    constructor Create;
    destructor Destroy; override;
  End;

implementation

{ TContexto }
function TContexto.IniCont: Boolean;
//Devuelve verdadero si se está al inicio del Contexto (columna 1)
begin
  Result := (col = 1);
end;
function TContexto.FinCont: Boolean;
//Devuelve verdadero si se ha pasado del final del Contexto actual
begin
  Result := (col >= Length(lin) + 1);
end;
function TContexto.VerCar: Char;
//Devuelve el caracter actual
//Si no hay texto en el Contexto actual o si se ha llegado al final del
//texto, devuelve FIN_CON.
begin
  if FinCont Then exit(FIN_CON);
  Result := lin[col];
end;
function TContexto.CogCar: Char;
//Lee un caracter del contexto y avanza el cursor una posición.
//Si no hay texto en el Contexto actual o si se ha llegado al final del
//texto, devuelve FIN_CON.
begin
  if FinCont Then exit(FIN_CON);
  Result := lin[col];
  inc(col);
end;
function TContexto.VerCarSig: Char;
//Devuelve el catacter siguiente al actual.
//Si no hay caracter siguiente, devuelve caracter nulo.
begin
  if FinCont Then exit(#0);
  Result := lin[col+1];
end;
function TContexto.CapBlancos: Boolean;
//Coge los blancos iniciales del contexto de entrada.
//Si no encuentra algun blanco al inicio, devuelve falso
begin
  Result := False;
  while not FinCont and (VerCar in [' ', #9]) do
    CogCar;
end;
procedure TContexto.CurPosIni;
//Mueve la posición al inicio del contenido.
begin
  col := 1;   //posiciona al inicio
end;
procedure TContexto.CurPosFin;
//Mueve la posición al final del contenido.
begin
  col := length(lin)+1;   //posiciona al final
end;
function TContexto.CogIdentif(var s: string): boolean;
{Coge un identificador, que debe corresponder a una variable.}
begin
  if not (VerCar in ['a'..'z','A'..'Z']) then   //primer caracter no valido
    exit(false);        //no es constante cadena
  s := '';         //inicia para acumular
  //Busca hasta encontar fin de identificador
  while not FinCont and (VerCar in ['a'..'z','A'..'Z']) do begin
    s += CogCar;
  end;
  Result := true;    //indica que se encontró identificador
end;
constructor TContexto.Create;
begin
  CurPosIni;
end;
destructor TContexto.Destroy;
begin
  inherited Destroy;
end;

end.

En este programa, el lexer está representado por la clase TContexto, e implementa diversos métodos. Se ha creado en una unidad independiente por modularidad.

Aunque no es estríctamente necesario, aquí he incluido al lexer en una clase, como un medio de encapsulamiento, siguiendo el paradigma de orientación a objetos, pero es completamente válido, si se crea de forma estructurada, sin objetos.

El lexer TContexto, solo tiene métodos básicos que le permiten extraer tokens que son caracteres, espacios, o identificadores.

La cadena a procesar, se debe escribir en el campo «lin», y el campo «col» indicará la posición actual en la que se encuentra la exploración del texto.

El método VerCar(), devuelve el carácter actual, pero sin incrementar «col». El método CogCar(), devuelve el carácter actual, e incrementa la posición actual, por eso es llamado CogCar(), una contracción de «Coger Carácter».

La función más elaborada es quizá CogIdentif(), que toma un conjunto de caracteres alfanuméricos, que corresponden a lo que se entiende por identificador, lo más cerca a la definición de «palabra» en nuestro lenguaje.

Dos funciones útiles, para ver el estado del lexer, son IniCont() y FinCont(), que nos permiten ver si estamos al inicio o al final del texto que estamos analizando.

Veamos un ejemplo de uso. En el formulario principal, escribamos el siguiente código:

unit Unit1;
 {$mode objfpc}{$H+}
 interface
 uses
 Classes, SysUtils, FileUtil, Forms, Controls, Graphics, Dialogs, Unit2;
 type

{ TForm1 }
 TForm1 = class(TForm)
 procedure FormCreate(Sender: TObject);
 procedure FormDestroy(Sender: TObject);
 private
 lex : TContexto;
 end;

var
 Form1: TForm1;

implementation
 {$R *.lfm}

{ TForm1 }
 procedure TForm1.FormCreate(Sender: TObject);
 var
 c: Char;
 begin
 lex := TContexto.Create;
 lex.lin := 'Hola';
 while not lex.FinCont do begin
 c := lex.CogCar;
 ShowMessage(c);
 end;
 end;

procedure TForm1.FormDestroy(Sender: TObject);
 begin
 lex.Destroy;
 end;

end.

Aquí solo estamos extrayendo carácter por carácter, así que no hay gran ventaja en usar un lexer, pero modificando la rutina de FormCreate(), podemos extraer identificadores:

procedure TForm1.FormCreate(Sender: TObject);
 var
 ident: string;
 begin
 lex := TContexto.Create;
 lex.lin := 'En un lugar de la mancha';
 while not lex.FinCont do begin
 if lex.CogIdentif(ident) then
 ShowMessage(ident)
 else
 lex.CogCar;
 end;
 end;

El método CogIdentif(), permite extraer un identificador completo, en la variable pasada como parámetro, y devuelve TRUE, si es que logra su cometido, es decir, si encontró un identificador en la posición actual.

En síntesis, lo que hace el programa es extraer y mostrar los tokens de tipo identificador. Los otros tipos de tokens (espacios, símbolos, números, etc), se ignoran y se extraen carácter por carácter.

Como el texto a analizar, solo contiene palabras y espacios, bastará con nuestro simple analizador, pero textos más complejos requerirán analizadores léxicos más complejos.

Para extraer los espacios en blancos TContexto, tiene un método especial: CapBlancos(), que extrae espacios en blanco que pueden ser caracteres de espacio o tabulaciones.

Un método adicional que se podría agregar a nuestro lexer, para hacerlo más útil sería uno, que permita extraer números, ya que los números constituyen tokens comunes en cualquier texto.

Hay herramientas especializadas en la creación de lexers, como los programas lex o flex, que permiten generar analizadores léxicos en C, para cualquier lenguaje, por medio de definiciones que incluyen expresiones regulares.

En la siguiente parte mostraré como usar la librería SynFacilSyn, para crear un aanalizador léxico, más elaborado.