Crea tu propio compilador – Parte 6 – Análisis sintáctico

En el artículo anterior vimos cómo construir un analizador léxico (lexer) usando instrucciones sencillas de Pascal. En esta parte empezaremos a implementar las rutinas del analizador sintáctico (parser). Pero como siempre, un poco de teoría antes de empezar.

Lexer y Parser

Como ya vimos, los analizadores léxicos nos permiten extraer tokens. Un analizador sintáctico, sin embargo, extrae elementos sintácticos, del código fuente.

¿Qué son elementos sintácticos?

Se podría decir que son los mismos tokens, pero con una interpretación distinta. Consideremos un ejemplo. La palabra “mi_variable” es considerada por el “lexer”, como un simple identificador (variable, constante, tipo, …). Para el “parser” sin embargo, puede tratarse del nombre de una variable. Eso implica que el “parser” tienen un conocimiento, a mayor nivel, del código fuente.

¿Qué que hacen los analizadores sintácticos?

Los analizadores léxicos solo generan tokens, y estos tokens son usados por el analizador sintáctico para que realice su trabajo, que por lo general, consiste en llenar una (o más de una) estructura llamada “El árbol de sintaxis”, que es luego usada para la generación de código.

Un analizador sintáctico puede también usar lo que se llama “La tabla se símbolos”. Esta estructura sirve para facilitar el reconocimiento de ciertos elementos sintácticos, del código fuente. Un compilador de C, por ejemplo, necesita de forma obligatoria una tabla de símbolos. Un compilador de Pascal, sin embargo, puede trabajar sin una.

El analizador sintáctico se maneja en base a reglas de una gramática conocida como”Gramática libre de contexto” (context-free grammar) , a diferencia de los analizadores léxicos que se manejan en al ámbito de las gramáticas regulares, usando terminología de la jerarquía de Chomsky.

Existe amplia literatura sobre el tema de las gramáticas que conviene leer un poco, antes de seguir con el tema de los compiladores.

¿Son realmente diferentes los “lexer” de los “parser”?

El analizador léxico y el sintáctico son dos módulos diferentes de un compilador con funciones diferentes, pero muchas veces estas diferencias no están bien separadas.

Pueden existir lenguajes con tokens bastante sencillos, de modo que no requieran un analizador sintáctico.

Hay toda una teoría (en realidad, más de una) detrás de este tema, pero siempre hay opiniones diversas y hasta contradictorias.

Como nosotros no somos especialistas en el tema,  solo nos basta con asumir que se tratan de módulos distintos. La experiencia nos dirá luego cuáles son las diferencias.

Sin embargo, uno de los métodos que nos sirven para detectar la diferencia de un analizador léxico con un analizador sintáctico, es que: Los “parser” suelen manejar recursividad, los “lexer” no. Siempre habrá excepciones, de acuerdo a la implementación, así que esto es solo una guía.

Los conceptos teóricos pueden parecer intimidantes pero constituye la base de un buen desarrollador de compiladores.

Soporte para errores

Después de algo de teoría, vamos ahora a seguir con la implementación de nuestro compilador.

Hasta el momento solo tenemos un analizador léxico bastante simple, pero cumple con su función de extraer. Nuestro siguiente paso es implementar rutinas de análisis sintáctico, las cuales caerían dentro del módulo del “parser”.

El análisis sintáctico, en nuestro compilador, se basará en revisar las reglas de sintaxis del lenguaje, por lo tanto, existirá una gran probabilidad de encontrar errores, y estos errores deben tratarse adecuadamente.

El comportamiento para procesar los errores, es muy variado, pero podemos considerar estos dos:

  1. El compilador  detiene la compilación y muestra un mensaje de error.
  2. El compilador pasa el error, muestra el mensaje, y trata de seguir compilando hasta el final.

El primer comportamiento es el más sencillo de implementar, porque solo tenemos que salir de la rutina actual y terminar el programa. Este es el método que usaremos en nuestro compilador Titan, pero podría cambiarse posteriormente.

El último comportamiento es el más común para los compiladores actuales (y algunos de antaño) y se ha usado bastante en los compiladores en C. Puede generar muchos mensajes de error y presumo que se implementó de esta forma porque un proceso de compilación, en los primeros días de la computación, era una tarea que podía tomar horas, y nadie deseaba volver a compilar todo, para encontrar el siguiente error. Desgraciadamente un compilador de este tipo (como lo dee saber todo programador de C/C++), suele generar mensajes de error que son dependientes del primer error y que no son errores realmente.

Para nuestros propósitos necesitamos una variable para almacenar el posible mensaje de error que nuestro compilador pueda generar.

 MsjError : string;

Esta variable nos servirá a la vez como bandera, ya que, si no contiene texto, asumiremos que no se han generado errores.

Algunas rutinas más

Una de las rutinas que necesitaremos, para el análisis sintáctico es la siguiente:

procedure TrimSpaces;
begin
  while (srcToktyp = 1) or (srcToktyp = 5) do begin
    NextToken;   //Pasa al siguiente
  end;
end;

La función de esta rutina es ir tomando los tokens de tipo espacio, hasta encontrar un token que no se espacio. Pero los comentarios (srcToktyp = 5)  son también tratados por esta rutina, como si fueran espacios, es decir que son ignorados.

Esta rutina será muy útil por cuanto el lenguaje es insensible al espaciado (y a los comentarios) y en muchas partes del programa, iremos extrayendo tokens, pasando los espacios por alto.

Otra rutina importante para el análisis sintáctico es la siguiente:

