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 |