Expresiones regulares (página 2)

Partes: 1, 2

rchivo
texto (los intérpretes de comandos reciben una o varias
cadenas como entrada, desde el teclado). Este monitoreo de la
entrada (programa fuente) lo efectúa el analizador
léxico con el fin de identificar tokens, los cuales son
cadenas o secuencias de caracteres que tienen un cierto
significado. P.F. ANALIZADOR LÉXICO Token n Token 2 Token
1 Ahh ! entonces la salida del analizador léxico es un LyA
conjunto de tokens. En un lenguaje de programación,
tenemos varias clases de tokens: Palabras reservadas,
Identificadores, Operadores aritméticos, Operadores
relacionales, Operadores lógicos, 7

8 + * ( CteLit , ) Expresiones regulares Constantes Literales
(String), Números, Separadores, Operadores de
asignación, Delimitadores, etc.. Es responsabilidad del
diseñador del lenguaje, definir cuántos y
cuáles tokens formarán precisamente al lenguaje de
programación en cuestión. En la fig. 1.7 se muestra
un fragmento de código en C y la descomposición de
cada instrucción en los tokens que la forman.
INSTRUCCIÓN TOKEN LEXEMA PATRÓN Letra seguida de id
OpAsig id iSuma = iSuma cualesquier # de letras, dig. ó
subrayado = iSuma = iSuma + 2 * x ; OpArit
+ó-ó*ó/ó% num OpArit id TermInstr
PalRes Sep 2 x ; printf dig dig … dig
+ó-ó*ó/ó% idem Suma ; Palabra
reservada o un archivo previamente definido (ó)ó,
Cualquier # de printf(“La suma es = % dn”, iSuma);
Sep id Sep “La suma es= %d n” caracteres ASCII
menos las “ encerradas entre comillas (ó)ó,
iSuma (ó)ó, TermInst ; ; Fig. 1.7. Token, Lexema y
Patrón. Los términos token, lexema y patrón
que aparecen en la tabla de la fig. 1.7 tienen cada uno un
significado especial, cuando hablamos de un análisis
léxico. En general, existen un conjunto de cadenas en la
entrada (programa fuente) para los cuales el mismo token es
producido como salida (Ejemplo las cadenas, iSuma, x, producen el
token id). A estas cadenas se les conoce como lexemas para un
cierto token. Asimismo este conjunto de 8

9 Expresiones regulares cadenas (lexemas) son descritas por una
regla denominada patrón, el cual esta asociado con el
token. Si analizamos detalladamente las instrucciones de la fig.
1.7, encontraremos que éstas, en su totalidad,
están “armadas” por tokens, es decir, cada
instrucción es un conjunto de tokens concatenados. O sea,
con los tokens … ¿ Formo las instrucciones de un
lenguaje de programación ? LyA Los tokens son
especificados formalmente por medio de expresiones regulares. El
reconocimiento de los tokens es hecho por el analizador
léxico utilizando reconocedores de lenguajes, llamados
autómatas finitos. Si quiero desarrollar un programa que
reconozca tokens -analizador léxico-, debo utilizar un
autómata finito (reconocedor de lenguajes). Mmmhh !! LyA
El análisis sintáctico recibe los tokens que le
envía el analizador léxico y con ellos construye
una estructura jerárquica, denominada arbol de
reconocimiento. El analizador sintáctico verifica que una
instrucción esté bien construida, es decir, que se
hayan observado las reglas de sintáxis para cada
instrucción, fig. 1.8. a) scanf
(“%d”,&iNum); b)
scanf(“%d”&iNum); c)
scanf(“Esp.Form.”,ListaParam); Fig.1.8. a)
Instrucción bien construida. b) Instrucción mal
construída. c) Sintáxis del scanf. 9

