Expresiones regulares (página 2)

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