Compilador - Pascal

Para la elaboración de nuestro compilador del lenguaje Pascal, es necesario tener ciertos conocimientos acerca de "Que es, para y como funciona el Analizador Léxico", "Que es, para y como funciona el Analizador Sintáctico" y "Que es, para y como funciona el Analizador Semántico" y además, conocer acerca del jFlex y Cup que es en lo que se basa nuestro compilador y el que nos ayudó a su elaboración, no se preocupen si no conocen lo básico o acerca de esto, más adelante empezaré a explicar cada uno de ellos.

ANÁLISIS LÉXICO

El analizador léxico o scanner (en lengua inglesa) lee los caracteres del programa fuente para agruparlos en palabras o lexemas y luego clasificarlos en componentes léxicos denominados “tokens” que serán posteriormente utilizados por el analizador sintáctico

como entradas.

Estos componentes léxicos representan:

- Palabras reservadas: if, while, do, break
- Identificadores: asociados a variables, nombres de funciones, tipos definidos por el usuario, etiquetas,... Por ejemplo: velocidad, - y11, elsex, _100
- Operadores: = * + - / ==
- Símbolos especiales: ; ( ) [ ]
- Constantes numéricas: valores enteros, valores en coma flotante, etc, 982,0xF678, -83.2E+2,...
- Constantes de caracteres: cadenas de caracteres, “hola mundo”,...
- Comentarios: /** abcde **/

El analizador léxico opera a solicitud del analizador sintáctico devolviendo un componente léxico conforme el analizador sintáctico lo va necesitando para obtener una representación de la estructura sintáctica del programa fuente.

El Scanner suele implementarse como una subrutina del analizador sintáctico.

Cuando recibe la orden obtén el siguiente componente léxico, el analizador léxico lee los caracteres de entrada hasta identificar el siguiente componente léxico.

El scanner realiza también otras tareas, tales como:

- Administrar el archivo de entrada del programa fuente: abrirlo, leer sus caracteres, cerrarlo y gestionar posibles errores de lectura.
- “Eliminar” comentarios, espacios en blanco, tabuladores y saltos de línea (caracteres no validos para formar un token).
- Incluir archivos: # include ...
- Expandir macros y funciones inline: # define ...
- Contabilizar el número de líneas y columnas para emitir mensajes de error.
- Reconocer las marcas de fin de archivo, de los archivos que contienen al
- programa fuente.
- Insertar los identificadores en la Tabla de Símbolos.
- Reconocer errores léxicos que ocurren cuando se escribe mal una palabra o
- cuando se encuentran caracteres que no pertenecen al alfabeto del lenguaje fuente.

1. DEFINICIONES BÁSICAS

1) TOKEN:

Categorías sintácticas más simples del lenguaje fuente que permiten clasificar las palabras que conforman el léxico del programa fuente.

2) PATRÓN:

Regla que especifica la secuencia de caracteres que puede representar a un determinado componente léxico.

3) LEXEMA:

Cadena de caracteres que concuerda con un patrón que describe un componente léxico.

4) ATRIBUTOS:

Información adicional sobre los tokens, que es usada por los analizadores sintáctico y semántico. El número de atributos depende de cada token. En la práctica, los tokens tienen un único atributo: un registro que contiene toda la información propia de cada caso (lexema, tipo de dato, valor, etc).

Ejemplo:

2. FUNCIONAMIENTO DEL ANALIZADOR LEXICO

Cada vez que el analizador sintáctico llama al scanner éste debe leer caracteres desde donde se quedó en la anterior llamada hasta completar un nuevo lexema, para luego clasificarlo según una categoría de token y devolver el par (token, lexema).

El analizador léxico almacena el lexema que se acaba de reconocer para ser usado posteriormente en el análisis semántico (completar la tabla de símbolos); y codifica los componentes léxicos como enteros.

Cuando el scanner intenta reconocer tokens no específicos (identificadores, números, etc.), el analizador debe leer caracteres hasta que lea uno que no pertenece a la categoría del token que está leyendo; ese último carácter no puede perderse, y debe devolverse al buffer de entrada para ser leído en primer lugar la próxima vez que se llame al analizador léxico.

