22 de febrero de 2005

Técnicas avanzadas de análisis para compiladores

Estuve recientemente investigando sobre la tecnología usada en editores inteligentes de entornos de desarrollo (IDEs), con capacidades de syntax highlighting, code completion, y otras facilidades de revisión incremental del código.

Los entornos modernos como Eclipse, Netbeans y otros ayudan al desarrollo rápido de software en Java u otros lenguajes (en el caso de Eclipse, por medio de una arquitectura excelente de plug-ins). Para facilitar el manejo de código fuente, se hace uso de técnicas en línea o incrementales de análisis de código. Por ejemplo, puede el editor crear automáticamente los bloques de { y } del cuerpo de una función, si detectan que se ha tecleado lo que pareciera ser una función en el lenguaje para el que se está editando. Si el programador cambiara la definición de la función, tal vez el editor tendría que modificar la estructura editada.

Para esto, se requiere analizar el texto editable, considerándolo como un stream de tokens, pero que tiene la posibilidad de cambiar dinámicamente, en un entorno muy localizado (muy cerca entre sí) de tokens adyacentes. Encontré un par de papers buenísimos del proyecto Harmonia de la Universidad de Berkeley: uno sobre análisis léxico dinámico (PDF) y otro sobre análisis sintáctico dinámico (PDF). Este último método es una adaptación del General LR (GLR) parsing algorithm, conocido también como Algoritmo de Tomita, o la versión rápida del GLR de Aycock y Horspool (PDF).

Lo interesante de estos algoritmos de parsing es que se realizan en paralelo, como si múltiples threads del parser se partieran en un punto del tiempo de análisis, para generar múltiples caminos dentro del proceso de búsqueda de soluciones.

Habrá que hacer más investigación de esto, y seguramente lo incorporaré en una clase futura.

1 comentario:

Osman Omar Mejia dijo...

estas técnicas que UD menciona para algunos compiladores realmente son de mucha utilidad al momento de estar programando y es importante saber como funcionan, pues en un futuro cercano todos los compiladores tendran esta herramienta e incluso estas tecnicas podriamos aplicarlas en otros tipos programas que no sean compiladores.