PDF de programación - Procesadores de Lenguajes - Tema 2. Análisis léxico

UNIVERSIDAD NACIONAL DE EDUCACIÓN A DISTANCIA

Escuela Técnica Superior de Ingeniería Informática

Procesadores de Lenguajes

Tema 2
Tema 2

Análisis Léxico
Análisis Léxico

Javier Vélez Reyes
[email protected]

Javier Vélez Reyes [email protected]

Objetivos del Tema
Objetivos del Tema
Conocer el funcionamiento de un analizador léxico
(cid:132)(cid:132) Conocer el funcionamiento de un analizador léxico
Entender las relaciones de éste con
(cid:132)(cid:132) Entender las relaciones de éste con
La tabla de símbolos
(cid:132)(cid:132) La tabla de símbolos
La gestión de errores
(cid:132)(cid:132) La gestión de errores
Aprender a especificar formalmente un analizador
(cid:132)(cid:132) Aprender a especificar formalmente un analizador
Conocer las distintas técnicas de implementación
(cid:132)(cid:132) Conocer las distintas técnicas de implementación

1

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Especificación de un Analizador Léxico
(cid:132)(cid:132) Especificación de un Analizador Léxico
Implementación de un Analizador Léxico
(cid:132)(cid:132) Implementación de un Analizador Léxico

Javier Vélez Reyes [email protected]

Introducción
Introducción

e d a d

Scanner
Scanner

Tabla Símbolos
Tabla Símbolos

G. Errores
G. Errores

Análisis Léxico
(cid:132)(cid:132) Análisis Léxico
Scanner
(cid:132)(cid:132) Scanner
Tabla de Símbolos
(cid:132)(cid:132) Tabla de Símbolos
Gestión de Errores
(cid:132)(cid:132) Gestión de Errores
Funciones
(cid:132)(cid:132) Funciones
Tratar con la tabla de símbolos
(cid:132)(cid:132) Tratar con la tabla de símbolos
Generar tokens bajo demanda del analizador sintáctico
(cid:132)(cid:132) Generar tokens bajo demanda del analizador sintáctico
Manejar el fichero fuente
(cid:132)(cid:132) Manejar el fichero fuente
Ignorar comentarios
(cid:132)(cid:132) Ignorar comentarios
Contabilizar posición de tokens
(cid:132)(cid:132) Contabilizar posición de tokens
Preprocesar macros, constantes, includes…
(cid:132)(cid:132) Preprocesar macros, constantes, includes…

[ID, “edad”]

2

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Especificación de un Analizador Léxico
(cid:132)(cid:132) Especificación de un Analizador Léxico
Especificación formal
(cid:132)(cid:132) Especificación formal
Gramáticas Linealmente Recursivas
(cid:132)(cid:132) Gramáticas Linealmente Recursivas
Lenguajes Regulares
(cid:132)(cid:132) Lenguajes Regulares
Autómatas Finitos
(cid:132)(cid:132) Autómatas Finitos
Términos utilizados
(cid:132)(cid:132) Términos utilizados
Pasos para especificar un analizador léxico
(cid:132)(cid:132) Pasos para especificar un analizador léxico
Implementación de un Analizador Léxico
(cid:132)(cid:132) Implementación de un Analizador Léxico

Javier Vélez Reyes [email protected]

Especificación de analizador léxico I
Especificación de analizador léxico I
Especificación formal
(cid:132)(cid:132) Especificación formal
Gramáticas Lineales
(cid:132)(cid:132) Gramáticas Lineales
Recursivas a izquierdas
(cid:132)(cid:132) Recursivas a izquierdas
Recursivas a derechas
(cid:132)(cid:132) Recursivas a derechas
Lenguajes (expresiones) regulares
(cid:132)(cid:132) Lenguajes (expresiones) regulares
Autómatas finitos (Diagramas de Transición)
(cid:132)(cid:132) Autómatas finitos (Diagramas de Transición)