10 1. 2. 5. Expresiones regulares La instrucción en la
fig. 1.8 (b) tiene error de sintáxis, ya que el token
separador coma ”,” no se encuentra separando la
constante literal de la dirección del identificador. La
especificación formal de la sintáxis de una
instrucción de un lenguaje, es posible realizarla mediante
el uso de gramáticas. Las gramáticas de contexto
libre son una clase de gramáticas que nos permiten
especificar las reglas de sintáxis para casi todas las
instrucciones de un lenguaje de programación. En este
curso de lenguajes y autómatas los temas principales a
tratar son : Representación finita de un lenguaje.
Expresiones regulares. 3. 4. Gramáticas .
Autómatas. Máquinas de Turing. Caray !! ahora si
parece que me quedó claro el porqué de este curso
de : LyA LENGUAJES y AUTÓMATAS. 1.4 ALFABETO, CADENAS Y
LENGUAJES. El término alfabeto -también llamado
vocabulario o clase caracter- denota a cualesquier conjunto
finito de símbolos. En una computadora estos
símbolos podrían ser los encontrados en el
código ASCII, es decir el conjunto de caracteres ASCII es
un alfabeto. Otros ejemplos: alfabeto binario B = { 0,1} alfabeto
octal O = {0,1,2,3,4,5,6,7} 10

11 Expresiones regulares Una cadena es una secuencia finita de
símbolos tomados de un determinado alfabeto. En el estudio
de los lenguajes, los términos sentencia y palabra son
frecuentemente usados como sinónimos del término
cadena. Para una cadena se definen básicamente dos
operaciones: longitud y concatenación. La longitud de una
cadena s usualmente escrita como |s|, es el número de
ocurrencias de símbolos en s. En la tabla de la fig. 1.9
se muestran algunos ejemplos. Cadena Longitud
_______________________ Hola Autómatas Peras 2 4 9 5 1
_______________________ Fig 1.9 Longitud de cadenas La
concatenación es una operación binaria cuyos dos
operandos son cadenas. Sean cad1 = Hola y cad2 = Todos, la
concatenación de cad1 y cad2 se escribe : cad1 cad2 =
HolaTodos y su longitud es : | cad1 cad2 | = 9. La
concatenación de cad2 y cad1 es : cad2 cad1 = TodosHola y
su longitud es | cad2 cad1 | = 9 Se observa que la
concatenación no es conmutativa ya que : cad1cad2 ?
cad2cad1 Existe una cadena especial, denominada cadena
vacía y se denota con el símbolo ? y su
característica consiste en que su longitud es 0. | ? |=0
11

12 = = = Expresiones regulares La cadena vacía ? es el
elemento identidad bajo la operación de
concatenación. Lo anterior significa que si cad es una
cadena entonces: cad ? = ? cad = cad Ejemplo 1.1 Sean cad1 =
Hola, cad2 = Todos, cad3 = ! . Obtener : (a) cad1 cad3 cad2 (b) ?
cad1 ? cad2 ? = Hola!Todos ? Hola ? Todos ? Hola ? Todos ?
HolaTodos ? = HolaTodos (c) ? ? ? = ? (d) ? ? cad3 ? ? ? cad1 = ?
? ! ? ? ? Hola = ! ? ? ? Hola = !Hola El término lenguaje
denota cualesquier conjunto de cadenas formadas con
símbolos de un cierto alfabeto. Este término suele
ser abstracto, como por ejemplo el lenguaje { ? }, que es el
conjunto cuyo único elemento es la cadena vacía. En
la tabla de la fig. 1.10 se muestran las diferentes operaciones
sobre lenguajes, algunas fundamentales y otras compuestas.
OPERACIÓN DEFINICIÓN Unión L U M L U M = { s
| s está en L ó s está en M }
Concatenación LM Potenciación L i Cerradura L*
Cerradura positiva L + L? L M = { s t | s está en L y t
está en M } L i = L L2 L3 … Li-1 Li L * = Ui=0 8 L i L +
= Ui=1 8 L i L ? = Ui=0 1 L i L * denota “ 0 ó
más concatenaciones de L” L + denota “ 1
ó más concatenaciones de L” L ? denota
“ 0 ó una concatenación de L” Fig 1.10
Operaciones sobre lenguajes 12

