Download Taller de POSIX - Web del Profesor

Teoría de la Computación y
Leguajes Formales
Expresiones Regulares, POSIX
Prof. Hilda Y. Contreras
Departamento de Computación
hyelitza@ula.ve
http://webdelprofesor.ula.ve/ingenieria/hyelitza
Contenido
• Jerarquía de Chomsky
• Relación de ER con los Autómatas
finitos y los lenguajes regulares
• Implementación de Expresiones
regulares – Autómatas finitos
• Ejemplos de aplicación con:
– Lenguajes de programación
– Herramientas de procesamiento de
Expresiones regulares
Jerarquía de Chomsky
Tipo
Lenguaje
Máquina
Gramática G = (V,T,P,S)
0
Recursivamente
enumerable
Máquina de
Turing
Gramática sin restricciones
αÎβ
(α, β en (V U T)*, α contiene una
variables)
1
2
Dependiente del
Contexto
Independiente
del Contexto
Autómata
linealmente
acotado
Gramática sensible al contexto
αÎβ
Autómata de
Pila
Gramática libre de contexto
AÎα
(α, β en (V U T)*, α contiene una
variables, |β| ≥ |α|)
(A en V y α en (V U T)*)
3
Lenguaje
Regular
Autómata
finito
Gramática Regular
A Î aB
AÎa
(A,B en V y a en T)
Relación ER – AF
AFN-ε
AFN
1
ER
AFD
2
Autómata Finito
Expresión Regular
Reconocer, Verificar
Describir, Expresar
Relación ER - Lenguaje
Σ={0,1}
Expresión Regular
Φ
ε
0
1
01
0+1
0*
Lenguaje
{}
{ε}
{0}
{1}
{0}{1} = { 01}
{0} U {1} = { 0, 1}
{ε,0,00,000,0000, ….}
Implementación de ER
• Implementación de Expresión Regular ≠
Definición formal de ER
• No es mas poderosa la implementación que la
definición (continua reconociendo el mismo tipo
de lenguajes)
• Implementación de ER es mas cómoda,
reducida y funcional
• p.e.: Lenguaje = { loco, loca, locaa, locaaa }
ER teórica = loco + loca.(ε + a + aa)
ER implementación = loc(o|a|aa|aaa)
ER implementación(POSIX) = loc(o|a{1,3})
Implementación de ER
• POSIX Portable Operating System Interface (X
viene de UNIX)
• Proyecto de normalización de API
• POSIX Regular Expressions (básico y extendido)
• GNU Regular Expression Extensions (The Open
Group en Single Unix Specification)
• Actualmente usando en muchos lenguajes de
programación, sistemas y aplicaciones
Referencias:
• http://www.regular-expressions.info/posix.html
• http://www.regular-expressions.info/gnu.html
Implementación de ER
• POSIX
ER-formal
+ unión (a+b)
. concatenación (a.b)
* clausura (a*)
ER-POSIX
| alternancia (a|b)
(ab) ó ab
* repite cero o más a
Implementación de ER
• POSIX básico
POSIX
Descripción
.
Cualquier carácter excepto fin de línea
^
Comienzo de la cadena | negación de conjuntos
[]
Lista o clases de símbolos: [abc] Conjunto {a,b,c}
[^abc] Conjunto Σ - {a,b,c}
[0-9] Rangos del 0 al 9, todos los digitos
$
Final de la cadena
\
Escape (no considera la expresión siguiente)
Implementación de ER
• POSIX extendido
POSIX
Descripción
r+
1 o mas ocurrencias de r
r?
0 o 1 ocurrencia de r
r{n}
n ocurrencias de r
r{n,}
n o mas ocurrencias de r
r{,m}
0 o a lo sumo m ocurrencias de r
(r)
r evaluada con prioridad | caracteres de salida con
variable $n
“r”
no interpretar los símbolos de r
Implementación de ER
• POSIX extendido
POSIX
Descripción
digitos
\d
\w
Caracter alfabetico
\s
Caracteres alfanumericos
\r | \n
Salto de linea
\t
Tabulación
• Las mismas variables en MAYÚSCULAS (\D) se
utilizan para la negación, éstas deben ser utilizadas
fuera de los corchetes [].
Implementación de ER
POSIX: Los metacaracteres: ?, +, {, |, (, y ) deben ser
escapados cuando se quieren usar como caracteres
normales, escribiendo \?, \+, \{, \|, \(, y \).
Ejemplos:
• ^.*$
• [0-9]?
• [0-9]{3} = \d*{3}
• [^&]+
• [0-9][0-9]* = [0-9]+
• . = [^\n]
Tester de ER:
http://www.metriplica.com/4_4_herramientas.asp
Implementación de ER
Lenguajes de programación:
• Procesar cadenas de caracteres (código
más legible, corto, útil, fácil de mantener)
• Ejemplos: Delphi, Gnulib, Java,
JavaScript, .NET, PCRE, Perl, PHP,
Python, REALbasic, Ruby, Tcl, VBScript,
Visual Basic 6, XML Schema, XLST
Ejemplo de ER en Lenguajes de
programación
<?php
/* Podemos pasar un patrón con subpatrones agrupados en parentesis.
Si en este caso usamos ereg, podemos añadir un tercer parámetro:
el nombre de un array que almacenará las ocurrencias; $array[1]
contendrá la subcadena que empieza en el primer paréntesis
izquierdo; $array[2] la que comienza en el segundo, etc. $array[0]
contendrá una copia de la cadena.
*/
$date = "24-09-2003"; // pasamos una fecha formato dd-mm-yyyy
if (ereg ("([0-9]{1,2})-([0-9]{1,2})-([0-9]{4})", $date, $mi_array)) {
echo "$mi_array[3].$mi_array[2].$mi_array[1]"; // coincide. Lo
mostramos en orden inverso
} else {
echo "Invalid date format: $date"; // no coincide
}
?>
Implementación de ER
Herramientas:
• Usan expresiones regulares como entrada
para su funcionalidad
• Ejemplos:
– grep (Global Regular Expression and Print)
– egrep, awk, emacs
– Lex (GNU flex)
Implementación de ER
ER permite:
• Describir de forma breve y formal un lenguaje
regular
• Como ER tiene un equivalente en AF entonces
también permite reconocer
w en Σ*
ER
Conversor
AF
Acepto o
NO acepto
= Herramientas, Lenguajes de programación
Referencias: http://osteele.com/tools/reanimator/
Implementación ER
LEX o GNU flex
• Programa que genera analizadores léxicos para
expresiones regulares
• Lex: estándar en los sistemas Unix y usa POSIX
• Lex toma como entrada una especificación
(incluye ER) y devuelve como salida el código
fuente del analizador léxico en lenguaje C.
Referencias:
http://flex.sourceforge.net/ (flex)
http://sourceforge.net/projects/jflex/ (Java flex)
Implementación de ER
Ejemplo:
• J. F. Quesada y J. G. Amores (2000).
“Diseño e Implementación de sistemas de
traducción automática”. Universidad de
Sevilla.
– Analizador léxico con Lex aplicado al
problema del Procesamiento del Lenguaje
Natural
Aplicaciones
Acciones de aplicación:
• Analizador léxico (compiladores,
interpretadores, navegadores, lenguaje
natural, etc.)
• Procesamiento de textos (búsqueda,
clasificación, sustituciones, conversión,
etc.)
En cualquier área de aplicación!
Implementación de ER
Práctica: Dado un texto
1. Reconocer una fecha en formato dd-mm-aaaa,
invertir el orden a aaaa/mm/dd con una expresión
regular
p.e.: [0-9]{1,2}-[0-9]{1,2}-[0-9]{4}
detecta 15-05-2009
2. Buscar un número IP válido *
3. Buscar una dirección de email, imprimir el nombre
de usuario
4. Buscar una dirección web válida (URL), imprimir el
dominio (ve, com, org…)
5. Buscar un “literal númerico” con puntos cada 3
posiciones en la parte entera, y parte decimal.