2 Expresiones regulares Palabras clave : expresiones regulares, definiciones regulares, cerradura, alternancia, concatenación, alfabeto, lenguajes, autómatas. 1.1 ¿ PORQUÉ LENGUAJES ?. Seguramente has escuchado, leído, o bien comentado acerca del “procesamiento electrónico de datos”, término que se utiliza para denotar al hecho de efectuar ciertas operaciones, tareas, desde simples hasta complicadas, teniendo como medio o herramienta una computadora, Fig. 1.1. Datos Datos de Entrada x, y COMPUTADORA (a) COMPUTADORA de Salida ?x+y? (b) No. de control Nombre Calif. parciales Calif. final de n alumnos para m grupos de r carreras COMPUTADORA COMPUTADORA Reporte estadístico del índice de aprobación de las r carreras en cierto instituto Período escolar (c ) Fig. 1.1 (a) Proceso electrónico de datos (b) Proceso electrónico de datos, relativamente simple (c) Proceso electrónico de datos, con operaciones mayores en cantidad y dificultad. 2
3 Expresiones regulares Hagamos la siguiente pregunta: ¿Cómo realiza la computadora, las operaciones citadas en la Fig. 1 (b) y (c) ?. Obviamente, tanto la obtención de la raíz cuadrada del valor absoluto de dos datos de entrada X y Y, como del reporte estadístico, representan un problema y éste es enfrentado, aplicando un algoritmo adecuado para su solución. Los algoritmos son introducidos a la computadora en forma de programas, Fig. 1.2. Algoritmo . . . . . . . . leer x leer y T1 = x + y T2 = | x + y | Z = sqrt(T2) COMPUTADORA Fig. 1.2 Programas. Asimismo , un programa está formado de un conjunto de instrucciones escritas (codificadas) en un cierto lenguaje de programación. Estas instrucciones manipulan los datos de entrada, (los reciben, los procesan), para convertirlos en información -“datos de salida”-. Y .. ¿ ésto ? ¿ Para qué me sirve ? !!! LyA 3
4 Expresiones regulares Así, el proceso electrónico de datos conlleva a la utilización de un computadora como recurso. La computadora requiere de programas y éstos a su vez, son entidades compuestas de instrucciones y datos, que se codifican en un determinado lenguaje de programación, Fig. 1.3. Proceso Electrónico de Datos Uso de Computadora Construcción de Programas Lenguaje de Programación Fig. 1.3 . La computadora como recurso en el P.E.D. Ahhh … LENGUAJES LyA Nuestro estudio comprenderá, la teoría formal para especificar, representar, definir y reconocer lenguajes de cualesquier naturaleza. Especialmente, nuestro interés serán los lenguajes de programación. ¿ Y los AUTÓMATAS ? LyA 4
5 Expresiones regulares 1.2 COMPILACIÓN. Supongamos que utilizamos un cierto lenguaje para expresarnos. Cualquier lenguaje en la construcción de las sentencias (instrucciones), requiere de observar ciertas reglas, denominadas reglas de sintáxis. Si no respetamos las reglas de sintáxis del lenguaje, nuestras sentencias pueden no ser entendidas, es decir, estamos cometiendo errores al hacer uso de ese lenguaje. Los compiladores son programas que se encargan de la tarea de revisar si un programa (programa fuente) de computadora, codificado (escrito) en un determinado lenguaje de programación, está libre de errores. Si así es, el compilador a su salida, nos proporciona un programa objeto, que generalmente es la traducción del programa fuente a código ensamblador o bien, un código ejecutable; de lo contrario nos informa con mensajes, de los errores encontrados, fig. 1.4. PROGRAMA FUENTE Compilador PROGRAMA OBJETO MENSAJES DE ERROR Fig. 1.4 Función del compilador. Vaya, vaya ! … Y luego qué ?? LyA 5
6 Expresiones regulares 1.3 ¿ PORQUÉ AUTÓMATAS ? El proceso de compilación de un programa se efectúa en dos fases: análisis y síntesis, fig. 1.5. Representación intermedia del programa fuente Programa fuente ANÁLISIS Errores SÍNTESIS Errores Programa objeto Fig. 1.5 Fases de un compilador. La fase de análisis tiene como entrada, el programa fuente. En base a este programa fuente, la fase de análisis construye una representación intermedia, ¿de quién?… pues del programa fuente, precisamente. En la fase de síntesis se toma de entrada a esta representación intermedia, para la generación del código que constituye al programa objeto. Pues no veo nada de los AUTÓMATAS. LyA Ocupémonos de la fase de análisis. La fase de síntesis no tiene relevancia para efectos de este curso. El análisis que toma al programa fuente como entrada, consiste a su vez de tres fases: 6
7 1. Análisis léxico. 2. Análisis sintáctico. 3. Análisis semántico.Expresiones regulares Programa Fuente ANÁLISIS LÉXICO ANÁLISIS SINTÁCTICO ANÁLISIS SEMÁNTICO hacia generación de código tokens árbol de parse intermedio Fig. 1.6 Fases de análisis de un compilador. La tarea principal del análisis léxico consiste en leer de izquierda a derecha, el programa fuente. El programa fuente es la entrada al analizador léxico y generalmente, reside en un a
| Página siguiente |