Procesadores de Lenguajes Tema II: Analisis Lexico

PROCESADORES DE LENGUAJES
TEMA II: ANALISIS LEXICO

Prof. Dr. Nicolas Luis Fernandez Garca

Departamento de Informatica y Analisis Numerico

Escuela Politecnica Superior
Universidad de Cordoba

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 1 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Programa

Tema I.- Introduccion

Tema II .- Analisis Lexicografico
Tema III.- Fundamentos Teoricos del Analisis Sintactico
Tema IV.- Analisis Sintactico Descendente
Tema V.- Analisis Sintactico Ascendente

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 2 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Programa

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 3 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Programa

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 4 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Programa

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 5 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Programa

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 6 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Programa

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 7 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido del tema

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 8 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion
El analisis lexico en el proceso de traduccion
Componentes Lexicos
Tabla de Smbolos
Palabras claves
Ejemplo
Autonoma del analizador lexico

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 9 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Analisis Lexico
Primera fase del proceso de traduccion
Lee el codigo fuente caracter a caracter
Genera los componentes lexicos
Procedimiento auxiliar del Analisis Sintactico
Crea la Tabla de Smbolos
El Gestor de errores procesa los errores lexicos detectados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 10 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Analisis Lexico
Primera fase del proceso de traduccion
Lee el codigo fuente caracter a caracter
Genera los componentes lexicos
Procedimiento auxiliar del Analisis Sintactico
Crea la Tabla de Smbolos
El Gestor de errores procesa los errores lexicos detectados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 11 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Analisis Lexico
Primera fase del proceso de traduccion
Lee el codigo fuente caracter a caracter
Genera los componentes lexicos
Procedimiento auxiliar del Analisis Sintactico
Crea la Tabla de Smbolos
El Gestor de errores procesa los errores lexicos detectados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 12 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Analisis Lexico
Primera fase del proceso de traduccion
Lee el codigo fuente caracter a caracter
Genera los componentes lexicos
Procedimiento auxiliar del Analisis Sintactico
Crea la Tabla de Smbolos
El Gestor de errores procesa los errores lexicos detectados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 13 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Analisis Lexico
Primera fase del proceso de traduccion
Lee el codigo fuente caracter a caracter
Genera los componentes lexicos
Procedimiento auxiliar del Analisis Sintactico
Crea la Tabla de Smbolos
El Gestor de errores procesa los errores lexicos detectados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 14 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Analisis Lexico
Primera fase del proceso de traduccion
Lee el codigo fuente caracter a caracter
Genera los componentes lexicos
Procedimiento auxiliar del Analisis Sintactico
Crea la Tabla de Smbolos
El Gestor de errores procesa los errores lexicos detectados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 15 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Codigo Fuente

Analizador Lexico

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 16 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Codigo Fuente

Tabla de Smbolos

Analizador Lexico

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 17 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Codigo Fuente

Tabla de Smbolos Gestor de Errores

Analizador Lexico

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 18 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
El analisis lexico en el proceso de traduccion

Codigo Fuente

Tabla de Smbolos Gestor de Errores

Analizador Lexico

Componentes Lexicos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 19 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion
El analisis lexico en el proceso de traduccion
Componentes Lexicos
Tabla de Smbolos
Palabras claves
Ejemplo
Autonoma del analizador lexico

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 20 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Definicion (Componente lexico)

Elemento mas simple con significado propio de un lenguaje de
programacion:

Ejemplo
Identificadores: variables, palabras claves, ...
Numeros
Cadenas de caracteres
Operadores: aritmeticos, relacionales, logicos, ...
Signos de puntuacion
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 21 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Definicion (Componente lexico)

Elemento mas simple con significado propio de un lenguaje de
programacion:

Ejemplo
Identificadores: variables, palabras claves, ...
Numeros
Cadenas de caracteres
Operadores: aritmeticos, relacionales, logicos, ...
Signos de puntuacion
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 22 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Definicion (Componente lexico)

Elemento mas simple con significado propio de un lenguaje de
programacion:

Ejemplo
Identificadores: variables, palabras claves, ...
Numeros
Cadenas de caracteres
Operadores: aritmeticos, relacionales, logicos, ...
Signos de puntuacion
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 23 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Definicion (Componente lexico)

Elemento mas simple con significado propio de un lenguaje de
programacion:

Ejemplo
Identificadores: variables, palabras claves, ...
Numeros
Cadenas de caracteres
Operadores: aritmeticos, relacionales, logicos, ...
Signos de puntuacion
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 24 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Definicion (Componente lexico)

Elemento mas simple con significado propio de un lenguaje de
programacion:

Ejemplo
Identificadores: variables, palabras claves, ...
Numeros
Cadenas de caracteres
Operadores: aritmeticos, relacionales, logicos, ...
Signos de puntuacion
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 25 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Definicion (Componente lexico)

Elemento mas simple con significado propio de un lenguaje de
programacion:

Ejemplo
Identificadores: variables, palabras claves, ...
Numeros
Cadenas de caracteres
Operadores: aritmeticos, relacionales, logicos, ...
Signos de puntuacion
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 26 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Definicion (Componente lexico)

Elemento mas simple con significado propio de un lenguaje de
programacion:

Ejemplo
Identificadores: variables, palabras claves, ...
Numeros
Cadenas de caracteres
Operadores: aritmeticos, relacionales, logicos, ...
Signos de puntuacion
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 27 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Los componentes lexicos

Tambien se denominan tokens
Son los smbolos terminales de las gramaticas de contexto
libre que generan los lenguajes de programacion.
Son en realidad codigos numericos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 28 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Los componentes lexicos

Tambien se denominan tokens
Son los smbolos terminales de las gramaticas de contexto
libre que generan los lenguajes de programacion.
Son en realidad codigos numericos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 29 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Componentes Lexicos

Los componentes lexicos

Tambien se denominan tokens
Son los smbolos terminales de las gramaticas de contexto
libre que generan los lenguajes de programacion.
Son en realidad codigos numericos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 30 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion
El analisis lexico en el proceso de traduccion
Componentes Lexicos
Tabla de Smbolos
Palabras claves
Ejemplo
Autonoma del analizador lexico

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 31 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Tabla de Smbolos

Tabla de Smbolos
Se crea durante el Analisis Lexico
Puede almacenar:
+ Numeros
+ Cadenas
+ ...
+ Pero, sobre todo, identificadores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 32 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Tabla de Smbolos

Tabla de Smbolos
Cuando el analizador lexico reconoce un identificador:
+ Se inserta el identificador en la Tabla de Smbolos
+ Devuelve el componente lexico de identificador y un puntero o
ndice a su posicion en la Tabla de Smbolos
La informacion del identificador depende de su naturaleza:
+ Variable: tipo de dato, valor, ...
+ Funcion: numero y tipo de argumentos, ...
+ Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 33 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Tabla de Smbolos

Tabla de Smbolos
Cuando el analizador lexico reconoce un identificador:
+ Se inserta el identificador en la Tabla de Smbolos
+ Devuelve el componente lexico de identificador y un puntero o
ndice a su posicion en la Tabla de Smbolos
La informacion del identificador depende de su naturaleza:
+ Variable: tipo de dato, valor, ...
+ Funcion: numero y tipo de argumentos, ...
+ Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 34 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Tabla de Smbolos

Ejemplo (dividendo = divisor * cociente + resto)

Nombre Tipo Valor ...
dividendo
divisor
cociente
resto

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 35 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Tabla de Smbolos

Nota
La informacion de los identificadores se completa durante todas las
fases del proceso de traduccion

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 36 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion
El analisis lexico en el proceso de traduccion
Componentes Lexicos
Tabla de Smbolos
Palabras claves
Ejemplo
Autonoma del analizador lexico

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 37 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves o reservadas

Son identificadores con un significado especial
Algunos lenguajes de programacion tambien permiten usar las
palabras claves como variables
+ Las palabras claves no seran palabras reservadas
+ Dificulta la legibilidad de los programas

Ejemplo (PL/I)
IF (IF > 1) THEN THEN = 0;

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 38 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves o reservadas

Son identificadores con un significado especial
Algunos lenguajes de programacion tambien permiten usar las
palabras claves como variables
+ Las palabras claves no seran palabras reservadas
+ Dificulta la legibilidad de los programas

Ejemplo (PL/I)
IF (IF > 1) THEN THEN = 0;

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 39 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves o reservadas

Son identificadores con un significado especial
Algunos lenguajes de programacion tambien permiten usar las
palabras claves como variables
+ Las palabras claves no seran palabras reservadas
+ Dificulta la legibilidad de los programas

Ejemplo (PL/I)
IF (IF > 1) THEN THEN = 0;

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 40 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
Tipos de reconocimiento de las palabras claves:
1.- Implcito: preinstalacion en la Tabla de Smbolos
2.- Explcito: reconocimiento especfico de cada palabra clave.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 41 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
Tipos de reconocimiento de las palabras claves:
1.- Implcito: preinstalacion en la Tabla de Smbolos
2.- Explcito: reconocimiento especfico de cada palabra clave.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 42 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
Tipos de reconocimiento de las palabras claves:
1.- Implcito: preinstalacion en la Tabla de Smbolos
2.- Explcito: reconocimiento especfico de cada palabra clave.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 43 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
1.- Preinstalacion en la Tabla de Smbolos:
+ Se almacena el nombre y el componente lexico
+ Al reconocer un identificador, se consulta la Tabla de Smbolos
para comprobar si es una palabra clave o no.
+ Ventajas
- La programacion del analizador lexico es mas sencilla
+ Inconvenientes
- El reconocimiento es mas lento
- Se necesita mas memoria para la Tabla de Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 44 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
1.- Preinstalacion en la Tabla de Smbolos:
+ Se almacena el nombre y el componente lexico
+ Al reconocer un identificador, se consulta la Tabla de Smbolos
para comprobar si es una palabra clave o no.
+ Ventajas
- La programacion del analizador lexico es mas sencilla
+ Inconvenientes
- El reconocimiento es mas lento
- Se necesita mas memoria para la Tabla de Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 45 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
1.- Preinstalacion en la Tabla de Smbolos:
+ Se almacena el nombre y el componente lexico

Ejemplo
Nombre Componente Lexico ... ...
if IF
while WHILE
...

+ Al reconocer un identificador, se consulta la Tabla de Smbolos

para comprobar si es una palabra clave o no.
+ Ventajas
- La programacion del analizador lexico es mas sencilla
+ Inconvenientes
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 46 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
1.- Preinstalacion en la Tabla de Smbolos:
+ Se almacena el nombre y el componente lexico
+ Al reconocer un identificador, se consulta la Tabla de Smbolos
para comprobar si es una palabra clave o no.
+ Ventajas
- La programacion del analizador lexico es mas sencilla
+ Inconvenientes
- El reconocimiento es mas lento
- Se necesita mas memoria para la Tabla de Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 47 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
1.- Preinstalacion en la Tabla de Smbolos:
+ Se almacena el nombre y el componente lexico
+ Al reconocer un identificador, se consulta la Tabla de Smbolos
para comprobar si es una palabra clave o no.
+ Ventajas
- La programacion del analizador lexico es mas sencilla
+ Inconvenientes
- El reconocimiento es mas lento
- Se necesita mas memoria para la Tabla de Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 48 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
1.- Preinstalacion en la Tabla de Smbolos:
+ Se almacena el nombre y el componente lexico
+ Al reconocer un identificador, se consulta la Tabla de Smbolos
para comprobar si es una palabra clave o no.
+ Ventajas
- La programacion del analizador lexico es mas sencilla
+ Inconvenientes
- El reconocimiento es mas lento
- Se necesita mas memoria para la Tabla de Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 49 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
2.- Reconocimiento especfico de cada palabra clave.
+ Cada palabra clave es reconocida de forma independiente de
los demas identificadores y palabras claves
+ Ventajas
- El reconocimiento es mas rapido
- No se necesita aumentar la memoria de la Tabla de Smbolos:
las palabras claves no se almacenan
+ Inconvenientes
- La programacion del analizador lexico es mas compleja

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 50 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
2.- Reconocimiento especfico de cada palabra clave.
+ Cada palabra clave es reconocida de forma independiente de
los demas identificadores y palabras claves
+ Ventajas
- El reconocimiento es mas rapido
- No se necesita aumentar la memoria de la Tabla de Smbolos:
las palabras claves no se almacenan
+ Inconvenientes
- La programacion del analizador lexico es mas compleja

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 51 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Palabras claves

Palabras claves
2.- Reconocimiento especfico de cada palabra clave.
+ Cada palabra clave es reconocida de forma independiente de
los demas identificadores y palabras claves
+ Ventajas
- El reconocimiento es mas rapido
- No se necesita aumentar la memoria de la Tabla de Smbolos:
las palabras claves no se almacenan
+ Inconvenientes
- La programacion del analizador lexico es mas compleja

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 52 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion
El analisis lexico en el proceso de traduccion
Componentes Lexicos
Tabla de Smbolos
Palabras claves
Ejemplo
Autonoma del analizador lexico

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 53 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

dividendo
+ Es reconocido como IDENTIFICADOR
+ Se devuelve el componente lexico y el puntero a la Tabla de
Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 54 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

Se eliminan
+ Espacios en blanco
+ Tabuladores
+ Saltos de lnea

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 55 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

Signo =
+ Se devuelve el token de ASIGNACION

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 56 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

Nota
El Analisis Sintactico solo necesita saber que se ha reconocido
el componente lexico ASIGNACION
No le importa si el smbolo es = o := o cualquier otro
No interesa el texto concreto, sino la categora a la que
pertenece

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 57 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

divisor
+ Es reconocido como IDENTIFICADOR
+ Se devuelve el componente lexico y el puntero a la Tabla de
Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 58 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

Signo *
+ Se devuelve el token de PRODUCTO

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 59 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

cociente
+ Es reconocido como IDENTIFICADOR
+ Se devuelve el componente lexico y el puntero a la Tabla de
Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 60 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

Signo +
+ Se devuelve el token de SUMA

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 61 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

resto
+ Es reconocido como IDENTIFICADOR
+ Se devuelve el componente lexico y el puntero a la Tabla de
Smbolos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 62 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Ejemplo

Ejemplo
Sentencia del lenguaje C
dividendo = divisor * cociente + resto ;

Signo ;
+ Se devuelve el token de FIN DE SENTENCIA

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 63 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion
El analisis lexico en el proceso de traduccion
Componentes Lexicos
Tabla de Smbolos
Palabras claves
Ejemplo
Autonoma del analizador lexico

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 64 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 65 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
+ La separacion de tareas facilita el mantenimiento y mejora del
traductor
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 66 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 67 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
+ Los componentes lexicos pueden ser denotados por Expresiones
Regulares
+ Los Automatas Finitos Deterministas (AFD) reconocen las
palabras denotadas por las expresiones regulares
+ Los Analizadores Lexicos estan basados en los Automatas
Finitos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 68 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
+ Los componentes lexicos pueden ser denotados por Expresiones
Regulares
+ Los Automatas Finitos Deterministas (AFD) reconocen las
palabras denotadas por las expresiones regulares
+ Los Analizadores Lexicos estan basados en los Automatas
Finitos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 69 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
+ Los componentes lexicos pueden ser denotados por Expresiones
Regulares
+ Los Automatas Finitos Deterministas (AFD) reconocen las
palabras denotadas por las expresiones regulares
+ Los Analizadores Lexicos estan basados en los Automatas
Finitos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 70 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 71 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
+ El Analisis Lexico es la unica fase que tiene contacto con el
codigo fuente
+ Puede procesar el texto: eliminar espacios en blanco,
comentarios
+ Almacena la posicion de los saltos de lnea para informar sobre
la localizacion de los errores detectados
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 72 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
+ El Analisis Lexico es la unica fase que tiene contacto con el
codigo fuente
+ Puede procesar el texto: eliminar espacios en blanco,
comentarios
+ Almacena la posicion de los saltos de lnea para informar sobre
la localizacion de los errores detectados
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 73 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
+ El Analisis Lexico es la unica fase que tiene contacto con el
codigo fuente
+ Puede procesar el texto: eliminar espacios en blanco,
comentarios
+ Almacena la posicion de los saltos de lnea para informar sobre
la localizacion de los errores detectados
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 74 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 75 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
+ Las operaciones de lectura / escritura son computacionalmente
muy costosas
+ Se puede mejorar la eficiencia si se codifican con sentencias de
bajo nivel: ensamblador, ...
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 76 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
+ Las operaciones de lectura / escritura son computacionalmente
muy costosas
+ Se puede mejorar la eficiencia si se codifican con sentencias de
bajo nivel: ensamblador, ...
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 77 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 78 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad
+ La codificacion de los caracteres pueden variar de un entorno
de ejecucion a otro: ASCII, EBCDIC, ...
+ El cambio de codificacion solo requerira modificar el Analisis
Lexico, no siendo necesario modificar el resto de fases.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 79 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad
+ La codificacion de los caracteres pueden variar de un entorno
de ejecucion a otro: ASCII, EBCDIC, ...
+ El cambio de codificacion solo requerira modificar el Analisis
Lexico, no siendo necesario modificar el resto de fases.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 80 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Introduccion
Autonoma del analizador lexico

