Unidad 2 - Expresiones Regulares.2.1. Definicin formal de una
ER.Es un equivalente algebraico para un autmata. Utilizado en
muchos lugares como un lenguaje para describir patrones en texto
que son sencillos pero muy tiles. Pueden definir exactamente los
mismos lenguajes que los autmatas pueden describir: Lenguajes
regulares. Ofrecen algo que los autmatas no: Manera declarativa de
expresar las cadenas que queremos aceptar.Dado un alfabeto Dado un
alfabeto , una , expresin regular sobre expresin regular sobre se
define de forma recursiva: ER primitivas:, , {a | a} Si y son ER,
entonces son tambin ER: + (unin), (concatenacin), * (cierre), ().
No existen otras reglas para la construccin de ER sobre .Ejemplos
de usos. Comandos de bsqueda, e.g., grep de UNIX. sistema de
formato de texto: Usan notacin de tipo expresin regular para
describir patrones. Convierte la expresin regular a un DFA o un NFA
y simula el autmata en el archivo de bsqueda. Generadores de
analizadores - Lxicos. Como Lex o Flex. Los analizadores lxicos son
parte de un compilador. Dividen el programa fuente en unidades
lgicas (tokens) divide el programa fuente en unidades. Produce un
DFA que reconoce el token.Las expresiones regulares denotan
lenguajes.Por ejemplo, la expresin regular: 01* + 10* denota todas
las cadenas que son o un 0 seguido de cualquier cantidad 1's o un 1
seguida de cualquier cantidad de 0's.Operaciones de los lenguajes:
Unin: Si L y M son dos lenguajes, su unin se denota por LUM.
Concatenacin: La concatenacin es: LM o L.M. Cerradura (o cerradura
de Kleene): Si L es un lenguaje su cerradura se denota por L *.Si E
es una expresin regular, entonces L(E) denota el lenguaje que
define E. Las expresiones se construyen de la manera siguiente: Las
contantes y son expresiones regulares que representan a los
lenguajes L (Q) = {Q} y L () L =respectivamente. Si a es un smbolo,
entonces es una expresin regular que representan al lenguaje: L (a)
= {a}.2.2. OperacionesUnin o Alternativa:Consideremos dos lenguajes
diferentes definidos sobre el mismo alfabeto L1W() y L2W(). Se
denomina unin de ambos lenguajes al lenguaje formado por las
palabras de ambos lenguajes: L1 U L2={ x | xL1
xL2}Concatenacin:Consideremos dos lenguajes definidos sobre el
mismo alfabeto, L1 y L2. La concatenacin o producto de estos
lenguajes es el lenguaje L1 L2= { xy / xL1 y xL2} Las palabras de
este lenguaje estarn formadas al concatenar cada una palabra del
primero de los lenguajes con otra del segundo.La concatenacin de
lenguajes con el lenguaje vaci esL = L =
Potencia de un lenguaje:Se define la potencia i-sima de un
lenguaje a la operacin de concatenarlo consigo mismo i veces. Li=
LLL ....L |------------| iClausura positiva de un lenguaje:Se
define la clausura positiva de un lenguaje L: L + = U L i
i=1Lenguaje obtenido uniendo el lenguaje con todas sus potencias
posibles excepto L. Si L no contiene la palabra vaca, la clausura
positiva tampocoCierre o Clausura de un lenguaje:Se define el
cierre o clausura de un lenguaje L como :L*=ULi=0Lenguaje obtenido
uniendo el lenguaje con todas sus potencias posibles, incluso L.
Todas las clausuras contienen la palabra vaca.Existen tres
operaciones bsicas que se pueden realizar sobre las ER: Seleccin de
alternativas :Se indica con el operador |(barra vertical). Si r y s
son ER, entonces r | s es una ER que define a cualquier cadena que
concuerde con una r o una s, tambin se dice que r | s , es la unin
de los lenguajes de r y s y lo podemos definir: L( r | s ) = L( r )
U L( s ). Esta operacin se puede extender a ms de dos ER.
Concatenacin:Se indica con la yuxtaposicin de las ER. Si r y s son
ER, entonces rs es una ER que define a cualquier cadena que
concuerde con la concatenacin de r y s , esta operacin la podemos
definir: L(rs) = L(r)L(s).Esta operacin se puede extender a ms de
dos ER.Repeticin o Cerradura:Tambin se conoce con el nombre de
cerradura de Kleene. Se indica con el operador*. Si r es una ER,
entonces r* es una ER que define a las cadenas de caracteres
representadas por la concatenacin repetida de r en n veces, o sea
que lo podemos definir como: L(r*) = L(r)*o tambin lo podemos
definir como la unin infinita de conjuntos r :r* n = r 0 r 1 r
2...r n.2.3 Aplicaciones en problemas reales.Una de las principales
aplicaciones de los hermanos Deitel, son las expresiones regulares
que facilitan la construccin de un compilador. A menudo se utiliza
una expresin regular larga y compleja para validar la sintaxis de
un programa. Si el cdigo del programa no concuerda con la expresin
regular, el compilador sabe que hay un error de sintaxis dentro del
cdigo.Generalmente convierten la expresin regular a un autmata
finito no determinista y despus construyen el autmata finito
determinista.Otra aplicacin del mismo libro es en los editores de
texto. Tambin encontramos a las expresiones regulares en la biologa
molecular. Tambin hay esfuerzos importantes para tratar de
representar cadenas como generadas por expresiones regulares o por
lenguajes regulares.
Unidad 2: Expresiones Regulares
Competencia especfica a desarrollarActividades de
Aprendizaje
Crear y reconocer ER mediante un lenguaje de programacin o un
analizador lxico.
Investigar las expresiones regulares y sus operaciones. Generar
cadenas a partir de una expresin regular. Obtener una expresin
regular a partir de un grupo de cadenas o visceversa. Obtener una
expresin regular a partir de la descripcin de un caso de estudio.
Elaborar por equipo, el reconocimiento de expresiones regulares
mediante un lenguaje de programacin o un analizador lxico.
Investigar las expresiones regulares y sus
operaciones.OperacionesUnin o Alternativa:Consideremos dos
lenguajes diferentes definidos sobre el mismo alfabeto L1W() y
L2W(). Se denomina unin de ambos lenguajes al lenguaje formado por
las palabras de ambos lenguajes: L1 U L2={ x | xL1
xL2}Concatenacin:Consideremos dos lenguajes definidos sobre el
mismo alfabeto, L1 y L2. La concatenacin o producto de estos
lenguajes es el lenguaje L1 L2= { xy / xL1 y xL2} Las palabras de
este lenguaje estarn formadas al concatenar cada una palabra del
primero de los lenguajes con otra del segundo.La concatenacin de
lenguajes con el lenguaje vaci esL = L = Potencia de un lenguaje:Se
define la potencia i-sima de un lenguaje a la operacin de
concatenarlo consigo mismo i veces. Li= LLL ....L |------------|
iClausura positiva de un lenguaje:Se define la clausura positiva de
un lenguaje L: L + = U L i i=1Lenguaje obtenido uniendo el lenguaje
con todas sus potencias posibles excepto L. Si L no contiene la
palabra vaca, la clausura positiva tampocoCierre o Clausura de un
lenguaje:Se define el cierre o clausura de un lenguaje L como : L*
= U Li i=0Lenguaje obtenido uniendo el lenguaje con todas sus
potencias posibles, incluso L. Todas las clausuras contienen la
palabra vaca.Existen tres operaciones bsicas que se pueden realizar
sobre las ER: Seleccin de alternativas :Se indica con el operador
|(barra vertical). Si r y s son ER, entonces r | s es una ER que
define a cualquier cadena que concuerde con una r o una s, tambin
se dice que r | s , es la unin de los lenguajes de r y s y lo
podemos definir: L( r | s ) = L( r ) U L( s ). Esta operacin se
puede extender a ms de dos ER. Concatenacin:Se indica con la
yuxtaposicin de las ER. Si r y s son ER, entonces rs es una ER que
define a cualquier cadena que concuerde con la concatenacin de r y
s , esta operacin la podemos definir: L(rs) = L(r)L(s).Esta
operacin se puede extender a ms de dos ER.Repeticin o
Cerradura:Tambin se conoce con el nombre de cerradura de Kleene. Se
indica con el operador*. Si r es una ER, entonces r* es una ER que
define a las cadenas de caracteres representadas por la
concatenacin repetida de r en n veces, o sea que lo podemos definir
como: L(r*) = L(r)*o tambin lo podemos definir como la unin
infinita de conjuntos r :r* n = r 0 r 1 r 2...r n.
Generar cadenas a partir de una expresin regular.El generador
Expresin regular permite generar cadenas que coincidan con un
modelo determinado.Puede usar este generador con cualquier columna
de datos que tenga un tipo de datos que acepte una cadena.Estos
tipos de datos
sonchar,varchar,varchar(max),text,nchar,nvarchar,nvarchar(max),ntext,sysnamey
tipos definidos por el usuario que se basan en estos tipos.Tambin
puede usar el generador Expresin regular con tipos definidos por el
usuario de CLR.El generador Expresin regular no puede garantizar
valores nicos.Por tanto, no estar disponible para las columnas que
requieran valores nicos.Para usar el generador de datos Expresin
regular en una columna, debe especificarlo en el recuadro de los
detalles de columna de la ventana del plan de generacin de
datos.Tras especificar el generador Expresin regular, debe
establecer la propiedadExpressionen la ventanaPropiedades.La
propiedadExpressioncontiene el modelo con el que deben coincidir
los datos.Para obtener ms informacin, veaEspecificar detalles de la
generacin de datos para una columna.
Obtener una expresin regular a partir de un grupo de cadenas o
visceversa.
ExpressionDescripcin
(F|M)Representacin simple del gnero.
[1-9][0-9]{2,2}-[1-9][0-9]{2,2}-[0-9]{4,4}Nmero de telfono
simple, representado como 800-555-8446
\+1 (425|206)-[1-9][0-9]{2,2}-[0-9]{4,4}Notacin internacional
para un nmero de telfono de la zona de Seattle.
[1-9][0-9]{4}-[0-9]{4}Cdigo postal ms cuatro (como
98008-2405)
[1-6]{1}[0-9]{1,3} (SE|NE|NW|SW) [1-2]{1}[0-9]{1,2}th
(ST|CT|PL|AVE), (Redmond, WA 9805[0-9]|Bellevue, WA
9800[1-9]|Sammamish, WA 9807[0-9]|Seattle, WA 9806[0-9]|Issaquah,
WA 9808[0-9])Direccin postal sencilla.
Seattle|(New York)|Boston|Miami|Beijing|(Los
Angles)|London|ParisLista de nombres de ciudades.
[a-z]{5,8}@(hotmail\.com|msn\.com|[a-z]{3,8}\.(com|net|org))Direccin
de correo electrnico simple.
[1-9][0-9]{3} [0-9]{4} [0-9]{4} [0-9]{4}Nmero de tarjeta de
crdito.
Obtener una expresin regular a partir de la descripcin de un
caso de estudio.
Elaborar por equipo, el reconocimiento de expresiones regulares
mediante un lenguaje de programacin o un analizador lxico.
JavaJava es un lenguaje de programacin orientado a objetos,
fuertemente tipado, independiente de la plataforma (write once, run
everywhere) que ejecuta sobre una mquina virtual.Al igual que en
Javascript, escribir una expresin regular literalmente en lugar de
obtenerla posteriormente de un campo de texto o de una funcion,
implicar tener que hacer un doble escapado de la para que se
considere expresin regular. De esta forma, si utilizamos una
variable String para guardar la expresin regular y la ponemos a
pelo, o si ponemos el texto directamente en el constructor,
necesitaremos hacer un doble escapado (recordamos que para
representar el caracter necesitaremos poner \\).Por otra parte, a
diferencia de Javascript (que no es Java, para evitar la tpica
equivocacin), en Java usaremos ms de un objeto para utilizar las
expresiones regulares. En este caso sern dos clases:ClasePattern:
define una expresin regular compilada. Para poder construir un
objeto de la clase Pattern haremos lo siguiente:1Pattern regex =
Pattern.compile("^(\w+)@(\w+)\.([a-zA-z]{2,6})$");
ClaseMatcher: define un objeto que va a intentar encajar la
expresin regular en una cadena por medio de varias funciones. Para
crear un objeto de esta clase necesitamos un Pattern ya creado. De
forma que:1Pattern regex =
Pattern.compile("^(\w+)@(\w+)\.([a-zA-z]{2,6})$");
2Matcher matcher =
regex.matcher("[email protected]");
Una vez tenemos esto, llega el momento de ver las funciones que
se usan para encajar expresiones regulares. Bsicamente tendremos
dos funciones para poder hacer esto:Funcinmatches(): esta funcin es
parte del objetoMatcher. Intenta encajar la expresin regular en la
cadena de forma absoluta. En otras palabras, en caso de que
nuestroPatternno tuviera los smbolos ^ y $, iba a actuar como si
los tuviera. Devuelve un boolean. Veamos un ejemplo:1Pattern regex
= Pattern.compile("(\w+)@(\w+)\.([a-zA-z]{2,6})");
2Matcher matcher =
regex.matcher("[email protected]");
3System.out.println(matcher.matches());
4// output: true
5
6Pattern regex =
Pattern.compile("(\w+)@(\w+)\.([a-zA-z]{2,6})");
7Matcher matcher = regex.matcher("basura
[email protected] basura");
8System.out.println(matcher.matches());
9// output: false
Funcinfind(): esta funcin es tambin parte del objetoMatcher.
Intenta encajar la expresin regular en alguna parte de la cadena.
Al contrario quematches(), si el Pattern no contiene los smbolos de
inicio y final, no los inserta. Devuelve un boolean tambin. Cuando
utilizamos esta funcin, el objeto de la clase Matcher guarda la
posicin en la que consigui encajar el patrn, de forma que podremos
usar las funcionesstart(),end()ygroup()para acceder a la posicin
inicial donde encaj, la posicin final y la cadena que encaj,
respectivamente. Veamos el ejemplo anterior con esta
funcin:1Pattern regex = Pattern.compile("(\w+)");
2Matcher matcher =
regex.matcher("[email protected]");
3while(matcher.find())
4System.out.println(matcher.group());
5/* output:
6test
7vidasconcurrentes
8com
9*/
10
11Pattern regex =
Pattern.compile("(\w+)@(\w+)\.([a-zA-z]{2,6})");
12Matcher matcher =
regex.matcher("[email protected]");
13System.out.println(matcher.find());
14// output: true
15
16Pattern regex =
Pattern.compile("(\w+)@(\w+)\.([a-zA-z]{2,6})");
17Matcher matcher = regex.matcher("basura
[email protected] basura");
18System.out.println(matcher.find());
19// output: true
Existe una forma rpida de ejecutar estas lneas en una sola, de
forma que compilamos unPatterny sobre l aplicamos la
funcinmatches()directamente sin crear el objeto. Esta forma es
relativamente buena si, primero no vamos a querer reutilizar la
expresin regular (hay que fijarse en que podemos sacar
variosMatcherde un mismoPattern), y segundo si lo que queremos es
encajar una cadena entera, y no partes internas slo. La
claseMatcherpermite resetear la cadena que guarda (tambin las
posiciones que ha encajado confind()y de esta forma ahorrar
movimiento al recolector de basura, para ello se usan las
funcionesreset()yreset(nuevaCadena). Veamos un ejemplo bastante
simple para esta forma rpida de
encajar:1System.out.println(Pattern.matches("(\w+)@(\w+)\.([a-zA-z]{2,6})","[email protected]"));
2// output: true
3
4System.out.println(Pattern.matches("(\w+)@(\w+)\.([a-zA-z]{2,6})","basura
[email protected] basura"));
5// output: false
Por otra parte existe una forma de reemplazar texto en una
cadena utilizando una expresin regular, pero de una forma un poco
enrevesada. Para esto vamos a usar las
funcionesappendReplacement()yappendTail().Por una parte vamos a ir
recorriendo nuestra cadena buscando el patrn y cuando lo encajemos
vamos a guardarlo en unString. Una vez hayamos acabado de recorrer
la cadena, vamos a poner todo el contenido de esteStringen
elMatcherpara realmente hacer efectiva la sustitucin. Hagamos una
variante del ejemplo que mostramos anteriormente en
Javascript:1Pattern patron = Pattern.compile("(\w+)");
2Matcher matcher =
patron.matcher("[email protected]");
3
4StringBuffer sb =newStringBuffer();
5matcher.find();
6
7// reemplazamos solo la primera
8matcher.appendReplacement(sb,"prueba");
9matcher.appendTail(sb);
10
11System.out.println(sb.toString());
12// output: [email protected]
Por otra parte podemos aplicar modificadores a la expresin
regular como hicimos en Javascript cong,i,m,s. En el siguiente
ejemplo mostramos como hacer el ejemplo de encajar una cadena sin
distinguir maysculas de minsculas:1Pattern patron =
Pattern.compile("([a-z]+)", Pattern.CASE_INSENSITIVE);
2Matcher matcher =
patron.matcher("[email protected]");
3
4StringBuffer sb =newStringBuffer();
5while(matcher.find())
6// reemplazamos todo, no solo la primera
7matcher.appendReplacement(sb,"prueba");
8matcher.appendTail(sb);
9
10System.out.println(sb.toString());
11// output: [email protected]