13 Expresiones regulares Ejemplo 1.2 Sean los lenguajes A =
{0,1}, B = {a,b,c}, C= {1,2}, obtener : (a) A U B = {0,1}U{a,b,c}
= {0,1,a,b,c} (b) (BC) U A = {a,b,c} {1,2} U {0,1} =
{a1,a2,b1,b2,c1,c2} U {0,1} = {a1,a2,b1,b2,c1,c2,0,1} (c) A* =
{0,1}* = {0,1}0 U {0,1}1 U {0,1}2 U {0,1}3 U … = { ? } U {0,1}
U {0,1}{0,1} U {0,1}{0,1}{0,1} U … = { ?,0,1} U {00,01,10,11} U
{000,001,010,011,100,101,110,111}U… = {
?,0,1,00,01,10,11,000,001,010,011,100,101,110,111,…} (d) (B+ U
C)0 = { ? } (e) (C? A)? = ( {1,2}? {0,1} )? = (( {1,2}0 U {1,2}1
) {0,1} )? = (( { ?} U {1,2} ) {0,1} )? = ( { ?,1,2} {0,1} )? =
{0,1,10,11,20,21}? = {0,1,10,11,20,21}0 U {0,1,10,11,20,21}1 = {
?} U {0,1,10,11,20,21} = { ?,0,1,10,11,20,21} (f) (C U A)+ = (
{1,2} U {0,1} )+ = {1,2,0}+ = {0,1,2}+ = {0,1,2}1 U {0,1,2}2 U
{0,1,2}3 U … = {0,1,2} U {0,1,2}{0,1,2} U {0,1,2}{0,1,2}{0,1,2}
U … = {0,1,2} U {00,01,02,10,11,12,20,21,22} U … =
{0,1,2,00,01,02,10,11,12,20,21,22,000,001,002,…,210,221,222,…
} (C U A)1 ( C U A)2 13 ( C U A)3

14 = = = = = = Expresiones regulares (g) (A U B?) { ?} ( {0,1} U
{a,b,c}? ) { ?} ( {0,1} U ( {a,b,c}0 U {a,b,c}1 ) ) { ?} ( {0,1}
U ( { ?} U {a,b,c} ) ) { ?} ( {0,1} U { ?,a,b,c} ) { ?} {0,1,
?,a,b,c} { ?} { ?,0,1,a,b,c} Uso de términos alfabeto,
cadena, lenguajes y sus LyA operaciones 1.5 REPRESENTACIÓN
FINITA DEL LENGUAJE. En la sección 1.3 hemos revisado el
concepto de token. Los tokens son cadenas de caracteres que
tienen un cierto significado. Por ejemplo el Token Id
(identificadores de variable y constantes en pascal) puede tener
un sin fin de lexemas: iCont, X, asNumCon, sNomAlu, iCalif,
iNum_Elem, A__T, Y11_ZAZ, etc. En escencia, un token representa a
un conjunto finito de cadenas, es decir, un token representa a un
lenguaje. Las cadenas que forman parte de este lenguaje, cumplen
con ciertas reglas. Estas reglas se les denomina patrón.
El patrón que reglamenta a un token, puede especificarse
utilizando expresiones regulares. Las expresiones regulares son
una notación, que nos permite definir de manera precisa,
al conjunto de cadenas que forman el lenguaje representado por un
token. Una expresión regular es construida a partir de
expresiones regulares simples, usando un conjunto de reglas bien
definidas. Un token representa un lenguaje. Una expresión
regular se utiliza para definir a un token. Entonces : LyA
¿ Una expresión regular denota a un lenguaje ?
14

15 Expresiones regulares Una expresión regular r denota a
un lenguaje L(r). Las reglas de definición para una
expresión regular especifican clara y precisamente, como
el lenguaje L(r) es formado o construido, por una
combinación de lenguajes denotados a su vez, por
subexpresiones regulares de r. Reglas para expresiones regulares
válidas sobre un alfabeto S. 1. ? es una expresión
regular que denota al lenguaje { ? } , o sea, el conjunto que
contiene solamente a la cadena vacía. 2. Si a es un
símbolo perteneciente al alfabeto S, entonces a es una
expresión regular que denota al lenguaje { a }, lenguaje
que sólo contiene a la cadena a. 3. Operaciones para
expresiones regulares. Sean r y s dos expresiones regulares que
denotan al lenguaje L(r) y L(s), respectivamente. Entonces: (a)
(r) | (s) es una expresión regular que denota al lenguaje
L(r) U L(s). A esta operación se le conoce como
alternancia. (b) (r) (s) es una expresión regular que
denota al lenguaje L(r) L(s). Operación
concatenación. (c) (r)* es una expresión regular
que denota al lenguaje (L(r))*. Operación cerradura. (d)
(r) es una expresión regular que denota al lenguaje L(r).
Además, tenemos dos operaciones derivadas de las
anteriores : + + (e) (r) es una expresión regular que
denota al lenguaje (L(r)) . Puede expresarse como : r+ = r* r .
(f) (r)? es una expresión regular que denota al lenguaje
(L(r))º U (L(r))¹. Puede expresarse como : r ? = r | ?.
• Un lenguaje denotado por una expresión regular, es
un conjunto regular. LyA 15

