Compiladores: autómatas, parsers, recuperación de errores, tabla de símbolos y gramáticas libres de contexto
Preguntas fundamentales sobre compiladores
14. ¿Qué es un autómata?
Es el modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si dicha cadena pertenece al lenguaje que el autómata reconoce.
16. ¿En qué consiste la recuperación de errores en el parser?
Uno de los aspectos más importantes en el desarrollo de parsers es el soporte de la recuperación de errores sintácticos. Se utilizan los mismos mecanismos de recuperación que YACC. En particular, se emplea un símbolo especial de error, denotado simplemente como error, que actúa como un no terminal especial: en lugar de ser definido por producciones, reconoce la secuencia de entrada errónea.
El símbolo error solo aparece cuando se detecta un error de sintaxis. Al detectarse, el parser intenta reemplazar alguna porción del flujo de tokens de entrada con error y luego continuar el parsing. Por ejemplo, en presencia de producciones como:
stmt ::= expr ; | while_stmt ; | if_stmt ; | ... | error ;
Esto indica que, si ninguna de las producciones normales para stmt puede reconocerse en la entrada, debe declararse un error, y la recuperación consistirá en ignorar los tokens erróneos (lo cual equivale a reconocerlos y reemplazarlos con error) hasta un punto en el que el parser pueda continuar, por ejemplo, con un punto y coma (y el contexto adicional que "legalmente" sigue a la sentencia).
Se considera que un error ha sido recuperado si y solo si un número suficiente de tokens anteriores al símbolo error pueden ser parseados exitosamente. El número de tokens requerido se determina mediante el método del parser error_sync_size() y por defecto es 3.
Funcionamiento específico
El parser primero busca en el tope de la pila el estado más cercano que tenga una transición de salida para error. Esto generalmente corresponde a trabajar desde producciones que representan constructores de nivel más alto (como una clase específica de sentencias) hacia producciones que representan constructores más generales o englobadores, como la producción general para todas las sentencias o la producción que representa la sección de declaraciones en su totalidad, hasta llegar a un lugar en el que se prueba la producción de recuperación del error.
Una vez que el parser ha alcanzado la configuración que tiene la recuperación de error inmediata (desapilando de la pila tantos estados como sea necesario), comienza a ignorar tokens hasta encontrar un punto en el que el parsing pueda continuar.
17. ¿Principales funciones de un manejador de errores?
- Comprobar si el programa es sintácticamente correcto.
- Generar las estructuras de datos (árboles sintácticos u otras estructuras) que representan el programa y sirven al analizador semántico y al generador de código.
- En el caso de compilación dirigida por sintaxis, invocar al analizador semántico y al generador de código.
19. ¿Objetivo del análisis sintáctico?
- Indicar los errores de forma clara y precisa, aclarando el tipo de error y su localización.
- Recuperarse del error, para poder seguir examinando la entrada.
- No ralentizar significativamente la compilación.
21. ¿Funciones del administrador de la tabla de símbolos?
La tabla de símbolos registra información acerca de cada nombre de símbolo en un programa. Históricamente, los nombres se llamaron símbolos, de ahí el nombre de tabla de nombres. La tabla de símbolos es la estructura de datos que contiene un registro por cada identificador, y dicho registro incluye los campos para los atributos del identificador. El administrador de la tabla de símbolos se encarga de manejar los accesos a la tabla en cada una de las etapas de compilación de un programa.
27. ¿Qué es una gramática libre de contexto?
Los lenguajes libres de contexto son aquellos que pueden ser reconocidos por un autómata de pila determinístico o no determinístico.