Razones para separar el analisis lexico del analisis sintactico

Modularidad
Menor complejidad de los componentes lexicos
Pre-procesamiento del codigo fuente
Mejora en la eficiencia del analizador lexico
Portabilidad

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 81 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido del tema

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 82 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

Descripcion de los componentes lexicos
Palabras y lenguajes formales
Expresiones Regulares

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 83 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Componentes lexicos
Elementos basicos de los lenguajes de programacion
Se describen mediante
+ Una descripcion informal
+ Una descripcion formal mediante expresiones regulares
+ Ejemplos o paradigmas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 84 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Componentes lexicos
Elementos basicos de los lenguajes de programacion
Se describen mediante
+ Una descripcion informal
+ Una descripcion formal mediante expresiones regulares
+ Ejemplos o paradigmas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 85 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Componentes lexicos
Elementos basicos de los lenguajes de programacion
Se describen mediante
+ Una descripcion informal
+ Una descripcion formal mediante expresiones regulares
+ Ejemplos o paradigmas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 86 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Componentes lexicos
Elementos basicos de los lenguajes de programacion
Se describen mediante
+ Una descripcion informal
+ Una descripcion formal mediante expresiones regulares
+ Ejemplos o paradigmas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 87 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Componentes lexicos
Elementos basicos de los lenguajes de programacion
Se describen mediante
+ Una descripcion informal
+ Una descripcion formal mediante expresiones regulares
+ Ejemplos o paradigmas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 88 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Ejemplo (Componentes lexicos en el lenguaje C 1 / 7)

IDENTIFICADOR
Descripcion informal: Cadenas de caracteres compuestas por
letras, cifras y el smbolo de subrayado, pero que no comienza
por una cifra.
Descripcion formal:
(letra + subrayado)(letra + cifra + subrayado)
Ejemplos o paradigmas:
dividendo, divisor, cociente, resto, suma total, x 1, ...

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 89 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Ejemplo (Componentes lexicos en el lenguaje C 2 / 7)

NUMERO
Descripcion informal: numeros enteros, reales, ...
Descripcion formal:
cifra cifra ( + .cifra ( + (E + e)( + + + )cifra cifra ))
Ejemplos o paradigmas: 9, 19.7, 97.7e2, ...

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 90 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Ejemplo (Componentes lexicos en el lenguaje C 3 / 7)

IF
Descripcion informal: palabra clave de la sentencia
condicional if
Descripcion formal: if
Ejemplo o paradigma: if

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 91 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Ejemplo (Componentes lexicos en el lenguaje C 4 / 7)

FOR
Descripcion informal: palabra clave de la sentencia de
repeticion for
Descripcion formal: for
Ejemplo o paradigma: for

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 92 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Ejemplo (Componentes lexicos en el lenguaje C 5 / 7)

ASIGNACION
Descripcion informal: signo igual para la sentencia de
asignacion
Descripcion formal: =
Ejemplo o paradigma: =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 93 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Ejemplo (Componentes lexicos en el lenguaje C 6 / 7)

MAYOR IGUAL QUE
Descripcion informal: operador relacional mayor o igual que
Descripcion formal: >=
Ejemplo o paradigma: >=

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 94 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Ejemplo (Componentes lexicos en el lenguaje C 7 / 7)

FIN SENTENCIA
Descripcion informal: signo de punto y coma para indicar el
fin de una sentencia
Descripcion formal: ;
Ejemplo o paradigma: ;

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 95 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Nota
Solo interesa saber el significado (Componente Lexico) que se
asocia a uno o mas signos, no como son dichos signos.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 96 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Descripcion de los componentes lexicos

Nota
Solo interesa saber el significado (Componente Lexico) que se
asocia a uno o mas signos, no como son dichos signos.

Ejemplo (Lenguaje Fortran)

La expresion regular para el componente lexico
MAYOR IGUAL QUE es: .(G+g)(E+e).

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 97 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

Descripcion de los componentes lexicos
Palabras y lenguajes formales
Expresiones Regulares

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 98 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Alfabeto o vocabulario)

Conjunto finito y no vaco de smbolos que permiten formar la
palabras pertenecientes a un lenguaje
Se suele denotar por o V
= {1 , 2 , , n }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 99 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplo
1 = {0, 1} (Alfabeto binario)
2 = {0, 1, 2, , 9}
3 = {a, b, c, , z}
4 = {if , else}
5 = {ab, ca, bbc}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 100 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Palabra o cadena)

Secuencia finita de smbolos pertenecientes a un alfabeto

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 101 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Palabra o cadena)

Secuencia finita de smbolos pertenecientes a un alfabeto

Ejemplo (Palabras definidas sobre)

1 = {0, 1}: 0, 1, 01, 1, 10, 010101, 100,...
3 = {a, b, c, , z}: aab, valor, punto,...
5 = {ab, ca, bbc}: ab, bbc, abab, abbbc,...

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 102 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Longitud de una palabra x)

Numero de smbolos de un alfabeto que componen dicha
palabra.
Se denota por |x|
Si = {1 , 2 , , n } y x = i1 i2 ik entonces |x| = k

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 103 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Nota
La longitud de una palabra depende del alfabeto sobre el que
este definida.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 104 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Nota
La longitud de una palabra depende del alfabeto sobre el que
este definida.

Ejemplo (Longitud de la palabra x = abab definida sobre)

3 = {a, b, c, , z}: |x| = 4
5 = {ab, ca, bbc}: |x| = 2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 105 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Lenguaje universal definido sobre )

Conjunto de palabras compuestas por cero o mas smbolos de
.
Se representa por .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 106 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplo (Palabras definidas sobre un alfabeto )

Si = {1 , 2 , , n } entonces se puede generar a partir
de las palabras de:
+ |x| = 0: palabra vaca que se denota por  o .
+ |x| = 1: x = 1 , x = 2 , , x = n
+ |x| = 2: x = 1 1 , x = 1 2 ,
+ Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 107 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplo (Palabras definidas sobre = {a, b, c})

|x| = 0: x = .
|x| = 1: x = a, x = b, x = c
|x| = 2: x = aa, x = ab, x = ac, x = ba, .
Etc.
En resumen, = {, a, b, c, aa, ab, ac, ba, }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 108 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Lenguajes formales)

L es un lenguaje formal definido sobre si L

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 109 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Lenguajes formales)

L es un lenguaje formal definido sobre si L

Ejemplo (Lenguajes formales definidos sobre )

L = .


L = {} donde
L = {}
+ = {x|x |x| 1}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 110 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Nota
L = {} =
6 L =
 + 

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 111 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplo (Lenguajes formales sobre = {a, b, c})

L =
L = {}
= {a, b, c}
= {, a, b, c, aa, ab, ac, }
La = {a}
L = {a, ab, abb, abbb, }

Nota
L puede ser denotado por la expresion regular ab

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 112 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Operaciones con palabras

Concatenacion
Potencia

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 113 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Concatenacion de palabras)

Sea = {1 , 2 , , n }
x = i1 i2 ip , y = j1 j2 jq
La concatenacion de x con y se denota por x y o
simplemente xy
xy = i1 i2 ip j1 j2 jq

Ejemplo (Concatenacion de palabras sobre = {a, b, c})

Si x = ab , y = bcc entonces xy = abbcc

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 114 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Concatenacion de palabras)

Sea = {1 , 2 , , n }
x = i1 i2 ip , y = j1 j2 jq
La concatenacion de x con y se denota por x y o
simplemente xy
xy = i1 i2 ip j1 j2 jq

Ejemplo (Concatenacion de palabras sobre = {a, b, c})

Si x = ab , y = bcc entonces xy = abbcc

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 115 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la concatenacion de palabras

Operacion cerrada sobre : si x, y entonces xy
|xy | = |x| + |y |
Asociativa: x(yz) = (xy )z = xyz
Existencia de elemento neutro: .
x = x = x
No conmutativa: xy 6= yx

Ejemplo (Si = {a, b, c})

Si x = ab , y = bcc entonces xy = abbcc 6= bccab = yx

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 116 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Potencia de una palabra)

Sea = {1 , 2 , , n }
x = i1 i2 ip
La potencia i-esima de x se denota por x i
x i = xx x}
| {z
i veces

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 117 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplo (Potencia una palabra definida sobre = {a, b, c})

Si x = abb entonces
x0 = 
x 1 = x = abb
x 2 = xx = abbabb
x 3 = xxx = abbabbabb
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 118 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Potencia de una palabra (version recursiva))

x0 = 
x i = x x i1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 119 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la potencia de una de palabra

Operacion cerrada sobre :
si x entonces i N, x i
|x i | = i|x|

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 120 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Operaciones con lenguajes formales

Union
Concatenacion
Potencia
Clausura o cierre de Kleene
Clausura positiva
Interseccion
Diferencia
Complementacion

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 121 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Union de lenguajes formales)

Si L1 , L2 entonces

L1 L2 = {x|x L1 x L2 }

Ejemplo
Si L1 = {ab, bc, bcc} y L2 = {a, bc, abb, ac}
entonces L1 L2 = {ab, bc, bcc, a, abb, ac}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 122 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Union de lenguajes formales)

Si L1 , L2 entonces

L1 L2 = {x|x L1 x L2 }

Ejemplo
Si L1 = {ab, bc, bcc} y L2 = {a, bc, abb, ac}
entonces L1 L2 = {ab, bc, bcc, a, abb, ac}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 123 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Union de lenguajes formales)

Si L1 , L2 entonces

L1 L2 = {x|x L1 x L2 }

Ejemplo
Si L1 = {ab, bc, bcc} y L2 = {a, bc, abb, ac}
entonces L1 L2 = {ab, bc, bcc, a, abb, ac}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 124 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la union de lenguajes

Operacion cerrada sobre :
si L1 , L2 entonces L1 L2
Asociativa: L1 (L2 L3 ) = (L1 L2 ) L3 = L1 L2 L3
Conmutativa: L1 L2 = L2 L1
Existencia de elemento neutro:
L=L=L
Idempotente: L L = L

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 125 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Concatenacion de lenguajes formales)

Si L1 , L2 entonces
L1 L2 = {x|x = yz y L1 z L2 }

Ejemplo
Si L1 = {ab, a, bb} y L2 = {bc, c, aa}
entonces L1 L2 = {abbc, abc, abaa, ac, aaa, bbbc, bbc, bbaa}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 126 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Concatenacion de lenguajes formales)

Si L1 , L2 entonces
L1 L2 = {x|x = yz y L1 z L2 }

Ejemplo
Si L1 = {ab, a, bb} y L2 = {bc, c, aa}
entonces L1 L2 = {abbc, abc, abaa, ac, aaa, bbbc, bbc, bbaa}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 127 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Concatenacion de lenguajes formales)

Si L1 , L2 entonces
L1 L2 = {x|x = yz y L1 z L2 }

Ejemplo
Si L1 = {ab, a, bb} y L2 = {bc, c, aa}
entonces L1 L2 = {abbc, abc, abaa, ac, aaa, bbbc, bbc, bbaa}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 128 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la concatenacion de lenguajes

Operacion cerrada sobre :
si L1 , L2 entonces L1 L2
Asociativa: L1 (L2 L3 ) = (L1 L2 )L3 = L1 L2 L3
Existencia de elemento neutro: L = {}
L{} = {}L = L
No conmutativa: L1 L2 6= L2 L1
Nota
La concatenacion lenguajes formales no es conmutativa porque la
concatenacion de palabras tampoco lo es

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 129 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la concatenacion de lenguajes

Operacion cerrada sobre :
si L1 , L2 entonces L1 L2
Asociativa: L1 (L2 L3 ) = (L1 L2 )L3 = L1 L2 L3
Existencia de elemento neutro: L = {}
L{} = {}L = L
No conmutativa: L1 L2 6= L2 L1
Nota
La concatenacion lenguajes formales no es conmutativa porque la
concatenacion de palabras tampoco lo es

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 130 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Potencia de un lenguaje formal)

Si L e i N entonces
Li = {x|x = xj1 xji xj1 , , xji L}

Ejemplo
L0 = {x 0 |x L} = {}
L1 = L
L2 = LL

Li = LLi1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 131 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Potencia de un lenguaje formal)

Si L e i N entonces
Li = {x|x = xj1 xji xj1 , , xji L}

Ejemplo
L0 = {x 0 |x L} = {}
L1 = L
L2 = LL

Li = LLi1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 132 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la potencia de un lenguaje formal

Operacion cerrada sobre :
si L entonces i N Li

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 133 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Clausura de Kleene de un lenguaje formal)

Si L entonces
L = i 0 1 2
S
i=0 L = L L L

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 134 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplo
Si L = {a} entonces

[

L = Li
i=0
= L L1 L2
0

= {} {a} {aa}

= {, a, aa, }

L = {a} puede ser denotado por la expresion regular a

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 135 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la clausura de un lenguaje formal

Operacion cerrada sobre :
si L entonces L

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 136 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Clausura positiva de un lenguaje formal)

Si L entonces
L+ = i 1 2
S
i=1 L = L L

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 137 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la clausura positiva de un lenguaje formal

Operacion cerrada sobre :
si L entonces L+

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 138 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplos (Operaciones con lenguajes formales)

Si L1 = {a} y L2 = {b} entonces

L3 = L1 L2 = {ab}
L4 = L2 L1 = {ba}
L5 = L3 L4 = {ab, ba}

[
L6 = L5 = Li5 = L05 L15 L25
i=0
= {} {ab, ba} {abab, abba, baab, baba}
= {, ab, ba, abab, abba, baab, baba, }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 139 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Interseccion de lenguajes formales)

Si L1 , L2 entonces

L1 L2 = {x|x L1 x L2 }

Ejemplo
Si L1 = {ab, bc, bcc} y L2 = {a, bc, abb, ac}
entonces L1 L2 = {bc}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 140 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Interseccion de lenguajes formales)

Si L1 , L2 entonces

L1 L2 = {x|x L1 x L2 }

Ejemplo
Si L1 = {ab, bc, bcc} y L2 = {a, bc, abb, ac}
entonces L1 L2 = {bc}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 141 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Interseccion de lenguajes formales)

Si L1 , L2 entonces

L1 L2 = {x|x L1 x L2 }

Ejemplo
Si L1 = {ab, bc, bcc} y L2 = {a, bc, abb, ac}
entonces L1 L2 = {bc}

Nota
No hay palabras o cadenas repetidas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 142 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la interseccion de lenguajes

Operacion cerrada sobre :
si L1 , L2 entonces L1 L2
Asociativa: L1 (L2 L3 ) = (L1 L2 ) L3 = L1 L2 L3
Conmutativa: L1 L2 = L2 L1
Existencia de elemento neutro:
L = L = L
Idempotente: L L = L

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 143 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Diferencia de lenguajes formales)