Gramáticas
Gramáticas
Lineales
Lineales

ISOMORFO
ISOMORFO

Diagramas
Diagramas
de transición
de transición

Expresiones
Expresiones
regulares
regulares

3

Javier Vélez Reyes [email protected]

Gramáticas Linealmente Recursivas
Gramáticas Linealmente Recursivas
Gramáticas Linealmente Recursivas
(cid:132)(cid:132) Gramáticas Linealmente Recursivas
Alfabeto terminal
(cid:132)(cid:132) Alfabeto terminal
Alfabeto no terminal
(cid:132)(cid:132) Alfabeto no terminal
Axioma
(cid:132)(cid:132) Axioma
Reglas de producción
(cid:132)(cid:132) Reglas de producción
Tipos
(cid:132)(cid:132) Tipos
Recursividad a izquierdas
(cid:132)(cid:132) Recursividad a izquierdas

S := A letra | A digito
A := A letra | A digito | letra

Recursividad a derechas
(cid:132)(cid:132) Recursividad a derechas

S := letra A
A := letra A | digito A | letra | digito

Javier Vélez Reyes [email protected]

Expresiones regulares
Expresiones regulares

(1 o más)
(1 o más)
(0 o más)
(0 o más)

Expresiones regulares
(cid:132)(cid:132) Expresiones regulares
Alfabeto
(cid:132)(cid:132) Alfabeto
Cierre simétrico +
(cid:132)(cid:132) Cierre simétrico +
Cierre transitivo *
(cid:132)(cid:132) Cierre transitivo *
Ejemplos
(cid:132)(cid:132) Ejemplos
(b | c)++
(cid:132)(cid:132) aa**(b | c)
bccbcbccbc
(cid:132)(cid:132) bccbcbccbc
abbbccc
(cid:132)(cid:132) abbbccc
abbcbcccbbc
(cid:132)(cid:132) abbcbcccbbc
(cid:132)(cid:132) (0(0--9)9)**.(0.(0--9)9)++

0.236425
(cid:132)(cid:132) 0.236425
3567.45627
(cid:132)(cid:132) 3567.45627
.758478
(cid:132)(cid:132) .758478
(cid:132)(cid:132) 5.05.0

4

Javier Vélez Reyes [email protected]

Diagramas de transición
Diagramas de transición

Diferencias con autómatas finitos
(cid:132)(cid:132) Diferencias con autómatas finitos
Acciones asociadas a ciertos estados
(cid:132)(cid:132) Acciones asociadas a ciertos estados
Estados de Aceptación
Aceptación
(cid:132)(cid:132) Estados de
Estados con Retroceso (*)
(cid:132)(cid:132) Estados con Retroceso (*)
No tienen estados de absorción (se omiten)
(cid:132)(cid:132) No tienen estados de absorción (se omiten)
Los estados de aceptación no tienen transiciones
(cid:132)(cid:132) Los estados de aceptación no tienen transiciones
Transición especial otrootro
(cid:132)(cid:132) Transición especial

AFD

DT

Javier Vélez Reyes [email protected]

Especificación de analizador léxico II
Especificación de analizador léxico II
Términos utilizados
(cid:132)(cid:132) Términos utilizados
Token
(cid:132)(cid:132) Token
Elemento léxico del lenguaje
(cid:132)(cid:132) Elemento léxico del lenguaje
Símbolo No Terminal de las fases siguientes
(cid:132)(cid:132) Símbolo No Terminal de las fases siguientes
Patrón
(cid:132)(cid:132) Patrón
Expresión regular que define el lenguaje
(cid:132)(cid:132) Expresión regular que define el lenguaje
Letra (Letra
(cid:132)(cid:132) Letra (
Lexema
(cid:132)(cid:132) Lexema
Secuencia de caracteres que concuerda con un patrón
(cid:132)(cid:132) Secuencia de caracteres que concuerda con un patrón
numeroUsuarios
(cid:132)(cid:132) numeroUsuarios
Atributos
(cid:132)(cid:132) Atributos
Estructura de datos de cada token para almacenarse en la TS
(cid:132)(cid:132) Estructura de datos de cada token para almacenarse en la TS
Depende del tipo de token
(cid:132)(cid:132) Depende del tipo de token
[ID, Lexema, Tipo, Valor, línea]
(cid:132)(cid:132) [ID, Lexema, Tipo, Valor, línea]

Letra | Digito)
| Digito)**

