Un analizador léxico y/o analizador lexicográfico (en inglés scanner) es la primera fase de
un compilador consistente en un programa que recibe como entrada el código fuente de otro
programa (secuencia de caracteres) y produce una salida compuesta de tokens (componentes
léxicos) o símbolos. Estos tokens sirven para una posterior etapa del proceso de traducción,
siendo la entrada para el analizador sintáctico (en inglés parser).
La especificación de un lenguaje de programación a menudo incluye un conjunto de reglas
que definen el léxico. Estas reglas consisten comúnmente en expresiones regularesque
indican el conjunto de posibles secuencias de caracteres que definen un token o lexema.
En algunos lenguajes de programación es necesario establecer patrones para caracteres
especiales (como el espacio en blanco) que la gramática pueda reconocer sin que constituya
un token en sí.
Esta etapa está basada usualmente en una máquina de estados finitos. Esta máquina
contiene la información de las posibles secuencias de caracteres que puede conformar
cualquier token que sea parte del lenguaje (las instancias individuales de estas secuencias de
caracteres son denominados lexemas). Por ejemplo, un token de naturalezaentero puede
contener cualquier secuencia de caracteres numéricos.
Un analizador sintáctico (o parser) es una de las partes de un compilador que transforma su
entrada en un árbol de derivación.
El análisis sintáctico convierte el texto de entrada en otras estructuras (comúnmente árboles),
que son más útiles para el posterior análisis y capturan la jerarquía implícita de la entrada.
Un analizador léxico crea tokens de una secuencia de caracteres de entrada y son
estos tokens los que son procesados por el analizador sintáctico para construir la estructura
de datos, por ejemplo un árbol de análisis o árboles de sintaxis abstracta.
El análisis sintáctico también es un estado inicial del análisis de frases de lenguaje natural. Es
usado para generar diagramas de lenguajes que usan flexión gramatical, como los idiomas
romances o el latín. Los lenguajes habitualmente reconocidos por los analizadores sintácticos
son los lenguajes libres de contexto. Cabe notar que existe una justificación formal que
establece que los lenguajes libres de contexto son aquellos reconocibles por un autómata de
pila, de modo que todo analizador sintáctico que reconozca un lenguaje libre de contexto es
equivalente en capacidad computacional a un autómata de pila.
Los analizadores sintácticos fueron extensivamente estudiados durante los años 1970,
detectándose numerosos patrones de funcionamiento en ellos, cosa que permitió la creación
de programas generadores de analizadores sintáticos a partir de una especificación de la
sintaxis del lenguaje en forma Backus-Naur por ejemplo, tales como yacc,GNU
bison y javaCC.
Clasificación
La tarea esencial de un analizador es determinar si una determinada entrada puede ser
derivada desde el símbolo inicial, usando las reglas de una gramática formal, y como hacer
esto, existen esencialmente dos formas:
Analizador sintáctico descendente (Top-Down-Parser): ..un analizador puede empezar con
el símbolo inicial e intentar transformarlo en la entrada, intuitivamente esto sería ir
dividiendo la entrada progresivamente en partes cada vez más pequeñas, de esta forma
funcionan los analizadores LL, un ejemplo es el javaCC.
Analizador sintáctico ascendente (Bottom-Up-Parser): un analizador puede empezar con
la entrada e intentar llegar hasta el símbolo inicial, intuitivamente el analizador intenta
encontrar los símbolos más pequeños y progresivamente construir la jerarquía de
símbolos hasta el inicial, los analizadores LR funcionan así y un ejemplo es el Yacc.
Otros tipos de analizadores son:
Analizador sintáctico descendente recursivo
Chart parser
Left corner parser
Analizador sintáctico LR