Si L1 , L2 entonces

L1 L2 = {x|x L1 x 6 L2 }

Ejemplo
Si L1 = {ab, bc, bcc} y L2 = {a, bc, abb, ac}
entonces L1 L2 = {ab, bcc}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 144 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Diferencia de lenguajes formales)

Si L1 , L2 entonces

L1 L2 = {x|x L1 x 6 L2 }

Ejemplo
Si L1 = {ab, bc, bcc} y L2 = {a, bc, abb, ac}
entonces L1 L2 = {ab, bcc}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 145 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la diferencia de lenguajes

Operacion cerrada sobre :
si L1 , L2 entonces L1 L2
No asociativa: (L1 L2) L3 6= L1 (L2 L3 )
No conmutativa: L1 L2 6= L2 L1
No existencia de elemento neutro
No idempotente: L L =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 146 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Definicion (Complementacion de un lenguaje formal)

Si L entonces

L = L = {x|x x 6 L}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 147 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplo
Si = {a, b}
Si L = {, a, ab, abb, abbb, . . .}
entonces L = {b, aa, ba, bb, aaa, aab, . . .}

Ejemplo
=
=

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 148 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Ejemplo
Si = {a, b}
Si L = {, a, ab, abb, abbb, . . .}
entonces L = {b, aa, ba, bb, aaa, aab, . . .}

Ejemplo
=
=

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 149 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Palabras y lenguajes formales

Propiedades de la complementacion de lenguajes

Operacion cerrada sobre :
si L entonces L
Doble complementacion L = L

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 150 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

Descripcion de los componentes lexicos
Palabras y lenguajes formales
Expresiones Regulares

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 151 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Definicion (Expresion regular)

Expresiones regulares sobre = {1 , 2 , , n }:
1 es una expresion regular
2  es una expresion regular
3 Si entonces es una expresion regular
4 Si y son expresiones regulares entonces tambien son:
a) +
b)
c) () P (o ())

d) = i=0 i = 0 + 1 + 2 +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 152 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Notas
La palabra vaca se puede representar por  o
La alternativa se puede representar por + o por |
El punto de la concatenacion se suele omitir

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 153 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplos (Expresiones regulares sobre = {0, 1})

, , 0, 1
0 + ,  + 0, 0, 0
1 + ,  + 1, 1, 1
0 + 0, 0 + 1, 1 + 0, 1 + 1
00, 01, 10, 11
0 , 1
(0 + 1), (0 + 1) , 0 (0 + 1)1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 154 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Prioridad de los operadores de las expresiones regulares

+ Maxima prioridad ( )
*

- Mnima prioridad +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 155 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Definicion (Lenguaje denotado por una expresion regular)

1 L() =
2 L() = {}
3 Si entonces L() = {}
4 Si y son expresiones regulares sobre
a) L( + ) = L() L()
b) L( ) = L() L()
c) L(()) = L()
P S S
d) L( ) = L( i=0 i ) = i=0 L(i ) = i=0 (L())i

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 156 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplos (Lenguajes denotados 1 / 5)

Dado = {0, 1}
L(0) = {0}
L(0 + 1) = L(0) L(1) = {0} {1} = {0, 1}
L(01) = L(0)L(1) = {0}{1} = {01}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 157 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Lenguaje denotado 2 / 5)

P S
L(1 ) = L( i
i=0 1 ) = i
i=0 L(1 )
S i
S i
= i=0 (L(1)) = i=0 {1}

= {, 1, 11, 111, }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 158 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Lenguaje denotado 2 / 5)

P S
L(1 ) = L( i
i=0 1 ) = i
i=0 L(1 )
S i
S i
= i=0 (L(1)) = i=0 {1}

= {, 1, 11, 111, }

Palabras compuestas por cero o mas unos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 159 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Lenguaje denotado 3 / 5)

L((0 + 1)1 ) = L((0 + 1))L(1 )

= L(0 + 1)L(1 )
= {0, 1}{, 1, 11, 111, }
= {0, 01, 011, 0111, , 1, 11, 111, }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 160 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Lenguaje denotado 3 / 5)

L((0 + 1)1 ) = L((0 + 1))L(1 )

= L(0 + 1)L(1 )
= {0, 1}{, 1, 11, 111, }
= {0, 01, 011, 0111, , 1, 11, 111, }

Palabras que comienza por cero o por uno y van seguidas por cero
o mas unos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 161 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Lenguaje denotado 4 / 5)

L(0 (11)0 ) = L(0 )L((11))L(0 )

= {, 0, 00, 000, }{11}{, 0, 00, 000, }
= {11, 011, 0011, 00011, }{, 0, 00, 000, }
= {11, 0110, 00110, 00110, 001100, }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 162 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Lenguaje denotado 4 / 5)

L(0 (11)0 ) = L(0 )L((11))L(0 )

= {, 0, 00, 000, }{11}{, 0, 00, 000, }
= {11, 011, 0011, 00011, }{, 0, 00, 000, }
= {11, 0110, 00110, 00110, 001100, }

Palabras que contienen a la cadena 11 y comienzan y terminan por

una secuencia de ceros, posiblemente nula

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 163 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Lenguaje denotado 5 / 5)

Dado = {a, b, c, , z}

L(a + b + c + + z) = L(a) L(b) L(c) L(z)

= {a} {b} {c} {z}
= {a, b, c, , z}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 164 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Definicion (Definicion regular)

Identificador que se asocia a una expresion regular
Puede ser utilizado para definir nuevas expresiones regulares

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 165 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplos
letra = (a + b + c + + z)
cifra = (0 + 1 + + 9)
guion =
subrayado =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 166 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplos (Identificadores de lenguajes de programacion)

Pascal:
letra (letra + cifra)

C:
(subrayado + letra) (subrayado + letra + cifra)

Cobol:
letra (letra + cifra + guion (letra + cifra))

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 167 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplos (Numeros en el Lenguaje C)

numero = parte entera ( + parte decimal)
donde
parte entera = cifra cifra
parte decimal
= punto cifra ( + (E + e)( + + + )cifra cifra )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 168 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Nota (Abreviaturas)
? = +  =  +
+ = =

Ejemplo (Numeros en el Lenguaje C)

numero = parte entera parte decimal?

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 169 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Nota (Abreviaturas)
? = +  =  +
+ = =

Ejemplo (Numeros en el Lenguaje C)

numero = parte entera parte decimal?

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 170 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Nota
Palabras claves: existe una expresion regular para cada palabra
clave.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 171 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en C 1/3)

COMPONENTE LEXICO: IF
Expresion regular: if
Paradigma: if

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 172 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en C 2/3)

COMPONENTE LEXICO: WHILE
Expresion regular: while
Paradigma: while

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 173 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en C 3/3)

COMPONENTE LEXICO: FOR
Expresion regular: for
Paradigma: for

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 174 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en FORTRAN 1/3)

COMPONENTE LEXICO: DO
Expresion regular: (D+d)(O+o)
Paradigma: DO, Do, dO, do

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 175 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en FORTRAN 2/3)

COMPONENTE LEXICO: FORMAT
Expresion regular: (F+f)(O+o)(R+r)(M+m)(A+a)(T+t)
Paradigma: FORMAT, . . . , Format, . . . , format

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 176 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en FORTRAN 3/3)

COMPONENTE LEXICO: REAL
Expresion regular: (R+r)(E+e)(A+a)(L+l)
Paradigma: REAL, . . . , Real, . . . real

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 177 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en Pascal 1/3)

COMPONENTE LEXICO: INTEGER
Expresion regular:
(I+i)(N+n)(T+t)(E+e)(G+g)(E+e)(R+r)
Paradigma: INTEGER, . . . , Integer, . . . , integer

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 178 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en Pascal 2/3)

COMPONENTE LEXICO: THEN
Expresion regular: (T+t)(H+h)(E+e)(N+n)
Paradigma: THEN, . . . , Then, . . . , then

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 179 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Palabras claves en Pascal 3/3)

COMPONENTE LEXICO: VAR
Expresion regular: (V+v)(A+a)(R+r)
Paradigma: VAR, . . . , Var, . . . , var

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 180 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores aritmeticos en C)

COMPONENTE LEXICO Expresion regular Paradigma
SUMA + +
RESTA - -
MULTIPLICACION * *
DIVISION / /
RESTO DIVISION ENTERA % %

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 181 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores aritmeticos en FORTRAN)

COMPONENTE LEXICO Expresion regular Paradigma
SUMA + +
RESTA - -
MULTIPLICACION * *
DIVISION / /
POTENCIA ** **

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 182 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores aritmeticos en PASCAL)

COMPONENTE LEXICO Expresion regular Paradigma
SUMA + +
RESTA - -
MULTIPLICACION * *
DIVISION / /
RESTO DIVISION ENTERA mod mod
COCIENTE DIVISION ENTERA div div

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 183 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores relacionales en C)

COMPONENTE LEXICO Expresion regular Paradigma
MENOR QUE < <
MENOR IGUAL QUE <= <=
MAYOR QUE > >
MAYOR IGUAL QUE >= >=
IGUAL == ==
DISTINTO != !=

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 184 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores relacionales en FORTRAN)

COMPONENTE LEXICO Expresion regular Paradigma
MENOR QUE .(L+l)(T+t). .LT., . . . .lt.
MENOR IGUAL QUE .(L+l)(E+e). .LE., . . . .le.
MAYOR QUE .(G+g)(T+t). .GT., . . . .gt.
MAYOR IGUAL QUE .(G+g)(E+e). .GE., . . . .ge.
IGUAL .(E+e)(Q+q). .EQ., . . . .eq.
DISTINTO .(N+n)(E+e). .NE., . . . .ne.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 185 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores relacionales en Pascal)

COMPONENTE LEXICO Expresion regular Paradigma
MENOR QUE < <
MENOR IGUAL QUE <= <=
MAYOR QUE > >
MAYOR IGUAL QUE >= >=
IGUAL = =
DISTINTO <> <>

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 186 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores logicos en C)

COMPONENTE LEXICO Expresion regular Paradigma
NEGACION LOGICA ! !
CONJUNCION LOGICA && &&
DISYUNCION LOGICA || ||

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 187 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores logicos en FORTRAN)

COMPONENTE LEXICO Expresion regular Paradigma
NEGACION LOGICA .(N+n)(O+o)(T+t). .NOT, . . . .not.
CONJUNCION LOGICA .(A+a)(N+n)(D+d). .AND.,. . . .and.
DISYUNCION LOGICA .(O+o)(R+r). .OR., . . . .or.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 188 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo (Operadores logicos en PASCAL)

COMPONENTE LEXICO Expresion regular Paradigma
NEGACION LOGICA (N+n)(O+o)(T+t) NOT, . . . not
CONJUNCION LOGICA (A+a)(N+n)(D+d) AND, . . . and
DISYUNCION LOGICA (O+o)(R+r) OR, . . . or

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 189 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Nota
El analizador sintactico solo necesita saber cual es el
componente lexico reconocido

No necesita saber como es dicho componente lexico.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 190 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Definicion (Equivalencia de expresiones regulares)

y son equivalentes si y solo si denotan el mismo lenguaje:
L() = L()
L() = L()

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 191 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Ejemplo
Se verifica que
aa a a
porque
L(aa ) = L(a)L(a )
= {a}{, a, aa, }
= {a, aa, aaa, }
= {, a, aa, }{a}
= L(a )L(a)
= L(a a)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 192 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

1.- Disyuncion idempotente: + =
2.- Disyuncion asociativa: + ( + ) = ( + ) +
3.- Disyuncion conmutativa: + = +
4.- Concatenacion asociativa: ( ) = ( )
5.- Concatenacion no conmutativa: 6=
6.- Distributiva: ( + ) = +
7.- Elemento neutro de la disyuncion: + = + =
8.- Elemento neutro de la concatenacion:  =  =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 193 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

1.- Disyuncion idempotente: + =
2.- Disyuncion asociativa: + ( + ) = ( + ) +
3.- Disyuncion conmutativa: + = +
4.- Concatenacion asociativa: ( ) = ( )
5.- Concatenacion no conmutativa: 6=
6.- Distributiva: ( + ) = +
7.- Elemento neutro de la disyuncion: + = + =
8.- Elemento neutro de la concatenacion:  =  =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 194 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

1.- Disyuncion idempotente: + =
2.- Disyuncion asociativa: + ( + ) = ( + ) +
3.- Disyuncion conmutativa: + = +
4.- Concatenacion asociativa: ( ) = ( )
5.- Concatenacion no conmutativa: 6=
6.- Distributiva: ( + ) = +
7.- Elemento neutro de la disyuncion: + = + =
8.- Elemento neutro de la concatenacion:  =  =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 195 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

1.- Disyuncion idempotente: + =
2.- Disyuncion asociativa: + ( + ) = ( + ) +
3.- Disyuncion conmutativa: + = +
4.- Concatenacion asociativa: ( ) = ( )
5.- Concatenacion no conmutativa: 6=
6.- Distributiva: ( + ) = +
7.- Elemento neutro de la disyuncion: + = + =
8.- Elemento neutro de la concatenacion:  =  =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 196 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

1.- Disyuncion idempotente: + =
2.- Disyuncion asociativa: + ( + ) = ( + ) +
3.- Disyuncion conmutativa: + = +
4.- Concatenacion asociativa: ( ) = ( )
5.- Concatenacion no conmutativa: 6=
6.- Distributiva: ( + ) = +
7.- Elemento neutro de la disyuncion: + = + =
8.- Elemento neutro de la concatenacion:  =  =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 197 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

1.- Disyuncion idempotente: + =
2.- Disyuncion asociativa: + ( + ) = ( + ) +
3.- Disyuncion conmutativa: + = +
4.- Concatenacion asociativa: ( ) = ( )
5.- Concatenacion no conmutativa: 6=
6.- Distributiva: ( + ) = +
7.- Elemento neutro de la disyuncion: + = + =
8.- Elemento neutro de la concatenacion:  =  =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 198 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

1.- Disyuncion idempotente: + =
2.- Disyuncion asociativa: + ( + ) = ( + ) +
3.- Disyuncion conmutativa: + = +
4.- Concatenacion asociativa: ( ) = ( )
5.- Concatenacion no conmutativa: 6=
6.- Distributiva: ( + ) = +
7.- Elemento neutro de la disyuncion: + = + =
8.- Elemento neutro de la concatenacion:  =  =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 199 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

1.- Disyuncion idempotente: + =
2.- Disyuncion asociativa: + ( + ) = ( + ) +
3.- Disyuncion conmutativa: + = +
4.- Concatenacion asociativa: ( ) = ( )
5.- Concatenacion no conmutativa: 6=
6.- Distributiva: ( + ) = +
7.- Elemento neutro de la disyuncion: + = + =
8.- Elemento neutro de la concatenacion:  =  =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 200 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

9.- = =
10.-  = 
11.- = 
12.- =
13.- = = +
14.- ( ) =
15.- =  +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 201 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

9.- = =
10.-  = 
11.- = 
12.- =
13.- = = +
14.- ( ) =
15.- =  +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 202 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

9.- = =
10.-  = 
11.- = 
12.- =
13.- = = +
14.- ( ) =
15.- =  +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 203 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

9.- = =
10.-  = 
11.- = 

L( ) = (L())
S i
= ()
= i=0 = 0 1 2
= {}
= {} = L()

12.- =
13.- = = +
14.- ( ) =
15.- =  +
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 204 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

9.- = =
10.-  = 
11.- = 
12.- =
13.- = = +
14.- ( ) =
15.- =  +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 205 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

9.- = =
10.-  = 
11.- = 
12.- =
13.- = = +
14.- ( ) =
15.- =  +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 206 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

9.- = =
10.-  = 
11.- = 
12.- =
13.- = = +
14.- ( ) =
15.- =  +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 207 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Propiedades de las expresiones regulares

9.- = =
10.-  = 
11.- = 
12.- =
13.- = = +
14.- ( ) =
15.- =  +

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 208 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Capacidad de las expresiones regulares