16 Expresiones regulares • Podemos en expresiones regulares
seguir ciertas convenciones al evaluar o indicar las operaciones
entre ellas. Nosotros adoptaremos las siguientes: 1 El operador *
tiene la más alta precedencia y es asociativo a la
derecha. 2 La concatenación tiene la segunda más
alta precedencia y es asociativa a la izquierda. 3 La alternancia
tiene la más baja precedencia y es asociativa a la
izquierda. Los paréntesis innecesarios pueden eliminarse
siguiendo estas convenciones, como por ejemplo : (a) | ((b)* (c))
es equivalente a : a | b*c. En la práctica, un token (un
lenguaje) a menudo, es especificado no solamente por una
expresión regular, sino por un conjunto de expresiones
regulares. A este conjunto de expresiones regulares que definen a
un token, se le denomina definición regular. Si S es un
alfabeto de símbolos básicos, entonces una
definición regular es una secuencia de definiciones de la
forma: d1 ? r 1 d2 ? r 2 …. dn ? r n donde cada di tiene un
identificador o nombre distinto a las demás, y cada ri es
una expresión regular sobre los símbolos en : S U
{d1,d2, … ,di-1 }. Hagamos algunos ejemplos, donde
especificaremos tokens (lenguajes) que cumplen con ciertas
características. Ejemplo 1.3. Obtener la definición
regular para el token con las siguientes características:
• Es un número entero (sin signo) par. • El cero
es considerado par. Lexemas: 8, 0, 16, 7772, 14444, 222, 418,
1000, 000, 04, … Dig ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Par ? 0 | 2 | 4 | 6 | 8 NumPar ? ( Dig* ) ( Par )
“Nota” : Emplearemos la notación Dig ? 0 | 1 |
… | 9 que es menos verbosa. El lenguaje representado por NumPar
es la concatenación de Dig* con Par. 16

17 Expresiones regulares NumPar ? Dig* Par Apliquemos la regla 2
y 3(a) para obtener el lenguaje de la expresión regular
Dig : Dig = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } Usaremos la
notación 0-9 para indicar 0, 1, … , 9. Calculamos ahora
Dig* – regla 3(c) – : Dig* = { 0-9 }* = { 0-9 }º U { 0-9
}¹ U { 0-9 }² U { 0-9 }³ U … = { ? } U { 0-9
}¹ U { 0-9 }{ 0-9 } U { 0-9 }{ 0-9 }{ 0-9 } U … = { ?, 0-9
} U { 00-99 } U { 000-999 } U … = { ?, 0-9, 00-99, 000-999, …
} Por último, efectuamos la concatenación – regla
3(b) – : NumPar ? Dig* Par Dig* Par = { ?, 0-9, 00-99, 000-999,
… } { 0, 2, 4, 6, 8 } Aplicamos la regla 2 y 3 (a)
Concatenamos: LyA Todos contra todos Dig* Par = { 0, 2, 4, 6, 8,
00-98, 000-998, 0000-9998, … } O sea, NumPar denota al lenguaje
formado por las cadenas de dígitos que terminan en Par, 0,
2, 4, 6, 8. 17

