Ligadores y cargadores

Unidad III Análisis Léxico
M.C. Juan Carlos Olivares Rojas

Agenda
3.1 Introducción a los Autómatas finitos y expresiones regulares. 3.2 Analizador de léxico. 3.3 Manejo de localidades temporales de memoria (buffers). 3.4 Creación de tablas de símbolos. 3.5 Manejo de errores léxicos. 3.6 Generadores de código léxico: Lex y Flex.

3.1 Introducción a los Autómatas finitos y expresionesregulares
• ¿Qué es un autómata? Es un modelo matemático que sirve para determinar si una cadena pertenece a un lenguaje no. • M = (Q, Σ, &, F)
– Q = conjunto de estados – Σ = alfabeto de entrada – & = funciones de transición – F = conjunto de estados de aceptación

Autómatas finitos
• La característica que tienen los autómatas finitos es que solo existe una función de transición definida paraun símbolo de entrada. Esto elimina ambigüedades • Una expresión regular es una forma abreviada de representar lenguajes: • a Representa el lenguaje de las letras a • a* Representa el lenguaje que tiene 0 hasta n a’s

Autómatas
• Oprel |=|=|

• Un solo autómata varios sub_autómatas • Programar un autómata: • Identificador letra (letra|digito|gb)*

Expresión Regular
• Generar la expresiónregular para identificar correos electrónicos válidos. • Formato: • jcolivar@itmorelia.edu.mx • id@dominio

Expresiones Regulares y una gramatica
• Una gramática sirve para generar cadenas de un determinado lenguaje pero también sirve para generarla. • Existente una relación uno a uno entre Lenguajes, Autómatas, Expresiones regulares y gramáticas.

Gramática de un if
prop if expr then prop| if expr then prop else prop |ε termino oprel termino | termino id | num

expr

termino

Gramática de un if
• oprel • id • num < |>|=|=| letra (letra | digito)* digito+ (.digito+)?(E(+|-)?digito+)?

delim+ • eb • delim blanco | tab | linenueva

3.2 Análizador Léxico
• Primera fase de la compilación • Leer caracteres de entrada y generar como salida una secuencia de componentesléxicos • Eliminar espacios en blanco • Eliminar comentarios • Proporcionar información acerca de errores léxicos

Componentes léxicos, lexema y patrones
ID 201 202 203 204 Componente léxico Lexema IF OP_RELACIONAL IDENTIFICADOR ENTERO if , !=, == Patrón if , !=, ==

var, s1, letra (letra | suma, prom dígito | gb)* 2, 23, 5124 (dígito)+

Análisis Léxico
• El análisis exploración. lineal, sellama léxico o

• Posicion := inicial + velocidad * 60 • Posicion: identificador • := símbolo de asignación • Inicial: identificador

Análisis Léxico
• • • • +: signo de suma Velocidad: identificador *: signo de multiplicación 60: numero

• Se elimina todos los espacios en blancos (espacios, tabuladores, salto de línea, etc.)

Análisis Léxico
• Reconocedores de identificadores ypalabras clave • La tabla de símbolo debe insertar y buscar componentes léxicos • La tabla de símbolos es utilizada por el analizador sintáctico y por otras fases del proceso de traducción

Función del analizador léxico

Componente léxico Código fuente Analizador Léxico Obtener siguiente componente léxico Analizador Sintáctico

Tabla de símbolos

Análisis léxico
• Un patrón es una regla quedescribe el conjunto de lexemas que puede representar a un conjunto léxico • Los componentes léxicos se tratan como terminales de la gramática del lenguaje fuente • La devolución de un componente léxico se hace a través de un número entero

Especificación de componentes léxicos
• Expresiones regulares (patrón) • Cada patrón concuerda con una serie de cadenas • Las expresiones regulares dan elnombre al conjunto de cadenas con que concuerdan

Expresiones regulares
• Se construyen a partir de otras expresiones regulares más simples • Cada expresión regular r, representa un lenguaje L(r) • Letra a u b u c u … u z • Dígito 1 u 2 u 3 u … u 0 • Identificador letra(letra u dígito)*

Definiciones regulares
• Dan nombres a las expresiones regulares • Nos permiten referenciarlas...