Denotan los componentes lexicos
Pueden denotar
+ Un numero fijo de repeticiones: aaaaa
+ Un numero arbitrario de repeticiones: a
+ Repeticiones no coordinadas

Ejemplo
L1 = {ai b j |i, j 0}
= {, a, aa, aaa, b, ab, aab, }
= {, a, aa, aaa, }{, b, bb, bbb}
= L(a b )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 209 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Capacidad de las expresiones regulares

Denotan los componentes lexicos
Pueden denotar
+ Un numero fijo de repeticiones: aaaaa
+ Un numero arbitrario de repeticiones: a
+ Repeticiones no coordinadas

Ejemplo
L1 = {ai b j |i, j 0}
= {, a, aa, aaa, b, ab, aab, }
= {, a, aa, aaa, }{, b, bb, bbb}
= L(a b )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 210 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Nota (Limitaciones de las expresiones regulares)

No pueden denotar caractersticas sintacticas
No pueden denotar repeticiones coordinadas

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 211 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Nota (Limitaciones de las expresiones regulares)

No pueden denotar caractersticas sintacticas
No pueden denotar repeticiones coordinadas

Ejemplo
Lenguaje que no puede ser denotado por una expresion regular

L2 = {ai b i |i 0} = {, ab, aabb, aaabbb, }

L2 no es un lenguaje regular.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 212 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Especificacion de componentes lexicos

Expresiones Regulares

Nota (Limitaciones de las expresiones regulares)

No pueden denotar caractersticas sintacticas
No pueden denotar repeticiones coordinadas

Ejemplo
L2 = {ai b i |i 0} representa a muchas estructuras sintacticas
de los lenguajes de programacion:
+ Balanceo de parentesis, llaves o corchetes.
+ Paso de parametros
+ Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 213 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido del tema

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 214 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

Automatas finitos
Automatas finitos deterministas: AFD
Automatas finitos NO deterministas: AFN
Minimizacion de automatas finitos deterministas

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 215 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

COMPONENTES LEXICOS

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 216 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

COMPONENTES LEXICOS

EXPRESIONES REGULARES

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 217 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

COMPONENTES LEXICOS

EXPRESIONES REGULARES

AFN

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 218 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

COMPONENTES LEXICOS

EXPRESIONES REGULARES

AFN

AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 219 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

COMPONENTES LEXICOS

EXPRESIONES REGULARES

AFN

AFD

ANALIZADOR LEXICO

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 220 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

COMPONENTES LEXICOS

EXPRESIONES REGULARES

AFN
LEX
AFD

ANALIZADOR LEXICO

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 221 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

Expresiones regulares: denotan componentes lexicos.

Automatas finitos: reconocen componentes lexicos:
+ Automata finito no determinista: AFN
+ Automata finito determinista: AFD
Generacion de automatas finitos a partir de expresiones
regulares:
Paso 1.- Algoritmo de Thompson: genera un AFN a partir de una
expresion regular
Paso 2.- Algoritmo de Construccion de subconjuntos: genera un AFD
a partir de un AFN.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 222 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

Expresiones regulares: denotan componentes lexicos.

Automatas finitos: reconocen componentes lexicos:
+ Automata finito no determinista: AFN
+ Automata finito determinista: AFD
Generacion de automatas finitos a partir de expresiones
regulares:
Paso 1.- Algoritmo de Thompson: genera un AFN a partir de una
expresion regular
Paso 2.- Algoritmo de Construccion de subconjuntos: genera un AFD
a partir de un AFN.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 223 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos

Expresiones regulares: denotan componentes lexicos.

Automatas finitos: reconocen componentes lexicos:
+ Automata finito no determinista: AFN
+ Automata finito determinista: AFD
Generacion de automatas finitos a partir de expresiones
regulares:
Paso 1.- Algoritmo de Thompson: genera un AFN a partir de una
expresion regular
Paso 2.- Algoritmo de Construccion de subconjuntos: genera un AFD
a partir de un AFN.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 224 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

Automatas finitos
Automatas finitos deterministas: AFD
Automatas finitos NO deterministas: AFN
Minimizacion de automatas finitos deterministas

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 225 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Descripcion general
Definicion formal
Funcion de transicion para palabras
Representacion grafica
Lenguaje reconocido por un AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 226 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Descripcion general
Definicion formal
Funcion de transicion para palabras
Representacion grafica
Lenguaje reconocido por un AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 227 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Definicion (Automata finito determinista: AFD)

Dispositivo formal que permite reconocer si una palabra
pertenece o no a un lenguaje regular.
Tambien se denomina maquina reconocedora o aceptadora

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 228 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Componentes de un AFD
Cinta de lectura:
+ Dividida en celdas.
+ Infinita hacia la derecha.
Cabeza de lectura:
+ Lee el smbolo actual de la cinta.
+ Solo se puede mover hacia la derecha.
Alfabeto de la cinta
Unidad de control de estados: indica el estado actual.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 229 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Sentido de recorrido

... Cinta

Cabeza de lectura

q
i

Unidad de control de estados

Componentes basicos de un automata finito determinista.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 230 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Pasos del AFD para reconocer a x = i1 . . . ij ij+1 . . . ik

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 231 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Pasos del AFD para reconocer a x = i1 . . . ij ij+1 . . . ik

... i j i j+1 ... i k ...

i1

q
0

Configuracion inicial

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 232 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Pasos del AFD para reconocer a x = i1 . . . ij ij+1 . . . ik

... i j i j+1 ... i k ...

i1

Transicion: situacion anterior

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 233 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Pasos del AFD para reconocer a x = i1 . . . ij ij+1 . . . ik

... i j i j+1 ... i k ...

i1

Transicion: situacion posterior

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 234 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Pasos del AFD para reconocer a x = i1 . . . ij ij+1 . . . ik

... i j i j+1 ... i k ...

i1

q
f

Configuracion final

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 235 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Descripcion general
Definicion formal
Funcion de transicion para palabras
Representacion grafica
Lenguaje reconocido por un AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 236 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Definicion (Automata finito determinista)

A = (Q, , , q0 , F )
donde
Q: conjunto finito de estados
: alfabeto de smbolos de entrada
: funcion de transicion entre estados:
: Q Q
(q, ) = q 0

q0 Q: estado inicial
F Q: conjunto de estados finales
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 237 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (AFD que reconoce identificadores de COBOL)

l d g
q0 q1 q3 q3
q1 q1 q1 q2
q2 q1 q1 q3
q3 q3 q3 q3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 238 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (AFD que reconoce identificadores de COBOL)

Los componentes del automata son:
Q = {q0 , q1 , q2 , q3 }
F = {q1 }
El smbolo indica el estado inicial.
El smbolo indica los estados finales.
= {l, d, g } donde: l = letra, d = dgito y g = guion.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 239 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Descripcion general
Definicion formal
Funcion de transicion para palabras
Representacion grafica
Lenguaje reconocido por un AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 240 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Definicion (Funcion de transicion para palabras)

: Q Q

(q, ) = qQ
(q, x) = ((q, x), ) Q x

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 241 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Notas
y coinciden sobre smbolos de :

(q, ) = (q,  ) = ((q, ), ) = (q, )

(q, xy ) = ((q, x), y ) x, y

(q, x) = ((q, ), x) = ((q, ), x)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 242 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo

(q0 , x) = (q0 , llgd) = ((q0 , l), lgd)

= (q1 , lgd) = ((q1 , l), gd)
= (q1 , gd) = ((q1 , g ), d)
= (q2 , d) = (q2 , d)
= q1 F

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 243 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Nota
x = llgd es reconocida por el AFD porque q1 es un estado final.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 244 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Nota
Existe una notacion mas simple para el reconocimiento de un
AFD.

Ejemplo

(q0 , llgd) ` (q1 , lgd)

` (q1 , g d)
` (q2 , d)
` (q1 , )

o simplemente (q0 , llgd) ` (q1 , )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 245 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Nota
Existe una notacion mas simple para el reconocimiento de un
AFD.

Ejemplo

(q0 , llgd) ` (q1 , lgd)

` (q1 , g d)
` (q2 , d)
` (q1 , )

o simplemente (q0 , llgd) ` (q1 , )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 246 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Nota
Existe una notacion mas simple para el reconocimiento de un
AFD.

Ejemplo

(q0 , llgd) ` (q1 , lgd)

` (q1 , g d)
` (q2 , d)
` (q1 , )

o simplemente (q0 , llgd) ` (q1 , )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 247 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Descripcion general
Definicion formal
Representacion grafica
Lenguaje reconocido por un AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 248 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Definicion (Representacion grafica de un AFD)

Grafo dirigido:
Numero de nodos = cardinal(Q).
Etiqueta de cada nodo Q.
q0
Estado inicial:
q q
f f
Estados finales:

q q
Si (q, ) = q 0 entonces
Se agrupan las aristas que enlazan los mismos estados.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 249 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (AFD que reconoce identificadores de COBOL)

l, d
g
l
q q q
0 1 2
l,d

d, g
q g
3

l, d, g

Representacion grafica de un AFD.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 250 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Descripcion general
Definicion formal
Representacion grafica
Lenguaje reconocido por un AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 251 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Definicion (Lenguaje reconocido por un AFD)

L(A) = {x|x (q0 , x) F }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 252 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Notas
Si F = Q entonces L(A) =
Si F = entonces L(A) =
q0 F si y solo si  L(A)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 253 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo
L(A) = L(l(l + d + g (l + d)) )

Lenguaje reconocido por un AFD que reconoce identificadores de

COBOL

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 254 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (Lenguaje reconocido por un AFD)

Funcion de transicion
a b

q0 q0 q1

q1 q2 q1
q2 q2 q2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 255 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (Lenguaje reconocido por un AFD)

Los componentes del automata son:
Q = {q0 , q1 , q2 }
F = {q0 , q1 }
= {a, b, c}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 256 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (Lenguaje reconocido por un AFD)

b a
q q q
0 1 2

a b a, b
aa b bb
L(A) = L(a b )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 257 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Nota
El estado q2 es inutil o superfluo

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 258 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (Lenguaje reconocido por un AFD)

(q0 , aabb) = ((q0 , a), abb)

= ((q0 , a), bb)
= ((q0 , b), b)
= (q1 , b)
= (q1 , b)
= q1 F

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 259 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (Lenguaje reconocido por un AFD)

(q0 , aabb) ` (q0 , abb)

