02_analisis lexico i

CompiladoresIntroducción

Msc. Ing. Esmeide LealUniversidad Autónoma del Caribe

◦ Analisis lexico

Análisis Léxico

Las principales funciones del análisis léxicos son:◦ Leer el programa fuente como un archivo de caracteres y dividirlo en

unidades lógicas denominada componentes léxicos o tokens

◦ Eliminar comentarios o espacios en blanco realizados con las teclas espaciadora, tabuladora o fin de líneas.

◦ Reportar errores si existen

◦ Si el analizador léxico no puede continuar por que ninguno de los patrones concuerda con un prefijo, entonces es necesario recuperar los errores de entrada así: Borrando el carácter extraño Reemplazando un carácter incorrecto por uno correcto Intercambiando los caracteres adyacentes Borrando caracteres sucesivos de la entrada hasta encontrar un

componente bien formado.

FUNCIONES DEL ANALIZADOR LÉXICO

En la fase de análisis léxico se revisa o se examina el programa fuente como una cadena de izquierda a derecha y se generan los componentes léxicos o token a partir de una secuencia de caracteres que tenga un significado válido.

FUNCIONES DEL ANALIZADOR LÉXICO

Componentes Léxicos o Tokens Es un carácter o secuencia de caracteres que

representan una unidad de información dentro del programa fuente, estos pueden ser un signo de puntuación, un operador aritmético, una palabra reservada, una constante, etc.

  Para la determinación de un análisis léxico se tienen

en cuenta las siguientes categorías. 

Palabras reservadas: Son palabras predefinidas, por ejemplo: for, while, if, etc

Análisis Léxico – Conceptos Básicos

Componentes Léxicos o Tokens Símbolos especiales: Elementos que son únicos,

por ejemplo: +, -, *, (,), etc. Variables o identificadores: Es una de las

categorías más importantes por que son diseñadas por nosotros mismos. Estas poseen una ó varias reglas asociadas.

Constantes numéricas: No son solamente enteras, pueden ser decimales o flotantes, estas también deben tener una ó varias reglas asociadas.

Análisis Léxico – Conceptos Básicos

Patrón Es una regla que describe el conjunto de cadenas

de la entrada que corresponden a un componente léxico.

Ejemplo: Una variable comienza en letras seguidas de letras y/ó dígitos.

Análisis Léxico – Conceptos Básicos

Lexema Es una secuencia de caracteres del programa

fuente que concuerdan con un patrón. Ejemplo: Una variable comienza en letras seguidas de letras

y/ó dígitos. CONT1 Es un lexema que concuerda con el

patrón anterior. CONT$ No es un lexema, por que no

concuerda con ese patrón. ¿Todo componente léxico puede ser un

Lexema? No. todo componente léxico no es un lexema, porque

por ejemplo: if es una palabra reservada (recuérdese que las palabras reservadas son componentes léxicos) y no es un lexema.

Análisis Léxico – Conceptos Básicos

Alfabeto Es un conjunto no vacío y finito de símbolos. Se

denota con el símbolo Nota: Cuando necesitamos mas de un

alfabeto le colocamos un subíndice, ejemplo:

Nota: En un solo alfabeto puedo colocar los tres, pero es mejor diferenciarlos por clase de caracteres

Análisis Léxico – Conceptos Básicos

