Código de análisis con errores de sintaxis

Question

Las técnicas de análisis están bien descritas en la literatura de CS. Pero los algoritmos que conozco requieren que la fuente sea sintácticamente correcta. Si se encuentra un error de sintaxis, el análisis se anula inmediatamente.

Pero los IDE (como Visual Studio) suelen ser capaces de proporcionar una terminación de código significativa y otras sugerencias al escribir, lo que significa que la sintaxis a menudo no está en un estado válido. P.ej. escribe un paréntesis de apertura en una llamada de función y el IDE proporciona sugerencias de parámetros para la función, aunque la sintaxis no sea válida hasta que se escriba el paréntesis de cierre.

Me parece que esto debe basarse en algún tipo de adivinador o analizador tolerante a errores. ¿Alguien sabe qué técnicas o algoritmos se utilizan para esto?

Answer 1

Packrat es prometedor: proporciona información sobre el intento de análisis exitoso y fallido en los puntos clave, que se puede recuperar y utilizar para informes de error, finalización, sugerencias, etc. Por ejemplo, si el cursor está en un punto donde todos los intentos de análisis están marcados como fallidos en un caché, se puede dar una lista de los tokens probados para las opciones de finalización.

Answer 2

El truco estándar es hacer algún tipo de reparación de errores utilizando la maquinaria de análisis para ayudar a hacer predicciones.

Para los analizadores basados ​​en tabla (como LALR o GLR), cuando se produce un error de sintaxis, el analizador se encontraba recientemente en algún estado en el que el error aún no se había producido. Se puede grabar la pila de análisis para recordar esto antes de cada turno (o registrar reducciones antes del error). Dado que se ha encontrado un error, se puede inspeccionar el estado de análisis de la pila guardada para determinar qué tokens podrían ser los siguientes (esta es también la forma en que se puede completar el código en términos de tokens de sintaxis). Una técnica más sofisticada puede inventar la secuencia más pequeña posible de tokens que permita un cambio por el token de error, o el árbol más pequeño posible que podría reemplazar el token de error y permitir un cambio en el siguiente.

Esto no es tan fácil con los analizadores de descenso recursivos porque no hay mucha información con la que hacer una predicción. Para la recuperación de errores, un truco cursi es definir los puntos de recuperación de errores (por ejemplo, cuando se acepte un "stmt") y continuar escaneando hasta un ";" se encuentra y acepta y "error stmt". Esto no ayuda si quieres completar el código.