Análisis léxico y sintáctico
El análisis léxico y sintáctico constituyen el front-end de un compilador, dividiendo el texto fuente en tokens y reconociendo su estructura gramatical como un árbol de análisis o sintaxis.
Definition
El análisis léxico es la fase que agrupa los caracteres de entrada en tokens, y el análisis sintáctico (parsing) es la fase que determina si esos tokens forman un programa válido y cómo lo hacen, de acuerdo con una gramática, produciendo un árbol de sintaxis.
Scope
Este tema abarca el análisis léxico, que convierte flujos de caracteres en tokens utilizando lenguajes regulares y autómatas finitos, y el análisis sintáctico (parsing), que reconoce la estructura de frase de un programa frente a una gramática libre de contexto. Incluye el análisis descendente (LL) y ascendente (LR), los generadores de analizadores sintácticos, la ambigüedad y la recuperación de errores, y la construcción de árboles de sintaxis abstracta.
Core questions
- ¿Cómo se utilizan los lenguajes regulares y libres de contexto para describir la estructura de un programa?
- ¿Cuáles son las ventajas y desventajas entre el análisis LL y LR?
- ¿Cómo se detectan y manejan la ambigüedad y los errores de análisis?
- ¿Cómo se construye un árbol de sintaxis abstracta a partir de un flujo de tokens?
Key theories
- Análisis LR
- Knuth introdujo el análisis LR, una técnica ascendente que analiza de forma determinista la amplia clase de gramáticas LR en tiempo lineal, formando la base de muchos generadores de analizadores sintácticos.
- Análisis general libre de contexto
- El algoritmo de Earley analiza gramáticas libres de contexto arbitrarias, incluidas las ambiguas, proporcionando un método general cuando los analizadores deterministas restringidos son insuficientes.
- Fundamentos regulares y libres de contexto del front-end
- El "Dragon Book" sistematiza el uso de expresiones regulares y autómatas finitos para el escaneo y las gramáticas libres de contexto para el análisis sintáctico, incluyendo los algoritmos estándar de construcción LL y LR.
Clinical relevance
El análisis léxico y sintáctico son fundamentales no solo para los compiladores, sino también para los intérpretes, linters, formateadores, IDEs y procesadores de formatos de datos. Un análisis robusto con una buena recuperación de errores es esencial para la experiencia del desarrollador con cualquier herramienta de lenguaje.
History
La jerarquía de lenguajes formales de Chomsky a finales de la década de 1950 proporcionó la teoría de los lenguajes regulares y libres de contexto. Knuth formalizó el análisis LR en 1965, y Earley presentó un algoritmo general libre de contexto en 1970. Los generadores de analizadores sintácticos como yacc hicieron práctico el análisis LR, mientras que trabajos posteriores exploraron las gramáticas de expresión de análisis y los analizadores basados en combinadores.
Debates
- Analizadores generados versus escritos a mano
- Los profesionales debaten el uso de generadores de analizadores sintácticos a partir de gramáticas formales, que son concisos y verificables, frente a los analizadores descendentes recursivos escritos a mano, que a menudo ofrecen mejores mensajes de error y control a costa de más código.
Key figures
- Donald Knuth
- Jay Earley
- Alfred Aho
- Noam Chomsky
Related topics
Seminal works
- knuth1965
- earley1970
- aho2006
Frequently asked questions
- ¿Cuál es la diferencia entre un analizador léxico (lexer) y un analizador sintáctico (parser)?
- Un analizador léxico agrupa caracteres brutos en tokens como identificadores y operadores, mientras que un analizador sintáctico organiza esos tokens en un árbol de sintaxis jerárquico según la gramática del lenguaje.
- ¿Cuál es la diferencia entre el análisis LL y LR?
- Los analizadores LL funcionan de arriba hacia abajo, prediciendo producciones a partir del prefijo de entrada, mientras que los analizadores LR funcionan de abajo hacia arriba, reduciendo subcadenas reconocidas; LR maneja una clase de gramáticas estrictamente mayor, pero es más complejo de construir.