Third Assignment

[felix91gr]

From SIDING:

Deberán completar la detección de errores en su programa recorriendo el AST generado y detectando todos los errores no capturados en las etapas anteriores.

El analizador semántico (...) debe ser capaz de extender la representación del AST con información de nombres, scope y tipos de datos. (...) Para cumplir con este requisito será necesario implementar una estructura llamada Tabla de Símbolos que mantenga un registro de todos los símbolos (variables, constantes, funciones, tipos, clases, o lo que corresponda a su lenguaje) presentes en su programa, junto con la información relevante de nombre, token, lexema, scope y tipo de dato cuando corresponda. Al ejecutar su programa deberá ser capaz de imprimir (...) una representación de la Tabla de Símbolos. También debe ser claro que el AST ha sido extendido con la información necesaria. (...) por ejemplo, mediante una referencia a la entrada correspondiente de la Tabla de Símbolos.

(...) el compilador debe ser suficientemente robusto, (...) no debe fallar al encontrar errores léxicos, sintácticos ni semánticos, sino que reportarlos al usuario. Es aceptable que ante un error (...) no se genere ni el AST ni la Tabla de Símbolos, o que se generen de manera incompleta. Los mensajes de errores debe ser reportados (...) de manera que sean una ayuda para el programador (por ejemplo, indicando fila y columna del código fuente). (...) El analizador debe ser capaz de detectar la mayor cantidad de errores posible en una sola ejecución, sin embargo, es aceptable que si hay errores sintácticos, por ejemplo, no se pase a la etapa de análisis semántico.

Requisitos:

• 50% Código de su compilador (lexer+parser+semantic en un solo ejecutable)

  • 8% Entrega de código fuente para generar el compilador. Descripción léxica (3%) y descripción de la gramática (5%). No subir binarios.
  • 2% Instrucciones para compilar (readme, make o algo equivalente, de manera que facilite las pruebas)
  • 10% Entregar al menos dos archivos de código fuente en el lenguaje a compilar, que deben pasar sin errores.
  • 10% Entregar al menos dos archivos de código fuente en el lenguaje a compilar, que deben poseer errores semánticos representativos.
  • 10% Si no hay errores en el código de su lenguaje, el programa debe generar el AST correspondiente extendido con la información de tipos y scope. El AST debe permitir ver o al menos acceder a la información relevante de cada nodo (tipo de token, lexema si corresponde, fila, columna, tipo de dato), y la relación padre-hijo. Para esta parte podremos probar con programas generados por el profesor+ayudante, además de los que deben entregar.
  • 5% Si hay errores en el código de entrada, el programa no necesita generar ni el AST ni la Tabla de Símbolos (podría hacerlo, pero no es necesario), pero sí debe avanzar lo más que pueda en el procesamiento del código de manera de detectar la mayor cantidad posible de errores. Para esta parte podremos probar con programas generados por el profesor+ayudante, además de los que deben entregar.
  • 5% Los mensajes de error deben corresponder al error encontrado, ser suficientemente explicativos, e indicar fila y columna donde lo detectaron. No necesitan mostrar el contexto que provocó el error, ni sugerir su corrección (bonus si hace sugerencias).

• 30% Documento PDF con la descripción de:

  • 5% Lenguaje a compilar y lista de características incluidas (solo lista, sin justificación) actualizada. Snippets de código solo si es necesario para la comprensión.
  • 5% Lista de tokens y gramática del lenguaje actualizada.
  • 10% Reglas semánticas usadas para inferencia de tipos. No necesita poner todas, pero sí las más representativas.
  • 10% Decisiones importantes sobre restricciones adicionales a la gramática, sobre las reglas de tipos utilizadas, y los criterios para definir los scopes.

• 20% Presentación donde deben mostrar:

  • 2% Recordatorio del lenguaje (menor a 1 min)
  • 2% Token y elementos importantes de la gramática. Por ejemplo, si restringieron o agregaron algo respecto a la presentación anterior (ejemplos solo si lo necesitan) (menor a 1 min)
  • 4% Reglas de tipos y de scope más importantes utilizadas (menor a 4 min)
  • 10% Demo de un programa sin errores (5%), y un programa con un error (5%) (menor a 4 min)
  • 2% Enviar la presentación.

[felix91gr]

My Checklist

Grammar and Parser

• Expand the grammar to have functions, prints and comments.
• Expand the grammar to have > and == comparators
• Have Span information on the AST nodes
• Print parsing errors instead of panicking (UI)
• Extensively document the grammar

Semantics

• Document the semantics of the language: what is the input and output of a program, and what is the behavior of the different language primitives.
• Define an algorithm for traversing the AST and checking its semantic correctness.
• Implement such an algorithm, and if successful, output a semantically-rich AST.
• If the algorithm is not successful, print the semantic error (UI)

Testing and Examples

• Make unit tests for all new functionalities
• Make 2+ representative, passing examples
• Make 2+ representative, failing examples
• Use code coverage analysis for measuring test suite quality
• Make a parse-and-serialize test suite?
• Make a fuzzer?
• Use Mutation Testing?

[felix91gr]

The parser was just fuzzed against 30k artificial strings, with 8 valid TC programs as initial seeds. There were no crashes, so I think it's probably fine. The parser should not crash.

[felix91gr]

The AST builder could however be tested against a more methodical approach. Pest handles the invalid input, but what if there's valid input and my AST builder crashes? I should use a CFG-based sentence generator like bnf and feed the parser syntactically valid input. This should never crash, but with this we could try to make sure it doesn't.