Analisis_lexico_parte_i.docx

1.

1.1.

ANALISIS LEXICO

FUNCIONES DEL ANALIZADOR LÉXICO

Las principales funciones del análisis léxicos son: 1. Leer el programa fuente como un archivo de caracteres y dividirlo en unidades lógicas denominada componentes léxicos o tokens 2. Eliminar comentarios o espacios en blanco realizados con las teclas espaciadora, tabuladora o fin de líneas. 3. 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í: 1. Borrando el carácter extraño 2. Reemplazando un carácter incorrecto por uno correcto 3. Intercambiando los caracteres adyacentes 4. Borrando caracteres sucesivos de la entrada hasta encontrar un componente bien formado.

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. 1.2. CONCEPTOS BÁSICOS 1.2.1.

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 ...

• 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. 1.2.2 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. 1.2.3 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 CONT$

Es un lexema que concuerda con el patrón anterior. 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.

1.2.4 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:

{0,1}  { 0 ,1 ,2 ,3 ,....., 9 }   { a ,b ,c ,d ,e ,f,...., z }  1

2

3



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

    4

2

3

1.2.5 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 ( 1 ) ó del alfabeto ( 2 )

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

Nota: La Cadena vacía se representa con el símbolo (  )

1.2.6 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}

1.3. OPERACIONES BASICAS

1.3.1. Operaciones con cadenas

1.3.1.1.

Concatenación

Si u y v son cadenas, entonces la concatenación se denota u.v ó uv Se define:

 y v   , entonces u.v=v.u=v Si u   y v   , entonces u.v  v.u

1. Si u=

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

1.3.1.2.

Potencia de una cadena

Si u es una cadena y n un y se define

 {0}

Z+ entonces la potencia se denota

= 1.3.1.3.

Longitud de una cadena

Si u es una cadena entonces la longitud se denota

y se define:

= 1.3.1.4.

Inverso de una cadena

Si u es una cadena su inverso se denota u-1 y se define:

1.3.1.5.

Subcadenas, sufijos y prefijos

Si v es una subcadena de u, entonces u=xvy donde x e y son cadenas que pueden ser vacías. 

, entonces,

“Toda cadena es subcadena de ella misma”



, entonces,

“El vacío es una subcadena de cualquier cadena” 

, entonces,

“v es prefijo de u” 

, entonces,

“v es sufijo de u”

1.3.2. Operaciones con Lenguajes 1.3.2.1. Concatenación Si L1 y L2 son lenguajes, entonces su concatenación se denota L 1.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!!!

1.3.2.2. 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}

1.3.2.3. Cerradura de Kleene (Ø ó más Casos) Sea L un lenguaje, la cerradura de de Kleene se denota L* y se define: 

L* =U

i 0

i

0

1

2

U …… LU L = LUL

Ejemplo: L={a,b} L*={  } u {a,b} u {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 (  ).

1.3.2.4. Cerradura Positiva (1 o más Casos) Sea L un lenguaje, la cerradura positiva se denota: 

L+ =U

i 1

i

1

2

2

U L =L LULU……

Ejemplo: L+={a, b, aa, ab, ba, bb,…} 

Nota: esta cerradura genera TODAS las posibles combinaciones entres los elementos del lenguaje pero la diferencia con la cerradura de Kleene es que en este NO se incluye el vacío (  ).

1.3.2.5. Cerradura de 1 o 2 Se denota como L? y se define: 1

L?= U Li = L0 u L1 i=0 Ejemplo: L={a,b} L0={  } L1=L . L0 =L={a,b} por tanto, L?= L0 U L1 = {  ,a,b}

1.3.2.5. Propiedades de las cerraduras 1. L+= LL* 2. L*= L+ u L0= L0 u L+ 3.(L*)n= L*

4.(L*)*= L* 5.(L*)+= L* 6. (L+)*= L* 7. (L+)+= L+ 8. (L1uL2)*= (L1*L2*)* 1.4. TIPOS DE LENGUAJES

Tipos de lenguaje

Lenguajes regulares Especificar Expresiones regulares

Lenguajes no regulares Especificar GIC

1.4.1. Lenguajes regulares 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. Definición formal: 1. {  } es un lenguaje regular 2. Si a pertenece al alfabeto (  ) entonces {a} es un lenguaje regular. 3. Si L1 y L2 son lenguajes entonces L1 L2, L1 U L2, L1*, L2* son lenguajes regulares.

1.4.

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: . | * + ? (,)

Concatenación Unión Cerradura de Klenne Cerradura Positiva Cerradura 0 o 1 caso Agrupar

El orden Jerárquico es el siguiente: 1 (,) 2 *, +, ? 3. 4| Definición: 1.  es una expresión regular.

2. si a pertenece 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 (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…}.

Propiedades de la expresión regular: Sean r, s y t expresiones regulares 1 r.  =  .r = r 2 (r . s) . t = r. (s . t) 3 (r | s) | t =r | (s | t) 4 r . (s | t) = r. s | r . t 5 (r*)* = r* 6 r+ = r . r* 7 r* =  | r+ 8 r? =  | r

MODULATIVA ASOCIATIVA (.) ASOCIATIVA (.) DISTRIBUTIVA IDEMPOTENCIA