1
Download Taller de POSIX - Web del Profesor
Transcript
Teoría de la Computación y Leguajes Formales Expresiones Regulares, POSIX Prof. Hilda Y. Contreras Departamento de Computación [email protected] 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.
