PDF de programación - 08 Análisis léxico IV - Compiladores

08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

2

Contenido

• Expresiones regulares

• Lenguaje generado por una expresión regular

• Precedencia de las operaciones con las expresiones
regulares

• Ejemplos

• Definiciones regulares

• Extensiones de las expresiones regulares

• Ejercicios 01



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

3

Expresiones regulares
• Las expresiones regulares se introducen para describir los
lenguajes regulares, entonces las expresiones regulares
serán metalenguajes i.e. las expresiones regulares son un
metalenguaje para describir los lenguajes regulares.


• Una expresión regular, a menudo es llamada también
patrón, y es una expresión que describe un conjunto de
cadenas sin enumerar sus elementos.
• P.g., el grupo formado por las cadenas Handel, Händel y Haendel

se describe mediante el patrón "H(a|ä|ae)ndel".

*Metalenguaje: Lenguaje para hablar de otro lenguaje.



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

4

Lenguaje generado por una expresión
regular
• Una expresión regular es una forma de representar a los
lenguajes regulares y se construye utilizando caracteres
del alfabeto sobre el cual se define el lenguaje.



• Específicamente, las expresiones regulares se construyen
utilizando los operadores unión, concatenación, cerradura
positiva y cerradura de Kleene.

08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

5

Lenguaje generado por una expresión
regular
• Las expresiones regulares describen los lenguajes regulares, lo
que implica que sus operaciones corresponderán a las
indicadas para los lenguajes regulares.



• Las expresiones regulares se construyen en forma recursiva a

partir de las expresiones regulares más pequeñas.



• Cada expresión regular r denota un lenguaje L(r), el cuál
también se define de forma recursiva, a partir de lenguajes
denotados por las subexpresiones de r.

08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

6

Precedencia de las operaciones con las
expresiones regulares

• Se permite el uso de paréntesis para indicar la precedencia
de las operaciones, pero cuando no se utilizan paréntesis
para evaluar una expresión regular, hay que tener en
cuenta el siguiente orden de precedencia:

1. Uso de paréntesis

2. Operación cierre y cierre positivo

3. Operación concatenación

4. Operación unión o alternativa



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

7

Ejemplos

• Ejemplo 1
• ∑ ={a, b}.

i. a|b denota el lenguaje L(a|b)={a, b}.

ii.

(a|b)(a|b) denota a L((a|b)(a|b))={aa, ab, ba,
bb}, el lenguaje de todas las cadenas de
longitud dos sobre el alfabeto ∑.

iii. (a|b)(a|b) =aa|ab|ba|bb
iv. L(a*)={λ, a, aa, aaa, …}, todas las cadenas de

cero o más a 's.

08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

8

Ejemplos

• Ejemplo 2

• (a)|((b)*(c)) = a|b*c

• Conjunto de cadenas que son una sola a o cero o
más b's seguidas por una c.



L(a|b*c)={a,c,bc,bbc,bbbc,bbbbc,…}

08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

9

Definiciones regulares

• Por conveniencia de notación se le da un nombre a algunas
expresiones regulares, para así hacer más fácil su
utilización en expresiones subsiguientes.
d1 → r1
d2 → r2
…
dn → rn
• En donde:

I.

di es un nuevo símbolo, que no está en ∑ y no es el mismo que
cualquier otro d.

II. Cada ri es una expresión regular sobre el alfabeto ∑ ∪{d1, d2, …,

dn}

08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

10

Definiciones regulares
(Ejemplo 1)

• Los identificadores de C son cadenas de letras, dígitos y

guiones bajos.

letra_ → A | B | … | Z | a | b | … | z | _

dígito →

0 | 1 | … | 9

id



→

letra_ ( letra_ | dígito)*



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

11

Definiciones regulares
(Ejemplo 2)

• Los números sin signo (enteros o de punto flotante) son

cadenas como 5280, 0.01234, 6.336E4 o 1.89E-4.

dígito

dígitos



→

→

0 | 1 | … | 9

dígito dígito *

fracción_opcional →

.dígitos | λ

exponente_opcional

→

( E ( + | - | λ ) dígitos ) | λ



numero→ <digitos><fracción_opcional><exponente_opcional>



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

12

Extensiones de las expresiones
regulares

1. Una o más instancias. El operador unario