18 Expresiones regulares Ejemplo 1.4. Repite la
especificación del token NumPar, pero ahora eliminando los
ceros (0) a la izquierda. El cero no es par. Lexemas: 4, 82, 10,
330006, 276, 4564, … La solución se obtiene con una
definición regular que separe: 1) El lenguaje de los pares
de una sola cifra, de donde excluiremos el cero { 2, 4, 6, 8 } y,
2) El lenguaje de los pares con dos o más cifras, y
éstos, si pueden terminar en cero (0) además del 2,
4, 6, 8. ¡Hagámoslo! NumPar ? ParUnaCifra |
ParDosóMásCifras (1.4.1) El lenguaje denotado por
la expresión regular NumPar, es la unión
(alternancia) de los lenguajes producidos por las expresiones
regulares : ParUnaCifra y ParDosóMásCifras, es
decir : L ( NumPar ) = L ( ParUnaCifra ) U L (
ParDosóMásCifras ) Si “uno” los
lenguajes, obtengo el lenguaje : L ( NumPar ) L ( ParUnaCifra ) L
( ParDosóMásCifras) LyA Para que la
definición regular 1.4.1 esté completa, es
necesario definir : ParUnaCifra y ParDosóMásCifras.
La definición de la primera expresión regular es
simple : ParUnaCifra ? 2 | 4 | 6 | 8 Y aplicando la regla 3(a):
18

19 Expresiones regulares L( ParUnaCifra ) = { 2, 4, 6, 8 } Ya
tengo … L(ParUnaCifra) LyA La definición regular para
ParDosóMásCifras consiste de 3 subexpresiones
regulares : ParDosóMásCifras ? ( Dig SinCero)
(Dig)* (Par) donde : DigSinCero ? 1 | 2 | … | 9 Dig ? 0 | 1 |
… | 9 Par ? 0 | 2 | 4 | 6 | 8 // Todos los dígitos menos
el cero. // Todos los dígitos se incluye al cero. //
Dígitos que dan la terminación par. Ahora, podemos
obtener el lenguaje denotado por la expresión regular
ParDosóMásCifras, el cual es la
concatenación de los lenguajes denotados por :
ParDosóMásCifras ? ( DigSinCero ) ( Dig )* ( Par) L
( ParDosóMásCifras ) = { 1, 2, … , 9 }{ 0, 1, 2,
… , 9 }* { 0, 2, 4, 6, 8 } = { 1-9 } ({ 0-9 }º U { 0-9
}¹ U { 0-9 }² U … } ) { 0, 2, 4, 6, 8 } = { 1-9 } ({
? } U { 0-9 }¹ U { 0-9 }{ 0-9 } U … } ) { 0, 2, 4, 6, 8 }
= { 1-9 } { ?, 0-9, 00-99, 000-999, … }{ 0, 2, 4, 6, 8 } pares
2 cifras pares 3 cifras pares 4 cifras … 19

20 ? ? ? Expresiones regulares La concatenación obliga a 2
cifras al menos …. !!!!!!, Ahora, uniré los dos
lenguajes LyA L ( NumPar ) = L ( ParUnaCifra ) U L (
ParDosóMásCifras ) = { 2, 4, 6, 8 } U { 10-98,
100-998, 1000-9998, … } = { 2, 4, 6, 8, 10-98, 100-998,
1000-9998, … } Lo encontré LyA La definición
regular pedida es : Dig DigSinCero Par
ParDosóMásCifras ParUnaCifra NumPar ? ? ? 0 | 1 |
… | 9 1 | 2 | … | 9 0|2|4|6|8 ( Dig SinCero) (Dig)* (Par)
2|4|6|8 ParUnaCifra | ParDosóMásCifras 20

21 Expresiones regulares Ejemplo 1.5. Encontrar una
definición regular para el token que representa al
conjunto de cadenas : Operadores relacionales en el lenguaje C.
Lexemas: CADENA <
1 LONGITUD DE CADENA <= > >= != == 2 1 2 2 2
Símbolos < y = concatenados Símbolos > y =
concatenados Símbolos ! y = concatenados Símbolos =
y = concatenados En este caso la solución es sencilla;
apliquemos la regla 3(a) alternancia y la 3(b)
concatenación: OpRel ? < | <= | > | >= | != |
= = Para comprobar la anterior definición regular,
obtenemos el lenguaje denotado por la alternancia de cada
expresión regular. L (OpRel ) = L ( < ) U L ( <= ) U
L ( > ) U L ( >= ) U L ( != ) U L ( = = ) = {<} U {
<= } U {>} U { >= } U { != } U { = = } = { < , <=,
>, >=, !=, = = } Ohh !! LyA Ejemplo 1.6. Encuentra la
definición regular para el token con las siguientes
características : • Las cadenas empiezan con al menos
un dígito, y terminan en letra. • El último
dígito debe ser par y la primera letra debe ser vocal ( El
cero se considera par ). Lexema: 764a, 6E, 596432izlkam, 11118M,
0Abcxyz, … 21