Ejemplos:

Obtener los pares token-lexema que devolvería un analizador de léxico ante las expresiones:

Expresión:

654– b * 30/5.07

(TKN_ENTERO, “654”)

(TKN_OPRES, “-“)

(TKN_ID, “b”)

(TKN_OPMUL, “*”)

(TKN_ENTERO, “30”)

(TKN_OPDIV, “/”)

(TKN_REAL, “5.07”)

Expresión:

printf(“Resultado: %d\n”, 25);

(TKN_PRINTF, “printf”)

(TKN_PARI, “(“)

(TKN_STR, “”Resultado: %d\n””)

(TKN_NUM, “25”)

(TKN_COMA, “,”)

(TKN_PARD, “)”)

(TKN_PYC, “;”)

JFLEX

Para la generación del autómata de estados del analizador léxico hemos utilizado JFlex(http://jflex.de/). Se trata de una potente herramienta, que dadas las expresiones regulares que reconocen los tokens del lenguaje y sus acciones asociadas, generan el autómata reconocedor de forma automática.

En el código se incluyen, en el paquete Léxico, el archivo original (Léxico.flex) y el compilado porJFlex, Léxico.java.

Estructura del archivo .flex

Una cabecera con las inclusiones de código (imports) necesarias.
Una serie de variables utilizadas por JFlex para insertar las declaraciones, y la definición del Token devuelto en el final del fichero.
Código empotrado en donde se declara la tabla de símbolos

return new Token(type.ordinal(), yyline, yycolumn, atributos);

El ordinal hace referencia al enumerado, que dice de qué tipo de Token se trata.
yyline hace referencia a la línea donde está ubicado el Token.
yycolumn hace referencia a la columna donde está ubicado el Token.
atributos es un Object que define los atributos del Token, generados en esta función a partir del tipo.

Luego viene el conjunto de expresiones regulares, que sigue un esquema:

nombre_expresión = expresión_regular

Más abajo se explica cómo se definen las expresiones regulares.

Por último, se definen las acciones asociadas a los patrones, que bien pueden estar definidos por expresiones regulares en el apartado anterior, o se pueden definir directamente. Aquí se utiliza la función creaToken mencionada antes.Si llega al final y no ha entrado en ninguna de las acciones, entonces se considera que el Token es erróneo y se notifica al gestor de errores.

Expresiones regulares

Introducimos aquí un pequeño resumen de cómo se escriben algunas expresiones regulares que hemos usado de JFlex, como referencia para aquéllos que no conozcan el lenguaje:

Léxico

Como ya se mencionó en la introducción, en esta sección de proyecto se observa cómo se comporta elanalizador léxico para gestionar cada entrada del código.Podemos distinguir dos partes, la especificación y la implementación. En la primera comentaremoscómo es la gramática que reconoce el analizador, cómo se ha diseñado la estructura interna de lostokens del lenguaje y su codificación. En la segunda parte, veremos la forma en que hemos plasmadoen JAVA toda esta información y la interfaz de acceso para el analizador sintáctico.

Especificación Gramática

Estudiando el lenguaje pascal, llegamos a ciertas reglas con las que hemos generado una serie de expresiones regulares para reconocer los tokens. A continuación mostramos dichas expresiones y las acciones semánticas que hemos asociado a dichos patrones

El autómata que obtenemos por la gramática, obtenido gracias a JFlex minimizado. Solo mostraremos una parte ya que es demasiado para mostrarlo en imágenes (con el programa ya descargado podrán ya observar todo en cuanto a palabras reservadas y demás)

En estas imágenes vemos:

LlenadorDeTabla.addArrayList0

LlenadorDeTabla.addArrayList1

LlenadorDeTabla.addArrayList2

LlenadorDeTabla.addArrayList3

Esto lo único que nos permite es mostrar en nuestra Interfaz los tokens. (Ya más adelante y con el programa ya descargado se podrán dar cuenta y resolver sus dudas)

Tokens

La materia de trabajo esencial para un analizador léxico son los tokens, que deben estar bien especificados y con una estructura clara. Cada token de nuestro analizador consta de un tipo y de los atributos asociados a dicho token. Además incluye la línea y la columna donde se encuentra situado en el código.Los tipos de token que pueden darse, responden a una lista concreta que hemos diseñado partiendo del lenguaje Pascal. El scanner se encarga de elegir cual será el tipo de un token recibido. Las directrices proporcionadas a JFlex, condicionadas por la gramática del diseño y sus acciones asociadas obligan a que se encuentre siempre un tipo. En caso de que el token no se asociase a ningún patrón establecido, sería un error léxico. A continuación mostramos una tabla orientativa del diseño de los tokens.

Errores

Hemos creado un tipo enumerado con los tipos básicos de errores:

ANÁLISIS SINTÁCTICO

El analizador sintáctico o parser (en lengua inglesa) comprueba que la sintaxis del programa fuente sea correcta. El analizador sintáctico recibe los tokens que envía el scanner y verifica que estén debidamente combinados de tal manera que cumplan con las reglas sintácticas del lenguaje fuente especificadas mediante una gramática libre de contexto. El parser verifica que la sucesión de tokens pueda ser generada por la gramática correspondiente al lenguaje fuente.

Son funciones del analizador sintáctico:

· Comprobar si la cadena de tokens proporcionada por el analizador léxico puede ser generada por la gramática.

· Construir el árbol de análisis sintáctico que define la estructura sintáctica de un programa y obtener las derivaciones para generar la cadena de tokens.

· Informar de los errores sintácticos de forma precisa y significativa.

En la práctica, el analizador sintáctico realiza otras tareas tales como:

· Acceder a la tabla de símbolos (para hacer parte del trabajo del analizador semántico).

· Comprobación de tipos (del analizador semántico).

· Generar código intermedio.

· Generar mensajes de errores cuando se producen.

ESPECIFICACIÓN SINTÁCTICA DE LOS LENGUAJES DE PROGRAMACIÓN

La estructura sintáctica de los lenguajes de programación se especifica mediante Gramáticas Libres de Contexto que además son la base para los diferentes esquemas de traducción de la etapa de síntesis.

Las producciones de la gramática libre de contexto obedecen al formato:

P = { A?a | A?N y a?(N?S)* } donde:

N = Símbolos no terminales o variables sintácticas

S = Símbolos terminales o tokens

Durante el análisis sintáctico se utiliza una G.L.C. para determinar si la cadena de tokens, que se recibe del scanner, puede ser derivada a través de dicha gramática.

VENTAJAS DE UTILIZAR GRAMÁTICAS

Son especificaciones sintácticas y precisas de lenguajes.
Se puede generar automáticamente un analizador.
El proceso de construcción puede llevar a descubrir ambigüedades.
Imparte estructura al lenguaje de programación, siendo más fácil generar código y detectar errores.
Es más fácil ampliar y modificar el lenguaje.

DERIVACIONES Y ÁRBOL DE ANÁLISIS SINTÁCTICO

Analizar sintácticamente una cadena de tokens es construir para ella un árbol sintáctico o de derivación, que tenga como raíz el símbolo inicial de la gramática y mediante la aplicación sucesiva de sus producciones se pueda generar dicha cadena como hojas del árbol sintáctico. En caso de éxito la sentencia cumple con las reglas sintácticas de la gramática, en caso contrario, el compilador emite un mensaje de error sintáctico.

Un árbol de análisis sintáctico es un árbol tal que:

1) La raíz esta etiquetada con el símbolo inicial.