posfijo + representa la cerradura positivo de
una expresión regular y su lenguaje.

2. Cero o una instancia. El operador unario

postfijo ? Significa “cero o una ocurrencia”.

3. Clases de caracteres. Una expresión regular

a1|a2|…|an en donde las ai son cada una
símbolos del alfabeto, puede sustituirse
mediante la abreviación [a1a2…an].


08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

13

Definiciones regulares
(Ejemplo 1 Extensión)

• Los identificadores de C son cadenas de letras,
dígitos y guiones bajos.

letra_

→ [A-Za- z_]

dígito

→ [0-9]

id

→ letra_ ( letra_ | dígito)*



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

14

Definiciones regulares
(Ejemplo 2 extensión)

• Los números sin signo (enteros o de punto flotante)
son cadenas como 5280, 0.01234, 6.336E4 o
1.89E-4.



dígito →

dígitos →

[0-9]
dígito dígito *

numero →

digitos ( . digitos)?(E[+-]?digitos)?



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

15

Ejercicios 01

•

Sea ∑ ={a, b}.
los

1. Describa

las siguientes
expresiones regulares y de ejemplos de las palabras
pertenecientes al lenguaje generado.

lenguajes denotados por

a) a(a|b)*a

b)

((λ|a)b*)*
(a|b)*a(a|b)(a|b)

c)
d) a*ba*ba*ba*

e)

(aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

16

Ejercicios 01
2. Escriba definiciones regulares para los siguientes

lenguajes

a) Todas las cadenas de letras en minúsculas que contengan las cinco

vocales en orden.

b) Comentarios que consistan de una cadena rodeada por /* y */, sin un

*/ entre ellos, a menos que se encierre entre dobles comillas(“).
c) Todas las cadenas de dígitos que tengan por lo menos un digito

repetido.

d) Las palabras reservadas de ANSI C

auto · double · int · struct · break · else · long · switch · case · enum · regist
er · typedef · char · extern · return · union · const · float · short · unsigned ·
continue · for · signed · void · default · goto · sizeof · volatile · do · if · stat
ic · while

e) Los nombres que pueden darse a una función o variable en ANSI C

Todos los posibles identificadores en ANSI C

f)


08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

17

Ejercicios 01

• La fecha máxima de entrega de los ejercicios es el
domingo 20 de Febrero de 2011 a las 23:59:59 hrs.

• El documento solo incluirá portada, la redacción y

respuesta de los 2 ejercicios con sus subíndices.


• Si deberá de incluir encabezados en cada página.



• Enviar con el nombre: Ejercicios01_NombreAlumno.*



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

18

Mapas Conceptuales 01 y 02

• La fecha máxima de entrega de los mapas es el
domingo 27 de Febrero de 2011 a las 23:59:59 hrs.

• Mapa conceptual 01: De las clases 02 y 03
• Mapa conceptual 02: De las clases 05 a la 09
• Si deberá de incluir encabezados en cada mapa.
• Recomendación usar CmapTools
• Enviar separados con el nombre:

• MapaConceptual0x_NombreAlumno.pdf



08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

19

Características de un mapa
conceptual

• Jerarquización: Se refiere a la ordenación de los conceptos más generales e
inclusivos en la parte superior o central y mediante una diferenciación progresiva,
están incluidos los conceptos más específicos.



• Impacto visual: Debe considerar la limpieza, espacios, claridad, ortografía para
reducir confusiones y amontonamientos, por ello es conveniente dibujarlos varias
veces ya que el primer mapa que se construye tiene siempre, casi con toda
seguridad algún defecto. También se recomienda usar óvalos ya que son más
agradables a la vista que los triángulos y los cuadrados.



• Simplificación: Se refiere a la selección de los conceptos más importantes,
haciendo una diferenciación del contenido y localizando la información central de
la que no lo es para una mejor comprensión y elaboración de un contenido. Los
conceptos, al ir relacionándose por medio de las palabras enlace, se van
almacenando en la mente de modo organizado y jerárquico de manera que serán
más fácilmente comprendidos.

Tipo abstracto de datos (Edgardo A. Franco)

19

08 Análisis léxico IV

Compiladores - Profr. Edgardo Adrián Franco Martínez

20

Ejemplo

Tipo abstracto de datos (Edgardo A. Franco)

20