I. INTRODUCCIÓN. ˇHola!, bienvenido al uso del programa PS1. Este programa es una herramienta desarrollada para ayudarte en el estudio de 2 materias : “Lenguajes y Autómatas” y “Programación de Sistemas I”. Inicialmente, este manual te indicará el uso de Ps1 como auxiliar didáctico tanto para la enseńanza como para el aprendizaje de los siguientes temas del curso de “Lenguajes y Autómatas” : • Expresiones regulares. • Reglas de Thompson. • Algoritmo de construcción de subgrupos. • Algoritmo de particiones. • Gramáticas. El uso de Ps1 como auxiliar didáctico para el curso de “Programación de Sistemas I”, se trata en otro documento. Ps1 es un programa que te facilita la edición de expresiones regulares, y su compilación según las reglas descritas en el libro del dragón : “COMPILADORES, Principios, técnicas y herramientas”, con autores Aho, Sethi y Ullman. Una vez que has editado y compilado una expresión regular, puedes visualizar la descomposición sintáctica que efectuó Ps1 (en forma de parejas token-lexema) para reconocer cada expresión regular que compone tu definición regular. Realmente esta característica, sólo es útil si tú eres profesor o bien, si eres alumno te servirá como ejemplo de estudio para el tema de analizadores sintácticos que se incluye en la materia de “Programación de Sistemas I” y que seguro te llamará la atención. Recuerda que a un conjunto de expresiones regulares se le denomina una definición regular, y ésta denota a un lenguaje regular. Los tokens son secuencias de caracteres con un cierto significado semántico. Por ejemplo el token id puede tomar los lexemas siguientes en un segmento de código : iCont, iNum, sNoCon, fPromedioGrupo. Un token situado en el contexto de un lenguaje de programación, es un lenguaje cuyas cadenas cumplen con un cierto patrón. Este patrón generalmente es definido utilizando una definición regular, es decir, utilizando un conjunto de expresiones regulares. Las definiciones regulares en su construcción siguen una serie de reglas bien específicas. Ps1 usa esta serie de reglas para compilar tu definición regular. Además Ps1 ańade otras reglas que deberás respetar para lograr que tus definiciones regulares puedan ser compiladas de manera exitosa. Todo lo anterior se te explica en el capitulo II. En el capítulo III verás cómo es generado un autómata finito no determinístico, para cada una de tus expresiones regulares que conforman la definición regular 1
que editaste y compilaste. Este autómata finito no determinístico AFND es construído por Ps1, usando las reglas de THOMPSON. El formato empleado por Ps1 para dibujar estos autómatas es .BMP , por lo que fácilmente podrás agregarlos a un documento Word ya sea directamente o bien, utilizando un editor de imágenes (Paint por ejemplo) donde podrás personalizar el autómata producido por Ps1. Puedes también modificar los colores de los componentes del autómata además del tamańo del bitmap donde es dibujado el autómata. El AFND construído empleando las reglas de THOMPSON es visualizado a colores y en blanco y negro según hayas seleccionado en la opción correspondiente. Además, Ps1 dibuja un AFND por cada expresión regular que hayas editado y compilado de manera exitosa. Ps1 te proporciona la opción de obtener el autómata finito determinístico AFD, a partir del autómata finito no determinístico AFND –reglas de THOMPSON-. El capítulo IV describe los pasos que deberás seguir para obtener lo siguiente : • Dibujo en un formato .BMP del autómata finito determinístico. • Descripción paso a paso del algoritmo de construcción de subgrupos utilizado para construir dicho autómata AFD. Ps1 te da la facilidad de poder incluir texto para documentar cada etapa de este algoritmo. • Visualización de los componentes del AFD. También puedes incluir texto para documentar el reporte de componentes. • Tabla de transición –función move- del AFD. Se incluye el grupo de estados del AFND correspondiente a cada estado del nuevo AFD. • Facilidad de cambiar el color del autómata. Ya sea el texto o el dibujo logrado en cualquiera de las funciones anteriores, puedes manipularlo para insertarlo en un documento de Word, un documento HTML, etc. El capítilo V es dedicado a explicarte la manera en que puedes obtener el autómata finito determinístico óptimo o reducido. Este AFD reducido o mínimo en cuanto al número de estados que lo componen, Ps1 lo construye usando el algoritmo de particiones sucesivas. La visualización del dibujo del AFD reducido, de los componentes del AFD reducido, de su tabla de transición ,son tareas que puedes consultar en este capítulo V. Además puedes grabar en disco, el dibujo del AFD reducido para posteriormente utilizarlo en la construcción de analizadores léxicos. Por último, puedes utilizar Ps1 para editar y compilar gramáticas. Ps1 te visualiza los componentes de la gramática que editaste y su descomposición sintáctica. También te permite derivar a la izquierd
| Página siguiente |