` (q0 , bb)
` (q1 , b)
` (q1 , )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 260 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (AFD que reconoce identificadores de C)

Funcion de transicion
letra subrayado dgito
q0 q1 q1 q2
q1 q1 q1 q1
q2 q2 q2 q2

Nota
El estado q2 es superfluo

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 261 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (AFD que reconoce identificadores de C)

letra, dgito, subrayado
letra, subrayado
q q
0 1

dgito

q letra, dgito, subrayado

2

L(A) = L((letra + subrayado)(letra + subrayado + dgito) )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 262 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos deterministas: AFD

Ejemplo (AFD que reconoce cadenas de caracteres)

\y"

" " q
q q
0 1 2

q q
3 b

L(A) = L((letra + )(BARRA + letra + ) )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 263 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

Automatas finitos
Automatas finitos deterministas: AFD
Automatas finitos NO deterministas: AFN
Minimizacion de automatas finitos deterministas

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 264 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Descripcion general
Definicion formal
Representacion grafica
Funcion de transicion para palabras
Lenguaje reconocido por un AFN
Equivalencia entre AFN y AFD
Equivalencia entre expresiones regulares y automatas finitos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 265 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Descripcion general
Definicion formal
Representacion grafica
Funcion de transicion para palabras
Lenguaje reconocido por un AFN
Equivalencia entre AFN y AFD
Equivalencia entre expresiones regulares y automatas finitos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 266 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Automata finito NO determinista: AFN)

Un automota finito es no determinista si posee alguna de las
siguientes transiciones:
Transicion : no lee el smbolo actual pero cambia de estado
Transicion multiple: puede cambiar a mas de un estado.
Estos tipos de transiciones no son excluyentes.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 267 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Descripcion general
Definicion formal
Representacion grafica
Funcion de transicion para palabras
Lenguaje reconocido por un AFN
Equivalencia entre AFN y AFD
Equivalencia entre expresiones regulares y automatas finitos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 268 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Automata finito NO determinista: AFN)

A = (Q, , , q0 , F )
Q: conjunto finito de estados
: alfabeto de smbolos de entrada
: funcion de transicion entre estados:
: Q ( {}) P(Q)
(q, ) Q
(q, ) Q
q0 Q: estado inicial
F Q: conjunto de estados finales
P(Q): conjunto de las partes de Q

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 269 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Transicion () trivial)

q (q, ) q Q

Nota
Las transiciones triviales siempre existen y se suponen tacitamente
por defecto.

Definicion (Transicion () no trivial)

q 0 (q, ) q 6= q 0

Nota
Si existen, estas transiciones se han de indicar expresamente.
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 270 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Transicion () trivial)

q (q, ) q Q

Nota
Las transiciones triviales siempre existen y se suponen tacitamente
por defecto.

Definicion (Transicion () no trivial)

q 0 (q, ) q 6= q 0

Nota
Si existen, estas transiciones se han de indicar expresamente.
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 271 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Transicion () trivial)

q (q, ) q Q

Nota
Las transiciones triviales siempre existen y se suponen tacitamente
por defecto.

Definicion (Transicion () no trivial)

q 0 (q, ) q 6= q 0

Nota
Si existen, estas transiciones se han de indicar expresamente.
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 272 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Transicion () trivial)

q (q, ) q Q

Nota
Las transiciones triviales siempre existen y se suponen tacitamente
por defecto.

Definicion (Transicion () no trivial)

q 0 (q, ) q 6= q 0

Nota
Si existen, estas transiciones se han de indicar expresamente.
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 273 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo
a b 
q0 {q1 } {q0 , q1 }
q1 {q3 , q4 } {q1 , q2 }
q2 {q5 } {q2 }
q3 {q2 } {q3 }
q4 {q4 , q5 } {q2 , q4 }
q5 {q5 } {q3 , q5 }

Las transiciones triviales se pueden omitir.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 274 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Nota
Un AFD puede considerarse un caso especial de AFN:
No existen transiciones- no triviales.
y no existen transiciones multiples, es decir,

(q, ) = {q 0 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 275 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Descripcion general
Definicion formal
Representacion grafica
Funcion de transicion para palabras
Lenguaje reconocido por un AFN
Equivalencia entre AFN y AFD
Equivalencia entre expresiones regulares y automatas finitos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 276 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (AFN: representacion grafica)

Numero de nodos del grafo = cardinal(Q).
Etiqueta de cada nodo Q.
q0
Estado inicial:
q q
f f
Estados finales:

q q
Si q0 (q, ) entonces

q q
Si q0 (q, ) entonces
Las aristas de las transiciones- triviales se pueden omitir.
Se agrupan las aristas que enlazan los mismos estados.
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 277 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo

q
3

b
a

a, b b,
q q q q5
0 1 2

a
b

q
4
a,

AFN con transiciones triviales

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 278 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo
q
3
b
a

a, b b
q q q q5
0 1 2

a
b

q
4
a

AFN sin transiciones triviales

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 279 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Descripcion general
Definicion formal
Representacion grafica
Funcion de transicion para palabras
Lenguaje reconocido por un AFN
Equivalencia entre AFN y AFD
Equivalencia entre expresiones regulares y automatas finitos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 280 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Funcion de transicion para palabras en un AFN:

+ Clausura -  aplicada a estados
+ Clausura -  aplicada a conjuntos de estados
+ Funcion de transicion para palabras:

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 281 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Clausura -  aplicada a estados)

clausura  : Q P(Q)

Si q Q
+ q clausura (q)
+ Si q 0 clausura (q) q 00 (q 0 , )
entonces q 00 clausura (q)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 282 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Clausura -  aplicada a estados)

Segunda version

clausura  : Q P(Q)

clausura (q) = {q 0 |q 0 Q un camino de q a q

con las aristas etiquetadas con }

Nota
Siempre se verifica que q clausura (q)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 283 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplos (Clausura- de los estados del AFD anterior)

clausura (q0 ) = {q0 , q1 , q2 }

clausura (q1 ) = {q1 , q2 }
clausura (q2 ) = {q2 }
clausura (q3 ) = {q3 }
clausura (q4 ) = {q2 , q4 }
clausura (q5 ) = {q3 , q5 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 284 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Clausura -  aplicada a conjuntos de estados)

clausura  : P(Q) P(Q)

Si P Q
+ P clausura (P)
+ Si q 0 clausura (P) q 00 (q 0 , )
entonces q 00 clausura (P)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 285 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Clausura -  aplicada a conjuntos de estados)

Segunda version
Si P Q entonces
[
clausura (P) = clausura (q)
qP

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 286 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Clausura- de un conjunto de estados)

[
clausura ({q1 , q3 }) = clausura (q)
q{q1 ,q3 }
= clausura (q1 ) clausura (q3 )
= {q1 , q2 } {q3 }
= {q1 , q2 , q3 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 287 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Clausura- de un conjunto de estados)

[
clausura ({q0 , q5 }) = clausura (q)
q{q0 ,q5 }
= clausura (q0 ) clausura (q5 )
= {q0 , q1 , q2 } {q3 , q5 }
= {q0 , q1 , q2 , q3 , q5 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 288 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Funcion de transicion para palabras)

: Q P(Q)

(q, ) = clausura (q) !

(q 0 , )
S
(q, x) = clausura 
q 0 (q,x)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 289 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Funcion de transicion para palabras)

En particular
!
(q 0 , )
S
+ (q, ) = clausura 
q 0 (q,) !
(q 0 , )
S
= clausura 
q 0 clausura(q)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 290 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Reconocimiento de una palabra: 1 / 8)

(q0 , x) = (q0 , abb)

[
= clausura  (q 0 , b)
q 0 (q0 ,ab)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 291 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Reconocimiento de una palabra: 2 / 8)

[
(q0 , ab) = clausura  (q 0 , b)
q 0 (q0 ,a)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 292 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Reconocimiento de una palabra: 3 / 8)

[
(q0 , a) = clausura  (q 0 , a)
q 0 (q0 ,)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 293 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Reconocimiento de una palabra: 4 / 8)

(q0 , ) = clausura (q0 )

= {q0 , q1 , q2 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 294 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Reconocimiento de una palabra: 5 / 8)

Se sustituye (q0 , ) en (q0 , a):
!
0
S
(q0 , a) = clausura  (q , a)
q 0 (q0 ,)

!
0
S
= clausura  (q , a)
q 0 {q0 ,q1 ,q2 }

= clausura ((q0 , a) (q1 , a) (q2 , a))

= clausura ({q1 } )
= {q1 , q2 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 295 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Reconocimiento de una palabra: 6 / 8)

Se sustituye (q0 , a) en (q0 , ab): !
0
S
(q0 , ab) = clausura  (q , b)
q 0 (q0 ,a)

!
(q 0 , b)
S
= clausura 
q 0 {q1 ,q2 }
= clausura ((q1 , b) (q2 , b))
= clausura ({q3 , q4 } {q5 })
= clausura ({q3 , q4 , q5 })
= {q2 , q3 , q4 , q5 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 296 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Reconocimiento de una palabra: 7 / 8)

Por ultimo, se sustituye (q0 , ab) en (q0 , abb):
!
(q 0 , b)
S
(q0 , abb) = clausura 
q 0 (q0 ,ab)

!
(q 0 , b)
S
= clausura 
q 0 {q2 ,q3 ,q4 ,q5 }

= clausura ((q2 , b) (q3 , b) (q4 , b) (q5 , b))

= clausura ({q5 } {q5 })
= clausura ({q5 }) = {q3 , q5 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 297 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Reconocimiento de una palabra: 8 / 8)

x = abb L(A) porque

(q0 , abb) F = {q3 , q5 } F = {q5 } =

6

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 298 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Descripcion general
Definicion formal
Representacion grafica
Funcion de transicion para palabras
Lenguaje reconocido por un AFN
Equivalencia entre AFN y AFD
Equivalencia entre expresiones regulares y automatas finitos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 299 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Lenguaje reconocido por un AFN)

L(A) = {x|x (q0 , x) F 6= }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 300 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Descripcion general
Definicion formal
Representacion grafica
Funcion de transicion para palabras
Lenguaje reconocido por un AFN
Equivalencia entre AFN y AFD
Equivalencia entre expresiones regulares y automatas finitos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 301 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Necesidad de convertir AFN en AFD

Calcular (q0 , x) en un AFN es muy tedioso.
Se suele evitar el uso de AFN.
AFN y AFD tienen la misma capacidad de reconocimiento.
Paso de AFN a AFD: algoritmo de Construccion de
subconjuntos.
Se ha de extender la definicion de la funcion de transicion a
subconjuntos de Q.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 302 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Definicion (Extension de a subconjuntos de Q)

: P(Q) ( S
{}) P(Q)
(P, ) = (q, )
qP

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 303 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Aplicacion de a p Q)
Sea el AFN anterior y p = {q0 , q3 }:

(p, a) = ({q0 , q3 }, a)
[
= (q, a)
q{q0 ,q3 }
= (q0 , a) (q3 , a)
= {q1 } {q2 }
= {q1 , q2 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 304 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Teorema
Dado un AFN AN , se puede construir otro AFD AD equivalente:

L(AN ) = L(AD )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 305 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Demostracion
AFN

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 306 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Demostracion
AFN

Algoritmo de Construccion de subconjuntos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 307 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Demostracion
AFN

Algoritmo de Construccion de subconjuntos

AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 308 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Demostracion

Algoritmo (Construccion de subconjuntos)

Entrada: AN = (QN , , N , q0 , FN )
Salida: AD = (QD , , D , p0 , FD )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 309 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Algoritmo (Construccion de subconjuntos)

inicio
p0 clausura (q0 ) ; QD {p0 } y p0 no marcado
mientras haya un estado p QD no marcado hacer
Marcar a p
para cada hacer
p 0 clausura (N (p, ))
si p 0
/ QD entonces
QD QD {p 0 } y p 0 no marcado
fin si
Definir D (p, ) p 0
fin para
fin mientras
FD {pi |FN pi 6= }
fin
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 310 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo

q
3

b
a

a, b b,
q q q q5
0 1 2

a
b

q
4
a,

AFN con transiciones triviales

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 311 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo
q
3
b
a

a, b b
q q q q5
0 1 2

a
b

q
4
a

AFN sin transiciones triviales

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 312 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 0: Estado inicial del AFD:

p0 = clausura (q0 ) = {q0 , q1 , q2 }

QD = {p0 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 313 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

p
0

Paso 0: estado inicial p0

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 314 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 1: Transiciones de p0 = {q0 , q1 , q2 }

Se marca el estado p0 :
QD = {p 0 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 315 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 1: Transiciones de p0 = {q0 , q1 , q2 }
clausura (N (p0 , a)) =
[
= clausura ( N (q, a))
qp0
[
= clausura ( N (q, a))
q{q0 ,q1 ,q2 }

= clausura (N (q0 , a) N (q1 , a) N (q2 , a))

= clausura ({q1 } )
= clausura ({q1 }) = {q1 , q2 } = p1

Por tanto, D (p0 , a) = p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 316 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 1: Transiciones de p0 = {q0 , q1 , q2 }

Como p1
/ QD :

QD = QD {p1 } = {p 0 , p1 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 317 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 1: Transiciones de p0 = {q0 , q1 , q2 }
clausura (N (p0 , b)) =
[
= clausura ( N (q, b))
qp0
=
= clausura (N (q0 , b) N (q1 , b) N (q2 , b))
= clausura ( {q3 , q4 } {q5 })
= clausura ({q3 , q4 , q5 })
= {q2 , q3 , q4 , q5 } = p2

D (p0 , b) = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 318 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 1: Transiciones de p0 = {q0 , q1 , q2 }

Como p2
/ QD :

QD = QD {p2 } = {p 0 , p1 , p2 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 319 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

p
a 1

p
0

b
p
2

Paso 1: transiciones de p0

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 320 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 2: Transiciones de p1 = {q1 , q2 }

Se marca el estado p1 :

QD = {p 0 , p 1 , p2 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 321 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 2: Transiciones de p1 = {q1 , q2 }
[
clausura (N (p1 , a)) = clausura ( N (q, a))
qp1
=
= clausura (N (q1 , a) N (q2 , a))
= clausura ( )
= clausura () =

Por tanto, D (p1 , a) = , es decir, esta indefinida.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 322 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 2: Transiciones de p1 = {q1 , q2 }
[
clausura (N (p1 , b)) = clausura ( N (q, b))
qp1
=
= clausura (N (q1 , b) N (q2 , b))
= clausura ({q3 , q4 } {q5 })
= clausura ({q3 , q4 , q5 })
= {q2 , q3 , q4 , q5 } = p2

D (p1 , b) = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 323 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

p
a 1

p
0
b
b
p
2

Paso 2: transiciones de p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 324 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 3: Transiciones de p2 = {q2 , q3 , q4 , q5 }

Se marca el estado p2 :

QD = {p 0 , p 1 , p 2 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 325 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 3: Transiciones de p2 = {q2 , q3 , q4 , q5 }
[
clausura (N (p2 , a)) = clausura ( N (q, a))
qp2
[
= clausura ( N (q, a))
{q2 ,q3 ,q4 ,q5 }

= clausura (N (q2 , a) N (q5 , a))

= clausura ( {q2 } {q4 , q5 } )
= clausura ({q2 , q4 , q5 })
= {q2 , q3 , q4 , q5 } = p2

D (p2 , a) = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 326 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 3: Transiciones de p2 = {q2 , q3 , q4 , q5 }
[
clausura (N (p2 , b)) = clausura ( N (q, b))
qp2
[
= clausura ( N (q, a))
{q2 ,q3 ,q4 ,q5 }

= clausura (N (q2 , b) N (q5 , b))

= clausura ({q5 } {q5 })
= clausura ({q5 })
= {q3 , q5 } = p3

D (p2 , b) = p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 327 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 3: Transiciones de p2 = {q2 , q3 , q4 , q5 }

Como p3
/ QD
QD = {p 0 , p 1 , p 2 , p3 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 328 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

p
a 1

p p
0 3
b b
b
p
2

Paso 3: transiciones de p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 329 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 4: Transiciones de p3 = {q3 , q5 }

Se marca el estado p3 :

QD = {p 0 , p 1 , p 2 , p 3 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 330 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 4: Transiciones de p3 = {q3 , q5 }
[
clausura (N (p3 , a)) = clausura ( N (q, a))
qp3
=
= clausura (N (q3 , a) N (q5 , a))
= clausura ({q2 } )
= clausura ({q2 })
= {q2 } = p4

D (p3 , a) = p4

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 331 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 4: Transiciones de p3 = {q3 , q5 }

Como p4
/ QD
QD = {p 0 , p 1 , p 2 , p 3 , p4 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 332 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 4: Transiciones de p3 = {q3 , q5 }
[
clausura (N (p3 , b)) = clausura ( N (q, b))
qp3
=
= clausura (N (q3 , b) N (q5 , b))
= clausura ( {q5 })
= clausura ({q5 })
= {q3 , q5 } = p3

D (p3 , b) = p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 333 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

p
a 1

p p a p
0 3 4
b b
b
p b
2

Paso 4: transiciones de p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 334 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 5: Transiciones de p4 = {q2 }

Se marca el estado p4

QD = {p 0 , p 1 , p 2 , p 3 , p 4 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 335 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 5: Transiciones de p4 = {q2 }
[
clausura (N (p4 , a)) = clausura ( N (q, a))
qp4
=
= clausura (N (q2 , a))
= clausura () =

D (p4 , a) =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 336 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Paso 5: Transiciones de p4 = {q2 }
[
clausura (N (p4 , b)) = clausura ( N (q, b))
qp4
=
= clausura (N (q2 , b))
= clausura ({q5 })
= {q3 , q5 } = p3

(p4 , b) = p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 337 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Nota
El algoritmo finaliza al estar marcados todos los estados de QD .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 338 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

p
a 1

a
p p p
0 3 4
b b b
b
p b
2

Paso 5: transiciones de p4

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 339 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

La funcion de transicion del AFD es:
a b
p0 p1 p2
p1 p2
p2 p2 p3
p3 p4 p3
p4 p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 340 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Los dos unicos estados finales son p2 y p3 porque

p2 F N = {q2 , q3 , q4 , q5 } {q5 } = {q5 } =

6

p3 F N = {q3 , q5 } {q5 } = {q5 } =

6

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 341 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo

q
3

b
a

a, b b,
q q q q5
0 1 2

a
b

q
4
a,

AFN con transiciones triviales que se ha transformado en AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 342 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Construccion de AFD a partir de AFN)

Analisis de x = abb usando el AFD construido:

(p0 , abb) ` (p1 , bb)

` (p2 , b)
` (p3 , )

x L(AD ) porque p3 FD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 343 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Descripcion general
Definicion formal
Representacion grafica
Funcion de transicion para palabras
Lenguaje reconocido por un AFN
Equivalencia entre AFN y AFD
Equivalencia entre expresiones regulares y automatas finitos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 344 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

AFN

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 345 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

AFN

Algoritmo de Construccion de subconjuntos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 346 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

AFN

Algoritmo de Construccion de subconjuntos

AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 347 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

EXPRESION REGULAR

AFN

Algoritmo de Construccion de subconjuntos

AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 348 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

EXPRESION REGULAR

Algoritmo de Thompson

AFN

Algoritmo de Construccion de subconjuntos

AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 349 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Teorema
Dada una expresion regular , se puede construir un AFN AN
equivalente:
L() = L(AN )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 350 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Demostracion
EXPRESION REGULAR

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 351 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Demostracion
EXPRESION REGULAR

Algoritmo de Thompson

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 352 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Demostracion
EXPRESION REGULAR

Algoritmo de Thompson

AFN

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 353 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Demostracion

Algoritmo (Thompson)
Entrada: expresion regular .
Salida: AFN AN = (QN , , N , q0 , FN )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 354 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Algoritmo (Thompson)

q qf
0

AFN equivalente a la expresion regular .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 355 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Algoritmo (Thompson)

q0 qf

AFN equivalente a la expresion regular .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 356 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Algoritmo (Thompson)

q q
0 f

AFN equivalente a la expresion regular .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 357 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Algoritmo (Thompson)

q A q
0 f


q0 qf


q A q
0 f

Nuevo estado inicial Nuevo estado final

AFN equivalente a la expresion regular + .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 358 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Algoritmo (Thompson)

q0 A q q0 A q f
f

Estado inicial Estado final

AFN equivalente a la expresion regular .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 359 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Algoritmo (Thompson)

q q A qf
0 0 qf

Nuevo estado inicial Nuevo estado final

AFN equivalente a la expresion regular .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 360 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Algoritmo (Thompson)

Nota
L(()) = L() = L(AN )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 361 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Algoritmo de Thompson)

AFN equivalente a = l(l + d)

Paso 1: AFN equivalente a l

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 362 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Algoritmo de Thompson)

AFN equivalente a = l(l + d)

Paso 2: AFN equivalente a d

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 363 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Algoritmo de Thompson)

AFN equivalente a = l(l + d)

Paso 3: AFN equivalente a l + d

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 364 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Algoritmo de Thompson)

AFN equivalente a = l(l + d)

Paso 4: AFN equivalente a (l + d)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 365 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Algoritmo de Thompson)

AFN equivalente a = l(l + d)

l q
q
4 6
q l q q
q q

q
0 1 2 3 8 9
d
q q
5 7

Paso 5: AFN equivalente a l(l + d)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 366 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

EXPRESION REGULAR

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 367 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

EXPRESION REGULAR

Algoritmo de Thompson

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 368 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

EXPRESION REGULAR

Algoritmo de Thompson

AFN

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 369 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