22 y Expresiones regulares Analizando los lexemas, observamos que
por medio de una concatenación es posible llegar a la
solución. Dicha concatenación tiene como operandos
: la secuencia de dígitos y la secuencia de letras.
Token1.6 ? ( SecDígitos) (SecLetras) (1.6.1) y el lenguaje
denotado por token1.6 es : L (Token1.6) = L ( SecDígitos )
L ( SecLetras ) Concatenación de dos lenguajes LyA
Desglosemos SecDígitos. Esta secuencia de dígitos
termina en par, lo que nos obliga a una concatenación :
SecDígitos ? Dig* Par donde : Dig ? 0 | 1 | … | 9 Par ?
0 | 2 | 4 | 6 | 8 Luego, el lenguaje denotado por
SecDígitos es : L ( SecDígitos ) = (L (Dig))* L
(Par) = {0-9}* {0,2,4,6,8} = { ?, 0-9, 00-99, 000-999, … }
{0,2,4,6,8} // Todos los pares de una o más cifras,
empezando o no, con cero. La secuencia de letras, obliga a una
concatenación de una vocal con cualesquier número
de letras, inclusive ninguna. SecLetras ? ( Vocal ) ( Letras )*
22

23 = = = = ? Expresiones regulares donde : Vocal ? A | a | E | e
| I | i | O | o | U | u Letras ? A | B | … | Z | a | b | … |
z y el lenguaje denotado es : L ( SecLetras ) = L (Vocal) ( L
(Letras) )* {A,a,E,e,I,i,O,o,U,u} {A-Z, a-z} *
{A,a,E,e,I,i,O,o,U,u} ({A-Z, a-z}0 U {A-Z, a-z}1 U {A-Z, a-z}2 U
… ) {A,a,E,e,I,i,O,o,U,u} ( { ? } U {A-Z, a-z} U {A-Z,
a-z}{A-Z, a-z} U … ) {A,a,E,e,I,i,O,o,U,u} { ? ,A-Z,a-z,
AA-ZZ,Aa-Zz,aA-zZ,aa-zz, … } (Letras) 0 (Letras) 1 (Letras) 2
La concatenación obliga al inicio con vocal !!! L yA
Concluímos con la definición regular que
corresponde a la solución : Dig Par Vocal Letras ? ? ? ? 0
| 1 | … | 9 0|2|4|6|8 A|a|E|e|I|i|O|o|U|u A | B | … | Z | a |
b | … | z SecDígitos ? SecLetras ? Token1.6 Dig* Par (
Vocal ) ( Letras )* ( SecDígitos) (SecLetras) 23

24 y = Expresiones regulares Ejemplo 1.7 Encontrar la
definición regular para el token con las siguientes
características : • Números enteros con al
menos una cifra. Lexemas : 10, 0, 5, 476, 11111, 8965, … La
solución es : Ah caray !! Dig ? 0 | 1 | … | 9 NumEnt ?
Dig + LyA Para comprobar, obtenemos : L ( NumEnt ) = = = ( L (
Dig ) ) + {0,1, …,9} + = {0-9} + {0-9} 1 U {0-9} 2 U {0-9} 3 U
… {0-9} U {0-9}{0-9} U {0-9}{0-9}{0-9} U … = {0-9, 00–99,
000-999, … } // cadenas de dígitos con al menos una
cifra. (Dig) 1 (Dig) 2 (Dig) 3 Observa lo que sucede si en lugar
de la cerradura positiva Dig + utilizamos : NumEnt ? Dig * El
lenguaje denotado ahora por la expresión regular NumEnt es
: L ( NumEnt ) = ( L ( Dig ) ) * = {0-9} * = {0-9} 0 U {0-9} 1 U
{0-9} 2 U {0-9} 3 U … = { ? } U {0-9} U {0-9}{0-9} U
{0-9}{0-9}{0-9} U … 24

