II. Instituto Tecnológico de la Laguna en Torreón Coah. México. 3 EXPRESIONES REGULARES. En este capítulo te mostraré las reglas que debes observar para la edición y compilación de definiciones regulares. Iniciaré por indicarte cómo se traduce una definición regular hecha en clase –en el pintarrón ó en el cuaderno-, para que pueda ser reconocida como válida por Ps1. Seguiremos con las tareas de edición, almacenamiento-salvar- y compilación de una expresión regular. Después te mostraré con ejemplos los errores más comunes encontrados cuando Ps1 compila una definición regular. 2.1 REGLAS PARA CONSTRUCCIÓN DE EXPRESIONES REGULARES. Debes de observar las siguientes reglas cuando construyas un conjunto de expresiones regulares : 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). En la siguiente tabla 2.1 se ańaden otra reglas muy importantes, que debes considerar cuando edites tu conjunto de expresiones regulares. Expresión c c “s” . [s] [c-c] [^s] r* r+ r? r1 r2 r1 | r2 (r) Descripción cualesquier caracter no operador el caracter c literalmente la cadena s literalmente cualesquier caracter excepto el nueva línea cualesquier caracter en s Indica un rango ejo. [A-Z] cualquier letra mayúscula. cualesquier caracter no perteneciente a s cero o mas r’s uno o mas r’s cero o una r concatenación r1 con r2 alternancia r1 con r2 r Tabla 2.1 Reglas en la edición de expresiones regulares. 3
Instituto Tecnológico de la Laguna en Torreón Coah. México. 4 Para denotar una expresión regular utiliza el siguiente patrón : • Empieza con una letra, seguida de 0 o mas letras y/o digitos y/o caracter de subrayado. • El identificador que denota a la expresión regular lo debes de encerrar – delimitar- entre llaves. Ejo. 2.1 Supongamos que queremos denotar el lenguaje de todas las letras mayúsculas : {Letras} -> A | B | C | D | … | X | Y | Z Observa que el identificador Letras lo hemos encerrados entre llaves. Además, de aquí podemos concluir que la sintáxis que debes seguir para construir una expresión regular es la siguiente : {IdExprReg} -> Expresión Donde : es el operador de definición de expresiones regulares, Expresión es cualquier combinación de las reglas mencionadas al inicio de esta sección y {IdExprReg} es el identificador de la expresión regular. En la práctica las alternancias como la anterior A | B | C | D | … | X | Y | Z, no son aceptadas por Ps1, es decir Ps1 no acepta el operador … en una expresión. Lo anterior te lleva a inferir que debes de incluir a todas las letras o símbolos – mayúsculas para el ejemplo– que formen parte de una alternancia. Claro que no es recomendable hacerlo así, Ps1 soporta la notación subrango. El ejemplo lo podrás realizar como se ilustra a continuación : {Letras} -> [A-Z] Ejo. 2.2 Obtener la definición regular para denotar el lenguaje representado por todos los identificadores que inicien con al menos una letra, seguidos de cualquier número de letras y/o dígitos y/o caracter de subrayado. Letras -> A | B |… | Z | a | b | … | z Digitos -> 0 | 1 | 2 | … | 8 | 9 Sub -> _ Id -> Letras ( Letras | Digitos | Sub ) * La anterior es la definición regular que denota el lenguaje del token Id. Debes utilizar las reglas para identificadores de expresiones regulares y para rangos o subrangos. La definición que deberás introducir a la computadora será : {Letras} -> [A-Za-z] {Digitos} -> [0-9] 4
Instituto Tecnológico de la Laguna en Torreón Coah. México. 5 {Sub} -> _ {Id} -> {Letras} ( {Letras} | {Digitos} | {Sub} ) * En la práctica los identificadores son reconocidos hasta que se encuentre un caracter diferente a letra, a digito y al subrayado. Agrega una expresión concatenada al final de la expresión dada para el token Id. {Id} -> {Letras} ( {Letras} | {Digitos} | {Sub} ) * [^A-Za-z0-9_] Operador ^ de exclusión Ejo. 2.3 Escribe una definición regular para los operadores relacionales en C. La expresión regular puedes presentarla como : OpRel -> < | <= | > | >= | != | == En la aplicación Ps1 se introducirá : {OpRel} -> [<>!=] = | [<>] [^=] żPor qué no es válida la siguiente expresión? {OpRel} -> [<>!=] =? Ejo 2.4 Veamos la definición regular que aparece en el libro del dragón para el token num : Digito -> 0 | 1 | … | 9 Digitos -> Digito Digito * FraccionOpcional -> . Digitos | ? ExponenteOpcional -> ( E ( + | – | ? ) Digitos ) | ? Num -> Digitos FraccionOpcional Exponente Opcional Aquí debemos tener cuidado con las expresiones que contienen el punto . , el + y el -, ya que los tres son operadores que indican operaciones sobre expresiones regulares. En este caso representan el símbolo por si mismos, únicamente. Debes ańadir el símbolo antes del caracter según lo indica la 2da. regla de la tabla 2.1. Además debes eliminar el uso del caracter ? utilizando la propiedad ?, ya que Ps1 no acepta dicho caracter. La definición regular debes escribirla mas o menos así : {Digito} -> [0-9] {Digitos} -> {Digito} {Digito} * 5
Instituto Tecnológico de la Laguna en Torreón Coah. México. 6 {FraccionOpcional} -> ( . {Digitos} ) ? {ExponenteOpcional} -> ( [Ee] [+-] ? {Digitos} ) ? {Num} -> {Digitos} {FraccionOpcional} {ExponenteOpcional} 2.2 EDITANDO UNA DEFINICIÓN REGULAR. Para entrar al proceso de edición de un conjunto de expresiones regulares, debes de considerar si es una definición regular nueva o bien ésta ya existe. 1. Si es una definición regular nueva selecciona los items del menú Archivo | Nuevo. Ps1 te responde con una ventana de edición como es mostrado en la figura 2.1 : Fig. 2.1 Nueva edición. 2. Si el archivo donde se encuentra la definición regular ya existe, selecciona los items del menú Archivo | Abrir . Ps1 te muestra la caja de diálogo para abrir archivos según se te muestra en la Fig 2.2 . Ya que hayas seleccionado el archivo con extensión .exr Ps1 te responde con la ventana de edición con la definición regular en ella, Fig. 2.3. 6
Instituto Tecnológico de la Laguna en Torreón Coah. México. 7 Fig. 2.2 Cuadro de diálogo para abrir expresiones regulares. Fig. 2.3 Ventana para edición de expresiones regulares. 7
Instituto Tecnológico de la Laguna en Torreón Coah. México. 8 2.3 SALVANDO UNA DEFINICIÓN REGULAR. Una vez que hayas editado un conjunto de expresiones regulares, estarás interesado en guardar tu información para posteriores referencias. Puedes hacerlo fácilmente usando la selección de los items Archivo | Salvar como ó Archivo | Salvar. Nota : Debes guardar tus archivos que contienen las definiciones regulares en el mismo directorio en que reside el programa ejecutable Ps1. Esta restricción vive con la primera versión de Ps1. Ps1 te mostrará el CUADRO DE DIÁLOGO Salvar como según se ilustra en la Fig. 2.4. La extensión que debes considerar en el nombre del archivo es .exr. Si no la incluyes en el nombre, Ps1 te la ańade por omisión. Fig. 2.4 Cuadro de diálogo Salvar como. 2.4 COMPILANDO UNA DEFINICIÓN REGULAR. La compilación de una definición regular es tarea muy sencilla. Sólo debes asegurarte que antes de compilar hayas salvado tu definición regular si ésta en nueva. Cada vez que salves tu ventana de edición, estas asegurando que la opción de compilación se habilite. Entonces para compilar tu definición regular sólo selecciona del menú principal los items Expr Regulares | Compilar. Si no has cometido ningún error en la construcción de la definición regular obtendrás un cuadro de mensaje donde se te indica que la compilación ha sido exitosa, fig. 2.5. Si hubieras incurrido en errores, Ps1 te visualiza el primer error que encuentre, fig. 2.6. Deberás corregirlo y volver a compilar. Este proceso se repetirá hasta que Ps1 no encuentre más errores en tu ventana de edición. 8
• Instituto Tecnológico de la Laguna en Torreón Coah. México. 9 Fig. 2.5 Aviso de Ps1 al efectuar una compilación exitosa. Fig. 2.6 Mensaje de error al compilar una expresión regular. 2.5 ERRORES COMUNES AL CONSTRUIR EXPRESIONES REGULARES. ERROR 3. Falta de la llave inicial que delimita al identificador de la expresión regular. Veamos la definición regular para el token Id : {Dig} -> [0-9] Letra} -> [A-Za-z] {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] En la línea 2 el identificador de la expresión regular no inicia con el símbolo {. Ps1 responde al compilar con el mensaje de error de la fig. 2.7. Fig. 2.7 ERROR 3: token no conocido. 9
• • Instituto Tecnológico de la Laguna en Torreón Coah. México. 10 ERROR 4. Falta de la llave que termina al identificador de una expresión regular. Ahora quitemos la segunda llave y dejemos la primera en la expresión regular del token Id. {Dig} -> [0-9] {Letra -> [A-Za-z] {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] Ps1 responde con el mensaje de error de la fig. 2.8. Fig. 2.8 ERROR 4. Falta de }. El mismo mensaje es exhibido por Ps1 cuando insertas antes de la llave final o entre el propio identificador, uno o mas caracteres de espacio. Haz la prueba anadiendo un espacio antes de la llave en la línea dos : {Dig} -> [0-9] {Letra } -> [A-Za-z] // o bien {L etra} -> [A-Za-z] Inserción de un espacio antes de la llave final {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] ERROR 9. Falta de las dos llaves que delimitan al identificador de una expresión regular. Ahora quitemos las dos llaves en la línea dos de la definición regular para el token Id. Ps1 visualiza el cuadro de diálogo de error de la fig. 2.9. {Dig} -> [0-9] Letra -> [A-Za-z] {Sub} -> _ 10
• • Instituto Tecnológico de la Laguna en Torreón Coah. México. 11 {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] Fig. 2.9 ERROR 9. Falta de las dos llaves en el identificador de una expresión regular. ERROR 2. Identificador mal construido. Este error –fig. 2.10- se presenta cuando después de la primera llave del identificador de una expresión regular, anades uno o mas espacios. Veamos lo siguiente : {Dig} -> [0-9] { Letra} -> [A-Za-z] Inserción de uno o mas blancos después de la primera llave {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] Fig. 2.10 ERROR 2. Identificador mal construido. ERROR 10. Falta del operador ->. Este error ocurre cuando después del identificador de la expresión regular olvidas anadir el operador ->, o bien cuando lo construyes mal, es decir si insertas un espacio entre el – y el >, o bien te falta alguno de ellos, fig. 2.11. 11
• Instituto Tecnológico de la Laguna en Torreón Coah. México. 12 {Dig} -> [0-9] {Letra} [A-Za-z] Falta del operador -> {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] {Dig} -> [0-9] {Letra} – > [A-Za-z] Espacio entre los dos símbolos del operador -> {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] {Dig} -> [0-9] {Letra} > [A-Za-z] Falta de uno de los dos símbolos del operador -> {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] Fig. 2.11. ERROR 10. Falta de operador -> ERROR 5. Falla en la construcción de una cadena. Este error sucede cuando olvidas iniciar una cadena con el símbolo de comillas “. 12
• Instituto Tecnológico de la Laguna en Torreón Coah. México. 13 Por ejemplo : {Hijo} -> MIGUEL” Ps1 responderá con el mensaje de la figura 2.12. Fig. 2.12. ERROR 5. Falla en la construcción de la cadena. ERROR 8. Error de sintáxis. Un ejemplo de error de sintáxis es cuando fala el caracter “ en la terminación de una cadena, fig. 2.13. Fig. 2.13 ERROR 8. Error de sintáxis. Otro ejemplo es cuando falta un corchete delimitador de expresiones de rango. Observa la línea 2 del ejemplo para el token Id. Ps1 responde a la falta de corchete con el mensaje de error 8, fig. 2.14. {Dig} -> [0-9] {Letra} -> [A-Za-z // {Letra} -> A-Za-z] Falta de corchete en la expresión de rango. {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] 13
• {Letra} -> A-Za-z] • {Letra} -> A-Za-z] Instituto Tecnológico de la Laguna en Torreón Coah. México. 14 Fig. 2.14 ERROR 8. Error de sintáxis falta de corchete. ERROR 7. Falta de caracter en car. Cuando usas la regla de caracter en forma literal car y que olvidas teclear el caracter después del símbolo , Ps1 te responde con el mensaje de error 7, fig. 2.15. Observa las siguientes líneas : {Dig} -> [0-9] Falta el caracter después del símbolo {Sub} -> _ {Id} -> {Letra} ( {Letra} | {Dig} | {Sub} ) * [^_A-Za-z0-9] Fig. 2.15. ERROR 7. Falta de caracter en car. ERROR 11. Expresión regular no definida. Este error es muy común. Se presenta cuando usas un identificador de una expresión regular en el miembro derecho de una definición, siendo que aún no la habías definido en renglones previos. Por ejemplo, observa la línea 4 de la definición regular para el token Id : {Dig} -> [0-9] Expresión regular no definida, fig. 2.16 {Sub} -> _ {Id} -> {Letra} ( {Letr} | {Dig} | {Sub} ) * [^_A-Za-z0-9] 14
Instituto Tecnológico de la Laguna en Torreón Coah. México. 15 Fig. 2.16. ERROR 11. Expresión regular no definida. 15
III. Instituto Tecnológico de la Laguna en Torreón Coah. México. 16 REGLAS DE THOMPSON –AFND-. Existen un conjunto de reglas que permiten obtener el autómata finito no determinístico a partir de una definición regular. Se les denominan reglas de Thompson. Estas reglas son fáciles de aplicar y como son rigurosas –formales-, son susceptibles de ser tratadas por un programa de computadora. Ps1 te proporciona la característica de lograr el AFND dado que has editado y compilado una definición regular, según lo visto en el anterior capítulo. Las reglas de Thompson son explicadas en el capítulo III págs 106 a 128, correspondientes al volúmen 2 del manual técnico. En las siguientes secciones te ilustraré acerca de visualización en pantalla del AFND construido en base a las reglas de Thompson, de la conmutación entre pantallas de edición de la definición regular y de visualización del autómata finito no determinístico, además de cómo resolver el problema de un mal dibujo del autómata cuando las dimensiones del bitmap no soportan al total del AFND. También te mostraré cómo seleccionar los colores del AFND según tu agrado. 3.1 OBTENCIÓN DEL AFND. Una vez que Ps1 ha detectado que una definición regular ha sido compilada sin errores, habilita las opciones del menú Autómatas | Thompson(AFND). Selecciona este par de items del menú para obtener el dibujo del AFND construído aplicando las reglas de Thompson, fig. 3.1. En la figura 3.1 sólo es visto el autómata final, es decir el autómata que reconoce la definición regular {Id} -> {Letra} ( {Letra} | {Digito} | {Sub} ) * [^A-Za-z0-9_]. Ps1 ańade el autómata según las reglas de Thompson para cada línea que compone a la definición regular. Para que veas lo anterior mencionado, sólo navega con las barras de desplazamiento sobre el dibujo del autómata. El dibujo del autómata se despliega sobre una superficie de 1000 x 1000 pixeles. Hay ocasiones en que esta superficie no es suficiente para desplegar el dibujo de un autómata. Cuando ésto suceda, el autómata no será dibujado de manera correcta y será necesario que modifiques las dimensiones de la imágen en la que es dibujado el autómata. Esta modificación es tratada en las siguientes secciones. 3.2 CONMUTACIÓN ENTRE VENTANA DE EDICIÓN Y VENTANA DE DIBUJO DEL AFND. Frecuentemente es necesario observar los cambios que produce una edición de cierta definición regular, en el AFND de Thompson. Luego de ver el AFND, volver a la edición para corregir o salvar los cambios. Esta conmutación entre las ventanas de edición y de dibujo del autómata, es lograda de una manera muy sencilla. Sólo debes hacer un doble click sobre la superficie de la ventana donde te encuentres y cambiarás a la otra ventana. dobleclick Ventana de edición dobleclick Ventana de dibujo del AFND 16
Instituto Tecnológico de la Laguna en Torreón Coah. México. 17 Fig. 3.1 AFND para la definición regular Id. 3.3 MODIFICACIÓN DE LAS DIMENSIONES DEL BITMAP DEL AFND. Ahora veremos lo que sucede en ocasiones en que la definición regular produce un AFND cuyas dimensiones son mayores a las tomadas por Ps1 por omisión (10000 x 1000 pixeles), y el dibujo del AFND es mutilado por Ps1. Edita la siguiente definición regular, la cual es la resolución del problema propuesto No. 10 del capítulo I página 32 del manual técnico volúmen II. {Vocal} -> [AaEeIiOoUu] {Par} -> [02468] {IniAux} -> {Vocal}| {Par} {Inicio} -> {IniAux} 6 {Fin} -> " | @ {Non} -> [13579] {Dig} -> [0-9] {SecAux} -> {Non} {Dig}* {Non} | {Non} {SecInter} -> {SecAux} ? {Prob10} -> {Inicio} {SecInter} {Fin} Este problema viene en el disco que incluye ejemplos de Ps1, en el archivo Prob10.exr. 17
Instituto Tecnológico de la Laguna en Torreón Coah. México. 18 Selecciona los items Autómatas | Thompson(AFND) y navega con la barra de desplazamiento vertical hasta el último autómata. ˇA verdad!!?? … seguramente ya te habrás percatado que el dibujo del autómata está mutilado o no se alcanza a visualizar en su totalidad, fig.3.2. Fig. 3.2 Dimensiones del bitmap no suficientes. Ps1 te permite manipular AFND con dimensiones hasta de 2000 x 2000 pixeles. Para aumentar la dimensión del bitmap selecciona los items del menú Opciones | Mapa de bits AFND. Ps1 te contesta con la caja de diálogo de la fig 3.3. Teclea en la dimensión de altura el valor de 2000. Ahora Ps1 te visualiza el AFND en un bitmap con dimensiones 1000 x 2000. El dibujo del AFND ahora no tendrá errores y puedes visualizarlo navegando con las barras de desplazamiento vertical y horizontales, fig. 3.4. 3.4 SELECCIÓN DE COLORES DEL AFND. Es posible que efectúes cambio en el color de los diferentes componentes del dibujo de un AFND. Los items del menú que te permiten realizar lo anterior son las mismas que para cambiar la dimensión del bitmap, Opciones | Mapa de bits AFND.Observa la figura 3.3 en su parte izquierda. Puedes seleccionar el color de los arcos, etiquetas de los arcos, círculos y números de los estados, y de la descripción de la expresión regular. 18
Instituto Tecnológico de la Laguna en Torreón Coah. México. 19 Fig. 3.3 Caja de diálogo para cambio de dimensiones en el bitmap. Fig. 3.4 AFND con correción en dimensiones. 19
Instituto Tecnológico de la Laguna en Torreón Coah. México. 20 IV. ALGORITMO DE CONSTRUCCIÓN DE SUBGRUPOS AFD. El algoritmo de construcción de subgrupos toma como entrada un autómata finito no determinístico AFND para construir un autómata finito determinístico AFD. Ambos reconocen el mismo lenguaje. El algoritmo es descrito ampliamente en el capítulo III del manual técnico volúmen II páginas 129 a 157. En las secciones de este capítulo te diré como obtener el dibujo del AFD, el texto del algoritmo de construcción de subgrupos paso a paso, la tabla de transición del nuevo AFD y la correspondencia de cada estado del AFD con los estados del AFND, así como los componentes del nuevo AFD. 4.1 OBTENCIÓN DEL NUEVO AFD, TABLA DE TRANSICIÓN, ALGORITMO DE CONSTRUCCIÓN DE SUBGRUPOS Y COMPONENTES. Son muy simples los pasos que debes seguir para tener en pantalla el dibujo del autómata finito determinístico que corresponde a un AFND que es obtenido previamente de una edición de una definición regular. Ya que Ps1 ha detectado la orden de dibujar el AFND según Thompson, habilita la opción de Subgrupos (AFD) del menu autómatas. Selecciona estos dos items del menú y Ps1 te visualizará una nueva ventana, fig. 4.1. Fig. 4.1 Ventana de funciones AFD de Ps1. 20
Instituto Tecnológico de la Laguna en Torreón Coah. México. 21 La nueva ventana tiene en su encabezado la expresión regular sobre la cual se construye el autómata finito no determinístico, y por consiguiente éste será el AFND al que se le aplicará el algoritmo de construcción de subgrupos. Puedes visualizar las dos ventanas a la vez tal y como se te muestra en la figura 4.2, seleccionando los items del menu Ventanas | Mosaico. Fig. 4.2 Mosaico de ventanas AFND y AFD. Ahora sólo haz un click sobre el primer botón al extremo izquierdo de la ventana para AFD’s, Fig 4.3.El algoritmo de construcción de subgrupos se muestra en la misma ventana. Sólo haz un click sobre el segundo botón de izquierda a derecha de la nueva ventana del AFD, fig. 4.3. La tabla de transición la obtienes haciéndo un click sobre el tercer botón de izquierda a derecha de la ventana del AFD, fig. 4.4. Por último, haciéndo un click sobre el cuarto botón de velocidad situado de izquierda a derecha en la ventana del nuevo AFD, podrás visualizar los componentes del nuevo autómata finito determinístico, fig. 4.4. 21
Instituto Tecnológico de la Laguna en Torreón Coah. México. 22 Fig. 4.3. Dibujo del AFD y algoritmo de construcción de subgrupos 22
Instituto Tecnológico de la Laguna en Torreón Coah. México. 23 Fig. 4.4 Tabla de transición y componentes del AFD. 23
Instituto Tecnológico de la Laguna en Torreón Coah. México. 24 V. ALGORITMO DE PARTICIONES – AFD REDUCIDO-. El AFD que se deriva de un AFND a partir de una definición regular, puede ser eficientizado en cuanto al número de estados que lo conforman. El algoritmo de particiones es útil para reducir el número de estados de un autómata finito determinístico. En las páginas 157 a 171 del manual técnico se describen varios ejemplos de la utilización de este algoritmo para reducir autómatas. Ps1 te proporciona la facilidad con sólo hacer un click, de obtener el dibujo del AFD reducido, sus componentes, su nueva tabla de transición y el texto del algoritmo paso a paso. Asimismo puedes grabar la tabla de transición del AFD reducido y el dibujo de dicho autómata, para después utilizarlo en el ensamble de analizadores léxicos, facilidad que el mismo paquete didáctico Ps1 te brinda para el curso de Programación de Sistemas I. Ahora sólo haz un click sobre el sexto botón de izquierda a derecha de la ventana para AFD’s, Fig 5.1.El algoritmo de particiones se muestra en la misma ventana. Sólo haz un click sobre el séptimo botón de izquierda a derecha de la nueva ventana del AFD, fig. 5.1. La tabla de transición la obtienes haciéndo un click sobre el octavo botón de izquierda a derecha de la ventana del AFD, fig. 5.2. Por último, haciéndo un click sobre el noveno botón de velocidad situado de izquierda a derecha en la ventana del nuevo AFD, podrás visualizar los componentes del nuevo autómata finito determinístico reducido, fig. 5.2. Para grabar el AFD reducido debes de hacer un click sobre el botón que tiene un diskette como imágen –décimo botón-. Ps1 te responderá con el mensaje siguiente : Si no has derivado el AFD reducido y quieres grabarlo, Ps1 te muestra el siguiente mensaje de error : 24
Instituto Tecnológico de la Laguna en Torreón Coah. México. 25 Fig. 5.1 AFD reducido y algoritmo de particiones. 25
Instituto Tecnológico de la Laguna en Torreón Coah. México. 26 Fig. 5.2 Tabla de transición y componentes del nuevo AFD reducido. 26
Instituto Tecnológico de la Laguna en Torreón Coah. México. 27 VI. GRAMÁTICAS. Ps1 te permite editar y compilar gramáticas de contexto libre con recursividad a la izquierda o recursividad a la derecha. Una vez compilada una gramática puedes usar Ps1 para efectuar una derivación a la izquierda o a la derecha de una sentencia previamente definida. Ps1 también te encuentra y visualiza los componentes de la gramática. 6.1 EDICIÓN Y COMPILACIÓN DE UNA GRAMÁTICA. La edición de una gramática la haces tal y como lo viste en el capítulo de definiciones regulares. Sólo debes cuidar de grabar tu gramática con la extensión .gra, cuando salves tu edición, fig.6.1. Fig. 6.1 La gramática tiene una extensión .gra. Una vez que grabas una gramática, puedes compilarla si asi lo deseas. Cuando salvas la gramática Ps1 te habilita las opciones del menú Gramáticas | Compilar. Si no tienes errores Ps1 te responde con el siguiente mensaje, fig. 6.2 : Fig. 6.2 Éxito en la compilación de una gramática. 27
Instituto Tecnológico de la Laguna en Torreón Coah. México. 28 6.2 COMPONENTES DE UNA GRAMÁTICA. Selecciona los items del menú Gramáticas | Operaciones y tendrás una nueva ventana, fig. 6.3. Fig. 6.3 Ventana de operaciones sobre gramáticas. Puedes visualizar la gramática agrupada haciéndo un click sobre el primer botón de la nueva ventana para las gramáticas. Las producciones una a una –gramática desagrupada-, las puedes ver con un click sobre el segundo botón de la ventana. Los componentes de la gramática los tienes si haces un click sobre el tercer botón en la ventana de gramáticas. Lo anterior se muestra en las figuras 6.4 y 6.5. 6.3 DERIVACIÓN A LA IZQUIERDA Y A LA DERECHA DE UNA SENTENCIA. Para utilizar Ps1 como herramienta para efectuar una derivación de una sentencia, debes primero indicarle el tipo de derivación que vas a emplear. Haciéndo un click sobre el quinto botón de la ventana de gramáticas, tendrás la oportunidad de seleccionar el tipo de derivación, fig. 6.6. La derivación podrás realizarla en la ventana que obtienes si haces un click sobre el cuarto botón en la ventana de las gramáticas, fig. 6.7. 28
Instituto Tecnológico de la Laguna en Torreón Coah. México. 29 Fig. 6.4 Gramática agrupada y desagrupada. 29
30 Instituto Tecnológico de la Laguna en Torreón Coah. México. 30 Fig. 6.5 Componentes de la gramática. Fig. 6.6 Tipo de derivación
Instituto Tecnológico de la Laguna en Torreón Coah. México. 31 Fig. 6.7 Derivación a la izquierda de una sentencia. 31
| Página siguiente |