1

}1,0{

2

}9,.....,3,2,1,0{

3

},....,,,,,,{ zfedcba

4 2 3

Cadena Es una sucesión ó secuencia de caracteres

tomados a partir de un alfabeto. Ejemplos:

010001 es una cadena que pudo ser tomado del alfabeto ( ) ó del alfabeto ( )

01834 fue tomado del alfabeto ( ), puesto que sus elementos hacen parte solo de este alfabeto.

◦Nota: La Cadena vacía se representa con el símbolo (∊ o λ )

Análisis Léxico – Conceptos Básicos

Lenguaje Es un conjunto finito ó infinito de cadenas

construidos a partir de los símbolos del alfabeto. Se denota con la letra L. Ejemplo: L1= {010, 0110, 11100} L2= {ab, abbc, cajk}

Análisis Léxico – Conceptos Básicos

Concatenación Si u y v son cadenas, entonces la concatenación

se denota u.v ó uv Se define:

Si u = ∊ y v ≠ ∊, entonces u.v=v.u=v Si u ≠ ∊ y v ≠ ∊, entonces u.v ≠ v.u

Si u= a1a2 a3…. an y v= b1b 2b 3….bm, entonces u.v= a1a2 a3….an b1b 2b 3….bm

Análisis Léxico – Operaciones Básicas

Potencia de una cadena◦ Si u es una cadena y n ∈ {0} Z+ entonces la

potencia se denota un y se define.

Longitud de una cadena◦ Si u es una cadena entonces la longitud se

denota y se define:

Análisis Léxico – Operaciones Básicas

=

=

Inverso de una cadena◦ Si u es una cadena su inverso se denota u-1 y

se define:

Análisis Léxico – Operaciones Básicas

Concatenación◦ Si L1 y L2 son lenguajes, entonces su

concatenación se denota L1.L2 ó L1L2 y se define: L1L2={ xy| x ∊ L1 y ∊ L2} Si L1={∊} L2 {∊} L1L2 = L2L1 = L2

◦ Ejemplo

L1={a,b} L2={c,d} L1L2= {a,b} {c,d} ={ac, ad, bc, bd}

Nota: en las operaciones de concatenación se debe tener en cuenta que “ac” no es lo mismos de “ca”. La concatenación no es conmutativa!!!

Análisis Léxico – Operaciones BásicasLenguajes

Potencia de un Lenguaje Sea L un Lenguaje, entonces su potencia

se denota Ln y se define:

◦ Ln=

Ejemplo◦ L={a,b}◦ L0={∊}◦ L1=L . L0 =L={a,b}◦ L2=L .L={a,b} {a,b}= {aa, ab, ba, bb}◦ L3=L . L2={a,b} {aa, ab, ba, bb}◦ = {aaa, aab, aba, abb, baa, bab, bba, bbb}

Análisis Léxico – Operaciones BásicasLenguajes

Cerradura de Kleen (0 o mas casos) Sea L un lenguaje, la cerradura de Kleene

se denota L* y se define: 

◦L* = = ……

Ejemplo◦ L={a,b}◦ L*={∊} ∪ {a,b} ∪ {aa, ab, ba, bb}…◦ L*={∊, a, b, aa, ab, ba, bb,…}◦ Nota: esta cerradura genera TODAS las posibles combinaciones entres

los elementos del lenguaje incluyendo el vacío (∊). 

Análisis Léxico – Operaciones BásicasLenguajes

Cerradura Positiva (1 o mas casos) Sea L un lenguaje, la cerradura positiva se

denota L+ y se define : 

◦L+= = ……

Ejemplo◦ L={a,b}◦ L+={ a, b, aa, ab, ba, bb,…}◦ Nota: esta cerradura genera TODAS las posibles

combinaciones entres los elementos del lenguaje pero NO

incluye el vacío (∊). 

Análisis Léxico – Operaciones BásicasLenguajes

UUU LLL221

Cerradura 1 o 0 Sea L un lenguaje, la cerradura 1 o 0 se

denota L? y se define: 

◦L? = ∪ = ……

Ejemplo◦ L={a,b}◦ L0={∊}◦ L1=L . L0 = L = {a, b}◦ L0 = {∊ , a, b}

Análisis Léxico – Operaciones BásicasLenguajes

1

LL 10

Propiedades de las Cerraduras

1. L+= LL* 2. L*= L+ ∪ L0= L0 ∪ L+

3.(L*)n= L*

4.(L*)*= L*  5.(L*)+= L*

6. (L+)*= L*

7. (L+)+= L+

8. (L1 ∪ L2)*= (L1*L2

*)*

Análisis Léxico – Operaciones BásicasLenguajes

Análisis Léxico – Tipos de Lenguajes

Tipos de lenguaje

Lenguajes regulares

Expresiones regulares

Lenguajes no regulares

GIC

Especificar Especificar

Lenguajes Regulares◦ Se llaman así porque sus palabras contienen

“regularidades” o repeticiones de los mismos componentes.

Ejemplo: L1 = {ab, abab, ababab, abababab, . . .}

◦ En este ejemplo se aprecia que las palabras de L1 son simplemente repeticiones de “ab” cualquier número de veces. Aquí la “regularidad” consiste en que las palabras contienen “ab” algún número de veces.

Análisis Léxico

Lenguajes Regulares◦ Definición: Un lenguaje L es regular si y solo si se

cumple al menos una de las condiciones siguientes: i. L es finito ii. L es la unión o la concatenación de otros lenguajes

regulares R1 y R2, L = R1 ∪ R2 o L = R1R2 respectivamente iii. L es la cerradura de Kleene de algún lenguaje regular, L=

R*

Análisis Léxico

Lenguajes Regulares◦ Definición: Es un lenguaje que se forma a partir de los

lenguajes básicos como {∊} y {a} donde a ∈ Σ y debe cumplir tres operaciones básicas: Unión, concatenación y cerradura de Kleene. i. {∊} es un lenguaje regular ii. Si a pertenece al alfabeto (Σ ) entonces {a} es un lenguaje

regular. iii. Si L1 y L2 son lenguajes entonces L1 L2, L1 U L2, L1*, L2* son

lenguajes regulares.

Análisis Léxico

Expresiones Regulares◦ Simplifica la especificación de un lenguaje

regular y sirve para especificar un patrón. Los operadores que se utilizan son los siguientes:

El orden Jerárquico es el siguiente: 1 (,) 2 *, +, ? 3 . 4 |

Análisis Léxico

. Concatenación| Unión* Cerradura de Klenne+ Cerradura Positiva? Cerradura 0 o 1 caso(,) Agrupar

Expresiones Regulares◦ Definición: ◦ 1. {∊} es una expresión regular.◦ 2. Si a ∈ Σ, entonces a es una expresión regular.◦ 3. Si r y s son expresiones regulares entonces su lenguaje

regular es respectivamente L(r) y L(s) a. r es una expresión regular y se representa L (r) = {r} b. (r | s) es una expresión regular y se representa,

L(r) U L(s) = {r} U {s} = {r, s}. c. r.s es una expresión regular y se representa L(r) L(s) = {r}

{s} = {rs}. d. r* es una expresión regular y se representa L*(r) = {r}* = {∊, r, rr,

rrr, rrrr…}.

Análisis Léxico

Propiedades de las Expresiones Regulares Sean r, s y t expresiones regulares 1 r. ∊ = ∊.r = r MODULATIVA 2 (r . s) . t = r. (s . t) ASOCIATIVA (.) 3 (r | s) | t =r | (s | t) ASOCIATIVA (.) 4 r . (s | t) = r. s | r . t DISTRIBUTIVA 5 (r*)* = r* IDEMPOTENCIA 6 r+ = r . r* 7 r* = ∊ | r+

8 r? = ∊ | r◦ Nota: Todas las propiedades del lenguaje se

aplican en las expresiones regulares.

Análisis Léxico