procedure GetLastToken;
begin
  NextToken;  //Toma último token
  TrimSpaces;
  if srcToktyp=0 then begin
    //El token actual es EOL
    //Ya estamos apuntando a la otra línea
  end else begin
    MsjError := 'Error de sintaxis: ' + srcToken;
    exit;
  end;
end;

Esta rutina la usaremos para la extracción de un token, que esperamos sea el último en una línea, como los comentarios ya que se esperan que los comentarios sean siempre el último token de una línea, ello considerando que no implementaremos soporte para comentarios de múltiples líneas.

Sin embargo nosotros usaremos esta rutina para simplificar el análisis sintáctico cuando no esperamos un token más en la misma línea. Esto nos simplificará código, aunque probablemente no sea la mejor forma de proceder.

Observar el mecanismo para generar errores en esta rutina: Se pone el mensaje en “MsjError” y se sale de la rutina. Las rutinas de mayor nivel verificarán luego el estado de “MsjError” después de la llamada a cada función que pueda generar error.

Este mismo mecanismo, lo usaremos en todas las funciones que puedan generar error.

Quizá alguien pueda preguntar ¿Y cómo se sabe el número de línea en que se generó el error?

La respuesta es simple. Recordemos que hemos creado una variable que guarda siempre el número de línea que vamos explorando. Esta variable es “srcRow” y es actualizada en el procedimiento NextLine().

La última rutina que necesitaremos, en esta estapa, es una que nos permita extraer rápidamente un token que sea igual a un caracter:

procedure CaptureChar(c: integer);
{toma el caracter como token. Si no eneuentra, genera mensaje de error.}
begin
  TrimSpaces;
  if srcToken<>chr(c) then begin
    MsjError := 'Se esperaba: ' + chr(c);
    exit;
  end;
  NextToken;  //toma el caracter
end;

Esta rutina la usaremos en algunos casos en los que esperamos la aparición de un carácter específico (que debe ser un token), y cuya ausencia implicaría un error de sintaxis.

Soporte a variables

Una de las primeras tareas que debemos realizar en nuestro compilador, fuera del análisis léxico y sintáctico es crear las estructuras que van a almacenar a las variables declaradas en el código Titan.

Esto es ya un avance, hacia un compilador funcional, porque permitirá implementar luego el soporte para la declaración de variables.

Para almacenar información sobre las variables necesitaremos de alguna estructura que nos sirva a modo de “tabla de variables”. Es decir, una tabla que almacene información importante sobre las variables que se vayan declarando. Esto es importante porque las variables, una vez declaradas, pueden aparecer más adelante en el código fuente y se necesitará tener información sobre esas variables (como su existencia y tipo) para validar las reglas sintácticas y semánticas.

Como estamos restringidos a usar datos simples, y eso implica que no podemos usar registros (struct) u objetos, vamos a crear diversos arreglos, cada uno destinado a almacenar un campo en particular:

//Información sobre variables
nVars : integer;
varNames : array[0..255] of string[255];
varType : array[0..255] of integer;
varArrSiz: array[0..255] of integer;

Estos tres arreglos, en la práctica, se comportarán como si fuera uno solo de un registro de 3 campos.

La variable “nVars” nos servirá para almacenar la cantidad de variables que tenemos declaradas, sena locales o globales. El límite para la cantidad de variables en nuestro humilde compilador, está limitado a 256. Esta limitación la ponemos, porque de momento no podemos manejar estructuras dinámicas en la implementación de Titan y 256 es un número razonable para un compilador pequeño como el nuestro.

Los arreglos varNames[] y varType[] almacenarán el nombre y el tipo  de la variable, respectivamente.

Para el tipo de datos, usaremos el siguiente estándar:

1 -> integer
2 -> string

No necesitamos más por cuanto solo manejaremos dos tipos.

El arreglo varArrSiz[] nos indicará el tamaño de elementos que tiene la variable. Esto será útil cuando la variable sea de tipo “arreglo”, porque se necesita implementar este tipo en el compilador. Si la variable es de un tipo simple, se pondrá a cero su posición correspondiente en varArrSiz[].

Necesitaremos además variables adicionales para las rutinas que tratarán la declaración de variables:

 //Variable de trabajo
curVarName: string;
curVarType: integer;
curVarArSiz: integer;
//Campos para arreglos
idxStorag: integer;
idxCteInt: integer;
idxVarNam: string;

Se declararán como variables globales para facilitar el paso de parámetros entre funciones y para simplificar a nuestro compilador, que como ya sabemos debe tener un código lo más simple posible.

La utilidad de estas variables, la veremos en el siguiente artículo, pero de momento solo nos conformaremos son su declaración.

El código fuente completo, tiene casi 400 líneas y, por espacio, no lo incluiremos aquí sino que puede ser consultado aquí, en donde están los códigos completos de los últimos artículos.

De  momento nuestro compilador no hace nada nuevo, pero está ya preparado para soportar la declaración de variables, pero antes de ello necesitamos empezar a implementar  algunas rutinas básicas del generador de código. Ese tema es, precisamente, el que veremos en el siguiente artículo.

 

Puntuación: 0 / Votos: 0

2 pensamientos en “Crea tu propio compilador – Parte 6 – Análisis sintáctico

  • 12 febrero, 2019 al 2:33 pm
    Permalink

    Muy interesante.
    Estaré esperando el siguiente articulo

    Responder
    • 12 agosto, 2019 al 1:57 pm
      Permalink

      Muchas gracias, también estaré esperando el próximo artículo.

      Responder

Deja un comentario

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