2) Cada hoja esta etiquetada con un componente léxico. Las hojas de izquierda a

derecha forman la frase o frontera (el programa fuente).

3) Cada nodo interior esta etiquetado con un no terminal.

4) Si A es un no terminal y X1,X2,…,Xn son sus hijos de izquierda a derecha, entonces

existe la producción AàX1X2...Xn.

Ejemplo:

Sean las producciones de la gramática G:

E -> E A E | ( E ) | - E | id 1,2,3,4

A -> + | - | * | / 5,6,7,8

Determinar si la cadena id+id*id pertenece al lenguaje definido por la gramática.

Construimos su árbol de derivación:

RECURSIVIDAD

Las reglas de producción de una gramática están definidas de forma que al realizar derivaciones dan lugar a recursividades.

Una producción es recursiva a izquierda si es de la forma A -> Aß. De la misma forma A -> aA es recursiva a la derecha.

AMBIGÜEDAD

Una gramática es ambigua si el lenguaje que define contiene alguna sentencia que tiene más de un único árbol sintáctico. Es decir, si se puede construir más de un árbol de análisis sintáctico significa que esa sentencia puede “querer decir” cosas diferentes (tiene más de una interpretación). La ambigüedad es difícil de resolver pues no existe una metodología para eliminarla y tampoco hay otra fórmula para saber que una gramática es ambigua. Cuando se presenta una gramática ambigua se debe replantear el diseño de la misma para encontrar una gramática no ambigua equivalente (que genere el mismo lenguaje). Sin embargo en algunos lenguajes de programación, la ambigüedad sintáctica existe y se deberá eliminar con consideraciones semánticas.