25 Expresiones regulares = { ?, 0-9, 00–99, 000-999, … }
¿¡¡ Existe un entero sin dígitos o sea,
la cadena vacía .. ?!!! x = 2 + ?? LyA Ejemplo 1.8
Supongamos que hemos obtenido un conjunto de cadenas de un texto.
Algunos de los lexemas representativos de este lenguaje son los
que a continuación se listan. Lexemas : Al953bcz880,
kep17731fgxtp4, opaMKss6204, zz9975ThL02286, … (1) (2) (3) (4)
Encontrar una definición regular que represente a este
lenguaje. Observamos en los lexemas dados de ejemplo, 4
secuencias concatenadas : a) Secuencia de letras ( al menos una
letra ). b) Secuencia de dígitos nones. Esta secuencia
puede o no presentarse en algunos lexemas (lexema 3). c)
Secuencia de letras consonantes, al menos una. d) Secuencia de
dígitos pares, al menos uno. 25

26 ? Expresiones regulares De lo anterior, el token es
especificado con la siguiente definición regular : Letras
Cons Non ? ? ? [A-Za-z] [B-DF-HJ-NP-TV-Zb-df-hj-np-tv-z] // donde
: B-D = B | C | D 1|3|5|7|9 Par ? Token1.8 ? 0|2|4|6|8 ( Letras )
+ ( Non ) * ( Cons ) + ( Par ) + La comprobación del
lenguaje denotado por Token1.8, L ( Token1.8 ), se deja de
ejercicio al alumno. Ejemplo 1.9 Encontrar la definición
regular para especificar el token cuyas características
son las siguientes : • Inicia con al menos una letra y
termina con un caracter que puede ser una vocal o bien, un
dígito par.El cero se considera par. • La letra que
termina la secuencia inicial de letras, es una vocal. •
Entre la secuencia inicial de letras y el último caracter
(vocal o par), puede o no existir una secuencia de al menos un
dígito seguido del caracter : (dos puntos). Si existe la
secuencia intermedia, el último dígito de
ésta, debe ser non. Lexemas : A4, abcdu9961:i, xyEa,
tsqaei7:8, U67103:I, … (1) (2) (3) (4) (5) La definición
regular para este caso, consta de 3 subexpresiones regulares
concatenadas : Token1.9 ( SecLetras ) ( SecIntermedia ) ? (
CaracterTerminación ) Dado que el lenguaje producido por
la expresión regular SecIntermedia puede o no existir, se
utiliza la siguiente operación : SecIntermedia ? ?
SecIntermedia | ? Recordemos : r? = r | ? LyA Veamos la
subexpresión regular SecLetras : 26

27 Expresiones regulares Letras ? A | B | … | Z | a | b | … |
z Vocal ? A | a | E | e | I | i | O | o | U | u SecLetras ? (
Letra ) * ( Vocal ) La concatenación obliga a la
terminación en vocal para las cadenas del lenguaje
denotado por SecLetras, L ( SecLetras ). La expresión
regular CaracterTerminación es simple, y a
continuación se muestra. CaracterTerminación ?
Vocal | Par donde : Par ? 0 | 2 | 4 | 6 | 8 El lenguaje denotado
es : L ( CaracterTerminación ) = L ( Vocal ) U L ( Par ) =
{A,a,E,e,I,i,O,o,U,u} U {0,2,4,6,8} =
{A,a,E,e,I,i,O,o,U,u,0,2,4,6,8} Sólo queda por obtener la
expresión regular SecIntermedia. Sabemos que al menos hay
un dígito y el último debe ser non, por lo que la
condición obliga a una concatenación :
SecIntermedia ? Dig * Non : donde : Non ? 1 | 3 | 5 | 7 | 9 , y
el lenguaje denotado es : L ( SecIntermedia ) = ( L ( Dig ) ) * L
( Non ) L ( : ) = {0-9} * {1,3,5,7,9} { : } = { ?, 0-9, 00-99,
000-999, … } {1,3,5,7,9} { : } (Dig) 0 (Dig) 1 (Dig) 2 (Dig) 3
27