5

Javier Vélez Reyes [email protected]

Especificación de analizador léxico III
Especificación de analizador léxico III
Pasos para especificar un analizador léxico
(cid:132)(cid:132) Pasos para especificar un analizador léxico
Identificar la colección de tokens
(cid:132)(cid:132) Identificar la colección de tokens
Estructurar la colección de tokens
(cid:132)(cid:132) Estructurar la colección de tokens
Describir el lenguaje como expresiones regulares
(cid:132)(cid:132) Describir el lenguaje como expresiones regulares
Especificar un Diagrama de Transición
(cid:132)(cid:132) Especificar un Diagrama de Transición
Traducir el Diagrama a una tabla de transición
(cid:132)(cid:132) Traducir el Diagrama a una tabla de transición
Ejemplo
(cid:132)(cid:132) Ejemplo

Especificar un analizador léxico que reconozca
Especificar un analizador léxico que reconozca
• Números enteros
• Números enteros
• Operadores aritméticos y de incremento (+, - *, /, ++,--)
• Operadores aritméticos y de incremento (+, - *, /, ++,--)
• Identificadores
• Identificadores
• WHILE
• WHILE

Javier Vélez Reyes [email protected]

Índice General
Índice General

Introducción
(cid:132)(cid:132) Introducción
Especificación de un Analizador Léxico
(cid:132)(cid:132) Especificación de un Analizador Léxico
Implementación de un Analizador Léxico
(cid:132)(cid:132) Implementación de un Analizador Léxico
Estrategias de implementación
(cid:132)(cid:132) Estrategias de implementación
Prioridad de los tokens
(cid:132)(cid:132) Prioridad de los tokens
Reconocimiento de palabras reservadas
(cid:132)(cid:132) Reconocimiento de palabras reservadas
Gestión de errores
(cid:132)(cid:132) Gestión de errores

6

Javier Vélez Reyes [email protected]

Implementación del analizador léxico I
Implementación del analizador léxico I
Estrategias de implementación
(cid:132)(cid:132) Estrategias de implementación
Implementación automática
(cid:132)(cid:132) Implementación automática
Especificación de los patrones de la gramática
(cid:132)(cid:132) Especificación de los patrones de la gramática
(cid:132)(cid:132) LEXLEX
Implementación manual del diagrama de transiciones
(cid:132)(cid:132) Implementación manual del diagrama de transiciones
Simulación de transiciones del diagrama
(cid:132)(cid:132) Simulación de transiciones del diagrama
Implementación manual directa
(cid:132)(cid:132) Implementación manual directa
Codificación con estructuras condicionales (if, case, …)
(cid:132)(cid:132) Codificación con estructuras condicionales (if, case, …)
Implementación híbrida
(cid:132)(cid:132) Implementación híbrida
Análisis directo de las estructuras más sencillas
(cid:132)(cid:132) Análisis directo de las estructuras más sencillas

Operadores
(cid:132)(cid:132) Operadores

Análisis mediante diagrama de estructuras complejas
(cid:132)(cid:132) Análisis mediante diagrama de estructuras complejas

Cadenas no específicas
(cid:132)(cid:132) Cadenas no específicas
Prefijos comunes
(cid:132)(cid:132) Prefijos comunes

Javier Vélez Reyes [email protected]

Implementación del analizador léxico II
Implementación del analizador léxico II
Prioridad de tokens
(cid:132)(cid:132) Prioridad d