DISEÑO DE GRAMÁTICAS PARA LENGUAJES DE PROGRAMACIÓN

Algunas propiedades de los operadores y operandos en los lenguajes de programación se deben plasmar a través de las reglas sintácticas.

La precedencia y la asociatividad, son propiedades suficientes para convertir la gramática ambigua basada en operadores en no ambigua.

1. ASOCIATIVIDAD

La asociatividad de un operador binario define cómo se operan tres o más operandos. La asociatividad por la izquierda quiere decir que si aparecen tres o más operandos, primero se evalúan los dos operandos de más a la izquierda, y el resultado de esa operación se opera con el siguiente operando por la izquierda, y así sucesivamente. En la asociatividad por la derecha, los operandos se evalúan de derecha a izquierda.

En la gramática, la asociatividad de un operador por la izquierda, requiere que la producción en la que interviene dicho operador debe ser recursiva por la izquierda, y cuando es por la derecha, la producción debe tener recursión por la derecha.

2. PRECEDENCIA

La precedencia de un operador especifica el orden de evaluación de cada operador con respecto a los demás operadores. Si un operador tiene mayor precedencia que otro operador, cuando en una expresión aparezcan los dos operadores, se debe evaluar primero el operador con mayor precedencia.

En la gramática se utiliza un símbolo no terminal por cada operador de distinta precedencia. Cuanto más “cerca” esté la producción a la producción del símbolo inicial, menor será la precedencia del operador involucrado.

3. PARENTIZACIÓN

Los lenguajes de programación utilizan los paréntesis (operadores especiales de máxima precedencia) para agrupar los operadores según la conveniencia del programador y sortear las precedencias y asociatividades definidas en el lenguaje.

En la gramática se añade un símbolo no terminal que produzca expresiones entre paréntesis y los operandos (números, variables, etc.) a la mayor distancia posible del símbolo inicial. En esta producción también se pondrían los operadores unarios a no ser que tengan una precedencia menor.

Ejemplo:

Sea la gramática no ambigua que describe expresiones aritméticas:

E -> E + T | E - T | T

T -> T * F | T / F | F

F -> P ^ F | P

P -> P | B

B -> ( E ) | id | cte

El árbol sintáctico de la sentencia a*c+d^4 se muestra en la figura siguiente.

CUP

Es la herramienta principal de todo el proceso. Se encarga de ir demandando al JFlex los lexemas válidos a analizar y generar el código necesario para el análisis sintáctico y semántico.

CUP analiza lsa reglas de la gramática del lenguaje a compilar y genera una serie de acciones a partir del análisis de dichas reglas.

Además CUP distingue entre terminales (devueltos por el JFlex) y no terminales que son las reglas de la gramática.

Dentro de cada regla, CUP puede ejecutar código de Java para analizar su trabajo de análisis.

Un fichero de entrada para CUP consta de las siguientes partes.

1. Definición de paquete y sentencias import.

2. Secciòn de còdigo de usuario.

3. Declaraciòn de símbolos terminales y no terminales

4. Declaraciones de precedencia.

5. Definiciòn del símbolo inicial de la gramàtica y las reglas de producción.

ESTRUCTURA DEL ARCHIVO CUP

A continuación detallaré como se estructura un archivo de entrada para Cup.

