Planteamiento y alcance
Diseña un analizador sintáctico pequeño para expresiones aritméticas y declaraciones de variables. La entrada puede contener varios errores de sintaxis; aun así, el analizador debe reportar posiciones, continuar con las declaraciones posteriores y proporcionar un AST parcial para un IDE.
Esto evalúa los límites entre el análisis léxico, el análisis sintáctico, la recuperación y las estructuras de datos. Bison recomienda descartar la entrada hasta un punto de sincronización y continuar; los IDE también necesitan nodos de error, rangos estables y recuperación más allá del primer error.
Qué evalúa el entrevistador
El candidato debe definir tokens y gramática antes de elegir descenso recursivo o LR, distinguir errores léxicos de errores de sintaxis, elegir puntos de sincronización seguros, suprimir errores en cascada, preservar AST parciales y probar delimitadores anidados, separadores faltantes y cadenas sin terminar.
Estructura de respuesta en 30 segundos
“Separo el lexer, el parser y los diagnósticos. El parser rastrea un cursor de tokens y rangos de origen; tras un error, registra los tokens esperados y reales, salta hasta un punto y coma, delimitador de cierre o EOF, inserta un ErrorNode y continúa. La recuperación suprime duplicados hasta que varios tokens tengan éxito. Los nodos del AST retienen los rangos faltantes para que quienes lo invoquen puedan elegir el modo estricto o tolerante”.
Respuesta detallada paso a paso
Paso 1: Definir tokens y gramática
El lexer emite tipo, texto, desplazamientos y posiciones de línea y columna para identificadores, números, operadores, delimitadores, puntos y coma y caracteres no válidos. La gramática fija la precedencia y la asociatividad para que la recuperación no quede dispersa en las funciones de expresiones.
Paso 2: Elegir la estructura del parser
El descenso recursivo es legible para una gramática pequeña; la técnica de precedence climbing maneja las expresiones. Una gramática más grande puede usar un generador con una estrategia de error explícita. De cualquier manera, el parser necesita lookahead, recuperación de tokens acotada y rangos de origen.
Paso 3: Separar errores léxicos y sintácticos
Un carácter no válido o una cadena sin terminar es un error léxico: emite un token de error y continúa escaneando. Un operando, delimitador o punto y coma faltante es un error sintáctico reportado por el parser en contexto. No etiquetes cada problema como “Unexpected token”.
Paso 4: Elegir puntos de sincronización
Los puntos a nivel de sentencia son puntos y coma, llaves de cierre o EOF. Dentro de las expresiones, sincroniza en comas, paréntesis de cierre o límites de operadores. El salto siempre debe avanzar el cursor o alcanzar EOF, o el mismo error entrará en un bucle infinito.
Paso 5: Construir un AST parcial
Mantén los rangos de error en los nodos. Representa un hijo faltante con MissingNode y un tramo irrecuperable con ErrorNode que contenga los tokens originales. El formateo, el resaltado y el autocompletado deben manejar estos nodos en lugar de asumir un árbol completo.
Paso 6: Suprimir diagnósticos en cascada
Una recuperación puede exponer muchos errores superficiales. Rastrea el último punto de sincronización y el conteo de tokens exitosos; espera varios desplazamientos exitosos antes de reportar otro diagnóstico. Limita los errores por archivo para que los registros y la interfaz de usuario sigan siendo utilizables.
Paso 7: Admitir análisis incremental
Cuando el texto del editor cambie, vuelve a analizar el rango de tokens afectado y el contexto gramatical cercano mientras reutilizas los subárboles no modificados. Mantén estables los rangos de nodos y los identificadores de tokens; invalida cachés según los límites del padre y el estado del parser, no solo por desplazamientos de caracteres.
Paso 8: Probar y medir
Prueba entradas válidas, un solo error, muchos errores, errores anidados, cadenas largas y expresiones muy grandes. Realiza aserciones sobre posiciones, conteos, nodos de error y terminación. Mide el escaneo lineal, la profundidad de recursión, la memoria y el costo de recuperación en el peor caso sobre entradas extensas.
Compensaciones y límites
Fallar rápido frente a continuar
Los compiladores por lotes pueden continuar después de los diagnósticos para ofrecer una mejor retroalimentación; la validación de configuración puede rechazar tras el primer error. Haz que esto sea un modo mientras se comparten el lexer, los tokens y los diagnósticos para evitar discrepancias.
Muchos frente a pocos puntos de sincronización
Más puntos limitan el alcance del error pero pueden saltar tokens recuperables; menos puntos preservan el contexto pero aumentan las cascadas. Define los puntos mediante sentencias y delimitadores, y luego prueba con un corpus representativo.
Descenso recursivo frente a un generador
El descenso recursivo facilita los diagnósticos personalizados; un generador se adapta a una gramática grande y estable. La recuperación debe ser una interfaz explícita en lugar de valores predeterminados no probados del generador.
Simulacros de fallos y evolución
Falta un paréntesis de cierre
Agrega la siguiente sentencia y verifica la sincronización en su punto y coma o EOF, un diagnóstico de delimitador faltante y la preservación de la sentencia posterior.
Carácter no válido y cadena sin terminar
Verifica que el lexer emita un token de error y alcance el final de la línea o de la cadena sin que el parser se quede atascado en un solo carácter.
Una tormenta de errores consecutivos
Introduce una entrada donde cada token sea inválido. El cursor debe avanzar, el recuento de errores debe estar acotado y la CPU no debe crecer de forma cuadrática.
Errores comunes y preguntas de seguimiento
Error 1: Devolver null en el primer error
Pregunta cómo continúa el IDE con el resaltado y el autocompletado; devuelve un ErrorNode o MissingNode con rangos en su lugar.
Error 2: No avanzar durante la recuperación
Pide un argumento de terminación que descarte entrar en bucle sobre el mismo token.
Error 3: Reportar cada error en el parser
Pregunta si una cadena sin terminar y un carácter no válido pertenecen a los diagnósticos del lexer o del parser.
Error 4: Ignorar la supresión de errores en cascada
Pregunta por qué un punto y coma faltante no debería imprimir diez errores repetidos.
Error 5: Almacenar en caché el análisis incremental solo por desplazamiento
Pregunta qué nodos padre y estados del parser se vuelven inválidos después de insertar un delimitador.
Preguntas de seguimiento ampliadas y respuestas de referencia
¿Por qué conservar los nodos de error?
El formateo, el autocompletado y el resaltado aún necesitan estructura y rangos. Los nodos de error permiten que las herramientas posteriores manejen entradas incompletas explícitamente en lugar de fallar abruptamente.
¿Cómo garantizas que la recuperación termine?
Cada recuperación consume un token o alcanza EOF, con límites máximos de error y de recursión.
¿Cómo validas la calidad del diagnóstico?
Usa un corpus que contenga varios errores independientes y realiza aserciones sobre posiciones, conteos, el AST posterior y el tiempo de ejecución, en lugar de probar solo el primer error.