28 ? ? ? ? Expresiones regulares Uniendo a las expresiones
regulares anteriores, tenemos la definición que resuelve
el problema : Letras Vocal Par Dig Non SecLetras
CaracterTerminación SecIntermedia Token1.9 ? ? ? ? ? A | B
| … | Z | a | b | … | z A|a|E|e|I|i|O|o|U|u 0|2|4|6|8 0 | 1 |
… | 9 1|3|5|7|9 ( Letra ) * ( Vocal ) Vocal | Par Dig * Non :
(SecLetras) ( SecIntermedia ) ? (CaracterTerminación) 1.6
EJERCICIOS PROPUESTOS. 1. Identifica los tokens, lexema y
patrón en los siguientes segmentos de código : (a)
function iSuma ( x : real ) : integer; (b) Begin x := y * ( 5 + x
); writeln ( ‘x = ‘, x ); End; (c) puts (
“Hola” ); (d) if ( iNum != 0 ) iNum = iNum * x; 2.
Sean Cad1 = Hola, Cad2 = Todos, Cad3 = !, obtener : (a) (Cad1) ?
(Cad2) ? (Cad3) (b) (Cad3) ? ? (Cad1) ? (c) ? ? ? (d)
¿Cuál es la longitud de las cadenas que resultan de
las anteriores concatenaciones? 28

29 Expresiones regulares 3. Sean los lenguajes A = {0,1}, B =
{a,b,c}, C = {a,1}, obtener : (a) A U B0 U C (b) A2 U C (c) AC? U
B? (d) ( A* ) 0 (e) ( B U C ) ? A? (f) ( A + U { ? } (g) ( C + )
? 4. Sean los lenguajes K = { x,y }, L = { x,2,3 }, M = { ? },
obtener : (a) M* ( K U L ) ? (b) ( L? M + ) ? (c) ( K U M ) ? ( L
M ) (d) ( K ? M ) + 5. Encuentra la expresión regular para
el token con las siguientes características : •
Números con punto decimal, con al menos un dígito
tanto a la izquierda como a la derecha del punto decimal. •
La cifra a la izquierda del punto debe ser non, y la cifra a la
derecha del punto debe ser par. ( El cero es par ). Ejemplos :
5.2, 1137.01, 22689.87771, … 29

30 Expresiones regulares 6. Encuentra la definición
regular para el token con las siguientes características :
• Cadenas de dígitos ( solamente dígitos ),
que empiezan con par y terminan con non. Ejemplos : 81, 476543,
69999927, … 7. Encuentra la definición regular para el
token con las siguientes características : • Empiezan
con cualesquier número de letras ( puede que ninguna ).
• Siguen de las letras, cualesquier número de
dígitos, pero siempre los últimos dos son el 2 y el
1. Ejemplos : AB21, 999921, klmxab1111121, … 8. Encuentra la
definición regular para el token con las siguientes
características : • Empieza con letra consonante y
termina en vocal, o bien empieza con vocal y termina en
consonante. • Entre las dos letras de inicio y fin puede o
no existir una cadena de dígitos que empiezan con 2 o 3 y
terminan en 6 o 9. Ejemplos : ka, E21118766h, z333445969u, is,
… 9. Encuentra una definición regular para el token con
las siguientes características : • Inicia con @
(arroba) seguido de comillas “, y termina con vocal. O
bien, inicia con apóstrofe ‘ y termina con
consonante. • En ambos casos puede o no existir una
secuencia intermedia que puede o no iniciar con dígitos
seguidos de al menos una letra y terminando siempre en un
dígito non. 30

31 Expresiones regulares Ejemplos : @”A, @”765abc9E,
‘xyz5K, ‘6a7m, @”kl9A, … 10. Encuentra la
definición regular para el token con las siguientes
características : • Inicia con vocal o con
dígito par, y le sigue siempre un 6. • Termina en un
caracter que puede ser las comillas “ o el caracter @.
• Entre el inicio ( después del 6 ) y el final (
antes de “ o @ ) se intercala – a veces no existe una
secuencia de dígitos que empieza con non y termina con
non. Esta secuencia puede tener uno o más dígitos.
Ejemplos : A63”, 46”, 8634765@, E6155687”, u6@,
i61111”, … 31