Básicamente un archivo para Cup tiene la siguiente estructura:

< imports java >

< codigo del usu rio para el parser>

< Declaración de Variables para la gramatica>

Código del Usuario para el Parser: Como el código Java es generado por la herramienta es muy difícil modificar lo en el archivo de salida. Así que aquí podemos declarar métodos y variables que pensamos usar en la clase resultante. Si se declaran variables o métodos públicos en esta sección estos podrán ser accedidos por otras clases.

Se declara:

parser code {: /* Código del parser*/:}

Código del Usuario para las Acciones de la Gramática: Como nuestro propósito es el de generar un Compilador con estas herramientas o un interprete, necesitamos generar una salida ya sea esta errores semánticos, sintácticos o traducción a un código equivalente, para esto tenemos que hacer uso de traducciones dirigidas por sintaxis.

Sería muy engorroso programar largas funciones en cada acción del gramática así que estas las podemos declarar en esta sección y solo mandarlas a llamar en cada acción gramatical.

Se declara de la siguiente manera:

action code {:/*Codigo para las acciones*/:}

Declaración de Variables para la Gramática : En esta sección toca declarar las variables que se utilizaran en la gramática, estas variables pueden ser de dos tipos:

Variables Terminales < terminal>
Variables No Terminales <non terminal>

Las variables terminales serán todos los símbolos terminales de la gramática y las variables No-Terminales serán todas las variables que representaran producciones.

La sintaxis para la declaración es la siguiente:

< tipo de dato >

< id de la variable >

Donde <tipo de variable > puede ser Terminal o No terminal

<tipo de dato> puede ser cualquier tipo de dato primitivo de Java o uno creado por nosotros mismos. Si se no se especifica el tipo de dato Cup lo trabajará como un tipo de dato Symbol.

<id de la variable > aquí se especifica el id de la variable, se puede usar una lista de identificadores separadas por coma si deseamos variables del mismo tipo.

Gramática: En esta sección del archivo es donde escribiremos nuestra gramatica. La gramatica tiene la siguiente sintaxis :

<non terminal > ::= < terminales o No terminales > ;

Como un no terminal puede tener mas de un lado derecho en Cup se utiliza el simbolo “|”

|<terminales o No terminales> ;

Como es esperado se pueden escribir muchas producciones.

Sección de gramática:

Ahora si procederemos a mostrar la ejecución de nuestro programa usando Jflex y Cup y terminado ya nuestro compilador.

1) Descargamos el jFlex y Cup
http://www.jflex.de/download.html
http://www2.cs.tum.edu/projects/cup/
Y lo agregamos a nuestra librería de nuestro proyecto.

Ya una vez puesto todo eso, al descargar ambos nos viene con lo que irá en este caso en A_Lexico.flex y A_sintactico.cup, lo tenemos que crear e implementar (como venía diciendo anteriormente, en la sección de JFlex y Cup)

A_Lexico.flex

A_sintacto.cup

Luego de esto, procedemos a crear un clase para cada uno, es decir, para generar la clase del A_lexico.flex y para generar la clase del A_sintactico.cup

Pero tener en cuenta que para el caso de GeneradorLexico.java hemos puesto la ubicación de nuestra hoja en blanco (A_lexico.flex) al igual que para GeneradorSintactico.java hemos puesto la ubicación de nuestra hoja en blanco (A_sintactico.cup)

Pero al momento de implementar nuestro A_lexico.flex debemos tener en cuenta esto:

Ya que los tokens que ponemos en A_lexico.flex deben ir en esta clase Simblos.java, todo igual.

Ahora para detectar los errores que puede ocurrir, se crea esta clase

Y ojo, también debemos crear un hoja en blanco para ingresar lo que queremos analizar, en este caso lo hemos llamado, archivo_texto.txt

Que su dirección/ubicación será guardada en el botón compilar de nuestra interfaz

Y para el llenado de la tabla hicimos estas clases LlenadoTabla.java y LlenadoTablaA.java, estas clases se toman en cuenta también en el A_lexico.flex y A_sintactico.cup (ver en las imagenes anteriores) ya que de ahí serán pasadas a la tabla y plasmarse al momento de compilar.