Proyecto 1 - Scanner/Parser Análisis léxico y Sintáctico

Objetivos

Para este proyecto se espera:

  • Que el alumno construya un analizador léxico capaz de reconocer todos los tokens del lenguaje Decaf.
  • Que el alumno construya un analizador sintáctico capaz de reconocer y validar la estructura de un programa escrito en Decaf.
  • Que el alumno ponga en práctica lo visto en clase sobre análisis léxico y sintáctico, utilizando herramientas comom ANTLR.

Descripción

Scanner

Debe escribir un analizador léxico (scanner) capaz de identificar todos tokens del lenguaje Decaf.

Su scanner debe producir mensajes de error razonables y específicos para caracteres ilegales, comillas faltantes y otros errores léxicos. Su scanner debe encontrar tantos errores léxicos como sea posible, y debe continuar escaneando luego de encontrar dichos errores. El scanner también debe filtrar comentarios y espacios en blanco.

  1. ANTLR:
    No van a tener que escribir el scanner desde cero. Usarán un generador de scanners llamado ANTLR para crear su scanner. Este programa lee un archivo de especificación que contiene expresiones regulares que describen los tokens y produce un programa en Java que escanea el lenguaje descrito. Pueden encontrar más información acerca de ANTLR (incluyendo el manual y algunos ejemplos) en antlr.org

  2. DecafLexer:
    ANTLR va a leer las expresiones regulares de un archivo llamado Decaf.g en el directorio scanner y luego producirá un archivo de salida llamado DecafLexer.java. Noten que ANTLR solamente genera un archivo fuente de Java para el scanner; no lo compila, ni siquiera chequea que la salida sea sintácticamente correcta.
    Por lo tanto, cualquier typo o error sintáctico en el archivo de especificación (el .g) va a ser propagado a la salida. Ustedes deben arreglar cualquier error de este tipo en el archivo Decaf.g antes de entregar su proyecto.

    La clase Token del runtime de ANTLR provee una representación básica abstracta para los tokens. Contiene algunos métodos para obtener información acerca del token:

getType()   			// el tipo de símbolo (un valor de tipo int que es una constante, puede ver el valor en Decaf.tokens)
      getLine()   			// es la linea en la que se encuentra el lexema en el archivo de entrada
      getCharPositionInLine ()    	// es la posición del lexema dentro de la linea actual en el archivo de entrada
      getText ()   			// El lexema con el que hizo coincidencia

Todo terminal distinguible en su gramática para Decaf debe tener un tipo único (un entero) para que el generador de parsers los pueda distinguir. Esto números deben ser enteros consecutivos comenzando en 1. Para que el programa sea legible, debe mapear cada tipo de token a algo más descriptivo: por ejemplo, RETURN = 7. Estas constantes deben ser definidas como public static final int dentro de la clase decafLexer.java. El archivo conteniendo estas definiciones se autogenera por parte de ANTLR.

Cada una de las palabras reservadas es distinguible en la gramática, así que cada una debe tener asignado un identificador único. Algunas clases de tokens toman muchos valores, pero no es necesario que tengan un tipo único para cada valor. Un ejemplo de esto son los tokens tipo integer. La gramática no distingue entre dos valores distintos de un entero. Por lo tanto, todos los enteros pueden tener el mismo tipo. El valor de cada token tipo entero es guardado en el campo que puede obtenerse con el método getText() de la clase Token. definida por ANTLR.

Este campo contiene información descriptiva acerca del token. Noten que el campo Text es de tipo java.lang.String, pueden encontrar más información del Token de ANTLR en el API.

Recuerden que es importante reportar errores y deben hacerlo mostrando el número de línea, una aproximacion para esto es definir un objeto global ErrorMsg que guarda las posiciones de los cambios de línea en el archivo de entrada, y calcula la posición fila y columna de cualquier token usando esta información. Dado que ANTLR ya guarda esta información asociada con el Token pueden hacer uso de ella para que le sea mas fácil.

A pesar que la mayor parte del lexer va a ser generada automáticamente y no programada por ustedes, todavía deben crear una clase Compiler que lea la línea de comandos y llame al lexer generado si se le solicita la etapa scan. Es importante que esta clase se comporte como se especifica en la sección ¿Qué entregar?.

Parser

Su parser debe poder parsear correctamente programas que cumplan con la gramática del lenguaje Decaf.
Cualquier programa que no cumpla con la gramática del lenguaje, debe producir al menos un mensaje de error.

Esta parte del proyecto involucra las siguientes etapas:

  • Escriban una gramática adecuada para el lenguaje Decaf. Van a tener que transformar la gramática de referencia (junto con las reglas de precedencia) en la ‘‘Definición del Lenguaje Decaf’’ a una gramática expresada en la sintáxis de entrada en notación EBNF de ANTLR, el generador de parsers ALL(*) que usarán para el proyecto. La documentación de ANTLR está linkeada desde la página del curso.

  • Su compilador debe interpretar la línea de comandos y ejecutar su parser o su scanner dependiendo de lo que se le pida. Al utilizar la bandera de debug sólo debe ser aplicada a las etapas que se le solicite, de tal forma que el usarla solo para el parser no debería causar que el scanner imprima la lista de tokens. Recuerda que este programa debe estar en una clase llamada Compiler en la raiz de su jerarquía de clases, de tal forma que pueda ser ejecutado usando:

java Compiler [option] <filename>
  • Su parser debe incluir también recuperación básica de errores sintácticos mediante la adición de producciones extras de error que usen el símbolo de error de ANTLR. No traten de hacer recuperaciones de ningún error que dependa del contexto. Mantengan el parser simple. No requerimos recuperación de errores más allá que la habilidad de recuperarse de un paréntesis o llave derechos faltantes.

Su parser no tiene que, ni debe reconocer errores sensitivos al contexto, por ejemplo, usar un identificador entero donde se espera un identificador tipo array. Este tipo de errores van a ser detectados por el analizador semántico. No traten de detectar errores sensitivos al contexto en el parser.

Su parser debe estar implementado en un archivo llamado Decaf.g. Dado que haremos uso de lo que realizado para el scanner, es necesario que importen los tokens utilizando opciones del parser de la siguiente forma:

options {
    tokenVocab=Decaf;
  }

Para ejecutar ANTLR sobre este archivo, desde el directorio compiler, utilice el siguiente comando:

java org.antlr.Tool -lib scanner/ parser/Decaf.g

GIT

Todo el código debe estar actualizado en su repositorio de github, los issues identificados y la documentación también debe ser publicada en github a través del gestor de issues y del wiki.

¿Qué debe entregar?

Debe enviar los fuentes de su proyecto y la documentación del mismo. Su documentación debe incluir las siguientes partes:

  • Una lista de clarificaciones, suposiciones, o adiciones al problema asignado. Las especificaciones del proyecto son bastante amplias: dejan muchas decisiones al implementador (ustedes), lo cual es un aspecto real de ingeniería de software y es mejor que empiecen a acostumbrarse. Si necesitan alguna clarificación, consulten a un auxiliar.

  • Un resumen de su diseño.

  • Una desecripción de su diseño top-level, análisis de alternativas de diseño que consideraron, y decisciones claves de diseño. Asegurense de documentar y justificar cualquier decisión de diseño que tomen. Cualquier decisión acompañada de un argumento convincente va a ser aceptada. Si se dan cuenta que hay errores o deficiencias en su diseño muy tarde en el proceso de implementación discutan estos errores y expliquen qué habrían hecho de manera diferente para evitar el problema.

  • Una descripción de su diseño para módulos no triviales.

  • Cualquier cambio que hayan tenido que realizar en etapas anteriores y por qué fueron necesarios estos cambios.

  • Una breve descripción de temas de implementación interesantes. Esto debe incluir cualquier algoritmo, técnica, y estructura de datos no trivial.

  • Una lista de problemas conocidos de su compilador, y tanta información como le sea posible acerca de la causa de estos problemas. Si su proyecto falla alguno de los casos de prueba, y no pueden arreglar el problema, describan lo que entienden acerca del problema. Si descubren problemas que no pueden arreglar en su proyecto usando sus propias pruebas y estos problemas no son atrapados por los casos de prueba provistos, describan el problema tan específicamente como les sea posible. Si esto causa que su proyecto falle los casos de prueba escondidos, puede que todavía reciban puntos por considerar el problema. Si el problema no es revelado por los casos de prueba escondidos, no se les penalizará.

Asegurense de incluir una descripción completa de cómo su scanner y parser están organizados.
Su compilador debe manejar los argumentos scan y parse de la bandera -target, y debe asumir que el default es parse.

Su scanner (cuándo se usa scan como target) debe tener como salida una lista de errores (si los hay) y crear un archivo de salida que contenga una tabla con una línea para cada token de la entrada donde cada línea contiene el número de línea del token, el tipo de token, y el string de atributos.

La salida de su parser (cuándo se usa parse como target) debe ser un reporte de cualquier error de sintáxis encontrado al parsear el archivo. Los mensajes de error deben incluir el número de línea del error. Cualquier programa sintácticamente incorrecto debe producir al menos un mensaje de error. Deben producirse múltiples mensajes de error para programas que tienen múltiples errores sintácticos que son propicios para recuperación de errores (por ejemplo, un corchete derecho faltante o un punto y coma faltante).

Además recuerde que su parser debe soportar un modo de debug en el que las producciones que están siendo aplicadas durante la fase sean impresas de alguna forma. Esto puede ser activado desde la línea de comandos, mediante:

java Compiler -debug parse <filename>

Entrega

La entrega se realizará a través del GES antes de las 23:55:00 del día Lunes 01 de Septiembre de 2014, debe enviar un archivo llamado grupo.zip conteniendo todas sus clases y demás archivos indicados previamente.

Al desempaquetar su entrega, debemos poder ejecutar su proyecto de la siguiente forma:

java Compiler [option] <filename>

Si no se cumple lo anterior, se verán en riesgo de recibir una penalización del 50%, por lo que tenga mucho cuidado con esto.