EXPRESION REGULAR

Algoritmo de Thompson

AFN

Algoritmo de Construccion de subconjuntos

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 370 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

EXPRESION REGULAR

Algoritmo de Thompson

AFN

Algoritmo de Construccion de subconjuntos

AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 371 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo (Algoritmo de Construccion de subconjuntos)

AFN equivalente a = l(l + d)

l q
q
4 6
q l q q
q q

q
0 1 2 3 8 9
d
q q
5 7

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 372 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 0: Estado inicial del AFD:

p0 = clausura (q0 ) = {q0 }

QD = {p0 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 373 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

p
0

Paso 0: estado inicial p0

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 374 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 1: Transiciones de p0 = {q0 }

Se marca el estado p0 :
QD = {p 0 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 375 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 1: Transiciones de p0 = {q0 }
clausura (N (p0 , l)) =
[
= clausura ( N (q, l))
qp0
[
= clausura ( N (q, l))
q{q0 }

= clausura (N (q0 , l))

= clausura ({q1 })
= {q1 , q2 , q3 , q4 , q5 , q9 } = p1

Por tanto, D (p0 , l) = p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 376 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 1: Transiciones de p0 = {q0 }

Como p1
/ QD :

QD = QD {p1 } = {p 0 , p1 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 377 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 1: Transiciones de p0 = {q0 }
clausura (N (p0 , d)) =
[
= clausura ( N (q, d))
qp0
[
= clausura ( N (q, d))
q{q0 }

= clausura (N (q0 , d)))

= clausura ()
=

D (p0 , d) =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 378 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

l
p p
0 1

Paso 1: transiciones de p0

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 379 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 2: Transiciones de p1 = {q1 , q2 , q3 , q4 , q5 , q9 }

Se marca el estado p1 :

QD = {p 0 , p 1 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 380 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 2: Transiciones de p1 = {q1 , q2 , q3 , q4 , q5 , q9 }
[
clausura (N (p1 , l)) = clausura ( (q, l))
qp1
=
= clausura (N (q1 , l) N (q9 , l))
= clausura ( {q6 } )
= clausura ({q6 })
= {q3 , q4 , q5 , q6 , q8 , q9 } = p2

Por tanto, D (p1 , l) = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 381 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 2: Transiciones de p1 = {q1 , q2 , q3 , q4 , q5 , q9 }

Como p2
/ QD :

QD = QD {p2 } = {p 0 , p 1 , p2 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 382 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 2: Transiciones de p1 = {q1 , q2 , q3 , q4 , q5 , q9 }
[
clausura (N (p1 , d)) = clausura ( (q, d))
qp1
=
= clausura (N (q1 , d) N (q9 , d))
= clausura ( {q7 } )
= clausura ({q7 })
= {q3 , q4 , q5 , q7 , q8 , q9 } = p3

Por tanto, D (p1 , d) = p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 383 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 2: Transiciones de p1 = {q1 , q2 , q3 , q4 , q5 , q9 }

Como p3
/ QD :

QD = QD {p3 } = {p 0 , p 1 , p2 , p3 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 384 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

p
l 2
l
p p
0 1

d
p
3

Paso 2: transiciones de p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 385 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 3: Transiciones de p2 = {q3 , q4 , q5 , q6 , q8 , q9 }

Se marca el estado p2 :

QD = {p 0 , p 1 , p 2 , p3 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 386 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 3: Transiciones de p2 = {q3 , q4 , q5 , q6 , q8 , q9 }
[
clausura (N (p2 , l)) = clausura ( N (q, l))
qp2
=
= clausura (N (q3 , l) N (q9 , l))
= clausura ( {q6 } )
= clausura ({q6 })
= {q3 , q4 , q5 , q6 , q8 , q9 } = p2

D (p2 , l) = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 387 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 3: Transiciones de p2 = {q3 , q4 , q5 , q6 , q8 , q9 }
[
clausura (N (p2 , d)) = clausura ( N (q, d))
qp2
=
= clausura (N (q3 , d) N (q9 , d))
= clausura ( {q7 } )
= clausura ({q7 })
= {q3 , q4 , q5 , q7 , q8 , q9 } = p3

D (p2 , d) = p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 388 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

l
p
l 2
l
p p
0 1 d

d
p
3

Paso 3: transiciones de p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 389 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 4: Transiciones de p3 = {q3 , q4 , q5 , q7 , q8 , q9 }

Se marca el estado p3 :

QD = {p 0 , p 1 , p 2 , p 3 }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 390 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 4: Transiciones de p3 = {q3 , q4 , q5 , q7 , q8 , q9 }
[
clausura ((p3 , l)) = clausura ( (q, l))
qp3
= clausura (N (q3 , l) N (q9 , l))
= clausura ( {q6 } )
= clausura ({q6 })
= {q3 , q4 , q5 , q6 , q8 , q9 } = p2

D (p3 , l) = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 391 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Paso 4: Transiciones de p3 = {q3 , q4 , q5 , q7 , q8 , q9 }
[
clausura ((p3 , d)) = clausura ( (q, d))
qp3
= clausura (N (q3 , d) N (q8 , d))
= clausura ( {q7 } )
= clausura ({q7 })
= {q3 , q4 , q5 , q7 , q8 , q9 } = p3

D (p3 , d) = p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 392 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

l
p
l 2
l
p p
0 1 d l

d d
p
3

Paso 4: transiciones de p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 393 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Nota
El algoritmo finaliza al estar marcados todos los estados de QD .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 394 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Funcion de transicion del AFD
l d
p0 p1
p1 p2 p3
p2 p2 p3
p3 p2 p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 395 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo ( = l(l + d) : paso de AFN a AFD)

Estados finales: p1 , p2 y p3

p1 F N = {q1 , q2 , q3 , q4 , q5 , q9 } {q9 } = {q9 } =

6

p2 F N = {q3 , q4 , q5 , q6 , q8 , q9 } {q9 } = {q9 } =

6

p3 F N = {q3 , q4 , q5 , q7 , q8 , q9 } {q9 } = {q9 } =

6

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 396 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Automatas finitos NO deterministas: AFN

Ejemplo

l l, d
q q
0 1

AFD mas simple y equivalente a = l(l + d)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 397 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

Automatas finitos
Automatas finitos deterministas: AFD
Automatas finitos NO deterministas: AFN
Minimizacion de automatas finitos deterministas

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 398 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Definicion
Dos automatas son equivalentes si reconocen el mismo lenguaje:

A A0 L(A) = L(A0 )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 399 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Razones para minimizar un AFD

Un lenguaje regular puede ser reconocido por varios
automatas finitos deterministas equivalentes.
Se debe usar el AFD con el menor numero de estados.
La Minimizacion permite generar el AFD que reconoce un
lenguaje regular con el menor numero de estados.
La minimizacion esta basada en una relacion de
equivalencia entre estados.
El automata cociente de la relacion de equivalencia es el
AFD mnimo.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 400 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Definicion (Equivalencia entre estados)

Se dice que dos estados q, q 0 Q son equivalentes (qEq 0 ) si se
verifica que:

x ((q, x) F (q 0 , x) F )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 401 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

E es una relacion de quivalencia

x q, q 0 Q:
Reflexiva: qEq (q, x) F (q, x) F
Simetrica: qEq 0 = q 0 Eq

((q, x) F (q 0 , x) F ) = ((q 0 , x) F (q, x) F )

Transitiva: qEq 0 q 0 Eq 00 = qEq 00

((q, x) F (q 0 , x) F )

((q, x) F (q 00 , x) F )
((q 0 , x) F (q 00 , x) F )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 402 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Definicion (Clase de equivalencia de un estado)

Si q Q, la clase de equivalencia de q respecto de la relacion E
se define como:

E [q] = {q 0 |qEq 0 } = {q 0 | x ((q, x) F (q 0 , x) F )}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 403 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Propiedades de la relacion de equivalencia E

q Q q E [q]
Si q 0
/ E [q] entonces E [q 0 ] E [q] =
S
Q= E [q]
qQ

|Q|E | |Q|

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 404 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Definicion (Automata cociente)

A|E = (Q|E , , |E , E [q0 ], F|E )
Q|E = {E [q]|q Q}
La funcion de transicion |E se define como:
|E : Q|E Q|E
q, q 0 Q
|E (p, ) = p 0 Q|E p = E [q] p 0 = E [q 0 ]
(q, ) = q 0

E [q0 ] es el estado inicial y

F|E = {E [qf ]|qf F },

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 405 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Nota
La funcion |E se define de manera similar a .

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 406 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Teorema
Todo AFD es equivalente a su automata cociente:

L(A) = L(A|E )

Demostracion
x L(A) (q0 , x) F
qf F (q0 , x) = qf
p0 = E [q0 ] qf F pf = E [qf ] |E (p0 , x) = pf
|E (p0 , x) = pf F|E
x L(A|E )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 407 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Teorema
Todo AFD es equivalente a su automata cociente:

L(A) = L(A|E )

Demostracion
x L(A) (q0 , x) F
qf F (q0 , x) = qf
p0 = E [q0 ] qf F pf = E [qf ] |E (p0 , x) = pf
|E (p0 , x) = pf F|E
x L(A|E )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 408 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Demostracion

Algoritmo (Construccion del Automata Cociente)

Entrada: A = (Q, , , q0 , F ).
Salida: A|E = (Q|E , , |E , E [q0 ], F|E ), Automata cociente

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 409 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Algoritmo (Construccion del Automata Cociente)

inicio
p0 Q F , p1 F
Nuevo {p0 , p1 } y p0 y p1 no marcados
mientras p Nuevo no marcado hacer
Marcar a p
para cada hacer
Dividir p en subconjuntos de forma que sus estados
qi y qj estaran en el mismo subconjunto
si (qi , ) y (qj , ) pertenecen al mismo subconjunto
fin para
si se ha dividido p en subconjuntos
entonces
Sustituir p por los nuevos subconjuntos
Desmarcar todos los estados de Nuevo
fin si
fin mientras
fin
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 410 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (1.- Minimizacion de AFD)

q
l 2
l l
q q
0 1 d l

d d
q
3

AFD original que reconoce identificadores de Pascal.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 411 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (1.- Minimizacion de AFD)

Estados no finales: p0 = Q F = {q0 }
Estados finales: p1 = F = {q1 , q2 , q3 }
Nuevo = {p0 , p1 }
Los estados de Nuevo no estan marcados.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 412 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (1.- Minimizacion de AFD)

Paso 1: Analisis de p0 = {q0 }
Se marca p0 : Nuevo = {p 0 , p1 }
p0 solo contiene un estado y no se puede descomponer mas.
Transiciones provisionales de p0 :

|E (p0 , l) = E [(q0 , l)] = E [q1 ] = p1

|E (p0 , d) = E [(q0 , d)] = E [] =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 413 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (1.- Minimizacion de AFD)

Paso 2: Analisis de p1 = {q1 , q2 , q3 }
Se marca p1 : Nuevo = {p 0 , p 1 }
Se comprueban que los estados de p1 son homogeneos:
p1 l d
q1 p1 p1
q2 p1 p1
q3 p1 p1
Transiciones de p1 : |E (p1 , l) = p1, |E (p1 , d) = p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 414 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (1.- Minimizacion de AFD)

El algoritmo finaliza porque todos los estados de Nuevo
estan marcados.
Los estados generados son:
+ p0 = {q0 }
+ p1 = {q1 , q2 , q3 }
El estado inicial es p0 porque q0 p0 .
F|E = {p1 } porque p1 F = {q1 , q2 , q3 } =
6

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 415 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (1.- Minimizacion de AFD)

Funcion de transicion del automata minimizado
l d
p0 p1
p1 p1 p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 416 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (1.- Minimizacion de AFD)

l l, d
p p
0 1

AFD minimizado que reconoce identificadores de Pascal.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 417 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

[ d
q q q
0 1 2

[ d
]
q q
3 4 d
]

AFD original que reconoce componentes de arrays.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 418 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

Estados no finales: p0 = Q F = {q1 , q2 , q4 }
Estados finales: p1 = F = {q0 , q3 }
Nuevo = {p0 , p1 }
Los estados p0 y p1 no estan marcados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 419 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

Nota
El estado inicial q0 pertenece a p1 porque tambien es un estado
final

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 420 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

Paso 1: Analisis de p0 = {q1 , q2 , q4 }
Se marca p0 : Nuevo = {p 0 , p1 }
Se comprueban las transiciones de los estados de p0 :
[ d ]
q1 p0
q2 p0 p1
q4 p0 p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 421 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

Paso 1: Analisis de p0 = {q1 , q2 , q4 }
q1 no es equivalente a q2 y q4 .
El antiguo estado p0 se divide en dos nuevos estados:

p0 = {q1 }
p2 = {q2 , q4 }

Nuevo = {p0 , p1 , p2 }
Todos los estados estan desmarcados.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 422 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

Paso 2: Segundo analisis de p0 = {q1 }
Se marca p0 : Nuevo = {p 0 , p1 , p2 }
p0 solo contiene un estado y no se puede descomponer mas.
Transiciones provisionales de p0 :

|E (p0 , [) = E [(q1 , [)] = E [] =

|E (p0 , d) = E [(q1 , d)] = E [q2 ] = p2
|E (p0 , ]) = E [(q1 , ])] = E [] =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 423 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

Paso 3: Analisis de p1 = {q0 , q3 }
Se marca p1 : Nuevo = {p 0 , p 1 , p2 }
Se comprueban que los estados de p1 son homogeneos:
[ d ]
q0 p0
q3 p0
Transiciones provisionales de p1 :

|E (p1 , [) = E [(q0 , [)] = E [q1 ] = p0

|E (p1 , d) = E [(q0 , d)] = E [] =
|E (p1 , ]) = E [(q0 , ])] = E [] =

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 424 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

Paso 4: Analisis de p2 = {q2 , q4 }
Se marca p2 : Nuevo = {p 0 , p 1 , p 2 }
Se comprueban que los estados de p1 son homogeneos:
[ d ]
q2 p2 p1
q4 p2 p1
Transiciones de p2 :

|E (p1 , [) = E [(q2 , [)] = E [] =

|E (p1 , d) = E [(q2 , d)] = E [q4 ] = p2
|E (p1 , ]) = E [(q2 , ])] = E [q3 ] = p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 425 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

El algoritmo finaliza porque todos los estados de Nuevo
estan marcados.
Los estados generados son:
+ p0 = {q1 }
+ p1 = {q0 , q3 }
+ p2 = {q2 , q4 }
El estado inicial es p1 porque q0 p1 .
F|E = {p1 } porque p1 F = {q0 , q3 } =
6

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 426 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

Funcion de transicion del automata minimizado
[ d ]
p0 p2

p p0
1
p2 p2 p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 427 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (2.- Minimizacion de AFD)

[
p p
1 0

d
]

p
2 d
Automata cociente (automata mnimo).

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 428 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

1
0 1
0 1 0 0
q q q q
0 1 2 3

1 1 1
1
0
1
q 0 q q
5 4 6
0

AFD que se va a minimizar.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 429 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Estados no finales: p0 = Q F = {q0 , q2 , q3 , q4 , q5 , q6 }
Estados finales: p1 = F = {q1 }
Nuevo = {p0 , p1 }
Los estados p0 y p1 no estan marcados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 430 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso 1: Analisis de p0 = {q0 , q2 , q3 , q4 , q5 , q6 }
Se marca p0 : Nuevo = {p 0 , p1 }
Se comprueban las transiciones de los estados de p0 :
0 1
q0 p1 p0
q2 p0 p1
q3 p0 p1
q4 p1 p0
q5 p0 p1
q6 p0 p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 431 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso numero 1: Analisis de p0 = {q0 , q2 , q3 , q4 , q5 , q6 }
q0 y q4 tienen transiciones diferentes de los otros estados
El antiguo estado p0 se divide en dos nuevos estados:

p0 = {q0 , q4 }
p2 = {q2 , q3 , q5 , q6 }

Nuevo = {p0 , p1 , p2 }
Todos los estados estan desmarcados.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 432 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso 2: Segundo analisis de p0 = {q0 , q4 }
Se marca p0 : Nuevo = {p 0 , p1 , p2 }
Se comprueban si las transiciones de los estados contenidos en
p0 son homogeneas:
0 1
q0 p1 p2
q4 p1 p2
Transiciones provisionales de p0 :

|E (p0 , 0) = E [(q0 , 0)] = E [q1 ] = p1

|E (p0 , 1) = E [(q0 , 1)] = E [q5 ] = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 433 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso 3: Analisis de p1 = {q1 }
Se marca p1 : Nuevo = {p 0 , p 1 , p2 }
p1 solo contiene un estado y no se puede descomponer mas.
Transiciones provisionales de p1 :

|E (p1 , 0) = E [(q1 , 0)] = E [q1 ] = p1

|E (p1 , 1) = E [(q1 , 1)] = E [q2 ] = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 434 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso 4: Analisis de p2 = {q2 , q3 , q5 , q6 }
Se marca p2 : Nuevo = {p 0 , p 1 , p 2 }
Se comprueban si son homogeneas las transiciones de los
estados contenidos en p2 :
0 1
q2 p2 p1
q3 p2 p1
q5 p0 p1
q6 p0 p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 435 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso 4: Analisis de p2 = {q2 , q3 , q5 , q6 }
q2 y q3 tienen transiciones diferentes de los otros estados
El antiguo estado p2 se divide en dos nuevos estados:

p2 = {q2 , q3 }
p3 = {q5 , q6 }

Nuevo = {p0 , p1 , p2 , p3 }
Todos los estados estan desmarcados.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 436 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso 5: Tercer analisis de p0 = {q0 , q4 }
Se marca p0 : Nuevo = {p 0 , p1 , p2 , p3 }
Se comprueban si las transiciones de los estados contenidos en
p0 son homogeneas:
0 1
q0 p1 p3
q4 p1 p3
Transiciones provisionales de p0 han cambiado:

|E (p0 , 0) = E [(q0 , 0)] = E [q1 ] = p1

|E (p0 , 1) = E [(q0 , 1)] = E [q5 ] = p3

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 437 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso 6: Segundo analisis de p1 = {q1 }
Se marca p1 : Nuevo = {p 0 , p 1 , p2 , p3 }
El estado p1 no se puede dividir porque solo contiene a q1
Se comprueba si han cambiado las transiciones provisionales
de p1 :
|E (p1 , 0) = E [(q1 , 0)] = E [q1 ] = p1
|E (p1 , 1) = E [(q1 , 1)] = E [q2 ] = p2

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 438 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso numero 7: Segundo analisis de p2 = {q2 , q3 }
Se marca p2 : Nuevo = {p 0 , p 1 , p 2 , p3 }
Se comprueban si son homogeneas las transiciones de los
estados contenidos en p2 :
0 1
q2 p2 p1
q3 p2 p1
Los estados q2 y q3 son equivalentes y no se requiere ninguna
division.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 439 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Paso numero 8: Analisis de p3 = {q5 , q6 }
Se marca p3 : Nuevo = {p 0 , p 1 , p 2 , p 3 }
Se comprueban si son homogeneas las transiciones de los
estados contenidos en p3 :
0 1
q5 p0 p1
q6 p0 p1
Los estados q5 y q6 son equivalentes y no se requiere ninguna
division.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 440 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

El algoritmo finaliza porque todos los estados de Nuevo
estan marcados.
Los estados generados son:
+ p0 = {q0 , q4 }
+ p1 = {q1 }
+ p2 = {q2 , q3 }
+ p3 = {q5 , q6 }
El estado inicial es p0 porque q0 p0 .
F|E = {p1 } porque p1 F = {q1 } =
6

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 441 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

Funcion de transicion del automata minimizado
|E 0 1
p0 p1 p3
p1 p1 p2
p2 p2 p1
p3 p0 p1

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 442 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

0 1
0 1 0
p p p
0 1 2

1
0 1

p
3

Representacion grafica del AFD minimizado.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 443 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Reconocimiento de componentes lexicos

Minimizacion de automatas finitos deterministas

Ejemplo (3.- Minimizacion de AFD)

1
0 1
0 1 0 0
q q q q
0 1 2 3

1 1 1
1
0
1
q 0 q q
5 4 6
0

AFD que se ha minimizado.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 444 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido del tema

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 445 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Introduccion
Codificacion manual del analizador lexico
Generacion automatica del analizador lexico

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 446 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Introduccion

Definicion
Se denomina implementacion de un analizador lexico a su
codificacion en un lenguaje de programacion.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 447 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Introduccion

Nota
Se recuerda que el analizador lexico suele ser una funcion o
procedimiento auxiliar del analizador sintactico.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 448 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Introduccion

Tareas del analizador lexico

Reconocer todos los componentes lexicos:
+ Palabras reservadas
+ Identificadores
+ numeros
+ Operadores aritmeticos, relacionales, etc.
+ Etc.
Enviar al analizador sintactico los componentes lexicos
reconocidos.
Procesar los errores lexicos que pueda detectar.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 449 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Introduccion

Nota (Primer paso para implementar el analizador lexico)

Definir una expresion regular
para denotar cada componente lexico

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 450 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Introduccion

Tipo de reconocimiento de las palabras reservadas

Implcito
+ Se pre-instalan en la tabla de smbolos.
+ Se procesan inicialmente como identificadores.
+ Se reconocen como palabras claves al buscarlas en la tabla de
smbolos.
Explcito
+ Se reconocen de forma independiente a los identificadores
+ Siempre se utiliza el lexema mas largo: if - ifa
+ En caso de igualdad de longitudes, se escoge el componente
lexico que se haya especificado en primer lugar.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 451 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Introduccion

Metodos de implementacion del Analizador Lexico

Codificacion manual utilizando un lenguaje de programacion.

Utilizacion de un generador automatico del analizador lexico:

+ lex: lenguaje C y unix.
+ flex: lenguaje C y linux.
+ pclex: lenguaje C y MSDOS.
+ Jlex: lenguaje java y multiplataforma.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 452 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Introduccion
Codificacion manual del analizador lexico
Generacion automatica del analizador lexico

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 453 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Caractersticas
Se utiliza un lenguaje de programacion:
+ Alto nivel: C, C++, Pascal, Java, etc.
+ Bajo nivel: ensamblador.
Se codifica una funcion que combina todos los AFDs
transformados.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 454 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Lenguaje de programacion de alto nivel

Ventajas
+ Computacionalmente eficiente.
+ Permite la deteccion y recuperacion especfica de errores.
Inconvenientes
+ Requiere un gran esfuerzo de programacion.
+ Las modificaciones pueden ser dificultosas.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 455 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Lenguaje de programacion de bajo nivel

Ventajas
+ Computacionalmente muy eficiente: permite controlar de
forma directa la Entrada / Salida.
+ Permite la deteccion y recuperacion especfica de errores.
Inconvenientes
+ Requiere un esfuerzo de programacion muy elevado.
+ Las modificaciones son muy dificultosas.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 456 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Combinacion de los Automatas Finitos Deterministas

transformados
Se transforma cada AFD para que:
+ reconozca el componente lexico
+ compruebe si es necesario procesar el smbolo que sigue al
componente lexico:
- Si el smbolo es correcto, se devuelve al buffer de entrada.
- Si el smbolo es incorrecto, se procesa el error detectado.
+ devuelva el componente lexico reconocido.
+ y continue el analisis lexico.
Se combinan todos los Automatas Finitos Deterministas
transformados.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 457 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (1.- Transformacion de AFD: 1/3)

l, s l, s, d
q q
0 1

AFD que reconoce identificadores del lenguaje C.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 458 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (1.- Transformacion de AFD: 2/3)

l, s, d

l, s Smbolo correcto
q q q
0 1 2

Smbolo incorrecto
l, s

q
3

AFD transformado.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 459 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (1.- Transformacion de AFD: 3/3)

El estado q2 debe:
+ Devolver el componente lexico reconocido.
+ Devolver al buffer de entrada el smbolo correcto que no
pertenece al identificador de C:
- espacio en blanco
- punto y coma,
- etc.
El estado q3 debe procesar el error detectado.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 460 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Nota
Las celdas vacas de la funcion de transicion se completan con
rutinas de tratamiento de errores:

j
q0

qi Error

Error representa una funcion o procedimiento que permite el

tratamiento del error detectado.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 461 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Nota
Algunas veces no es necesario comprobar el smbolo que sigue
al componente lexico.
Suele ocurrir con los componentes lexicos mas simples:
Punto y coma
Espacio en blanco, tabular o salto de lnea
Operadores aritmeticos
Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 462 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (2.- Transformacion AFD: 1/2)

q
= 2
<
q q
0 1

otro smbolo
q
3

AFD transformado que reconoce los componentes lexicos MENOR

o MENOR IGUAL.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 463 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (2.- Transformacion AFD: 2/2)

q2 reconoce el componente lexico MENOR IGUAL
+ No se necesita procesar el smbolo siguiente, porque no ha sido
ledo.
q3 reconoce el componente lexico MENOR.
+ El otro smbolo debe ser devuelto al buffer de entrada.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 464 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Estrategias de la codificacion manual

Utilizar directamente las tablas de la funcion de transicion de
los AFDs.

Simular el funcionamiento de los AFDs mediante sentencias

de control.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 465 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (Uso de la tabla de la funcion de transicion)

INICIO ESTADO INICIAL
LEER (CARACTER)
MIENTRAS (FINAL(ESTADO) = FALSO Y CARACTER 6= FIN-DE-FICHERO)
HACER
ESTADO M(ESTADO,CARACTER)
LEER (CARACTER)
FIN MIENTRAS
SI ERROR(ESTADO) = VERDADERO ENTONCES
PROCESAR-ERROR(ESTADO)
SI NO
SI DEVOLVER-CARACTER(ESTADO) ENTONCES
DEVOLVER (CARACTER)
FIN SI
COMPONENTE-LEXICO(ESTADO)
FIN

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 466 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (Uso de la tabla de la funcion de transicion)

INICIO ESTADO INICIAL
LEER (CARACTER)
MIENTRAS (FINAL(ESTADO) = FALSO Y CARACTER 6= FIN-DE-FICHERO)
HACER
ESTADO M(ESTADO,CARACTER)
LEER (CARACTER)
FIN MIENTRAS
SI ERROR(ESTADO) = VERDADERO ENTONCES
PROCESAR-ERROR(ESTADO)
SI NO
SI DEVOLVER-CARACTER(ESTADO) ENTONCES
DEVOLVER (CARACTER)
FIN SI
COMPONENTE-LEXICO(ESTADO)
FIN

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 467 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (Simulacion con sentencias de control: 1/3)

yylex()
{
int c;
/* Salta blancos y tabuladores */
while((c=getchar())== || c==\t ); /* Sentencia nula */
if (c == EOF)
{
printf("\n Fin de la ejecucion de %s \n", progname);
return 0;
}
else if (c == . || isdigit(c))
{ /* El smbolo ledo se devuelve al buffer de entrada
para leerlo como parte de un numero */
ungetc(c,stdin);
/* Lee el numero */
scanf(" %lf",&[Link]);
return NUMBER;
}
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 468 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (Simulacion con sentencias de control: 2/3)

else if (isalpha(c))
{ /* comprueba si lee un identificador */
Symbol *s;
char sbuf[100],*p=sbuf;
do {
*p++=c;
} while((c=getchar()) != EOF && isalnum(c));
/* Devuelve el smbolo que no pertenece al identificador */
ungetc(c,stdin);
/* Cadena correcta: caracter nulo al final */
*p=\0;
/* Si no esta en la tabla de smbolos, lo instala */
if ((s=lookup(sbuf))==0) s = install(sbuf,INDEFINIDA,0.0);
[Link]=s;
return s->tipo==INDEFINIDA ? VAR : s->tipo;
}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 469 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Codificacion manual del analizador lexico

Ejemplo (Simulacion con sentencias de control: 3/3)

else if (c==\n)
{
lineno++;
return FIN;
}
else if (c==;) return FIN;
/* Devuelve el codigo ASCII de los demas caracteres */
return c;
}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 470 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

Introduccion
Codificacion manual del analizador lexico
Generacion automatica del analizador lexico

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 471 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

Caractersticas de la generacion automatica

Los componentes lexicos se denotan mediante expresiones
regulares.
El generador lexico crea automaticamente el codigo a partir de
las expresiones regulares.
Generadores lexicos: lex, flex, pclex, jlex, ...

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 472 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

COMPONENTES LEXICOS

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 473 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

COMPONENTES LEXICOS

EXPRESIONES REGULARES

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 474 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

COMPONENTES LEXICOS

EXPRESIONES REGULARES

AFN

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 475 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

COMPONENTES LEXICOS

EXPRESIONES REGULARES

AFN

AFD

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 476 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

COMPONENTES LEXICOS

EXPRESIONES REGULARES

AFN

AFD

ANALIZADOR LEXICO

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 477 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

COMPONENTES LEXICOS

EXPRESIONES REGULARES

AFN
LEX
AFD

ANALIZADOR LEXICO

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 478 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

LEX
Creado por M. E. Lesk y E. Schmidt (Bell Laboratories).
Genera analizadores lexicos para C, Fortran, Raftor.
Hay versiones para Unix, Linux, DOS, etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 479 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Generacion automatica del analizador lexico

Funcionamiento de LEX

nombre.l [Link].c

Expresiones regulares LEX yylex()

fichero de lex Analizador lxico

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 480 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Funcionamiento de LEX
Unix
> lex nombre.l
> cc -g [Link].c -ll -o [Link]
Linux
> flex nombre.l
> gcc -g [Link].c -lfl -o [Link]

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 481 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejecucion
> ./[Link]
Redirigiendo la entrada y la salida
> ./[Link] < fichero entrada
> ./[Link] < fichero entrada > fichero salida
Usando argumentos desde la lnea de comandos
> ./[Link] fichero entrada
> ./[Link] fichero entrada fichero salida

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 482 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Estructura del fichero de LEX

declaraciones (opcional)

%%

reglas de traduccion de las expresiones regulares

%%

funciones auxiliares (opcional)

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 483 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: expresiones regulares

Smbolos especiales:
+ |: disyuncion
+ ( ): agrupacion de expresiones regulares
+ *: repeticion de un patron cero o mas veces.
+ +: repeticion de un patron una o mas veces.
+ ?: el patron puede aparecer cero o una vez.
+ : delimitadores de cadenas
+ .: cualquier caracter distinto del salto de lnea (\n).
+ \n: salto de lnea
+ $ : caracter de final de lnea
+ [ ]: delimitadores de clases de caracteres
+ : inicio de lnea y complementario de una clase.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 484 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: expresiones regulares

Nota
Si se antepone la barra \ delante de un smbolo especial entonces
solo se representa a s mismo:
\. solo representa el punto.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 485 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (LEX: expresiones regulares 1 / 3)

Expresion regular Significado
a|b a, b
[ab] a, b
ab ab
ab+ ab, abb, abbb,
(ab)+ ab, abab, ababab,
ab* a, ab, abb,
(ab)* , ab, abab,
ab{1,3} ab, abb, abbb

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 486 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (LEX: expresiones regulares 2 / 3)

Expresion regular Significado
[a-z] a, b, c, , z
[a \-z] a, , z
[-az] , a, z
[az-] a, z,
[a-zA-Z] a, b, , z, A, B, , Z
[a-zA-Z0-9] a, b, , z, A, B, , Z, 0, 1, , 9
[a-zA-Z0-9]* cero o mas veces a, b, c, , 9
[a-zA-Z0-9]+ una o mas veces a, b, c, , 9

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 487 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (LEX: expresiones regulares 3 / 3)

Expresion regular Significado
[ \t \n] espacio en blanco, tabulador y salto de
lnea
[ ab] cualquier caracter distinto de a o b
[a b]
a, acento circunflejo, b
a/b
a solo si va seguido de b
a$
a si va seguido del caracter \n
a/ \n
a si va seguido del caracter \n
abc
abc si esta escrito al principio de la lnea
[\40-\176] caracteres ASCII imprimibles desde octal
40 (espacio) hasta octal 176 (tilde )

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 488 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: Zona de declaraciones (opcional)

Codigo extendido de lenguaje C delimitado por %{ y } %
+ Ficheros de cabecera.
+ Macros.
+ Prototipos de funciones.
+ Variables globales
+ Etc.
Directivas de lex: %x, %a, %n %o, %p, ...
Declaracion de definiciones regulares.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 489 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: Zona de declaraciones (opcional)

Directivas de lex (tablas internas):
+ %x ESTADO: permite activar reglas condicionales (vease el
ejemplo del comentario).
+ %a numero: cambia el numero de transiciones empaquetadas.
+ %n numero: cambia el numero de transiciones.
+ %e numero: cambia el numero de nodos.
+ %p numero: cambia el numero de posiciones.
+ Etc

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 490 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (Definiciones regulares 1/2)

numero [0-9]
letra [a-zA-Z]
identificador {letra}({letra}|{numero})*

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 491 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (Definiciones regulares 2/2)

La definicion regular identificador definida como

{letra}({letra}|{numero})

es transformada en

[a zA Z ]([a zA Z ]|[0 9])

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 492 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: Zona de reglas de traduccion

expresion regular sentencia de lenguaje C

expresion regular { sentencias de lenguaje C }

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 493 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (Lex: zona de reglas)

%%
[ \t] { ; } /* saltar los espacios y los tabuladores */
{numero}+\.?|{numero}*\.{numero}+ {
sscanf(yytext," %lf",&[Link]);
return NUMBER;
}

\n {lineno++; return FIN;}

. {return yytext[0];} /* Devuelve cualquier otro caracter */

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 494 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: resolucion de ambiguedades

Si una secuencia de caracteres se puede emparejar con varias
expresiones regulares,
1 tiene preferencia la expresion regular que denote la cadena de
caracteres de mayor longitud.
2 si la longitud de la cadena es igual, tiene preferencia la que
aparezca en primer lugar.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 495 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (Lex: resolucion de la ambiguedad de if)

%%
if { return IF; }
{identificador} { Symbol *s;
if ((s=lookup(yytext)) == 0)
s = install (yytext, INDEFINIDA, 0.0);
[Link] = s;
return s->tipo == INDEFINIDA ? VAR : s->tipo;
}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 496 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: comandos especiales

ECHO: imprime por pantalla el texto reconocido.
BEGIN: cambia a un estado definido por el programador
(vease el ejemplo del comentario).
REJECT: rechaza el texto reconocido para que pueda ser
procesado por otra regla (vease el ejemplo de pink).

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 497 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (ECHO)
Imprime por pantalla todos los caracteres
%%
.|\n ECHO;
%%
Equivalencia
%%
.|\n printf(" %s",yytext");
%%

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 498 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: Zona de funciones auxiliares (opcional)

Codigo de funciones auxiliares utilizadas por las reglas de
traduccion
Tambien se pueden incluir
+ Ficheros de cabecera.
+ Macros.
+ Prototipos de funciones.
+ Declaracion de variables globales
+ Etc.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 499 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: variables globales predefinidas

yytext: cadena que contiene el texto reconocido (tipo: char *)
yyleng: longitud de yytext (tipo: int)
yyin:
Puntero al fichero de entrada
Tipo: FILE *
Valor por defecto: stdin, el teclado
yyout:
Puntero al fichero de salida
Tipo: FILE *
Valor por defecto: stdout, la pantalla

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 500 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

LEX: funciones predefinidas

yylex(): contiene el analizador lexico generado por flex o lex
yymore(): indica a lex que anada el siguiente componente
lexico al componente lexico actual (vease el ejemplo hiper).
yywrap(): se ejecuta cuando el analizar lexico encuentra el fin
de fichero:
Si devuelve 0, el analizador lexico continua explorando.
Si devuelve 1 (valor por defecto), el analizador lexico devuelve
un componente lexico nulo para indicar el fin del fichero.
Esta funcion puede ser redefinida por el programador.
yyless(n): retiene los primeros n caracteres de yytext y
devuelve el resto al dispositivo de lectura.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 501 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (Lex: zona de declaraciones 1/3)

%{
#include "macros.h"
#include "hoc3.h"
#include "[Link].h"
extern char *progname;
extern int lineno;
%}

/* definiciones regulares */
numero [0-9]
letra [a-zA-Z]
identificador {letra}({letra}|{numero})*

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 502 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (Lex: zona de reglas 2/3)

%%
[ \t] { ; } /* saltar los espacios y los tabuladores */
{numero}+\.?|{numero}*\.{numero}+ {
sscanf(yytext," %lf",&[Link]);
return NUMBER;
}
{identificador} { Symbol *s;
if ((s=lookup(yytext)) == 0)
s = install (yytext, INDEFINIDA, 0.0);
[Link] = s;
return s->tipo == INDEFINIDA ? VAR : s->tipo;
}
; {return FIN ;}
\n {lineno++; return FIN;}
. {return yytext[0];} /* Devuelve cualquier otro caracter */

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 503 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Implementacion de los analizadores lexicos

Ejemplo (Lex: zona de funciones auxiliares 3/3)

/***** Zona de funciones auxiliares *****/
extern FILE *yyin, *yyout;
main(int cantidad, char *palabras[])
{ switch(cantidad)
{
case 2: yyin=fopen(palabras[1],r);
break;
case 3: yyin=fopen(palabras[1],r);
yyout=fopen(palabras[2],w);
}
yylex();
}

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 504 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido del tema

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 505 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion
Errores lexicos
Tratamiento de los errores
Metodos de recuperacion de los errores lexicos
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 506 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion

Tipos de errores
Invisibles: errores que no pueden ser detectados por el
procesador de lenguajes
Visibles: errores que s pueden ser detectados

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 507 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion

Ejemplo (Error invisible)

Se ha tecleado
a = b+c
en vez
a = bc

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 508 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion

Errores invisibles
Suelen ser errores conceptuales o algortmicos
No pueden ser detectados porque no infrigen ninguna
norma del lenguaje de programacion.
Podran ser detectados si se incluyen tecnicas de verificacion
en el procesador de lenguajes:
+ Poseen gran complejidad
+ Su coste computacional es muy elevado
En la practica, estos errores son detectados y corregidos
manualmente

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 509 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion

Errores visibles
Pueden ser detectados:
+ durante el proceso de traduccion
+ o durante la ejecucion del programa ejecutable.
Son producidos porque no se ha tenido suficiente cuidado al
programar:
+ falta de comprension o desconocimiento de las
caractersticas del lenguaje
+ o confusion con las caractersticas de otro lenguaje.
Se caracterizan por
+ Ser errores de ortografa
+ Ser errores que omiten requisitos formales del lenguaje de
programacion.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 510 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion

Errores visibles
Se clasifican segun la fase en que son detectados:
Errores lexicos: no se reconoce un componente lexico correcto.
Errores sintacticos:
+ Sentencia que no respeta las reglas gramaticales del lenguaje
de programacion
+ Se origina al procesar un componente lexico inesperado
Errores semanticos: el significado de un componente lexico es
incorrecto o inapropiado.
Errores de ejecucion:
+ Funcionamiento incorrecto del programa.
+ No detectables durante el proceso de compilacion.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 511 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion

Ejemplos (Errores visibles)

Errores lexicos:
+ Componente lexico mal escrito.
+ Componente lexico con smbolos no permitidos.
Errores sintacticos:
+ Sentencias de control incompletas o mal escritas.
+ Parametros incorrectos, parentesis no balanceados, ...
Errores semanticos:
+ Identificador usado incorrectamente o no declarado.
+ Valor fuera de rango, ...
Errores de ejecucion:
+ Bucles infinitos.
+ Flujo de control incorrecto, ...

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 512 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion
Errores lexicos
Tratamiento de los errores
Metodos de recuperacion de los errores lexicos
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 513 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Tipos de errores lexicos

Componentes lexicos
con smbolos ilegales.
incompletos o muy largos.
mal escritos: infrigen alguna restriccion del lenguaje de
programacion

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 514 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplos (Errores lexicos 1/3)

Componentes lexicos con smbolos ilegales
+ Smbolo no permitido en un identificador: dato$
+ Smbolo no permitido en un numero: 3.17#10

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 515 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplos (Errores lexicos 2/3)

Componentes lexicos incompletos
+ Cadenas de caracteres no cerradas
/* faltan las comillas finales */
static char *nombre = Almudena ... ;
+ Comentarios no cerrados.
/* Este es un ejemplo maravilloso de comentario
que no tiene cierre final

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 516 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplos (Errores lexicos 3/3)

Componentes lexicos mal escritos
Lenguaje Componente lexico Incorrecto Correcto
C IDENTIFICADOR 1dato- dato 1
C NUMERO 3.14.15 3.1415
C MENOR IGUAL =< <=
Prolog MENOR IGUAL <= =<
Fortran MENOR IGUAL .le .le.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 517 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Caractersticas de los errores de los componentes lexicos

Son provocados por una escritura incorrecta.
Son los mas frecuentes.
El Analisis Lexico no puede detectar todos los errores de los
componentes lexicos.
Muchos errores de los componentes lexicos son detectados
durante las demas fases.
Pueden provocar errores sintacticos, semanticos o de
ejecucion.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 518 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplo (1.- Error no detectable durante el analisis lexico)

Palabra reservada mal escrita
fi (x >= 0) valor absoluto = x;
else valor absoluto = -x;

Nota
El analisis lexico genera para fi el componente lexico
IDENTIFICADOR en vez de IF.
Este error podra ser detectado durante el analisis sintactico

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 519 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplo (1.- Error no detectable durante el analisis lexico)

Palabra reservada mal escrita
fi (x >= 0) valor absoluto = x;
else valor absoluto = -x;

Nota
El analisis lexico genera para fi el componente lexico
IDENTIFICADOR en vez de IF.
Este error podra ser detectado durante el analisis sintactico

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 520 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplo (2.- Error no detectable durante el analisis lexico)

Omision de smbolo de fin de sentencia
/* falta el punto y coma */
if (x >= 0) valor absoluto = x
else valor absoluto = -x;

Nota
Este error puede ser detectado durante el analisis sintactico.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 521 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplo (2.- Error no detectable durante el analisis lexico)

Omision de smbolo de fin de sentencia
/* falta el punto y coma */
if (x >= 0) valor absoluto = x
else valor absoluto = -x;

Nota
Este error puede ser detectado durante el analisis sintactico.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 522 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplo (3.- Error no detectable durante el analisis lexico)

Indice de un array que posee un valor que fuera de rango
a[-999999] = 10;

Nota
Este error puede ser detectado durante el analisis semantico.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 523 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplo (3.- Error no detectable durante el analisis lexico)

Indice de un array que posee un valor que fuera de rango
a[-999999] = 10;

Nota
Este error puede ser detectado durante el analisis semantico.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 524 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplo (4.- Error no detectable durante el analisis lexico)

Argumento erroneo de una funcion
valor = log(-10);

Nota
Este error se detectara durante la ejecucion.
Podra ser detectado con tecnicas de verificacion

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 525 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Errores lexicos

Ejemplo (4.- Error no detectable durante el analisis lexico)

Argumento erroneo de una funcion
valor = log(-10);

Nota
Este error se detectara durante la ejecucion.
Podra ser detectado con tecnicas de verificacion

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 526 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion
Errores lexicos
Tratamiento de los errores
Metodos de recuperacion de los errores lexicos
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 527 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Tratamiento de los errores

Criterios generales para el tratamiento de los errores

Informar del error
+ Localizacion: ubicacion del error dentro del codigo.
+ Descripcion: motivo o caractersticas del error
Evitar la cascada de errores
+ Informar una sola vez de cada error.
+ Si un error es producido por otro entonces solo se debe
informar del primero.
Reparar el error, si es posible, e informar de la correccion
realizada.
Continuar con el proceso de traduccion para detectar otros
posibles errores.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 528 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Tratamiento de los errores

Criterios generales para el tratamiento de los errores

Informar del error
+ Localizacion: ubicacion del error dentro del codigo.
+ Descripcion: motivo o caractersticas del error
Evitar la cascada de errores
+ Informar una sola vez de cada error.
+ Si un error es producido por otro entonces solo se debe
informar del primero.
Reparar el error, si es posible, e informar de la correccion
realizada.
Continuar con el proceso de traduccion para detectar otros
posibles errores.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 529 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Tratamiento de los errores

Criterios generales para el tratamiento de los errores

Informar del error
+ Localizacion: ubicacion del error dentro del codigo.
+ Descripcion: motivo o caractersticas del error
Evitar la cascada de errores
+ Informar una sola vez de cada error.
+ Si un error es producido por otro entonces solo se debe
informar del primero.
Reparar el error, si es posible, e informar de la correccion
realizada.
Continuar con el proceso de traduccion para detectar otros
posibles errores.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 530 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Tratamiento de los errores

Criterios generales para el tratamiento de los errores

Informar del error
+ Localizacion: ubicacion del error dentro del codigo.
+ Descripcion: motivo o caractersticas del error
Evitar la cascada de errores
+ Informar una sola vez de cada error.
+ Si un error es producido por otro entonces solo se debe
informar del primero.
Reparar el error, si es posible, e informar de la correccion
realizada.
Continuar con el proceso de traduccion para detectar otros
posibles errores.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 531 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Tratamiento de los errores

Nota
Los criterios generales para el tratamiento de los errores son
aplicables a todos los tipos de errores.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 532 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Tratamiento de los errores

Nota (Reparacion del error)

Siempre debe ser revisada despues por el programador.
Solo propone una solucion, que no tiene por que ser la
correcta.
Solo pretende que el proceso de traduccion continue ... para
detectar mas errores.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 533 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Contenido de la seccion

1 Introduccion

2 Especificacion de componentes lexicos

3 Reconocimiento de componentes lexicos

4 Implementacion de los analizadores lexicos

5 Deteccion y recuperacion de errores

Clasificacion de los errores del proceso de traduccion
Errores lexicos
Tratamiento de los errores
Metodos de recuperacion de los errores lexicos
Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 534 / 539
Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Metodos de recuperacion de los errores lexicos

Metodos de procesamiento de los errores lexicos

Modo de panico o de sincronizacion
Metodo de la mnima distancia

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 535 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Metodos de recuperacion de los errores lexicos

Modo de panico o de sincronizacion

Se eliminan los caracteres de la entrada hasta que se
encuentra un componente lexico bien formado
Es sencillo de aplicar
Puede provocar errores en el analisis sintactico al suprimir
otros componentes lexicos correctos.
Es util en un entorno interactivo.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 536 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Metodos de recuperacion de los errores lexicos

Metodo de la mnima distancia

Supone que la mayora de los errores lexicos son provocados
por una unica transformacion.
Se realizan transformaciones relativamente simples:
+ Eliminar un caracter: dato$1 = dato1
+ Insertar un caracter: include = #include
+ Permutar dos caracteres: => = >=
+ Modificar un caracter: /# = /*
Es costoso de implementar.
Es adecuado para un entorno local o interactivo.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 537 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

Deteccion y recuperacion de errores

Metodos de recuperacion de los errores lexicos

Nota
Se debe informar de la transformacion realizada.
La transformacion no pretende corregir el error, sino continuar
con el analisis lexico.
Posteriormente, el programador debera supervisar la
transformacion realizada.

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 538 / 539

Procesadores de Lenguajes Tema II: Analisis Lexico

PROCESADORES DE LENGUAJES
TEMA II: ANALISIS LEXICO

Prof. Dr. Nicolas Luis Fernandez Garca

Departamento de Informatica y Analisis Numerico

Escuela Politecnica Superior
Universidad de Cordoba

Universidad de Cordoba: Escuela Politecnica Superior Ingeniera Informatica 539 / 539