Lenguajes De Programación, 2da Edición - Doris Appleby-freelibros.pdf [1q7jdkzxyxqv] (2024)

Sólo fines educativos - FreeLibros

(5.3.5)

244

PARTE II:

Lenguajes imperativos

Las variables permanentes se mantienen a través de cada invocación del monitor. De este modo, un monitor, como un objeto, tiene un estado. Los procesos pueden llamar las operaciones de un monitor del mismo modo que se haría una llamada a procedimiento. Las variables permanentes se pueden accesar sólo a través de estas llamadas. Dos operaciones, además de las definidas en el monitor, están asociadas con cada monitor. Éstas son delay y continué, que son análogas a las del semáforo Wait y Signal. Un monitor también tiene una cola en la que almacena las solicitudes para accesos. De esta forma, la ejecución de un delay (retraso) implica un proceso en cola, y continué (continuación) extrae de la cola el primer proceso en espera y le permite entrar al monitor. Un monitor puede ser visto como un módulo [Parnas, 1972], con la mayoría de los detalles ocultos al usuario. Su implementación también estará oculta en el siste­ ma operativo, de modo que los usuarios se comportarán como si cada uno fuera el único proceso en ejecución. Un uso antiguo de los monitores fue el que se le dio en uno de los sistemas de tiempo compartido BASIC. Los usuarios del BASIC interactivo no se ejecutan en paralelo, sino uno a la vez, compartiendo un solo CPU. Sus procesos eran suspendidos o se les permitía ejecutarse con el uso de ope­ raciones de monitor asociadas con dos colas, una para los procesos suspendidos y otra para los procesos terminados. Éstos también se incluyen en voto Concurrent Pascal y en Modula. Ben-Ari [Ben-Ari, 1982] demuestra que los monitores pueden ser reemplaza­ dos por semáforos, excepto para la suposición primero en entrar, primero en salir (FIFO, por sus siglas en inglés) en las colas del monitor. Cuando se usa semáforos, lo que el proceso haga a continuación será aleatorio más que ordenado. Pero la -decisión de utilizar un monitor o un semáforo por lo general depende de lo que tenga disponible el programador. El beneficio principal de los monitores radica en la claridad y confiabilidad del sistema que los emplea, no en su operación.

Rendezvous (Punto de reunión) El punto de reunión o rendezvous incluye la sincronización, comunicación y eje­ cución de un bloque de código en uno, dos o más procesos que se ejecutan de manera concurrente. Coordina lo que se conoce como llamadas de procedimiento re­ moto (RPCs; remóte procedure calis); es decir, un procedimiento que se ejecuta en un procesador remoto llama a uno que se localiza en un procesador diferente. El pro­ cedimiento o función que llama es un cliente del procedimiento o función que acep­ ta, el cual se conoce como el servidor. Cada tipo de rendezvous en un proceso de servidor se denomina una transacción. Esta palabra es una sugerencia de lo que ocurre en realidad. Un cliente envía un mensaje hacia un servidor al cual solicita servicio de alguna clase y es bloqueado de ejecución adicional hasta que el servicio se realiza. Un rendezvous puede implementarse con o sin memoria compartida. El rendezvous difiere de un monitor en dos formas fundamentales. La prime­ ra, no es un módulo separado que coordina procesos en ejecución, sino que se con­ sigue a través de los procesos mismos. Un proceso (el cliente) inicia una llamada, y otro (el servidor) la acepta. La llamada es procesada por el servidor, que recibe Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

245

cualquier parámetro transmitido mediante la llamada y devuelve valores de pará­ metro hacia el cliente. La segunda forma en la que difiere es que un proceso (llamado una tarea o task en Ada) puede incluir varias entradas (entry), que otros procesos pueden llamar. Cada entrada (entry) mantiene su propia cola de solicitudes, mientras que un monitor tiene sólo una cola. Un proceso que gana el acceso a un monitor puede llamar cualquiera de sus procedimientos, mientras que un proceso que solicita un rendezvous debe obtener en la cola cada entrada que necesite. Además del lenguaje de producción Ada, los rendezvous están implementados en CSP (Communicating Sequential Processes; procesos secuenciales de comuni­ cación), un lenguaje experimental para explorar las facilidades de la programación concurrente, y en Concurrent C.

Paso de mensajes El paso de mensajes involucra dos asuntos: cómo son designados las fuentes y los destinos y en qué forma son sincronizados los procesos. Una fuente y un destino definen un canal de comunicaciones. La designación más simple es el nombrado directo; es decir, enviar datos a un receptor o recibir datos de un emisario; aquí "receptor" y "emisario" son los nombres de los procesos. Cuan­ do múltiples procesos envían o reciben mensajes en un momento dado, puede ser necesario el almacenamiento intermedio o temporal (buffering) para mantener un mensaje hasta que un proceso de recepción esté listo para él. Un almacén temporal (buffer) de este tipo con frecuencia es llamado un buzón (mailbox). En el caso parti­ cular en el cual sólo existe un receptor pero muchos emisarios, el buzón se conoce como un puerto (port). Un programa particular puede involucrar varios puertos, pero un acuse de recibo designará un solo puerto. La idea aquí es que todas las solicitudes para un servicio particular vayan a un solo buzón o puerto. Otra noción de canal es la de una tubería (pipe), en la que la salida de un proceso es entubada o dirigida como la entrada hacia otro. Ambos procesos pueden estar ejecutándose de manera concurrente, con el segundo proceso recibiendo la entrada de la tubería a medida que la produce el primer proceso. Sin embargo, las tuberías fluyen sólo en un sentido. Ya examinamos la noción de rendezvous, en el cual los mensajes pue­ den enviarse en cualquier dirección. La sincronización del paso de mensajes difiere de aquella para recursos com­ partidos puesto que no es necesario mantener secciones o regiones críticas. Inclu­ so, un proceso que reciba un mensaje debe estar listo para recibirlo, o el proceso que lo envía debe esperar hasta que el receptor esté listo para procesarlo. La espera por lo regular se administra mediante una o varias colas. Existen cuatro modelos básicos de paso de mensajes: Punto a punto. La técnica más simple de paso de mensajes consiste en invo­ lucrar un proceso que envía un mensaje hacia otro, el cual lo recibe. Algunos lenguajes, como SR y Concurrent C, estipulan recepción condicional. Por ejem­ plo, una solicitud en Concurrent C para abrir un archivo, si no está protegido, puede codificarse como sigue [Bal, 1989]: Sólo fines educativos - FreeLibros

246

PARTE II:

Lenguajes

im p e r a t iv o s

accept open (f) suchthat no t _ l o c k e d t f )

C ...proceso abrir co dificado aqui...

} Si el archivo está protegido, la solicitud no será aceptada. Los esquemas punto a punto son simétricos si el proceso que llama así como el que recibe se nom­ bran entre sí. El esquema anterior es asimétrico porque el receptor no nombra al emisario. En este caso, un emisario el cual solicita que un archivo sea abierto está dispuesto a que esto se realice por cualquier proceso que sea capaz de hacerlo así. Los mensajes punto a punto pueden pasarse en forma sincrónica o asincrónica. En el paso sincrónico, el proceso de envío es bloqueado hasta que el receptor está listo para aceptarlo. Si el paso es asincrónico, el emisor conti­ núa la ejecución aun cuando su mensaje no haya sido aceptado. En un sistema sincrónico puede haber sólo un mensaje pendiente de cualquier proceso, mien­ tras pueda haber hasta ahora varios mensajes por ser contestados desde un emisario asincrónico. Occam, el lenguaje ensamblador para trasponedores y un lenguaje derivado de CSP, pasa los mensajes de manera sincrónica; por otro lado, NIL (Network Implementation Language; lenguaje de implementación de red) es implementado en forma asincrónica. Punto de reunión (Rendezvous). Ya se discutió el punto de reunión o rendezvous, basado en los tres conceptos: declaraciones entry, llamadas entry, y declaraciones accept. El punto de reunión es sincrónico por completo e involucra sólo dos procesos: el emisor, el cual es suspendido hasta que es acep­ tado, y el receptor. Llamadas de procedimiento remoto (RPC). Las RPC son muy parecidas a los procesos que se usan para realizar el rendezvous o punto de reunión. Sin embargo, están destinados a tener exactamente el mismo significado que los procedimientos regulares. Cuando esto puede lograrse, permite la codificación de procesos concurrentes en lenguajes de procedimiento tradicionales y deja que los programas convencionales sean transportados al sistema de sincronización. Las RPC han sido consideradas para su uso con Modula-2 e implementadas en el sistema operativo V y en CLU concurrente. Paso de mensajes de tipo uno a muchos. El paso de mensajes de tipo uno a muchos recibe también el nombre de transmisión, en la medida que se compor­ ta de manera muy semejante a una estación de radio en la que todos los recep­ tores escuchan el mismo mensaje. Un tipo es sin memoria temporal (unbuffered), de modo que un mensaje enviado puede ser obtenido sólo por aquellos proce­ sos listos para recibirlo. Si los mensajes tienen memoria temporal (buffered), pue­ den permanecer en esa memoria de manera indefinida de modo que los procesos puedan recibirlos en cualquier momento. Un lenguaje que implementa el paso de mensajes de uno a muchos es el BSP (Broadcasting Sequential Processes; procesos secuenciales de transmisión), otro derivado de CSP. Sólo fines educativos - FreeLibros

CAPÍTULO 5: Construcciones de lenguajes para procesamiento en paralelo

247

E J E R C I C I O S 5.3 1. Una fila de cafetería es una buena aplicación para el procesamiento en paralelo. Los consumidores están uniéndose a la fila al mismo tiempo que otros la dejan. Esta situación tipifica un problema de productor-consumidor en el cual no es posible "consumir" un elemento hasta que haya sido "producido", pero los consumidores y los productores pueden trabajar en paralelo. Escriba un algoritmo informal para si­ mular una fila de cafetería, con dos procesos, HacerAlmuerzo y ComprarAlmuerzo, funcionando en paralelo. Pruébelos con algunos consumidores simulados. Intente evitar: • Inanición: un comprador espera siempre mientras los almuerzos se preparan. • Alternancia: un segundo almuerzo no se prepara hasta que el primero es vendi­ do. • Estancamiento: un preparador de almuerzo espera por una señal para hacer otro almuerzo, mientras que un comprador espera una señal para comprar uno. 2. Utilice cinco semáforos binarios, Palillo0 a Palillo4, y escriba procesos P. Philosopher (filósofo) que se ejecutarán en paralelo para implementar el problema de la Cena de los Filósofos. La sección crítica incluirá la declaración Eat (comer) y deberá estar rodeada por operaciones de Wait (espera) y Signal (señal). En el principio, cada palillo, deberá estar establecido en up (arriba) para indicar su disponibilidad. 3. ¿A qué tiene acceso un proceso cuando "entra a un monitor"?

5.4

ALGUNAS SOLUCIONES DE SINCRONIZACIÓN Diversas soluciones para ejecución en paralelo o compartida en un CPU han sido implementadas. Examinaremos algunas de ellas a continuación.

Semáforos en ALGOL 68/ C y Pascal S ALGOL 68 ALGOL 68 fue el primer lenguaje con un semáforo incorporado, y sus dos opera­ ciones, up (arriba) y down (abajo). El modo sena (tipo) de ALGOL estipula varios procesos para ejecutar en paralelo, con un contador que sigue la pista de cuánto tiempo esperar para la comunicación de otro proceso. Así, ALGOL 68 proporciona la posibilidad de evitar estancamiento de procesos ávidos. Cuando el contador al­ canza algún límite asignado con anterioridad, un proceso en ejecución que haya ejecutado un down sobre un semáforo en particular será forzado a ejecutar un up, que permitirá el siguiente proceso de espera para tener acceso a recursos comparti­ dos. C Cuando C está en ejecución bajo el sistema operativo UNIX tiene un semáforo, y sus operaciones están proporcionadas en una librería en tres archivos de siste­ mas, con encabezados sys/types.h, sys/ipc.h y sys/sem.h. Dos de las operacio­ nes son: Sólo fines educativos - FreeLibros

248

PARTE II:

Lenguajes imperativos

senil = semget ( . . . ) , el cual crea un semáforo llamado senil smectl (seml val), que restablece seml a val Las operaciones semaphore_$end y semaphore_wa i t, las cuales implementan Signal y Wait, son accesadas al utilizar semop. Por ejemplo, semop(semaphore_$end,. . . ) ejecutará una señal. Los semáforos escritos en C pueden utilizarse con las operaciones f o r k , execl y wait de UNIX. C (y UNIX) administran la memoria de diversas maneras, f o r k , execl ywait permiten que un programa en ejecución {padre) sea suspendido mien­ tras que otro programa se ejecuta y utiliza las mismas localidades de memoria. Una llamada a f o r k produce una nueva copia del programa padre, yexecKchil d_name, a l , a 2 , . . . , a n , 0 ) permite que un nuevo programa denominado c hi 1d_n ame se eje­ cute en lugar de esta copia, wai t fuerza al padre a permanecer en suspenso hasta que el hijo se completa. Un usuario puede ordenar a UNIX que ejecute dos o más programas "simultáneamente" con el uso del operador &de UNIX $ payroll hours employee payment & ed

comenzará la ejecución de payroll (nómina), pero permite al editor interrumpirlo si es necesario. Si se tiene disponible más de un procesador, estos operadores pue­ den administrar el procesamiento en paralelo. Un hijo (child) puede ejecutarse en forma concurrente con su padre (parent), y se puede bifurcar ( f o r k ) a su propio hijo también, como se muestra en la figura 5.4.1 . Una llamada a f o r k sin parámetros crea una nueva copia de su proceso padre (process 1), el cual se ejecuta en forma concurrente con el padre. Una llamada sub­ secuente a e x e c l ( p 2, a 1........an,0) reemplaza la copia de p r o c e s s l conp2 einicia el proceso p2 ejecutándose en forma concurrente con el padre, processl. Aquí p2 es un apuntador hacia una cadena de caracteres llamada process2, y an son apuntadores a los nombres de los argumentos deprocess2.

processl (procesol)

processl

execl (p2, a-,,..., an, 0)

FIGURA 5.4.1 Operaciones UNIX fork y execl para iniciar dos procesos ejecutándose en forma concurrente

Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

249

No hay límite (en teoría) para el número de procesos que pueden ejecutarse en forma concurrente en procesadores múltiples o bien intercambiarse dentro y fuera de un solo procesador. En el último caso, UNIX traslapa la memoria de un padre con la que necesita el hijo. De este modo, programas extensos pueden ejecutarse "en una memoria relativamente limitada, previniendo que es posible subdividir el texto y datos del programa de manera tal que cada uno y todos los [procesos] ejecutables se ajusten a las limitaciones de memoria de la máquina" [Silvester, 1984] (véase la figura 5.4.2). Puede establecerse una tubería a través de la capa de entorno (shell) de modo que la salida de un programa se dirija en forma directa como la entrada de otro. Por ejemplo, $ payroll

| Ipr

redirigirá la salida del programa de nómina (payroll) directamente hacia la impre­ sora en línea. Esto realiza la misma acción que los tres comandos: $ payro l1>scratch_fi 1e $ 1pr<scratch_fi 1e $ rm $cratch_file

/* salida de payroll hacia seratch_fi 1e /* envió de ser atch_fi 1e hacia la linea /* elimina scratch_file del sistema */

*/ de impresión */

De manera similar, $ payroll

| sort | Ipr

redirigirá la salida de la nómina hacia el programa s o r t (clasificar), y s o r t la diri­ girá hacia 1pr, para un listado clasificado y ordenado. Los tres programas comen­ zarían a ejecutarse de manera simultánea, con posibles pausas para la salida desde el otro. P a sca l S Pascal S viene de las palabras Pascal Secuencial, y es un intérprete que puede implementarse como un subconjunto aumentado de Pascal. El programa de Pascal

FIGURA 5.4.2 Jerarquía de procesos concurrentes

Sólo fines educativos - FreeLibros

250

PARTE II: Lenguajes imperativos

pascal s compila Pascal S en seudocódigo, llamado código-P, y luego procede a leerlo e interpretar un programa escrito en Pascal S. Niklaus Wirth es autor de Pascal y de Pascal S, que fue modificado más tarde por M. Ben-Ari en la Universi­ dad de Tel Aviv. Los procesos "concurrentes" son intercalados en vez de que se ejecuten de un modo concurrente. Pascal fue previsto como ion lenguaje de ense­ ñanza más que de producción, como lo es Pascal S. Cualquiera con un solo proce­ sador capaz de correr Pascal puede correr Pascal S, pero espere que sea ineficiente en tiempo de ejecución. Los procesos concurrentes P l, P2,...,Pn están señalados por: cobegin Pl; P2;..; Pn coend;

Wirth describe esta declaración como sigue: "la declaración cobegin es una señal al sistema de que los procedimientos encerrados no van a ejecutarse, pero van a mar­ carse para ejecución concurrente. Cuando se llega a la declaración coend, la ejecu­ ción del programa principal se suspende y los procesos concurrentes son ejecutados. El intercalamiento de las ejecuciones de estos procesos no es predecible y puede cambiar de una ejecución a otra. Cuando todos los procesos concurrentes han fina­ lizado, entonces el programa principal se reanuda en la declaración que sigue a la coend" [Ben-Ari, 1982]. El programa Pascal S del listado (5.4.1) es una solución al problema de la Cena de los Filósofos, con una variación. El semáforo del palillo está arriba (1) si un palillo se encuentra disponible, y abajo (0) si un filósofo lo está sosteniendo. El semáforo de hambre está arriba (de 1 hasta 4) si cuatro o menos filósofos están hambrientos; y abajo (lugar = 0) si hay cinco. Esto asegura (mediante el principio del casillero)3 que al menos un filósofo tendrá acceso a dos palillos. En este caso, el número de filósofos hambrientos representa la cantidad de nichos, y el número de palillos representa cinco pichones. El semáforo notHungry (no hambriento) trabaja como sigue: cuando un procedimiento Philosopher (Filósofo) comienza, el primer filósofo espera que notHungry tome un valor de 1 a 4, con lo cual indica que de cero a cuatro filósofos no están hambrientos y, por lo tanto, no están interesados en comer. Esto proporciona al menos una oportunidad de que habrá dos palillos dis­ ponibles. Cuando esto ocurre, wai t ( notHungry ) se ejecuta al decrementar notHungry en 1. Cuando también encuentra sus dos palillos adyacentes disponibles ( C[ i 1=1 y C[ ( i+1) mod 51-1), procede a eat (comer), después de lo cual hace una señal de que los dos palillos se encuentran disponibles para otro filósofo y que él ya no tiene (notHungry + 1) mod 5). hambre (notHungry pr ograi DiningPhiloso phers; const SomeBigNumber - maxint; var C: array[0..4] of tbinary] semaphore; nothungry : semaphore: (Supone valores 0..4.} i : integer:

(5.4.1)4

3 El principio del casillero (pigeonhole) establece que si se tiene n nichos y n+1 pichones, al menos un nicho debe acomodar dos o más pichones. ADe [Ben-Ari, 1982], con modificaciones.

Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

251

procedure Philosopheríi : integer); begin fo r j :™ 1 to So mebigNumber do think; wait(notHungr y); waitCCEil); w a i t C C C i + 1 ) mod 53); eat; signal CCti3); signal (CC(i+l) mod 53): signal (n ot H u n g r y ) end (for); end; (P) begin C m a i n 3 notHungry 4; [todos los 5 filósofos están Si nHambre (n o t H u n g r y )3 fo r i 0 to 4 do C t i 3 1; (todos los palillos están di sponibles) cobegln Ph ilosopher(ü); Ph ilosopher(l); Ph i 1 o s o p h e r (2); Philosopher(3 ); Ph i 1 o s o p h e r (4); coend end.

Tipos de proceso y monitor en Concurrent Pascal Recuerde que una memoria temporal (buffer) es un área de almacenamiento en un disco que se utiliza para guardar datos de entrada y salida de manera temporal. También puede ser implementada en Concurrent Pascal con el uso de un monitor. Existe dos formas para entrar a la memoria temporal, Send y Rece i ve. Send en­ vía tma página hacia la memoria temporal desde un proceso de llamada, y Rece i ve devuelve una página para un proceso desde la memoria temporal. En el monitor Di skBuffer, las entradas son procedimientos y son llamadas desde algún proceso, y controlan un dispositivo de entrada o salida. Estos controladores no pueden te­ ner acceso a un Virtual Di sk en forma directa, sólo a través del procedimiento monitor titulado Entry. La coordinación de los procesos en ejecución quizá concu­ rrentes que llaman a Send y Recei ve se realiza dentro del monitor. type DiskBuffer =* ■o n1tor(Conso leAccess, D i skA cce ss; Resource; Base, Li mi t : integer); var Cshared data) disk: VirtualDisk; Sender, Receiver ; queue; He.ad, T a i l , Length : integer; 5 [Brinch Hansen, 1978.

Sólo fines educativos - FreeLibros

(5 . 4 . 2 ) 5

252

PARTE II:

Lenguajes imperativos

procedure entry Send(Block: Page); (envía una pagina desde un procedimiento de llamada hacia el buffer o memoria temporal del disco) begin I f Length * Lim11 then de lay ( s e n d e r ) : (buffer f u l ! , wait) di sk.writeCBase + Tal 1, Block); Tail(Tail + 1) aod Limit; Length:- Length + 1; contlnue(Receiver) [t ransfiere el control a Receive (recibir) si hay algo en su cola, Receiver (r ecibidor)) end; procedure entry Re ceive(var Block: Page); [regresa una pagina para el proceso de llamada) begin end; begin init di sk(ConsoleAccess, DiskAccess): (o peración de iniciación no descrita aqui) Head:- 0; Tai 1 0 : L e n g h t := 0: end.

Si se mira el código en el listado (5.4.2) de manera descendente, primero vemos que DiskBuffer va a ser un tipo nonltor con cuatro parámetros. Los primeros dos, Consol eAccess y Di skAccess, serán variables de un tipo dependiente del sistema, Resource. Los dos segundos estipulan una dirección base en la que el DiskBuffer comienza y un límite (Limit), que fija su tamaño. El tipo Vi rtua 1Di s k es una clase de Concurrent Pascal, que incluye datos así como operaciones asociadas. Dos de estas operaciones son disk.writeydisk.read. Nuestra memoria temporal de da­ tos será de esta clase. Concurrent Pascal incluye un tipo integrado, queue (cola). Una cola (queue) puede estar asociada con un monitor para administrar múltiples procesos en la espera de un recurso que se solicitó en forma mutua. Un proceso de llamada, si no es retrasado en queue, tiene acceso exclusivo a las variables compartidas di s k, He ad, Tail y Length desde el begin (inicio) de la entrada que se llamó hasta que alcan­ za la declaración continué. Head se inicializa a 0, la dirección relativa del comienzo de la memoria temporal. Ta i 1, que es la dirección relativa del final (en páginas) de la memoria temporal o buffer, también se inicializa a 0, lo que indica un buffer vacío. El procedimiento Send incluye tres declaraciones que debe ejecutarse antes que un proceso llame, lo que, con éxito, ha ganado entrada para Send sin ser retra­ sado, dando datos compartidos a un proceso en la entrada del procedimiento Recei ve. Estos escriben a la memoria temporal e incrementan Tai 1 y Length. Aunque el monitor Di s kBuf f e r no lo estipula, los monitores de Concurrent Pascal pueden incluir llamadas a otros monitores.

Sólo fines educativos - FreeLibros

CAPÍTULO 5: Construcciones de lenguajes para procesamiento en paralelo

253

Rendezvous (Punto de reunión) en Ada y Concurrent C A da La unidad de programa de Ada con potencial para ejecutarse en paralelo con otras unidades se denomina una task (tarea). En cuanto a sintaxis, es semejante a un package (paquete); tiene una especificación y un cuerpo. ta sk T 1s

— especificació n

(5 . 4 . 3 ) 6

•♦ •

end T; task body T 1s

— cuerpo

end T;

Veamos un ejemplo simple de tareas que puede ejecutarse de manera concu­ rrente. Supongamos que planeamos una fiesta. procedure Plan_Party i s

(5.4.4)

task Invitations; task body Invitations is begin Write_Invitations; Mail_Them; end Invitations; task Clean; task body Clean is begin Clean_House; end Clean; begin Prepare_Food; end Plan_Party;

P l a n _ P a r t y es la unidad padre para las dos tareas I n v i t a t i o n s y Clean. Cuando

procedure Plan__Party se está ejecutando, y se alcanza el begin para esta unidad

padre, las dos tareas locales comenzarán en forma automática a ejecutarse tam­ bién. El end para Pl an_Pa r t y no puede ejecutarse hasta que todas las tareas locales se hayan terminado. En el esquema anterior, los tres procedimientos, I n v i t a t i o n s , C1 ean y Prepa re_Food, se ejecutan en forma concurrente, pero no en algún orden en particular. No existe comunicación entre ellos. Dependiendo del compilador y del

6 La convención utilizada por el manual de referencia de Ada [ANSI/ISO-8652,1995] implica el uso de letras minúsculas en negritas para las palabras reservadas, y sólo la primera letra versal para otros identificadores.

Sólo fines educativos - FreeLibros

254

PARTE n: Lenguajes imperativos

hardware, estos tres procedimientos podrían ejecutarse en paralelo o en un solo procesador al emplear alguna clase de tiempo compartido. Ahora imaginemos un poco de la fiesta, de manera que las tareas puedan co­ municarse entre sí. En Ada esto se realiza por medio de una tarea (la que llama), accept (aceptando) una entry en ella cuando es llamada por otra tarea. Una entry (entrada) es una llamada de procedimiento, pero lo que hace es determinado por la tarea que acepta la llamada (véase el listado (5.4.5)). procedure Plan_Party is

(5.4.5)

type Name_List is array (i nteger range <>) of S t r i n g ( l . .50); task In vi t a t i o n s is entry Guest_List(Ñames: in Name__List); end I n vi t a t i o n s; task body I n v i t a t i on s is

Guests: Name_List; begin accept Guest_List(Ñames: in Name_List) do

Guests:= Ñames; end Guest_List;

Wr it e_Invi tat i ons ; Mail_Them; end I n vi t a t i o n s; task Clean; task body Clean is begin

Clean_House; end Clean;

G: Name_List; begln

Prepare_Food; Read_List(G); I n vi t at i on s. G u es t_ Li s t ( G ) ; end Plan_Party;

Aquí, P la n _ Pa r t y es el llamador para I n v i t a t i o n s . Puesto que todas las tres tareas, Plan_Party, I n v i t a t i o n s y Clean comienzan en forma simultánea, I n v i t a t i o n s debe esperar para accept (aceptar) la entry G u e s t _ L i s t hasta que sea enviada por el procedimiento principal. Lo que ocurre durante el accept... do... end ; es el rendez­ vous o punto de reunión. Un ejemplo simple pero práctico de tareas es el de una memoria temporal de entrada/salida para un carácter simple, como se muestra en el listado (5.4.6). task Char_Buffer Is entry Read (C: out C h a r a c t e r ); entry Write (C: In Character); end Char_Buffer;

(5.4.6) --Lectura desde la memoria temporal (buffer) — Escritura hacia la memoria temporal

Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

255

task body Charjiuffer 1s F u l l : Boolean False: Ch: Character; loop select when Full -> accept ReadíC: out Character) do C Ch; end Read; Full

False;

or when not Full -> accept WritetC: In Character) do Ch C; end Write; Full True; or te riln a te ; end select; end loop; end Char_Buffer;

Como es usual, existe varias cosas que notar aquí. Antes que nada, Char_Buffer. Read(. . . ) y Char_Buffer.Wri t e ( . . . ) serán llamadas por otras tareas. Cada entra­ da tiene una cola asociada, de manera que si varias tareas están intentando Read (leer) o Wri te (escribir) de manera simultánea, las llamadas serán puestas en una cola y procesadas en orden FIFO (primero en entrar, primero en salir). Por supues­ to, debemos tener algo en una memoria temporal antes de Read (leer) de ella. De este modo accept Read se guarda mediante la expresión when Fu11. La declaración select significa que cualquiera de las declaraciones accept puede elegirse sin un orden particular. Más específico, si la memoria temporal se encuentra vacía y Ful 1-Fal se, la tarea Char_Buffer puede seleccionar (select) una llamada desde la cola Write antes de aceptar un Read. Otra manera de manejar una memoria temporal de carácter de lectura/escritu­ ra puede ser establecer Read_Char y Wr it e_Char como dos tareas y comenzarlas ejecutándose simultáneamente, como se ilustra en el listado (5.4.7).

procedure B u f f e r_ Ta s ks ; Ful 1; boolean

False;

pragia Sh a red ( F u l l ); Ch: Character; pragna Sha r e d (C h ); task Read_Char is entry ReadíC: out Character); end Read_Char;

Sólo fines educativos - FreeLibros

(5.4.7)

256

PARTE II:

Lenguajes imperativos

task write_Char 1s entry Write (C: 1n Character); end Write_Char; task body Read_Char 1s begin loop when Ful 1 -> accept ReacKC: out Character) do C Ch; Ful 1 False; end Read; end loop; end R e a d :C h a r ; task body write„Char 1s begin loop accept Write(C: 1n Character) do Ch C; Ful 1 True; end Write; end loop; end Write_Char; begin — Establece la ejecución de Read_Char asi como de Write__Char end B u f f e r _ T a s k s ;

Un pragma de Ada es una directiva de compilador. El Shared pragma, para implementar memoria compartida, garantiza dos cosas. Primero, si una variable com­ partida, tal como la Ch o Ful 1 anteriores, se lee en una sección crítica (CS) en una tarea, no será actualizada por ninguna otra tarea hasta que la CS termine. En el listado (5.4.7), una CS de este tipo se presenta para Ch entre accept Read y su end. Segundo, si una variable compartida se actualiza en una CS, no será ni leída ni actualizada por ninguna otra tarea hasta que se salga de la CS. Esto ocurre entre accept W r i t e ysuend para Ch, y en ambas declaraciones accept para Ful!. Ada no implementa semáforos ni monitores, de modo que éstos deben progra­ marse si deseamos evitar los problemas de sincronización discutidos en la sección 5.3. Sólo variables simples o access (apuntador) pueden declararse Shared, por tal motivo debemos prever otros medios para la protección de datos estructurados. El estudio se encaminará hacia esto en el Laboratorio 5.1, donde construiremos una memoria temporal de lectura/escritura más grande que un simple carácter. Las tareas de Ada pueden ser dinámicas así como estáticas. Es decir, se les puede crear o destruir a medida que se ejecuta un programa. Supóngase que de­ seamos crear tareas Cha r_Buf f er a medida que van necesitándose en un programa, y también la capacidad de tener más de una memoria temporal de este tipo a la Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

257

vez. Para conseguir esto, agregaríamos la palabra reservada type a la declaración de tarea, y luego crearíamos valores tipo access apuntando a las tareas, como se muestra en el listado (5.4.8). task type Char_Buffer is entry Read

(5.4.8)

(C: out Character);

entry Write (C: in Character); end CharJBuffer; type Buffer_Ptr is access Char_Buffer; P, Q: Buffer^Ptr; begin P := new Buffer_Ptr; Q := new Buffer_Ptr; P := nuil;

Q

:= nuil;

end;

Ada no destruye de manera dinámica los objetos creados a través de un proce­ dimiento como d1 spose. Esto fue una decisión de diseño de Pascal para eliminar apuntadores colgantes que señalen a objetos de datos no existentes. En Ada, asig­ nar a una variable access el valor nul 1 hace inaccesibles a los objetos. Sus localida­ des de memoria serán liberadas cuando la ejecución del programa salga del alcance de los objetos.

Concurrent C El lenguaje C no tiene construcciones para procesamiento concurrente, aunque vi­ mos cómo los procedimientos de ejecución concurrente podrían ser implementados con el uso de directivas hacia el sistema operativo UNIX. Concurrent C se desarro­ lló para proporcionar un tipo process y sus operaciones asociadas como caracterís­ ticas de lenguaje concurrente. No implementa memoria compartida, pero emplea el paso de mensajes sincrónico con la ejecución del programa del cliente y bloquea hasta que el servicio haya sido recibido. Ello difiere de Ada en varias formas, de las cuales mencionaremos cuatro. En primer lugar, las transacciones de C son simila­ res a llamadas de función, mientras que en Ada son como procedimientos. Esto significa que una llamada puede aparecer en cualquier lugar en el que una función sería apropiada; por el contrario, en Ada una llamada es siempre una declaración. C estipula prioridades de proceso especificadas por el usuario; en Ada, siempre son procesadas en orden FIFO. C permite una llamada de transacción con paráme­ tros, de modo que sólo aquellas llamadas que satisfa*gan ciertos criterios serán ser­ vidas. En Ada, cuando se introduce un bloque principal con tareas, sus tareas son activadas también y terminadas cuando se sale del bloque. En Concurrent C se debe activar cada proceso, por ejemplo, Sólo fines educativos - FreeLibros

PARTE n: Lenguajes imperativos

25 8

process buffer b; b = create buffe r(128);

También puede finalizarse mediante c_abort(b);. Otras diferencias más sutiles pueden encontrarse en [Gehani, 1986], Concurrent C tiene un tipo, process, que requiere de una parte de especifica­ ción (spec) y una de body (cuerpo). La spec es visible para otros procesos, mientras que body no. Un proceso de servidor incluye una declaración accept para recibir llamadas de transacción (trans). Veamos el problema de la Cena de los Filósofos implementado en Concurrent C, como se muestra en el listado (5.4.9). process spec C h o p s t t c k ( )

(5.4.9 ) 7

C

trans vold pick_up(); trans vold put.downí);

); process spec Ph i1 os o p h e r ( Int id, process Chopstick left, process Chopstick right); //define

LIFE.LIMIT 100000

process body P h i1o s o p h e r (i d , left, right)

{ Int times_eaten; fo r (ti mes_eaten - 0; times_eaten !- LIFE_LIMIT; times_eaten++) C /* piensa, luego entra al cuarto de la cena */ /* levanta Palillos */ right.pick_up(); left.pick_up( ); /*come*/ p r i n t f C P h i l o s o p h e r % d : * b u r p * / n M , id); /*baja Palillos*/ left.put_down(); ri g t h . p u t _ d o w n ( ); /*se levanta y abandona el cuarto de la cena */

} process body C h o p s t i c k O

C fo r(;;) select

/*siempre */

} accept pick_up(); accept put_down();

7 La Cena de los Filósofos en Concurrent C. Reproducido con permiso de N. H. Gehani y W. D. Roome, Concurrent C, © 1986 por John Wiley & Sons.

Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

259

or terslnate;

] ) mainO

C process Chopstick f[53: in t j;

/*arreglo de cinco palillos*/

/* pr1mero crea los palillos, después procede a crear a los Filósofos */ for (j - 0; j < 5; j++) fCj] - create Chops ti c k { ); fo r (j - 0; j < 5; j++) create Philosopherfj, f[j], f C (j + 1 ) %8 5]);

) Cada filósofo existe sólo hasta que haya comido 100 000 veces. Los palillos siguen siempre. Sin embargo, una vez que todos los filósofos terminaron, los pali­ llos no tienen nada que hacer, y así la opción or de la declaración select se elige y cada palillo termina. Entonces, puesto que todos los procesos se completaron, el programa mai n de Concurrent C también puede terminar. L A B O R A T O R IO 5.1: S IM U L A C IÓ N DE P R O C E S A M IE N T O EN P A R A L E L O : A D A

O bjetivos (Los Laboratorios pueden encontrarse en el Instructor's Manual) 1. Experimentar con diferentes métodos de sincronización una memoria temporal o buffer implementado a través de tareas. 2. Observar qué ocurre cuando la memoria temporal es accesada sólo por una tarea exterior o por varias. 3. Diseñar un esquema de sincronización para dos tareas de clientes con el uso de la memoria temporal de modo que el cód ig o de cadena de los dos clientes no se entre­ mezcle.

Paso de mensajes en Occam Los mensajes en Occam se envían a través de canales que son visibles tanto el pro­ ceso de llamada así como para el proceso de aceptación. Con cada canal está aso­ ciado un protocolo, que describe el tipo de datos capaz de ser enviado a través de cada canal. Un canal y los dos procesos que conecta son establecidos cuando el programa que los declara es compilado, y ni los procesos ni el canal pueden estar asignados en tiempo de ejecución. Un mensaje es salida para el canal por un proce­ so y entrada al otro proceso del canal. Para sincronizar la comunicación del canal, el primer proceso, con el fin de emprender la entrada o la salida sobre un canal,

Recuerde que % es el operador mod en C.

Sólo fines educativos - FreeLibros

260

PARTE II: L en g u ajes im p erativ o s

debe esperar hasta que el otro proceso esté listo ya sea para salida del canal o en­ trada hacia éste. Cualquier operación adicional de un proceso es suspendida du­ rante un tiempo de espera. Si se desea comunicación bidireccional; es decir, que los datos entren al Proceso2 desde la salida del Procesol, y la subsecuente salida de los datos del Proceso2 sean la entrada al Procesol, entonces deben establecerse dos canales. El problema del productor-consumidor consiste de uno o más productores y uno o más consumidores trabajando en forma concurrente con un consumo posi­ ble sólo si un elemento se produjo y se encuentra disponible. La versión más sim­ ple es en la que un productor produce elementos para un solo consumidor, como se muestra en la figura 5.4.3. El productor no debe sacar un elemento hasta que el consumidor esté listo para introducirlo y procesarlo. Un esquema de Occam del problema, es: C U F OCCEXAMP.OCC

(5.4.10)

--archivo oc cexamp.occ //INCLUDE “hostio.inc" PROC pr o d c o n (CHAR OF SP fs, ts, [] INT memor y)9 #USE “hostio.1ib" CHAN OF BYTE input, output, source PROC producer PROC consumer PROC interface PAR interface (fs, ts, input, output) p r o d u c e r (i n p u t , source) consumer(output, source)

}}} Canal de entrada

Canal de salida

A >f Proceso productor

Canal fuente

Proceso consumidor

FIGURA 5.4.3 Sistema productor-consumidor 9 f s y ts son canales desde y hacia el servidor de archivos anfitrión, como se describe en el "Occam 2 Toolset User M anual" ("M anual de Usuario del Conjunto de Herramientas de Occam 2"), que es parte del CSA Transputer Education Kit. El tipo de canal lo indica las palabras clave CHAN OF. El protocolo SP utilizado por los canales del archivo anfitrión está definido en “hosti o . i nc”.

Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

261

Los paréntesis de llave indican un fold (doblez), en el que el texto del programa puede estar oculto. Aquí utilizamos el conjunto de herramientas Occam 2, que se ejecuta en el equipo de educación transponedor de CSA (CSA; Transputer Education Kit) e incluye el editor de doblaje Origami. En un programa completo, los dobleces se convierten en comentarios, precedidos por y con remplazo de Los dobleces pueden estar anidados. Occam tiene una orientación hacia el uso en pan­ talla, de modo que si el texto del programa llega a ser muy largo para una pantalla simple, algo de ella puede ser doblada en un espacio más pequeño. El programa completo es: — archivo oc cexamp.occ #INCL UDE "hostio.inc" PROC prodcon (CHAN OF fs, ts, SP, □ INT memory) #USE “hostio.lib" CHAN OF BYTE input, output, source — CíC PROC producer PROC producerCCHAN OF BYTE input, source.ch) BYTE x: NHILE TRUE SEQ input ? x source.ch ! x —

--procesa se cuencialmente

3]33

— CtC PROC consumer PROC consumeríCHAN OF BYTE output, destination.ch) BYTE y: NHILE TRUE SEQ destination.c h ? y output ! y -333 — CCC PROC interface PROC interface (CHAN OF fs, ts, SP,CHAN OF BYTE to.prod,from.cons) BOOL done: BYTE c h l , ch2, result: VAL end IS •**': SEQ s o . w r i t e . n l ( f s , ts) done FALSE NHILE NOT done SEQ so.getkeytfs, ts, chl, result) to.prod ! chl from.cons ? ch2

— nueva linea

— espera por una clave, sin eco — envia al productor — hace eco en la pantalla

Sólo fines educativos - FreeLibros

(5.4. 11)

262

PARTE II: Lenguajes imperativos IF ch2 - end done :» TRUE TRUE S K I P 10 so.exitífs, ts, sps.success)

--}}} PAR interface ífs, ts, input, output) produceríinpu t, source) consumerfoutput, source)

E J E R C I C I O S 5.4 1. a. Rastree la Cena de los Filósofos en Pascal S (listado (5.4.1)) ungís cuantas veces para convencerse de que en realidad funciona. Recuerde que el orden en que los cinco procedimientos Ph11 osophert i ) son llamados es indeterminado, b. Elimine el ciclo notHungry (wait(notHungry),.signal(notHungry)) y rastree el progra­ ma de nuevo. ¿Es posible para un filósofo morir de hambre sin el semáforo de lugar? 2. SiHead es la dirección relativa del OiskBuffer del listado (5.4.2), ¿Qué es la variable Base? 3. Complete la entry Recei ve para el monitor Di skBuffer del listado (5.4.2). 4. ¿Por qué es necesario incluir una cláusula teralnate en la tarea Char_Buffer del listado (5.4.6), y por qué no está enumerada como una entry? 5. ¿Qué pasaría si dejamos la actualización de Fu) 1 de las declaraciones accept en la segunda implementación de memoria temporal del listado (5.4.7), como lo hicimos en el primer fragmento de Ada del listado (5.4.6)? 6. Escríba el código para una tarea de Ada con dos entradas para implementar el semá­ foro binario de Dijkstra (listado (5.3.1)). 7. El programa de la Cena de los Filósofos del listado (5.4.9) puede conducir a un estan­ camiento. ¿Cuándo ocurrirá esto? Sugiera cómo evitar este problema. Nótese tam­ bién que la salida de los procesos Philosophers pueden mezclarse si más de uno intenta tener acceso al mismo tiempo a la salida estándar. ¿Cómo podría resolverse esto?

5.5

TUPLAS Y OBJETOS Hay unidades de paralelismo además de los procesos sincronizados que hemos visto. Las versiones de los objetos del capítulo 4 pueden también ejecutarse en for­ ma concurrente. Aquí, los métodos actúan como procesos al ejecutarse en paralelo. Un paradigma radicalmente diferente, espacio de tupias, también puede utilizarse.

10Occam requiere de una declaración "else" para cada IF. Aquí se emplea la declaración muda SKIP.

Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

263

El espacio de tupias es un espacio de datos compartidos que no es propiedad de ninguno de los procesos. Las tupias que contienen datos así como procesos son extraídas desde y restauradas hacia el espacio a medida que se necesitan. Conside­ raremos esto a continuación.

El espacio de tupias de Linda No todos los procesos se comunican a través de paso de mensajes o mediante loca­ lidades de memoria compartida. Estos dos últimos sufren de algún grado de no confiabilidad debido a la necesidad de la sincronización administrada por el pro­ gramador. Linda,11 desarrollado en la Universidad de Yale, es un lenguaje para procesamiento en paralelo que implementa el espacio de tupias. Actúa como una memoria asociativa y relaciona una dirección base con una clave en un almacena­ miento rápido. Los mensajes pueden, aunque no lo necesitan, ser pasados con el uso de tupias. El propio Linda no es un lenguaje de calidad de producción desarro­ llado por completo, pero se incrustó en diversos lenguajes, entre ellos Ada y C. A continuación, utilizaremos la sintaxis de C-Linda. Una tupia es una colección ordenada de elementos de datos, por ejemplo, ( “hola mundo", 22, 2.17). El espacio de tupias es la colección de tupias colocada en el es­ pacio de tupias con el uso de los operadores out y eval. Existe cuatro operaciones sobre tupias: out(t), 1n(T), rd(T), eval(t); y dos predicados, 1np() y rdp(). out(t) evalúa la tupia t y la coloca en el espacio de tupias. Por ejemplo, out ( “ hola mundo” , 22, 2.17) crea una tupia y la coloca en el espacio de tupias. 1n (T ) empareja la plantilla (descripción) T con una tupia en el espacio de tupias si existe uno, y la elimina del espacio de tupias. Si no se encuentra una tupia que coincida, el proceso que llama se suspende hasta que una está disponible. Si se encuentra más de una que coincida con T, se elige una de manera arbitraria para ser eliminada. Por ejemplo, 1n ( " h o l a mundo” , ? i , ? f ) elimina una tupia con la primera coordenada igual a “ hol a mundo” ; la segunda, cualquier entero; y la terce­ ra, un número de punto flotante, suponiendo que i y f hayan sido declarados con anterioridad como entero (integer) y punto flotante (float). rd ( T ) funciona de manera muy parecida a 1n, pero la tupia emparejada perma­ nece en el espacio de tupias. Se devuelve una copia de la tupia emparejada, rd permite que el espacio de tupias funcione como memoria sólo de lectura, la que puede ser compartida por cualquier número de procesos en ejecución. Si no se encuentra una tupia que empareja, el proceso que llama se bloquea. eval(t) es similar a out, excepto que la tupia se evalúa después, en vez de antes, y se coloca en el espacio de tupias, eval crea una nueva tupia activa (un nuevo proceso); por ejemplo, eval ( 45 , A l g u n a F u n c i o n ( x ) ) crea un nuevo pro­

11 El nombre "Linda", es una travesura irreverente. Ada fue llamado así en honor de Ada Lovelace, que según se cree fue la primera mujer programadora de computadoras quien trabajó con Charles Babbage en su máquina analítica. En la época en que el lenguaje Linda se encontraba en desarrollo, había una estrella del cine p*rnográfico llamada Linda Lovelace. De esta manera, con juvenil buen humor y en un intento de conservar los lenguajes "entre familiares", David Gelemtner nombró su nue­ vo lenguaje según el nombre de la Lovelace contemporánea: Linda.

Sólo fines educativos - FreeLibros

264

PARTE II:

Lenguajes imperativos

ceso, que se ejecuta en paralelo con el proceso que llamó eval. La tupia (45, A l g u n a F u n c i o n ( x ) ) está activa tanto tiempo como Al gunaFuncion se encuentre eje­ cutándose, y pasiva cuando AlgunaFuncion termine. Las dos operaciones de predicado (que devuelven el valor de verdadero o de falso) son Inp O y rdp(). Se comportan justo como 1n y rd, pero no bloquean el proceso de llamada. Si no se encuentra un emparejamiento, se vuelve falso (0 en CLinda) y el procesamiento puede continuar. La idea, puesta de forma simple, es que un proceso que desee alterar los datos removería una tupia del espacio de tupias al utilizar un tn, procesaría los datos y luego la devolvería al espacio de tupias utilizando out. Cualquier otro proceso será incapaz de tener acceso a esa tupia hasta que sea devuelta. Los mensajes también pueden ser enviados si se usa out y recibirse utilizando 1n. Las implementaciones de Linda incluyen un preprocesador que utiliza colas y semáforos, entre otras técnicas, para acelerar la búsqueda de tupias. Un kernel de Linda está incluido en el sistema operativo QIX, el cual se desarrolló para imple­ mentar el procesamiento en paralelo. Sus creadores afirman que es más eficiente que UNIX, mientras que mantiene una considerable compatibilidad con él. Tam­ bién afirman que hace la escritura de programas en paralelo más fácil, resultando independientes de la arquitectura en particular que se utilice. David Gelemter, el creador de Linda [Markoff, 1992], cree que el procesamien­ to en paralelo con el uso de una red ordinaria de estaciones de trabajo, o incluso de PC, caracterizará la moderna oficina del futuro. Por lo menos una firma de Wall Street conduce sus actividades cotidianas de comercio empleando Linda sobre una red y utiliza también ciclos ociosos de CPU de diversas máquinas a lo largo del día para generar grandes modelos matemáticos de sistemas financieros. Los procesos de Linda son débilmente acoplados; es decir, sin memoria com­ partida, lo que permite al programador ignorar muchos de los problemas de sincronización que se presentan en sistemas de memoria compartida. Un simple programa de C-Linda para simular un juego de ping-pong con dos jugadores, que demuestra la comunicación de procesos, se muestra en el listado (5.5.1). /* PING_PONG. CL - Dos procesos en comunicación */

( 5 . 5 . 1 ) 12

//define NUM_PING_PONGS 1000 real_ia1n()

í Int p i n g O , p o n g O ;

/*los dos procesos co operando */

eval ( p i n g O ) ;

/*

pone ping en el espacio de tupias y se

bi f ur c a a un nuevo proceso para r e a l i z a r la evaluación */

eval

(pongO):

} pingO

/*

definición de ping */

12 Tomado del C-Linda Reference Manual®, Scientific Computing Associates, New Haven, CT.

Sólo fines educativos - FreeLibros

CAPÍTULO 5: C o n stru ccio n es d e len g u ajes p ara p ro cesa m ien to en p a ra lelo

265

[ ín t í ; for (i = 0; i < NUM_PING_P0NGS; ++) { out(“ping” ); /*

evalúa

y

posteri ormente regresa ping al

espaci o de tupi as */

InCpong");

/* quita pong del espacio de tupias

*/

} } pongO

[ lí lt i ; fo r (i = 0; i < NUM_PING_P0NGS; ++) í 1 n ( "p ing” ); /* quita ping del espacio de tupi as */ o u t ( " p o n g ” ); /* evalúa y posteri ormente devuelve pong al espacio de tupias */

} } Este programa no hace más que conmutar el control hacia atrás y hacia adelante entre ping y pong. Ambos procesos comienzan su ejecución en forma simultánea; ping es evaluado después de pong y remueve a este último del espacio de tupias. Después de su ejecución ping remueve a pong del espacio de tupias, el cual puede entonces ser evaluado cuando el proceso pong alcanza out( “ pong” ). Si agregamos una pequeña gráfica en C para cada proceso después de cada out, podríamos ver la "pelota" ir hacia atrás y hacia adelante sobre la pantalla. Quizá ping podría enviar la pelota de izquierda a derecha y pong de derecha a izquierda. C-Linda también tiene una facilidad para módulos de temporización. Esto ac­ túa como un cronómetro y es útil para recolectar la estadística acerca de la ejecu­ ción en paralelo y factores de rendimiento. Existe también varios niveles de rastreo de tupias que pueden ser activados o desactivados. Una estructura de datos, tal como un arreglo, puede estar distribuido en varias tupias; por ejemplo, cada renglón o elemento podría ocupar una tupia por separa­ do. Un programa podría entonces ser escrito con un solo maestro y tantos trabaja­ dores como hubiera tupias de arreglo, todos corriendo de manera simultánea, para procesar el arreglo. Los ciclos del listado (5.5.2) calculan los "cincos" que se repiten en el renglón de tabla, m = [0 ,5 ,1 0 ,1 5 ,2 0 ,2 5 ,3 0 ,3 5 ,4 0 ,4 5 ]. //define FALSE 0 //define TRUE1 1nt 1nt 1nt in t

(5.5.2)

dim - 9; workers = //processors a v a í l ab l e

*mCd1m]; w or k e r O ;

for (i = 0 ; i <= di n; ++i) out( “ f i v e s r o w ” . i , FALSE. mCi]);

/ ^d is t r i b u ye el ar r eg l o en di ez tupi as*/

Sólo fines educativos - FreeLibros

266

PARTE II: Lenguajes imperativos /*start wo rkers*/ for (i - 0; i <» dim; + + i K e v a l ( “f u n ct ion” , i, w o r k e r O ) ;

} w o r k e r t ){ 1nt i , *p; 1n (“f i v es row” ,? i , FALSE, ?p); *p - i * 5; o u t ( “f i v es row” ,i, TRUE, p)

/*manti ene cualquier tupia di sponible sin procesar */ /^calcula el valor de * p [ i ]*/ /*!o pone de vuelta en el espacio de tupias*/

3 Las declaraciones son código C. El primer ciclo distribuye las localidades de ele­ mento del arreglo a tupias separadas. FALSE indica que el valor del elemento aún no se ha calculado. Note que ? i se convierte a i y ? p a p después que se evalúa p y se asigna a m[i ]. Cada uno de los procesos trabajadores iniciados por el segundo ciclo evalúan cualquier tupia sin procesar en el arreglo distribuido. Si hay menos procesadores que el número dim de tupias por ser procesadas, cada procesador tendrá que evaluar la función trabajadora (worker) más de una vez. Antes del pro­ cesamiento, la tercera tupia es ( " f i ves row” , 3, 0, p ), en el que p apunta al cuarto elemento del arreglo mC3]. Después out (t ), *p - 15, y la tupia es ( " f i ves row” , 3, 1, p).

En el Laboratorio 5.2, se le solicitará finalizar el programa productor-consumi­ dor para dos productores y un consumidor, para lo cual involucrará la comunica­ ción entre tres procesos ejecutándose en paralelo. L A B O R A T O R IO 5.2: P R O D U C T O R E S - C O N S U M ID O R E S : PA SC A L S / O CC AM 2 / C -L IN D A

O bjetivos (Los Laboratorios pueden encontrarse en el Instructor's Manual) 1. Ver cómo se implementan tres procesos cooperativos en un lenguaje concurrente. 2. Experimentar con diferentes soluciones para el problema del productor-consumidor utilizando la concurrencia. 3. Intentar un tipo diferente de solución: el espacio de tupias de Linda. Se le solicitará programar dos procesos de Productor y un proceso de Consumidor en los lenguajes seleccionados por su instructor.

Objetos como unidades de paralelismo La programación basada en objetos u orientada a objetos es el área más actual en investigación y en aplicaciones de lenguajes de programación para la presente dé­ cada. Así, utilizar objetos como unidades de paralelismo ha recibido un nivel ele­ vado de atención. Los objetos pueden considerarse como "máquinas abstractas independientes que interactúan en respuesta a mensajes" [Caromel, 1989]. Pero la mayoría de los intentos para implementar objetos de ejecución concurrente no in­ Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

267

cluye paso de mensajes asincrónico temporizado en forma aleatoria. Las llamadas de procedimiento remoto, en las cuales un objeto llama a un procedimiento en otro objeto y espera una respuesta, es el método preferido. Esto ocurre así en lenguajes como Concurrent Smalltalk, ABCL/1 y Orient85. Emerald, desarrollado en la Uni­ versidad de Washington, también soporta procesos concurrentes. No está orienta­ do a objetos, sino basado en objetos, ya que la herencia no está soportada. Caromel [Caromel, 1989,1993] propone un modelo para lenguajes orientados a objetos en paralelo que fomenta los puntos fuertes de los objetos: reutilización, extensibilidad y programas altamente legibles. En Nancy, Francia, la experimenta­ ción con este modelo recibe un seguimiento bajo el uso del lenguaje de objetos Eiffel. Esta implementación usa un objeto llamado PROCESS, con dos métodos, Cr eat e y Live. C r e a t e permite la creación de una instancia de un objeto PROCESS, el cual procede a ejecutar su rutina Li ve. Cuando esta rutina se completa, el PROCESS mue­ re. Eiffel soporta herencia múltiple, en el que un solo objeto puede heredar de más de una superclase. De este modo, cualquier objeto apropiado podría llegar a ser un P ROC ESS al heredar los métodos de PROC ESS. Otra extensión similar, pero algo diferente, de Eiffel [Karaorman, 1993] permi­ te que cualquier objeto herede de la clase CONCURRENCY, la que hereda de ICP (Interprocess Comm unication Primitives), las Primitivas de Comunicación Interprocesos del sistema UNIX. CONCURRENCY requiere que cualquier clase que he­ rede de ella proporcione su propio planificador. El enfoque de la concurrencia orientada a objetos es modelar situaciones en las cuales los objetos actúan juntos, en vez de acelerar la ejecución del programa. Ésta es una nueva y creciente área de investigación, incluyendo los esfuerzos para com­ binar Concurrent C con su primo orientado a objetos C++ como una extensión simple para C.

5.6 ADMINISTRACIÓN DE FALLAS PARCIALES Cuando se pasan los mensajes, varios errores pueden ocurrir: 1. 2. 3.

El mensaje puede ser perdido por la red. La respuesta puede perderse. El servidor puede fallar antes de enviar la respuesta.

Una manera para manejar estas situaciones es que el cliente declare una pausa por un periodo especificado. Si la respuesta deseada no se recibe cuando el tiempo expirarse supone que ha ocurrido una de las tres contingencias y se toma acciones para remediarlo. Esto podría ser tan simple como volver a enviar la petición. Sin embargo, en una situación como la del segundo caso que se enumeró, esto puede no ser lo correcto. A menudo los procesos exhiben persistencia, con lo cual los valo­ res de estado se mantienen de invocación a invocación. Por ejemplo, suponga que el servidor incrementó un contador N y lo recuerda. Al volver a enviar una petición resultaría que N se incrementaría doblemente, aun cuando sólo una respuesta sea devuelta. Una posible solución a este problema es hacer atómico al servidor; es Sólo fines educativos - FreeLibros

268

PARTE n: Lenguajes imperativos

decir, del tipo todo o nada. De este modo, responderá en forma exitosa, o el estado anterior se restaurará. Las tareas de Ada son casi sin restricción, lo que puede conducir a errores de secuencia así como de bloqueo. Un error de secuencia ocurre cuando las tareas se comunican en un orden no anticipado. Una tarea está bloqueada cuando no puede proceder más. Un caso posible es el bloqueo o estancamiento circular (circular deadlock), como se muestra en la figura 5.6.1, en la cual cada tarea ha llamado a la siguiente en el círculo, la que no puede aceptarla hasta que llegue al punto de reunión (rendezvous) con la de adelante. Las tareas en ejecución concurrente son en particular difíciles de depurar debi­ do a que pueden ejecutarse de manera diferente cada vez que son invocadas. Las herramientas de depuración que se hallan en desarrollo se basan en monitores o durante tiempo de ejecución, en el cual una secuencia de "instantáneas" (snapshots) del programa son tomadas para resaltar los estados de los procesos en ejecución seleccionados cuando uno llega a bloquearse. Debido a las inconsistencias que se presentan de una ejecución a la siguiente, un sistema axiomático de demostración o prueba es en particular apropiado para validar los procesos concurrentes.

5.7

RESUMEN La programación distribuida incluye varios modelos. Todos involucran el uso de procesadores múltiples, cooperación entre los procesadores y manejo de las fallas de uno o más procesos en ejecución concurrente mientras otros continúan. Existe cuatro modelos principales: 1. 2. 3. 4.

Los que se basan en memoria compartida Los basados en paso de mensajes asincrónico (sin bloqueo) Los que se basan en paso de mensajes sincrónico (bloqueo) Una combinación de paso de mensajes y memoria compartida

FIGURA 5.6.1

Estancamiento o bloqueo circular Sólo fines educativos - FreeLibros

CAPÍTULO

5: Construcciones de lenguajes para procesamiento en paralelo

269

Ada implementa el cuarto modelo; mientras que Concurrent C, el tercero. No im­ porta cuál modelo se elija, los procesos en operación deben estar sincronizados si la información va a ser intercambiada. Los primeros mecanismos de sincronización fueron el semáforo y el monitor. Un semáforo controla el acceso a una sección críti­ ca de código. Un proceso que comienza a ejecutar este código crítico no puede interrumpirse hasta que haya completado la ejecución de este código. Los monitores contienen variables compartidas y cualquier operación permitida en ellas. Se co­ munican con otros monitores y también pueden ser accesados por procesos coope­ rativos. El punto de reunión o rendezvous es un tercer mecanismo para sincronizar procesos. Está basado en el modelo cliente/servidor, con el que un cliente solicita servicio y entonces espera hasta que se le proporciona. Occam también implementa el punto de reunión, pero aquí se le conoce como paso de mensajes. Las unidades de procesamiento de Ada, llamadas tareas, pueden ser creadas y destruidas en tiempo de ejecución; las de Occam, conocidas como procesos, son estáticas, como lo son sus canales de comunicación. Diversos lenguajes han sido desarrollados para experimentar con la concurren­ cia sobre un solo procesador. En ocasiones esto se denomina multiprogramación. Los procesos se piensan como de operación concurrente, pero en realidad se implementan a través de un intercambio de entrada y salida en un solo CPU. ALGOL 68, C, Modula-2, Pascal S y Concurrent Pascal son ejemplos de tales lenguajes. Un quinto modelo para la concurrencia es el espacio de tupias de Linda. Aquí, los procesos y sus variables asociadas se heredan y destruyen como tupias en una memoria asociativa con, pero separada de, la RAM de cada proceso. Los creadores de Linda hallaron este modelo más fácil de imaginar que el paso de mensajes y las memorias compartidas. Linda se implemento como un preprocesador para C o para Ada. No todos los teóricos coinciden en que los lenguajes orientados hacia procedi­ mientos proporcionen el mejor vehículo para implementar la concurrencia. El cue­ llo de botella de VonNeumann, en el que sólo una palabra es transferida dentro o fuera de la memoria en cada ciclo de procesador, aún causa problemas. En el capí­ tulo 8 examinaremos las nociones para el procesamiento en paralelo con el uso de funciones, después que el lector esté más familiarizado con los lenguajes funciona­ les por sí mismos. Las cláusulas de procesamiento lógico en paralelo serán consi­ deradas en el capítulo 7.

5.8 NOTAS SOBRE LAS REFERENCIAS [Wegner, 1983] proporciona una buen análisis de las diferencias entre monitores y el concepto de rendezvous (punto de reunión). Él usa Ada y CSP como ejemplos de la implementación de lenguajes de punto de reunión. Implementa un monitor en Ada, usando la definición de monitor de Brinch Hansen [Brinch Hansen, 1978]. [Bames, 1994,1996] es una buena introducción en la literatura en Ada y Ada95, escritos por John Bames, uno de los miembros clave en el equipo de diseño de Ada. Su principal línea de trabajo incluye las pruebas.

Sólo fines educativos - FreeLibros

270

PARTE

n: Lenguajes imperativos

Una buena representación de Concurrent C, con muchos programas ejemplo elementales, es [Gehani, 1986]. Describe una versión implementada en plataforma UNIX con un solo procesador. Por el tiempo en que se escribió este artículo, una versión para sistemas distribuidos se estuvo desarrollando en los laboratorios Bell. El apéndice A de [Ben-Ari, 1982] contiene un "paquete de implementación" para Pascal S. El paquete proporciona todos los códigos del programa Pascal nece­ sarios para implementar un interpretador de Pascal S, corriendo sobre un progra­ ma Pascal. La segunda edición de este libro [Ben-Ari, 1990], que se divide en tres partes, no hace referencia al Pascal S. La parte I considera sistemas de memoria compartida, semáforos y monitores. La parte II tiene que ver con paso de mensajes y vistas en los lenguajes Ada, Occam y Linda. La parte III analiza la implementación de estos temas, dando especial atención a sistemas de tiempo real, donde el tiempo de respuesta puede ser un tema. [Kerridge, 1987] es un buen tutorial sobre Occam que proporciona cierta canti­ dad de programas elementales así como también un análisis de cómo trabaja Occam con transputers. Para un breve análisis de Linda, se sugiere al lector consulte a [Leler, 1990], [Markoff, 1992] o [Carriero, 1989], El segundo artículo compara Linda con paso de mensajes, orientación a objetos, lógicos y modelos funcionales para programación concurrente. Sobresalen cuatro buenos tutoriales sobre la programación en paralelo, tres son de ACM y el cuarto de la IEEE. Éstos son [Brinch Hansen, 1978], [Andrews, 1983], [Bal, 1989] y [Shatz, 1989]. Se incluye en Shatz un buen análisis de las prue­ bas de depuración en Ada. La revista Communications ofthe ACM, de septiembre de 1993, se destinó a la programación orientada a objetos concurrentes. Se incluye [Caromel, 1993] y [Karaorman, 1993], así como artículos sobre sistemas operativos que soportan la concurrencia y a un sucesor concurrente de Trellis/Owl llamado DOWL.

Sólo fines educativos - FreeLibros

PARTE III

Autómatas y lenguajes formales

Esta sección contiene un capítulo en el que comenzamos a examinar los lenguajes de una manera más teórica. También incluimos temas acerca de aplicaciones prác­ ticas de esos conceptos teóricos para lenguajes de programación y diseño de compiladores. La jerarquía de Chomsky de los tipos de lenguajes formales proporciona la estructura para el material, desde el Tipo 3 (el más restrictivo) hasta el Tipo 0, que incluye todos los otros tipos. Examinaremos en particular el Tipo 3, gramáticas regulares, debido a su uso común en los compiladores para reconocer los compo­ nentes léxicos o tokens (elementos de programa) de un lenguaje. El Tipo 2, gramáti­ cas libres de contexto, se emplea con frecuencia para describir cómo dichos tokens se combinan para formar construcciones válidas de lenguaje. Las técnicas utiliza­ das ofrecen cierta visión acerca del análisis sintáctico o gramatical (parsing) de un programa y el entendimiento de su semántica (significado).

Sólo fines educativos - FreeLibros

CAPÍTULO 6 LENGUAJES FORMALES 6.0 En este capítulo 6.1 Lenguajes formales Definición de lenguajes formales La jerarquía de Chomsky de los lenguajes formales Viñeta histórica: Clasificaciones de los lenguajes: Noam Chomsky Tipo 3: Gramáticas regulares Tipo 2: Gramáticas libres de contexto Tipo 1: Gramáticas sensibles al contexto Autómatas lineales limitados (LBA) Viñeta histórica: Alan Turing: Lo que las máquinas no pueden hacer Tipo 0: Gramáticas no restringidas Ejercicios 6.1 6.2 Gramáticas regulares Expresiones regulares

273 274 275 277 278 280 281 282 283

286 288 289 290 291

Autómatas finitos (FA, NFA y DFA) Aplicaciones Ejercicios 6.2 6.3 Gramáticas libres de contexto (CFG) Autómatas descendentes (PDA) Árboles de análisis sintáctico Gramáticas ambiguas Aplicaciones Formas normales Forma normal de Chomsky (CNF) Forma normal de Backus (BNF) Diagramas de sintaxis Ejercicios 6.3 6.4 Gramáticas para los lenguajes naturales Ejercicios 6.4 6.5 Resumen 6.6 Notas sobre las referencias

Sólo fines educativos - FreeLibros

292 295 - 296 298 299 303 304 306 306 306 307 309 310 311 313 313 314

CAPÍTULO

6

Lenguajes formales

E l capítulo 2 trata con la abstracción, la destilación de una construcción de lengua­ je a su forma esencial desmenuzada. Como usted podrá recordar, examinamos tres aspectos de la abstracción: datos, control y modularización. Aquí no considerare­ mos las construcciones del lenguaje, sino la sintaxis, la forma escrita que un len­ guaje puede adquirir. Mencionaremos sólo de manera breve la semántica, el significado destinado de la sintaxis, y se dejará un tratamiento más completo para un curso posterior. El propósito de un lenguaje es la comunicación, ya sea con otras personas, con una computadora o con alguna otra entidad. Nuestra comunicación debe ser com­ prendida por la parte que la recibe, así como también por el escritor. Los lenguajes de computadora no son la excepción a este requerimiento. Las personas así como la computadora deben comprender el lenguaje en el que escribe el programador. Puesto que se encuentra involucrada una máquina, los lenguajes de programación deben ser muy precisos. Es necesario ajustarlos a reglas fijas. Aquí estudiaremos las reglas y símbolos de los lenguajes formales convenientes para la comunicación con las computadoras. Este capítulo se dirige a aquellos estudiantes que no planeen incluir un curso completo en diseño de compiladores o teoría de la computación en sus cursos de estudios universitarios. En vez de dirigimos al asunto de cuál lenguaje de progra­ mación es mejor para realizar una tarea en particular, trataremos con las caracterís­ ticas que debe tener cualquier lenguaje de computadora para ser reconocido por una computadora, el modo en que se construyen los lenguajes formales y las má­ quinas para reconocerlos.

6.0

EN ESTE CAPÍTULO Comenzaremos por examinar las maneras formales de especificar una gramáti­ ca. Existe cuatro tipos reconocidos de lenguajes formales (más algunos subtipos),

Sólo fines educativos - FreeLibros

274

PARTE

ni: Autómatas y lenguajes formales

cada uno de los cuales puede lograr diferentes cosas y son útiles para diversas tareas. Siguiendo la jerarquía de Chomsky, comenzamos por el tipo más restrictivo, el Tipo 3, después seguiremos por los Tipos 2 y 1, y por último con el Tipo 0, que incluye a todos los demás. Describiremos en forma tan sucinta como sea posible tres aspectos de cada tipo: • • •

Qué es lo que distingue a un tipo de otro de mayor jerarquía. La forma de las reglas gramaticales para los lenguajes del tipo. La máquina teórica que reconoce las palabras válidas del tipo.

Aún más, examinaremos de cerca el Tipo 3, gramáticas regulares y las expre­ siones regulares relacionadas, puesto que son de uso práctico en la definición de los tokens de un lenguaje. Después consideraremos el Tipo 2, las gramáticas libres de contexto y cómo se les utiliza en el reconocimiento de frases legales en la gramá­ tica. Por último, examinaremos brevemente las gramáticas para los lenguajes natu­ rales.

6.1

LENGUAJES FORMALES La estructura lexicográfica de ion lenguaje es la forma de sus tokens? La sintaxis des­ cribe las declaraciones que serán aceptadas como correctas por un compilador o intérprete para el lenguaje. La sintaxis, o precisamente lo que constituye una decla­ ración válida, está definida por una gramática que genera un lenguaje formal. Un lenguaje form al es el conjunto de declaraciones que en un contexto sintáctico son correctas. Una gramática implica una lista finita de símbolos, llamada un alfabeto, una lista finita de reglas para formar palabras con el alfabeto y quizás otro conjunto de reglas para formar declaraciones a partir de las palabras. Como un ejemplo, consi­ dere el minilenguaje que llamaremos Playa-Alegre. Alfabeto:

Regla:

Sustantivos: {Juan, María} Verbos: (nada, navega) Alfabeto = Sustantivos u Verbos u {"", .}2 S es una declaración de Playa-Alegre si S es de la forma N V., en el cual N £ Sustantivos, seguido por un espacio, seguido por V é Verbos, seguido por un punto.

El lenguaje Playa-Alegre es entonces las cuatro declaraciones {Juan nada., María nada., Juan navega., María navega.} Una computadora, aunque en forma esencial está compuesta de cadenas binarias y operaciones ligadas a éstas, también puede pensarse como una máquina 1Un token es una cadena válida en un lenguaje, tal como un identificador, un indicador de asigna­ ción (:=), una palabra reservada (por ejemplo, If), un comparador (por ejemplo, <), etcétera. 2 ' ' indica un espacio. Los signos de comillas no son elementos del alfabeto.

Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

275

virtual que se comporta como si se hubiera diseñado para reconocer exactamente un lenguaje y realizar las instrucciones codificadas en ese lenguaje. Por ejemplo, un lenguaje estructurado en bloques está implementado como una pila simple, mien­ tras que los lenguajes imperativos concurrentes requieren de varias pilas con colas asociadas. La máquina virtual para el lenguaje estructurado en bloques se compor­ taría como una pila, mientras que para los lenguajes imperativos concurrentes fun­ cionaría como pilas cooperativas con colas asociadas. En este capítulo, examinaremos lo básico de estas máquinas virtuales y comentaremos acerca de sus vínculos esen­ ciales para los tipos de lenguajes. Cuando hablamos de un lenguaje formal, nos referimos a la forma o sintaxis de las palabras válidas en el lenguaje. No nos interesa lo que eso significa; es decir, su semántica. Si "trabajo" y "casa" son palabras válidas, y una de las reglas de forma­ ción de palabras dice que la concatenación de dos palabras es también una palabra, entonces "trabajocasa", "casatrabajo", "casacasa" y "trabajotrabajo" son todas pala­ bras válidas. En español, las dos primeras tienen algún sentido, aunque su semánti­ ca sea diferente, pero las dos últimas no tienen sentido. ¡No importa! En un lenguaje formal con una regla de concatenación, la totalidad de las cuatro son válidas por igual. Los números no son tan ambiguos como las palabras en español. Si 3 y 17 son palabras en un lenguaje con una regla de concatenación, entonces 317,173,33 y 1717 también lo son. Las reglas formales para la generación y reconocimiento de lenguajes de com­ putadora son más sintácticas que semánticas, con la semántica descrita en algún lenguaje natural, en nuestro caso, el español. La sintaxis para la cadena 5 + 3 * 5 es el símbolo 5 seguido por un espacio, luego los símbolos +, espacio, 3, espacio, *, espacio y 5. Su semántica captura algunas reglas comunes de la aritmética de los números naturales. La semántica de cadenas válidas no será de interés aquí, aun­ que mucho de la teoría de los lenguajes trata de la noción de que la sintaxis apro­ piada captura los significados intuitivos, y que las declaraciones que son inexpresivas pueden bien no tener sentido. Los lenguajes formales son útiles al elaborar descripciones estándar, analizar si los lenguajes son correctos y construir generadores de análisis sintáctico o gramati­ cal como parte de un compilador. Como su primera tarea, un compilador debe analizar el código fuente descomponiéndolo en partes más finas; es decir, las decla­ raciones en expresiones, las expresiones en palabras, las palabras en tokens. Si el lenguaje sigue reglas formales, sin ambigüedades, esto puede ser automatizado sin dificultad. Se aplica diferentes niveles de análisis, desde el reconocimiento de erro­ res de sintaxis hasta la determinación de cuáles programas generan ciclos iterativos infinitos y cuáles terminan siempre con soluciones correctas al problema práctico. Los lenguajes formales y las máquinas teóricas que los reconocen son útiles, desde el reconocimiento de elementos del lenguaje hasta los niveles superiores para pro­ bar que un programa es correcto. D efinición de lenguajes formales Para definir un lenguaje formal L, necesitaremos dos cosas: 1.

Un alfabeto X de símbolos individuales. Sólo fines educativos - FreeLibros

276 2.

PARTE III:

Autómatas y lenguajes formales

Un conjunto de reglas para determinar cuáles cadenas o palabras3 de £ son válidas en L. Denotaremos el conjunto de reglas mediante la letra P, y cada una será dada en la forma a —» /?, llamada una producción.

En conjunto, el alfabeto y las reglas para formar palabras válidas son llamados una gramática sobre £. Por consecuencia, una gramática puede ser considerada como un par o 2-tupla (£, P). Si G es una gramática (£, P), generando un lenguaje L, L se escribe L(G). Por ejemplo, el lenguaje L(B), generado por la gramática B = (£, P) en el listado (6.1.1), es de todos los posibles decimales binarios no negativos menores que 1, correctos o aproximados a dos posiciones. L(B) = {0.00, 0.01, 0.10, 0.11), donde

£ = {0,., P = {Rl: R2: R3: R4: R5: R6:

1} S0

-> S2 -> S2 -> S3 -> S3 -»

(6 .1.1) 0ST .S2 0S3 1S3 0 1

Las reglas escritas en la forma a -» p se llaman producciones, debido a que se "produce" una nueva cadena a partir de una antigua mediante el reemplazo de la subcadena a la derecha por la correspondiente a la izquierda. Por ejemplo, la cade­ na 0.11 puede ser producida a partir de 0.1S3, al reemplazar la subcadena S3 por 1, utilizando la regla de producción R6. Cuando se genera una palabra para su inclusión en L(B), siempre comenzamos en S , el símbolo de inicio. La cadena inicial generada cuando se produce una palabra es el símbolo simple S0. Este último símbolo no se halla en el alfabeto de £ de símbo­ los terminales, y se le llama un no terminal. Tendrá que ser eliminado mediante algu­ na regla si va a producirse una cadena válida de L(B). En la gramática B del listado (6.1.1), el conjunto de no terminales es N = {SQ, S , S , S3). La aplicación de la regla R l involucra el reemplazo de SQcon OS . La aplicación de otras reglas implica reemplazo, en la cadena generada hasta ahora, de una ocu­ rrencia de alguna de las no terminales S por x, si S —» x es una regla. Si tanto Si x como S y son ambas reglas, cualquiera puede aplicarse. Por ejemplo, S3 puede reemplazarse ya sea con un 0 o un 1. Una derivación de la cadena 0.01 que represen­ te el decimal binario para V4 es: Rl R2 R3 R6 S0-> 0S1-> 0.S2-> 0.0S3-> 0.01 Un sistema de producción es una gramática G, en la cual las reglas están dadas en la forma de producciones. G = (£, N, P, Inicio) es una 4-tupla que incluye una serie de símbolos terminal, £; un conjunto de no terminales, N; un conjunto de reglas 3 Una palabra en un lenguaje L(G) incluye sólo símbolos de X, entre ellos la palabra vacía e. Este último no es un símbolo terminal ni uno no terminal. Una cadena puede incluir cualquier símbolo.

Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

277

de producción, P; y un símbolo de inicio, Inicio e S U N. En la gramática anterior, E = {0,1,.}, N = {S0, Sj, S2, S3) e Inicio = SQ.G es denominada una gramática estructurada en frases si toda producción resulta ser de la forma s. —> s., en la que s. y s son cadenas de (E U N) y s. contiene al menos una no terminal. (La mayoría de los autores emplea letras mayúsculas para no terminales y letras minúsculas o dígitos para terminales, pero esto es meramente una convención.) Usted se sorprendería al descubrir que existe sólo cuatro tipos de lenguajes formales, según la clase de reglas de producción que se utilice. Esta comunicación a escala fundamental no es tan variada como se podría pensar y ha atraído la aten­ ción de investigadores en diversos campos. Los lenguajes de cada forma tienen propiedades definitivas. De hecho, la relación entre lenguaje y máquina teórica es de uno a uno. Un lenguaje de un tipo particular se reconoce mediante una máquina específica. Lo opuesto se mantiene también; pero más en esto último. Primero ne­ cesitamos ver qué clases de lenguajes formales existe.

L a jerarq u ía de C hom sky de los lenguajes form ales

Muchos investigadores han trabajado en las formas de las reglas de decidibilidad4 para generar lenguajes de tipos particulares; esto plantea varias interrogantes. ¿Cuá­ les restricciones son justamente esenciales y cuáles pueden despreciarse? Con una clase dada de reglas, ¿qué tipo de problemas puede resolverse? Dado un lenguaje, ¿qué máquinas pueden reconocer en forma apropiada las cadenas formadas y re­ chazar aquellas que sean inválidas? Por otra parte, ¿qué es una máquina? ¿Para qué tipo de lenguajes una máquina siempre tendrá éxito al reconocer cadenas váli­ das? ¿Puede una máquina reconocer cadenas potencialmente infinitas?5 ¿Para qué aplicaciones son más apropiados ciertos lenguajes? Aunque los investigadores trabajaban en forma independiente sobre la teoría de los lenguajes formales, sus diversas formulaciones cayeron dentro de las mis­ mas cuatro distintas clases, comenzando con conjuntos de reglas bastante irrestrictas a través de las cuales se volvían cada vez más rígidas. Sólo más tarde se reconoció que cada una de estas formulaciones era equivalente a las mismas cuatro clases de lenguajes. Las máquinas que reconocían los lenguajes formados mediante reglas irrestrictas pueden generar soluciones para una variedad de problemas, pero nin­ guna máquina puede decidir si puede o no resolver cualquier problema arbitrario. Las máquinas que reconocen los lenguajes basados en clases de reglas más estrictas pueden garantizar la generación de soluciones, pero para una clase limitada de problemas. Examinaremos los tipos de lenguajes formales descritos por el lingüista Noam Chomsky. Como se muestra en la figura 6.1.1, estos lenguajes forman una jerarquía en la que cualquier lenguaje de Tipo 3 es también de Tipo 2, cualquier lenguaje de

4Una regla es de decidibilidad si existe un procedimiento efectivo de decisión para generar un sí o un no en un número finito de pasos. 5Una cadena es potencialmente infinita si no conocemos su longitud; es decir, una cadena de la forma an es infinita en forma potencial si no conocemos el valor de n. Para cualquier valor fijo de n, podemos generar una cadena que sea más larga.

Sólo fines educativos - FreeLibros

278

PARTE III: Autómatas y lenguajes formales

Tipo 0: Lenguajes recursivamente enumerables reconocidos por las máquinas de Turing

Tipo 1: Lenguajes sensibles al contexto reconocidos por autómatas lineales limitados Tipo 2: Lenguajes libres de contexto reconocidos por autómatas descendentes Tipo 3: Lenguajes regulares reconocidos por autómatas finitos

F I G U R A 6.1.1

La jerarquía de Chomsky

Tipo 2 es asimismo de Tipo 1, y aquellos que sean de Tipo 1 también lo son del Tipo 0. Este último es el más general, incluye a todos los otros tres tipos. Como veremos, cada tipo de lenguaje está asociado con una máquina de cómputo particular. Las gramáticas estructuradas por frases están asignadas a la jerarquía de Chomsky bajo los fundamentos de las formas de las producciones. Pero primero veamos quién es Noam Chomsky.

VIÑETA HISTÓRICA Clasificaciones de los lenguajes: Noam Chomsky Todos hemos oído hablar de las lenguas romances, pero rara vez del individuo que ha tenido toda una vida de romance con las lenguas o lenguajes, Noam Chomsky es ese individuo. Su profundo interés en el estudio de la lingüística comenzó cuando tenía sólo 10 años de edad. Estaba muy interesado con las demostraciones de una gramática del siglo Xin que leía en escritos de su padre. Ésta se encontraba escrita de un modo informal y no conforme a la escuela estructural tradicional de la lingüística. La introducción informal de Chomsky al estudio de los lenguajes matizó su futura labor en ese campo. Uno no puede más que intrigarse al pensar si él hubiese llega­ do a ser el revolucionario lingüista que ha sido si su primera aproximación al cam­ po hubiese sido más tradicional. En 1945 Chomsky ingresó a la Universidad de Pennsylvania donde se graduó en lingüística. Aquí es donde su interés de toda la vida en cambio político comenzó a surgir. Estaba atento en particular a los sucesos que condujeron al establecimiento del estado de Israel. Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

279

En 1951 recibió el grado de M.A. de la Universidad de Pennsylvania con una tesis llamada "Morfemas del Hebreo Moderno", basada en los esfuerzos para de­ sarrollar un sistema de reglas que podría utilizarse para caracterizar toda estructu­ ra de frases en un lenguaje* Recibió un Ph. D. en lingüística en 1955. Al principio Chomsky pasó por una época muy difícil para publicar alguno de sus trabajos, los cuales resultaron muy revolucionarios para la comunidad lingüís­ tica establecida. No sólo exponía lo inadecuado de las gramáticas estructuralistas, también criticaba la práctica lingüística más moderna. La escuela estructuralista planteaba que el lenguaje es principalm ente función del com portam iento conductista, según la respuesta del individuo a su medio ambiente externo. Chomsky sentía que la explicación estructural no tomaba en cuenta la creatividad lingüística en los humanos. Acerca del conductismo decía que, "el entrenamiento tipo skinneriano* es apropiado sólo para los trabajadores del área industrial que necesitan desarrollar complejas habilidades técnicas. ¿Es el crecimiento y aprendi­ zaje nada más que la forma de los comportamientos? Si eso es todo lo que la educa­ ción significa, figuras autoritarias formando personas, entonces tal vez no necesitemos de ella" [Newsweek, agosto 26 de 1968]. Creía también que la lingüísti­ ca moderna "no ha reconocido explícitamente la necesidad de complementar una 'gramática particular7de un lenguaje con una gramática universal si es para conse­ guir una adecuación descriptiva. De hecho, ha rechazado en forma característica el estudio de la gramática universal por estar desencaminada, y... no ha intentado tratar con el aspecto creativo del uso del lenguaje. De este modo, no sugiere ningu­ na manera de superar la insuficiencia descriptiva fundamental de las gramáticas estructuralistas" [Chomsky, 1965]. Para apoyar sus teorías, Chomsky confiaba fuertemente en las matemáticas, y publicó su primer libro en 1957. En ese tiempo él era profesor de lingüística en el MIT. En Cartesian Linguistics [Chomsky, 1966], dividió el estudio de la lingüística en tres categorías principales: 1.

2.

3.

Investigaciones que se enfocan en forma directa a la naturaleza del lenguaje, incluyendo descripciones de sintaxis, semántica, fonología (el estudio de los sonidos) y sus evoluciones Estudios acerca del uso del lenguaje y las habilidades y organización mental que esto presupone, tal como los procesos de aprendizaje del lenguaje en niños y adultos, y el lenguaje como se le emplea en la literatura. Estudios sociológicos de fondo con el establecimiento de los diversos enfoques para el estudio del lenguaje en configuraciones intelectual e histórica apro­ piadas.

Aunque se le considera un genio en el campo de la lingüística, Chomsky nunca minimizó sus dificultades. En una ocasión afirmó: "Puede estar más allá de los límites de la inteligencia humana comprender cómo trabaja la inteligencia huma­ na" [Time, febrero 16 de 1968]. Los intereses políticos de Chomsky resurgieron alrededor de 1965 con sus pro­ testas por la guerra de Vietnam. Llegó a ser un líder en organizaciones de paz como

N. del T.: De B. F. Skinner, psicólogo estadounidense, padre del conductismo.

Sólo fines educativos - FreeLibros

280

PARTE III:

Autómatas y lenguajes formales

Resist, un movimiento nacional de resistencia a la conscripción. Dio cursos univer­ sitarios sobre cambio político y publicó muchos escritos de sus puntos de vista pacifistas. Una vez más, retó en forma franca a las autoridades. Israel Shenker es­ cribió en el New York Times (octubre 27 de 1968): "En la segunda década de su vida, Noam Chomsky revolucionó la lingüística. Después de sus treinta años, ha estado intentando revolucionar la sociedad." Sus escritos continúan hasta la actualidad. The Culture ofTerrorism [Chomsky, 1988], evidencia las políticas de Estados Unidos en áreas como Centroamérica e Irán; establece que "incluso en una sociedad am­ pliamente despolitizada como la de Estados Unidos, sin partidos políticos o prensa de oposición más allá del reducido espectro del consenso dominado por los intere­ ses mercantiles, es posible que la acción popular tenga un impacto significativo en la política, aunque sea indirectamente. Esa fue una lección importante para la gue­ rra de Indochina. Es de resaltar, una vez más, por la experiencia de los años ochen­ ta en lo que se refiere a Centroamérica. Y debería recordarse para el futuro" [Chomsky, 1988]. Su influencia hasta la actualidad continúa en otros campos además de la lin­ güística y el activismo político. Su legado es muy sobresaliente en la ciencia de la computación. Su desarrollo de una teoría matemática de los lenguajes naturales y la descripción de cuatro diferentes clases de lenguajes ha hecho posible el análisis de la sintaxis y la gramática de los lenguajes de programación. "Esto ha tenido beneficios prácticos importantes puesto que permitieron el desarrollo de genera­ dores de analizadores automáticos, automatizando de esta manera lo que había sido una de las partes más difíciles de la escritura de compiladores" [MacLennan, 1987].

Tipo 3: Gram áticas regulares Una gramática estructurada en frases G = (X, N, P, Inicio) es una gramática regular si sus producciones son de la forma: A —» a, o A —> aB, en el que A,B G N, y a G E.

(6.1.2)

Es decir, el primer símbolo en cada lado derecho debe ser una terminal y puede seguirle una no terminal. Considere, por ejemplo, las siguientes reglas para la creación de un identificador Pascal I: I —» a I ... I z I aL I ... I zL 1aD 1... I zD L —» aL I... I zL I aD I... I zD I a I... I z D —» 0 L I ... 19L10DI... 19D10 1... 19

(6.1.3)

Aquí I significa (OR); esto permite una abreviación para varias reglas. Entonces I es ya sea una letra o bien una letra seguida por una secuencia finita de caracteres alfanuméricos (letras y/o dígitos). Tales gramáticas pueden ser reconocidas por autómatas finitos (FA), que en ocasiones se conoce como autómatas de estado finito (FSA). Si se comienza en el

Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

281

estado inicial S0, a medida que cada nuevo símbolo es leído, hay una transición a otro (o quizás el mismo) estado. Dentro de un número finito de pasos debe deter­ minarse si una cadena es válida o inválida. Las gramáticas regulares son utilizadas a menudo en la fase de análisis lexicográfico de un compilador, que en ocasiones se conoce como el rastreador (scanner), en la cual los tokens válidos de un lenguaje son aceptados. Debido a esta im­ portante aplicación, examinaremos más de cerca las gramáticas regulares y los autómatas finitos en la sección 6.2.

Tipo 2: Gram áticas libres de contexto El tipo siguiente, que es menos restrictivo que el Tipo 3, es el Tipo 2. Los lenguajes Tipo 2, que se conocen también como libres de contexto, son en especial importan­ tes en la ciencia de la computación debido a que todas, excepto algunas, de las características de los lenguajes de programación de alto nivel pueden ser escritas haciendo uso de ellas. Como antes, vamos a caracterizar estos lenguajes al descri­ bir las gramáticas libres de contexto (CFG; Context-Free Grammars) que generan cadenas válidas, y las máquinas teóricas que las reconocen. Una gramática estructurada por frases, G = (X, N, P, Inicio), es libre de contexto si las producciones son de la forma: A —» s, en el cual A G N, el conjunto de no terminales, y s es cualquier cadena de X U N

(6.1.4)

Las gramáticas regulares son, por supuesto, libres de contexto ya que las cade­ nas de la forma 'a' o 'aB' son candidatos para s del lado derecho. Las gramáticas libres de contexto pueden escribirse con el uso de producciones de formas diferen­ tes al ejemplo (6.1.4), pero una gramática así siempre puede mostrarse como equi­ valente a una del tipo citado. Las CFG son llamadas libres de contexto porque pueden hacerse reemplazos dondequiera que se presenten, y no en el contexto de otros símbolos circundantes. Por ejemplo, una regla libre de contexto permitiría el reemplazo del artículo "el" con "este" en una frase en español; es decir, "El perro ladraba" "Este perro la­ draba". Una regla sensible al contexto sería reemplazar (en idioma inglés) "the" con "an" si la palabra siguiente comienza con una vocal, y de otro modo, reempla­ zarlo con "a". "The dog barked" —» "A dog barked" (bark: ladrar), mientras que "The otter barked" —>"An otter barked" (otter: nutria). Aquí el contexto del reem­ plazo es la palabra que sigue al artículo que será reemplazado. Como las gramáticas regulares son reconocidas por FA, un CFG puede ser re­ conocido por un autómata descendente (PDA; Push-Down Automaton). Como su nombre implica, aparte de la cadena de entrada, puede utilizarse una pila para un PDA. Éstos se usan con frecuencia en el analizador de un compilador, el cual toma tokens de la gramática como entrada y reconoce si el programa se encuentra en sintaxis apropiada. En este caso, cuando la forma del lado derecho de una regla está sobre la pila, podemos extraer esas entradas, después introducir la no terminal resultante del lado izquierdo sobre la pila. Examinaremos más de cerca las CFG, PDA y el análisis en la sección 6.3. Sólo fines educativos - FreeLibros

282

PARTE III:

Autómatas y lenguajes formales

Tipo 1: Gram áticas sensibles al contexto Existe lenguajes que no son libres de contexto. Una de las palabras más simples que no puede ser generada por una CFG es anbncn, para una n arbitraria pero fija. La demostración se encuentra más allá del alcance de esta breve introducción, pero puede hallarse en [Cohén, 1991]. Las producciones a —>/?para las gramáticas sen­ sibles al contexto (CSG; Context-Sensitive Grammars) son como las de los lengua­ jes libres de contexto, con las siguientes excepciones: 1. 2.

El lado izquierdo a puede contener más de un símbolo mientras que al menos uno sea un no terminal. La longitud de a es menor que o igual a la longitud de /3.

La segunda regla asegura que no existe producciones vacías, aquellas en las que el lado derecho es la cadena vacía e. El lector puede consultar lo referente a las reglas de borrado en el ejercicio 6.1.3. Esta última restricción evita los finales muer­ tos (dead end), en los cuales lo que se reemplaza, a, puede llegar a ser más extenso que la palabra generada hasta ahora. Una gramática CSG para palabras de la forma anbncn es: 1. 2. 3. 4. 5. 6. 7.

S - » aSBC S -> aBC CB- >BC aB ab bB -» b b bC —>be cC cc

y la producción de a3b3c3 es: 1 1 2 3 3 3 S —^aSBC —>aaSBCBC —) aaaBCBCBC —) aaaBBCCBC —) . . . —^ 4 5 aaaBBBCCC —» aaabBBCCC

5

6 7 aaabbbCCC —» aaabbbcCC —> . . .

7 ^aaabbbccc La única diferencia entre estas reglas de producción y las correspondientes a una CFG es la presencia de dos símbolos en los lados izquierdos de las reglas 3-7 anteriores. Éstos proporcionan los contextos. B puede cambiarse a b cuando esté precedida por una a (regla 4) o cuando lo esté por una b (regla 5). Las gramáticas de Tipo 1 que se utilizan para el procesamiento del lenguaje natural se conocen a veces como gramáticas estructuradas en frases restringidas. Una regla típica estructurada en frase es S: —>NP VP, en la que S denota una oración, NP una frase sustantiva y VP una frase verbal. Se incluye otras restricciones aparte de las enumeradas antes para gramáticas sensibles al contexto, con el fin de eliminar características que no se presentan en los lenguajes naturales. Ejemplos de algunas Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

283

construcciones indeseables de esta clase son NP —» NP S, o VP —>V VP, en el que V representa un verbo. Con las reglas sensibles al contexto, las cadenas de la forma NP NC VP pueden reemplazarse por NP PP VP2VP, en la cual PP es un pronombre personal. Por ejemplo, si NP es "El tigre" y VP es "se comió a la dama", NP PP VP2 VP se reemplazaría por algo como "El tigre, que estaba detrás de la primera puerta, se comió a la dama". Las gramáticas sensibles al contexto pueden ser reconocidas por un autómata lineal limitado, el cual es una Máquina de Turing (MT) con una cinta finita. In­ cluimos una breve introducción a las MT más adelante, puesto que algunos lecto­ res pueden no tener un curso de Teoría de la Computación en sus curricula universitarios.

A u tóm atas lin eales lim itad os (LBA; Linear-Bounded A utóm ata) Dado un lenguaje L, un reconocedor es un programa que se utiliza para determinar si una cadena S dada es o no una cadena válida en el lenguaje. Considere de nuevo el lenguaje L que aparece en el listado (6.1.1), el cual determina ciertos números decimales binarios. Un reconocedor debería decimos que 0.01 £ L y que 1.01 £ L. Un reconocedor para un lenguaje sensible al contexto es una Máquina de Turing (MT) determinística con una cinta finita, llamada autómata lineal limitado o LBA (por sus siglas en inglés). Requiere sólo de una cinta, mientras que el PDA, que reconoce lenguajes libres de contexto, utiliza dos. Una MT requiere de seis cosas [Cohén, 1991]: 1. 2. 3.

4. 5. 6.

Un alfabeto, X, de símbolos de entrada. Una cinta dividida en celdas, llamadas 1 , 2 , 3 , . . . Una cabeza de lectura/escritura que pueda moverse una celda a la izquierda o derecha, leer lo que encuentre y escribir o borrar esa información. No permiti­ remos a la cabeza ir más allá (a la izquierda) de la celda 1, puesto que no existe celdas que la precedan. Un alfabeto, T, de caracteres que pueda escribirse sobre la cinta. F puede in­ cluir a X, pero no lo necesita. Un conjunto finito, S, de estados, entre ellos Inicio (Start) y Alto (Halt). Un conjunto de reglas llamado programa, P. Cada regla es de la forma (estado^ leer-carácter, escribir-carácter, dirección, estado2). Si el estado actual de la MT es estado^ la cabeza lee el valor de leer-carácter en la celda, y escribe un valor de escribir-carácter a la misma celda y la mueve ya sea a la derecha o a la iz­ quierda. El nuevo estado es entonces estado2.

Veamos un ejemplo bastante extensivo de un LBA, LBA(AnBnCn) = (X, T, S, S0, S , P), para reconocer cadenas de la forma anbncn. El lenguaje de entrada X = {a b c #}. Aquí # marca el final de la entrada. F = (A B C T). T es un símbolo temporal utilizado para reemplazar las B. La cadena 'aabbcc' se transformará en 'aabbcc' 'AATTcc' —»AABBCC. Las T cuidan del contexto; la transformación extra es nece­ saria porque las b se encuentran entre las a y las c. La cinta LBA es inicializada para la cadena de entrada, y comienza el procesamiento en el estado SQ.Habrá reconoci­

Sólo fines educativos - FreeLibros

284

PARTE III:

Autómatas y lenguajes formales

do una cadena correcta cuando todas las letras minúsculas hayan sido cambiadas a mayúsculas, el símbolo # haya sido alcanzado y la máquina se encuentre en S5. Los estados son: SQ: Cuando la cabeza de lectura-escritura, *, se encuentra en una celda, y la máquina está en S0, todas las celdas antes de la celda, son correctas y no necesitan procesamiento adicional. Una a acaba de ser cambiada por una A, y buscamos ahora a la derecha una b para compararla. S2: Una b acaba de ser cambiada a una T, y estamos buscando a la izquierda por la siguiente a para cambiarla. S3*. Una T acaba de ser cambiada por una B, y buscamos ahora a la derecha una c para compararla. S4: Una c acaba de ser cambiada a una C, y estamos buscando a la izquierda la T siguiente para cambiarla. S5: HALT La figura 6.1.2 muestra el procesamiento de 'aabbcc'. El * muestra la posición de la cabeza de lectura-escritura. Hemos visto la ejecución de un programa exitoso, de modo que es tiempo de ver el programa mismo, como se ilustra en el listado (6.1.5). Cada instrucción se aplica al (estado actual, leer, escribir, mover y nuevo estado), dándonos los detalles necesarios para que se utilicen en los cambios de estado descritos antes. En la pri­ mera regla, por ejemplo, si estamos en el estado S0 y leemos una a, escribimos una A, nos movemos a la derecha, y pasamos al estado S . En el ejercicio 6.1.4, se le solicitará al lector que siga la secuencia de instrucciones empleadas en la ejecución mostrada en la figura 6.1.2. S0 a A R Sj) s 0 t b r s 4) S0 C C R S0) S0# # R S s) Sj a a R Sj)

(Inicia el procesamiento aqui)

(6.1.5)

{Buscando # para HALT} HALT {Buscando hacia adelante por una b para coincidir con una A}

S j T T R S j)

Sj b T L S2) S2 T T L S2) S2 a a L S2) S2A A R S 0) S3T T R S3) S CCRS) S j C C L S4) S4 C C L S4) S, T T L S.) S4 B B R S q)

{Buscando hacia atras por la siguiente a)

{Buscando hacia adelante por una c para coincidir con una B}

{Buscando hacia atras por la siguiente T}

La última regla (S4 B B R S0) es semejante a las otras, en la cual el símbolo leído, en este caso B, es el mismo que el escrito e indica que la celda que se está rastreando

Sólo fines educativos - FreeLibros

CAPÍTULO

E stado

Cinta

6: Lenguajes formales

Estado

285

Cinta

S 0:

a

a

b

b

c

c

#

A

A

B

T

C

c

#

Si:

A

a

b

b

c

c

#

A

A

B

T

C

c

#

Si =

A

a

b

b

c

c

#

A

A

B

T

C

c

#

S 2:

A

a

T

b

c

c

#

A

A

B

B

C

c

#

S 2:

A

a

T

b

c

c

#

A

A

B

B

C

c

#

S0:

A

a

T

b

c

c

#

A

A

B

B

C

C

#

Sv

A

A

T

b

c

c

#

A

A

B

B

C

C

#

Sv

A

A

T

b

c

c

#

A

A

B

B

C

C

#

S 2:

A

A

T

T

c

c

#

A

A

B

B

C

C

#

S 2:

A

A

T

T

c

c

#

A

A

B

B

C

C

#

S0:

A

A

T

T

c

c

#

s 3;

A

A

B

T

c

c

#

S 3:

A

A

B

T

c

c

#

S 0: Halt (Alto)

F I G U R A 6.1.2

Reconocimiento de aabbcc en LBA(AnBnCn)

permanece sin cambios cuando nos movemos a la siguiente celda y estado. Algu­ nas descripciones de las Máquinas de Turing ofrecen la opción de moverse sin es­ cribir. Elegimos volver a escribir un símbolo sólo para hacer más fácil la presentación. Sólo fines educativos - FreeLibros

286

PARTE ni: Autómatas y lenguajes formales

Un autómata lineal limitado determinístico (LBA) es una Máquina de Turing que se detiene en un lapso finito y que es determinística; es decir, para cada par de instrucciones, IN 1e IN2, s i INÍ = (S1X Y Z S2) e IN2 = (S3A B C S4) y si Sx = S3, X = A, Y = B y Z = C, entonces S2 = S4. Esto significa que el siguiente paso está siempre determinado por completo por el estado y la entrada. Si introducimos una cadena, la MT puede decidir si es una cadena legal o no en periodo proporcional a la longi­ tud de la cadena. Por supuesto, tomará más tiempo procesar a2346b2346c2346que a2b2c2, pero alguna función de la MT nos dirá cuánto tiempo más tomará. Nuestro grupo final de lenguajes no tendrá estas garantías.

VIÑETA HISTÓRICA Alan Turing: Lo que las máquinas no pueden hacer El título de la biografía de Alan Turing escrita por Andrew Hodges [Hodges, 1983], Alan Turing; El Enigma, es un juego de palabras. Enigma, que significa un misterio o problema desconcertante, también es el nombre de una ingeniosa máquina que utilizaron lo alemanes para generar códigos durante la Segunda Guerra Mundial. Turing fue ton genio matemático que descifró el código Enigma en 1942; estuvo convicto por "conducta indecente" (un eufemismo para la hom*osexualidad) en 1952, y se suicidó al comer una manzana empapada con cianuro en 1954. Es de estos asuntos que se hacen las leyendas, y por supuesto, el libro de Hodges fue llevado a una exitosa representación teatral en Broadway en 1988. Alan Turing nació en 1912, de padres en el Servicio Civil Indio de la Gran Bre­ taña. En 1933 ingresó a la Universidad de Cambridge para aprender matemáticas. Éstos eran tiempos vehementes, a medida que dos importantes preguntas acerca de la naturaleza de las matemáticas, cuestionamientos sobre su integridad y/o con­ sistencia, habían sido contestadas en forma negativa, mientras que una tercera per­ manecía abierta. En 1931 Kurt Gódel demostró que cualquier sistema matemático útil no podría ser completo sin ser inconsistente. Un sistema completo es aquel en el cual puede probarse cualquier proposición verdadera, mientras que uno consistente es aquel en que ninguna proposición falsa puede ser probada. En 1931 Gódel había demos­ trado que cualquier sistema matemático con suficiente complejidad para incluir multiplicación y división contiene proposiciones verdaderas que hacen al sistema inconsistente si son probadas. Una proposición de este tipo que puede expresarse en la Teoría de la Aritmética de Enteros (AE) es, G: "La fórmula G no es demostrable"

(6.1.6)

La fórmula G dice entonces de sí misma que no es demostrable; es decir, que no se puede probar dentro de la AE. Si se proporciona una prueba, la proposición es falsa, haciendo inconsistente la teoría, y si la proposición es verdadera, no puede hallarse una prueba, de modo que la teoría estaría incompleta. Tales proposiciones se conocen como "autorreferidas"(se// referent) porque hacen referencia a sí mis­ mas. La fórmula G misma es: G: (x) ~Dem(x,sub(n,13,n)) Sólo fines educativos - FreeLibros

(6.1.7)

CAPÍTULO 6: Lenguajes formales

287

El modo preciso en que la fórmula (6.1.7) expresa la (6.1.6) se encuentra más allá del alcance de este libro. El lector interesado puede consultar a [Nagel, 1958], En 1933, una pregunta aún abierta era si había algún método "mecánico" para determinar cuáles proposiciones eran decidibles o no; es decir, puede tomarse una decisión por adelantado acerca de qué clases de problemas llevarán a respuestas y cuáles conducirán a cálculos infinitos sin una decisión. Un método "mecánico" es aquel que sigue reglas, pero puede o no efectuarse en una máquina física. Alan Turing eligió dirigirse a este problema de la decidibilidad. Primero tuvo que hacer precisiones acerca de lo que se entiende por una "máquina". Esto resultó en una máquina teórica de la que se podría esperar que resolviese cualquier pro­ blema que otra máquina, o ser humano, siguiendo reglas especificadas, podría re­ solver. Él fue capaz de encontrar siete preguntas que una máquina de este tipo no puede contestar. 1. 2. 3. 4. 5. 6. 7.

Dada una máquina M para resolver problemas arbitrarios y un problema arbi­ trario P, ¿puede M resolver P? Dada una máquina particular M, ¿es capaz M de resolver un problema P arbi­ trario? Dada M, ¿puede reconocer la ausencia de problemas cuando los vea? Dada M, ¿es capaz de resolver cualquier problema en absoluto? Dada M, ¿puede resolver todos los problemas? Dadas dos máquinas, M I y M2, ¿son capaces de resolver los mismos proble­ mas? Dada una Máquina de Turing MT, ¿el lenguaje MT acepta regular? ¿libre con­ texto? ¿decidible?

La Segunda Guerra Mundial interrumpió los estudios teóricos de Turing, cuan­ do se le asignó a la Escuela del Gobierno de Códigos y Cifrado (GCCS; Government Code and Cypher School), justo a medio camino entre las universidades de Oxford y Cambridge. Los alemanes utilizaban una máquina con cuatro rotores con el pro­ pósito de generar códigos para las transmisiones hacia, entre otras cosas, sus sub­ marinos. Con 26 caracteres y cuatro rotores, un código podría tener 26 x 26 x 26 x 26 = 456 976 diferentes configuraciones, y los alemanes cambiaban el código diaria­ mente. Por 1940, los británicos tenían diseños de la máquina Enigma, obtenidos por agentes polacos, pero la determinación exacta de cuál era el estado de los rotores permanecía como un problema. Lo que se necesitaba era una máquina para anali­ zar códigos de enigma y descifrarlos con rapidez. Los conocimientos de Turing en teoría de números, lógica matemática y teoría de la probabilidad, más la ingeniería necesaria para construir una máquina en la práctica, rindieron frutos. En 1942 GCCS construyó una máquina, llamada "Bomba" debido a su fuerte sonido, capaz de descifrar los códigos de Enigma. Alan Turing fue el cerebro detrás de este logro. No es una exageración decir que este esfuerzo cambió el curso de la guerra. Como resultado, los británicos fueron capaces de determinar la ubicación exacta de cada submarino alemán en diversos mares. Después de la guerra, Turing volvió a su investigación ligada a las capacidades de la Máquina de Turing en el National Physical Laboratory y en la Universidad de Manchester. Su prometedora carrera se derrumbó con su arresto en 1952. Su muer­ Sólo fines educativos - FreeLibros

288

PARTE ni: Autómatas y lenguajes formales

te en 1954 fue considerada por la mayoría como un suicidio, pero el chapucero trabajo policiaco nunca pudo eliminar la posibilidad de un accidente. Algunos tratadistas creen que esto era un subterfugio, destinado por Turing para ahorrarle a su familia la ignominia de un suicidio. Ellos eran libres de creer lo que quisieran. Durante su breve existencia, Alan Turing se enfrentó a algunas de las interro­ gantes más profundas que planteaban las computadoras. ¿Puede una máquina ser tan "inteligente" como un humano? ¿Es el libre albedrío compatible con una visión mecánica del mundo? ¿Las emociones y la razón son lo mismo o cosas diferentes? ¿Pueden comprender las máquinas las experiencias humanas como el amor, la frus­ tración, el sufrimiento o la desesperación? También intentó combinar las matemá­ ticas, la filosofía y la ingeniería; algo ridiculizado durante su existencia, pero ahora tomado en cuenta, 42 años después de su muerte.

Tipo 0: G ram áticas no restringidas Las gramáticas Tipo 0 son construidas sin restricciones sobre las reglas de reempla­ zo, excepto que una no terminal debe aparecer en la cadena del lado izquierdo. Los lenguajes generados se conocen como lenguajes Tipo 0 o, de un modo más común, recursivamente enumerables (r.e.). Las producciones de Tipo 0 son las mismas que aquellas para los lenguajes Tipo 1, excepto que la regla 2, en la cual el lado izquierdo no debe ser más extenso que el derecho, se elimina. De este modo una gramática Tipo 0 es: 1. 2. 3.

Un alfabeto X de símbolos terminales Un alfabeto T de no terminales, incluyendo un símbolo de inicio Un conjunto de reglas de producción a —>¡i, en el que a y /?son cadenas de X U T, con a conteniendo por lo menos una no terminal, y sin restricciones sobre /?

Los reconocedores para lenguajes Tipo 0 son Máquinas de Turing, las cuales ya fueron presentadas, pero en este caso la cinta puede ser infinita, aunque el número de estados sea finito. Un ejemplo detallado de un lenguaje Tipo 0 que no es también del Tipo 1 está más allá del alcance de esta breve introducción, pero existe. Considere el lenguaje regular CWL (Code Word Language), generado por la gramática regular en el lista­ do (6.1.8). S —> a S l a B B ->bC C —>aC I aD D->bE E -> aF I bF F -» aG I bG G aH I bH H —>al I bl I ->a I b

(6.1.8)

Sólo fines educativos - FreeLibros

CAPÍTULO 6: Lenguajes formales

289

Cohén [Cohén, 1991] presenta una MT = (X, T, S, Sir S2, P), que reconoce pala­ bras de CWL como se muestra en el listado (6.1.9). X = (a, b, A], T = |b}, S - \SV S2, S3} P: (Sj, b, b, R, S}) (S1, a, b, R, S3) (S3, a, b, L, S3) (S3, A, b, L, S2)

(6.1.9)

¡Nada nuevo hay aquí! Puesto que los lenguajes regulares (Tipo 3) también son Tipo 0, pueden ser reconocidos por las MT. De hecho, la MT del listado 6.1.9 es un LBA. De este modo, CWL no es el lenguaje Tipo 0 que estamos buscando; es decir, un lenguaje que no sea también del Tipo 1. Cohén luego codifica las cuatro instrucciones del listado (6.1.9) en cadenas de a y b. Un código de una palabra para la MT entera de cuatro instrucciones es la cade­ na en el listado (6.1.10): ababababbabaaabaaabbaaabaaabaaabaaaabaabbaaba

(6.1.10)

De hecho, cualquier MT sobre X = (a, b) puede ser codificada en una cadena de CWL. Las cadenas de CWL también pueden ser decodificadas en las MT, algunas legales y algunas no (por ejemplo, una MT resultante puede tener reglas duplica­ das). El lenguaje MATHISON (por el apellido materno de Alan Turing) se define entonces: MATHISON = {todas las palabras en CWL que son aceptadas por sus correspondientes MT)

(6.1.11)

Dejamos como un ejercicio demostrar que la cadena del listado (6.1.10), codifican­ do la MT del listado (6.1.9), es aceptada por TM(CWL). Cohén suministra una prueba de que MATHISON es recursivamente enume­ rable (Tipo 0), pero nosotros no lo haremos, para que sigamos en el camino con nuestra cabeza sobre los hombros. Los lenguajes más generales que los del Tipo 1 son creaciones extrañas y maravillosas, de interés teórico, pero no para definir len­ guajes de programación. E J E R C I C I O S 6.1

1. Construya un sistema de producción P para generar cadenas de X = {1,0}, a. terminando en 0 (números pares). b. terminando en 1 (números impares). c. cadenas con cualquier combinación de 0 y 1 con una longitud exacta de 8. 2. Construya sistemas de producción para generar cadenas sobre X = {a, b) de la forma: a. an, n = 0,1,... b. anbn, n = 0,1,... c. anbncn, n = 0,1,..., 4 d. anbncn, n = 0,1,... (difícil) Usted notará diferencias en la forma de las reglas de producción en a, b, c y en d. Sólo fines educativos - FreeLibros

290

PARTE ni: Autómatas y lenguajes formales

3. Las reglas que contiene e son llamadas reglas de borrado. El símbolo e es la letra griega épsilon, y representa la cadena vacía, una palabra sin ningún carácter en ab­ soluto. £no es ni una terminal ni una no terminal. Pero es necesario de algún modo representar nada, así se utiliza e. Si A —» £ es una regla, la A no terminal puede ser borrada. Si S0 —>e es una regla, el lenguaje generado contiene la cadena nula. ¿Qué lenguaje genera el siguiente sistema? Rl: S —>aSb R2: S —» £ 4. Con el programa del listado (6.1.5), siga la secuencia de instrucciones empleadas en la ejecución que se muestra en la figura 6.1.2, la cual reconoce la cadena 'aabbcc'. 5. Sean Ia 1, Ib I y Ic I los indicadores del número de las a, b o c en una cadena de entrada. Utilizando la MT LBA(AnBnCn) descrita en el segmento acerca de los autó­ matas lineales limitados, intente cadenas de prueba para demostrar que: a. La MT se detiene en S0 si Ia I =0. b. La MT se detiene en S2 si Ia I > 0 y Ib I =0. c. Si Ia I > 0 y Ib I > 0, se detiene en S4si Ia I < Ib I, y en S2si Ia I > Ib!. d. Si 0 > Ia I = Ib I, la MT se detiene en St si Ic I > Ia I y en S4si Ic I < Ia I. 6. ¿Qué palabras son generadas por la gramática del listado 6.1.8? 7. Demuestre que la cadena del listado (6.1.10), modificando la MT del listado (6.1.9), es aceptada por MT(CWL). 8. Una palabra de código para la MT(S17b, b, R, S2) de una instrucción es abaabababb. a. Demuestre que la cadena de código no es aceptada por la MT. b. ¿Qué palabras acepta la MT?

6.2

GRAMÁTICAS REGULARES Como lo discutimos en la sección 6.1, una gramática estructurada en frases G = (X, N, P, Inicio) es una gramática regular si sus producciones son de la forma: A —>a, o A -» aB, en el que A,B G N, y a E I

(6.2.1)

Sin embargo, no es necesario que las reglas estén en la forma del listado (6.2.1) para que una gramática sea regular. Si las reglas están en la forma del listado que se citó, se garantiza que la gramática resultante sea regular, pero existe otros sistemas para gramáticas equivalentes. En la formulación de Chomsky, la gramática B7 = (X, N, P', S0) del listado (6.2.2) genera el lenguaje L(B7). Este último es el mismo lenguaje que L(B), el cual fue examinado en el listado (6.1.1). Se dice que dos gramáticas, B y B7 sobre X, son equivalentes (=) si ellas generan el mismo lenguaje, aquí L(B7) = L(B). Las producciones P7son: P': Rl': So R 2 ’: s, — > 0 R 3 ’: s2 — > S3S4 R4': S3 — > R5': s4 S A R6': S5 — » i R7': S4 SA R8': S4— > s5s4 R9': S4 s5s5 Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

291

Nótese que R l’, R31, R5' y de R71hasta R9' no son de las dos formas especificadas en (6.2.1). Pero veremos en forma posterior más de esto en la discusión acerca de for­ mas normales en la sección 6.3. Expresiones regulares Las gramáticas regulares también pueden ser construidas a partir de expresiones regulares, en lugar de utilizar esquemas de producción. Recuerde del capítulo 0 que los tokens son constantes, símbolos especiales, palabras reservadas e identificadores. La forma de estos tokens es con frecuencia bastante simple, de modo que es útil emplear una gramática regular para aceptarlos. Las expresiones regulares involucran una notación en especial bella para definirlas, o por lo general para definir cadenas válidas en una gramática regular. Considere, por ejemplo, un identificador Pascal, que puede ser definido como sigue: identificador —>letra (letra I dígito)* letra —» A I . . . I Z I a l . . . l z dígito —>01 — 19 Comienza con una letra, luego es seguido por (concatenado con) una secuencia de letras y dígitos. Aquí la I es alternativa; significará "o, pero no ambas". Los parén­ tesis se utilizan en agrupación y el asterisco (*) o estrella de Kleene indica cero o más repeticiones. Definimos una expresión regular e sobre un alfabeto X como sigue: 1. 2. 3. 4.

e (la cadena nula) es una expresión regular. Si x £ X, entonces x es una expresión regular Si e1es una expresión regular, entonces así es (ex). Si e 1y e2 son expresiones regulares, entonces así son e 1 e2, e1 I e2 y e * .

El hecho de que £ sea una expresión regular no necesita explicación. La regla 2 dice que cada símbolo de X es una expresión regular. Note que las expresiones regulares están cerradas bajo tres operaciones: concatenación (sin símbolo entre ellas), alternancia ( I) y asterisco (*). Los paréntesis de la regla 3 necesitan una breve explicación. Éstos no son símbolos en X, pero pueden ser empleados con libertad para hacer más claras las expresiones. Símbolos tales como (,), 1 y *, que pueden utilizarse en expresiones pero que no son parte del lenguaje mismo, se denominan meta símbolos.6 Dentro de una expresión, * tiene la precedencia más alta, luego sigue la conca­ tenación y después la alternancia. De aquí, en el ejemplo ab I cd*, el asterisco se aplica sólo a d, y las alternativas son ab y cd* (es decir, c, cd, cdd, cddd, etc.). El lector debe confirmar que las cadenas como abd y acdd no son válidas, pero serían 6En algunos textos los símbolos de £ se escriben en negritas para separarlos de los metasímbolos; por ejemplo, (x)(yy). Sólo fines educativos - FreeLibros

292

PARTE III: Autómatas y lenguajes formales

válidas en a(b I c) d*. Como otro ejemplo, las cadenas de a y b que contienen al menos una 'a' estarían representadas por (a I b)*a(a I b)*. Con las expresiones regulares definidas, estamos listos para enumerar las re­ glas de una gramática regular usadas para construir un lenguaje regular L de una expresión regular e. Describiremos L(e) para indicar el lenguaje L definido por e. 1. 2.

Si e = x, entonces L(x) = {x}. Es decir, la única palabra en el lenguaje L es x. L(e) = {€}. Si L(e1) = Lx y L(e2) = L2, entonces a- L(ej e2) = L jL2 b. L(ei I e2) = L1 I L2 c. L(e/) = V

Algunos ejemplos están en orden. Supongamos que Lx= {x| y L2= (y), en la que ex = x y e2 = y. Esto es, cada lenguaje tiene exactamente una palabra en él. Entonces: 1. L(xy) = (xy), una sola palabra, xy 2. L(x I y) = {x} I {y} = {x, y} 3. L(x*) = L* = (e, x, xx, xxx,...} 4. L(x*y) = L(x*)L(y) = {y, xy, xxy, xxxy,...) Para ser un poco más prácticos, considere el lenguaje B, de decimales binarios entre ellos el 0 pero menores que 1, y aproximados a dos posiciones. El alfabeto, £ = {., 0, 1). B = {0.00, 0.01, 0.10, 0.11). B puede ser construido a partir de los dos lenguajes: L1 = {0.) - L(0.)

y L2 = {00, 0 1 , 10,11¡ = L((0 I 1)(0 I 1)) = L((0 I l) 2)

Entonces B = L((0.)(0 I l ) 2) = LXL2. Bes generado por la expresión regular 0 . (0 I l ) 2. Autómatas finitos (FA, NFA y DFA) Ahora que hemos visto cómo generar un lenguaje regular, nos enfrentaremos con el problema opuesto. Dada la gramática regular B en el listado (6.1.1) y una cadena de su alfabeto, ¿cómo podemos reconocer si esa cadena particular es una palabra de L(B) o no? Queremos una máquina que aceptará palabras válidas y rechazará cadenas inválidas. Para los lenguajes regulares, una máquina de este tipo es llama­ da autómata finito (FA, por sus siglas en inglés). La máquina debe funcionar en forma automática y reconocer o rechazar una cadena de entrada en un número finito de pasos. Dada una cadena para procesar, se procede mecánicamente en cada uno de los símbolos para aceptar o rechazar la cadena como una palabra del len­ guaje para el que el autómata fue construido. Procesará un símbolo a la vez de izquierda a derecha. Si una palabra es procesada comenzando en la flecha de inicio que apunta al estado de inicio S0, se dice que es reconocida o aceptada por el FA si el proceso termi­ na en un nodo terminal o Final, mostrado en la figura 6.2.1 como el nodo en cuadro Sólo fines educativos - FreeLibros

CAPÍTULO 6: Lenguajes formales

293

doble F. Se dice que las palabras que no son reconocidas son rechazadas o fallan. La gráfica con direcciones en el extremo inferior, llamada diagrama de transición, repre­ senta un FA para el lenguaje L(B). La S. y la F son llamados estados. S0 es el estado de inicio, y F, una terminal o estado final. Un FA debe tener exactamente un estado de inicio, pero puede tener uno, ninguno o varios estados finales. Para reconocer la cadena s = '0.01', el procesamiento comenzaría en S0, en el extremo izquierdo de s. Puesto que la lectura del primer símbolo es 0, la máquina cambiaría al estado Sx, en el que se lee el segundo símbolo, El FA cambiaría entonces al estado S2, en el cual se lee 0, y luego a S3, en el que se lee el 1. El FA cambiaría entonces al estado F y se detendría, puesto que habría alcanzado el final de la cadena de entrada. Ya que F es un estado terminal, s ha sido reconocida. De manera formal, un autómata finito es una 5-tupla (S, E, T, Inicio, FS) con: 1. 2. 3.

4. 5.

Un conjunto de Estados S = {SQ, Sv ... Snl). Para el ejemplo de la figura 6.2.1, S = { S 0, S 1, S 2, S 3,F). Un alfabeto E. En nuestro caso, E = {0,., 1). Un conjunto de transiciones T. En la figura 2.1.1, las transiciones están repre­ sentadas por flechas; por ejemplo, una transición se hace desde el estado S: al S2 si el procesamiento está en el estado S1y se reconoce en la cadena que se encuentra en proceso. Inicio es el estado de inicio. En la figura 6.2.1, Inicio = SQ. Un subconjunto de los S. (posiblemente vacío) es designado como estados fina­ les, de parada o terminales FS. Aquí, FS = {F}.

Un FA es finito porque el alfabeto y el número de estados son finitos. Un FA se encuentra en el estado SQsi el procesamiento acaba de comenzar o si hay alguna transición de regreso a S0. El FA hace una transición al estado S. al leer un símbolo x. El FA, entonces, se encuentra en el estado Sf El conjunto de transiciones también puede representarse como una tabla de transición. Se puede utilizar con libertad cualquiera que sea el más claro. La tabla de transición para el FA de la figura 6.2.1 se muestra en la figura 6.2.2. Una tabla tal como la de la figura 6.2.2 puede ser construida a partir de una gramática regular G = (S, E, T, Inicio, FS) como sigue: 1.

Si m es el número de elementos en E, y n es el número de no terminales (S - Sn 2) utilizadas en T, construya una tabla de n x m con renglones titulados

FIGURA 6.2.1 Diagrama de transición para L(B) incluyendo estados

Sólo fines educativos - FreeLibros

294

PARTE III: Autómatas y lenguajes formales Entradas 0

So Si

s2 S3

*F

1

.

Si —

—

—

—

S2

S3 F —

S3

—

F

—

—

—

FIGURA 6.2.2 Tabla de transición para el lenguaje B

2. 3. 4.

S. (0 i n-1). Si hay cualquier producción de la forma N —>t, agregue un renglón titulado F. El renglón F está marcado con * para indicar que es un estado termi­ nal. Las columnas son tituladas con los símbolos de terminal m de X. Para cada regla de la forma S. —» tS., introduzca la transición desde S. hasta S. escribiendo "S " en Tabla(S., t). Para cada regla de la forma N —» t, escriba "F " en Tabla(N, t). Marque todas las otras celdas de la tabla con "— ", representando la ausencia de una transición.

Las no terminales de la gramática, con la posible adición de F, se convierten en los estados para la FA. En forma similar, un sistema de producción para una gramática regular puede construirse a partir de una tabla de transición, T-Table(X, y), como se explica a continuación: 1. 2.

Para cada entrada S. en T-Table(S., t), escriba la regla S. —» tS.. Para cada entrada F* en T-Table(S., t), escriba la regla S. —> t.

Si existe exactamente una transición posible de cada estado, dado un posible símbolo de entrada, un FA se denomina determinístico o un DFA. Si se ofrece múlti­ ples selecciones de un estado Si para algún símbolo t, el FA se llama no determinístico, o un NFA. En este caso, si el FA se encuentra en el estado S¡ y t es leído de la cadena de entrada, lo que debería hacerse no está determinado. La figura 6.2.3 representa un NFA porque existe dos elecciones de transición desde S0 al reconocer la letra b, resultando en cualquiera de losestados SQo Sr Resulta entonces que es más conveniente mostrar la entrada de latablacomo el Entradas

50

{S0}

{Sq.S ú

51

FIGURA 6.2.3 Diagrama y tabla de transición para un NFA

Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

295

conjunto {S0/ S J . De manera correspondiente, todas las otras entradas de la tabla indican el conjunto de los estados resultantes. ¿Puede usted deducir cuál lenguaje reconoce este NFA? Las transiciones SQ-^ SQy S0-^>S0 se conocen como ciclos. Es posible ciclar cero o más veces generando repetidas a o b. La relación para expresiones regulares ahora puede haber llegado a ser más clara. Las expresiones regulares (a I b)*b están re­ presentadas en la figura 6.2.3. La alternancia se indica mediante múltiples ramifi­ caciones desde SQhacia otro estado (en este caso, de regreso a S0). La concatenación se indica mediante la secuencia de estados desde S0 hasta Sr El asterisco de Kleene resulta en un ciclo desde un estado y de regreso a sí mismo. El trabajo de Kleene y otros muestra que cualquier lenguaje que puede recono­ cer un NFA también es capaz de reconocer un (probablemente más complicado) DFA. Un método mecánico para producir el DFA en la figura 6.2.4 a partir del NFA de la figura 6.2.3 se deja para los ejercicios. Cuando el procesamiento ha progresado hasta el estado de terminación (SQ,S J, puede o bien detenerse, repetirse durante 0 u otras b, o regresar a {S0} si una a se ha leído. El DFA reconoce infinitamente más palabras puesto que se puede ir a través de los ciclos cualquier número de veces. Un importante resultado de la teoría de los autómatas dice que cualquier lenguaje reconocido por un FA, como el lenguaje reco­ nocido por los FA de las figuras 6.2.3 y 6.2.4, es regular. También se ha demostrado que cualquier lenguaje con un número finito de palabras puede ser reconocido por un autómata finito. Lo inverso, por supuesto, no es verdad, como se ejemplifica me­ diante el DFA de la figura 6.2.4. Recomendamos al lector interesado a [Cohén, 1991]. Aplicaciones Hemos considerado un grupo de lenguajes, llamados regulares, que se generan mediante gramáticas regulares y cuyas palabras pueden ser reconocidas por los DFA (NFA). Vimos un ejemplo de cómo construir un FA desde la gramática regular B, y una gramática de un FA expresada en la tabla de la figura 6.2.2. Cada lenguaje con un número finito de palabras puede generarse a partir de una gramática regular; los procesadores de texto pueden ser escritos utilizando los DFA. La compilación de un lenguaje involucra varios pasos, el primero de los cua­ les, como se mencionó antes, es el análisis lexicográfico (rastreo) o el reconocimien­ to de tokens y símbolos válidos. Un lenguaje especial denominado LEX [Lesk, 1975] se implemento para producir un DFA a partir de código fuente. Algunos compi­ ladores también emplean un DFA para implementar el primer paso sobre el código fuente. Para un ejemplo de cómo LEX produce un rastreador DFA para declaracio­ nes aritméticas de FORTRAN, véase [Aho, 1986]. a {S0}

b ...

{S0,Si}

a b FIGURA 6.2.4 Equivalente DFA para el NFA de la figura 6.2.3

Sólo fines educativos - FreeLibros

296

PARTE III: Autómatas y lenguajes formales LABORATORIO

6.1: E X P R E S I O N E S R E G U L A R E S : grep

O bjetivos (Los Laboratorios pueden encontrarse en el Instnictor's Manual) 1. Usar la utilidad grep o egrep para investigar la forma y notación de expresiones regulares. 2. Volver a escribir una expresión regular como un autómata finito (FA). 3. Crear un diagrama y una tabla de transición para el FA generado en el punto 2 de este ejercicio.

E J E R C I C I O S 6.2 1. ¿Cuál de los sistemas que usted construyó en los ejercicios 6.1.2 anteriores son regu­ lares? 2. Construya una gramática regular para generar palabras sobre (a, b¡ que contenga la cadena 'abab'. 3. ¿Por qué la regla S —» aSb no está permitida para producir un lenguaje regular? 4. Suponga que un lenguaje con palabras anbnestá restringido a n < 1000. Llámelo L1000. Puesto que cualquier lenguaje con un número finito de palabras es regular, L1000 es regular. ¿Cómo podríamos construir reglas de producción para generar palabras de L1000 y un FA para reconocerlas? 5. ¿Es la gramática B' del listado (6.2.2) una gramática estructurada en frases? 6. Construya una tabla de transición y un FA para un lenguaje L con dos símbolos, X = {a bj, en el que L contiene palabras que contienen una cadena de por lo menos dos a. Algunas palabras de L son aa, aaab, abba, baa y bbaaaaa. 7. Usted quizá construyó un NFA para el ejercicio 6. Si fue así, construya el DFA equi­ valente. Existe una manera automática para hacer esto. Demostraremos el método; por ejemplo, con el uso de la gramática y NFA de la figura 6.2.3, la cual se incluye a continuación. a

Entradas

—

—

C*0

b

S, 1

So Si

a

b

{Sol 0

{So-Sú 0

b

Paso 1: sea S = {S0, S}} los estados del NFA en la figura 6.2.3, y sea P(S) = { 0 , {S0|, {SJ, {S0,S1}} el conjunto de potencia de S. Sea P(S) el conjunto de estados para el DFA relacionado con la figura 6.2.4. Paso 2: construimos transiciones de P(S) mediante: • • • •

{S0} es el estado de inicio, en el que S0 era el estado de inicio para el NFA. 0 ^ 0 para cualquier entrada. £ —> 0 para la entrada x, si no hay transición en el NFA de S para x. P. —> P. para la entrada x, si P =syp T(S.x)tal que existe un estado, S. en P., y existe una transición en el NFA, S —» T(S.,x), el conjunto de entradas de tabla de transi­ ción para el estado S. y la entrada x. • Marcar cualquier terminal de estado (*) que contenga un estado que era terminal en el NFA.

Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

297

Demuestre que este proceso siempre produce un DFA a partir de un NFA para un número finito de entradas que puedan hallarse en él [Johnsonbaugh, 1993]. La tabla de transición resultante es: Entradas UOlClvIvw 0

a

b

{S0}

{S0}

{So, S-J

*{Sd *{s0, Sd

{S0}

{So, S-,}

El DFA mostrado en la parte superior de la página siguiente representa esta tabla.

a

w

b

{Sol ^

*

{S0, S,}

a b

a

b

Las transiciones de (SJ y 0 pueden ser eliminadas, puesto que no se les puede alcan­ zar desde el inicio {S0}, y queda el diagrama de la figura 6.2.4. 8. Construya un DFA a partir del siguiente NFA:

a

a

b

Sólo fines educativos - FreeLibros

298

PARTE III: Autómatas y lenguajes formales 9. Construya sistemas de producción para sus lenguajes de los puntos 6 ,7 y 8 de estos ejercicios. 10. Escriba una gramática para generar palabras que contengan una sola vocal con una sola consonante a cada lado, o la consonante simple a la derecha seguida por una s. Usted puede limitar sus consonantes a {b, d, m, n) para simplificar el asunto. Algu­ nas palabras (en idioma inglés) en el lenguaje generado podrían ser "bed", "beds", "dad", "m an", "m uns", etcétera. 11. Escriba una gramática, tabla de transición y FApara generar palabras con cualquier número de letras a y exactamente tres b.

6.3

GRAMÁTICAS LIBRES DE CONTEXTO (CFG) Existe lenguajes que no pueden ser reconocidos por los FA y no son regulares. Uno de los más simples es el lenguaje: LN = [anbn: n = 1, 2, ...) = {ab aabb aaabbb ...)

(6.3.1)

La demostración de que LN no es regular utiliza el hecho que si lo fuera, habría un autómata finito que reconocería cadenas legales y rechazaría cadenas ilegales, y que la existencia de un FA de esta clase conduce a una contradicción. La demostra­ ción puede encontrarse en [Cohén, 1991]. De este modo, existe lenguajes de otro tipo aparte del Tipo 3 de Chomsky. Recuérdese de la sección 6.1 que para las CFG el lado izquierdo debe ser un no terminal, mientras que el lado derecho puede ser cualquier cadena de terminales y no terminales. Como un ejemplo, examinaremos la CFG para LN. Aquí X = (a, bj, N = {S} y el símbolo de inicio es S. Las reglas de producción para cadenas de la forma anbn son: P = {Rl: S

aSb, R2: S -» £}

Como hemos visto previamente en la notación, estas dos reglas pueden ser combi­ nadas en S —>aSb I £. Podemos producir la palabra a2b2 empleando la derivación: Rl Rl R2 S —» aSb —» aaSbb —» aabb en la cual la producción final borra la S. Nótese que puesto que S —>e es una produc­ ción válida, la cadena vacía ese encuentra en el lenguaje LN. El borrado puede con­ ducir a problemas, de modo que se desarrollaron varias estrategias para eliminar las reglas de borrado. Aquí, podríamos haber utilizado, en lugar de las reglas en P: P2 = (S -> aSb I ab)

(6.3.2)

Denotemos LN7 = L(P2). Las producciones de P2 no producen el lenguaje LN = L(P), ya que £ G LN, pero £ g LN7. Hay pruebas de que cualquier lenguaje que no incluya la palabra vacía £ puede ser generado por una gramática sin reglas de borrado. Sólo fines educativos - FreeLibros

6: Lenguajes formales

CAPÍTULO

299

Autómatas descendentes (PDA; Push-Down Autómata) Del mismo modo que las palabras de un lenguaje regular pueden ser reconocidas por un autómata finito (FA), las palabras de un lenguaje libre de contexto son reco­ nocidas por un autómata descendente (PDA). Los inversos también son verdaderos: cualquier lenguaje reconocido por un FA (o PDA) es regular (o libre de contexto). Un PDA se compone de dos cintas (quizá de longitud infinita). La primera es una cinta de entrada que contiene la palabra por reconocerse. Se agregó el símbolo # al final de la cinta de entrada para dar a entender el final de la entrada particular que se intenta reconocer. La segunda cinta funciona como una pila descendente, y contiene al principio el símbolo de inicio S y el símbolo de terminación #. Veamos cómo funciona esto en la figura 6.3.1, cuando reconozcamos a*b2 de nuestro len­ guaje LN' del listado (6.3.2). La acción es apilar las a y extraerlas a medida que encontremos las b correspondientes. El * debajo de la cinta de datos marca el apun­ tador de posición para el símbolo que se leerá a continuación. ¿Por qué no necesita­ mos un apuntador de posición para la pila? Un PDA puede ser definido como un conjunto de reglas para dos cintas: una que contiene una cadena de entrada y la otra para ser empleada como una pila. Una regla es de la forma:

Entrada a

Pila

a

b

b

#

s

#

a

b b

#

a

S

b

a

b b

#

S

b

#

b

b

#

a

b b

b

b

#

b b

b

#

b

* a

#

*

a

*

a

a *

a

a

#

*

a

a

b

#

*

a

a

b

b

#

¡Éxito!

F I G U R A 6.3.1

Operación de un PDA para reconocer a2b2 de LN'

Sólo fines educativos - FreeLibros

#

300

PARTE

ni: Autómatas

y

lenguajes formales

[r, s j -> [x, s2],

(6.3.3)

en la que r es un carácter simple leído de la cinta de entrada, s1enumera lo que es­ tá en la parte superior de la pila y s2 reemplaza a en la pila. El apuntador de lectura avanza un carácter si x es > en el lado derecho de la regla, o permanece en el último carácter leído si x es No estamos confinados a considerar sólo un símbolo de la pila, pero puede extraerse tantas veces como sea necesario. Por ejemplo, la regla [a,S] —» [-,aSb] significa que si a ha sido leída de la cinta de entrada, el apun­ tador de lectura permanece donde está, S se extrae de la pila y aSb se desplaza. Por claridad, cr puede emplearse para representar elementos arbitrarios de la cinta de entrada. Las reglas del PDA son, de este modo, algo parecidas a las reglas de pro­ ducción, en el sentido de que el lado izquierdo representa los estados actuales de las dos cintas, mientras que el lado derecho muestra los estados después de que se toman las acciones apropiadas. Las reglas de producción para un CFG pueden utilizarse para construir reglas de PDA con el uso del algoritmo no selectivo descendente o de arriba hacia abajo (NTB; Non-selective Top-to-Bottom) de Griffiths y Petrick [Griffiths, 1965] que se muestra en el listado (6.3.4). NTB: condición CFG 1. A —» s1s2...sn 2. a £ X

regla PDA ( a ,A ) - » ( - ,s 1s2...Sn) (^/^) —^ (^/ £)

(6.3.4)

NTB expresa (1) reemplazar en la pila un lado izquierdo de una producción CFG con su lado derecho, o (2) extraer un símbolo terminal hallado en ambas cintas de la pila y avanzar el apuntador de lectura. Las reglas para el PDA de LN' en el listado (6.3.2) se muestran en el listado (6.3.5). La primera regla fue descrita con anterioridad. La segunda regla enuncia: "Si S se encuentra en el tope o parte superior de la pila, extraiga S, y después des­ place ab sobre la pila." La tercera regla es: "Si usted lee una a en la cinta de entrada y observa una a en la pila, extraiga la a de la pila y haga avanzar elapuntador de lectura." La cuarta regla es similar a la tercera, con b en lugar de a; la quinta regla nos permite conocer cuando la cadena de entrada ha sido reconocida por el PDA. La pila es iniciada con S# y la cinta de entrada con la cadena que será reconocida seguida por #. La lectura de la cadena de entrada comienza al frente de la cinta y es de izquierda a derecha. Siga estas reglas a lo largo de la ejecución del PDA que se muestra en la figura 6.3.1 para a2b2. R l: R2: R3: R4: R5:

[a, S] -> aSb] [cr, S] -> [-, ab] [a, a] —^ [>, £] [b, b] -> [>, e] [#, #] -> ¡Éxito!

(6.3.5)

Note que R l y R2 son no determinísticos. Cualesquiera de ellos puede utilizarse para reemplazar S en la pila. Esto es la causa de que el algoritmo no sea selectivo: no hay directivas para elegir cuál regla de PDA emplear si se puede aplicar dos o más. Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

301

¿Por qué puede este PDA reconocer cadenas que no podrían ser reconocidas por un FA? Exploraremos esto para una n fija en los ejercicios 6.3.1 y 6.3.2. Un FA no tiene la habilidad para contar. Si una cadena anbnse envía a un FA para su reco­ nocimiento, en el cual un ciclo ha sido integrado para reconocer las a, el FA no puede recordar cuántas a ha visto (cuántas veces han circundado por el ciclo), de modo que un ciclo reconociendo las b podría no ser recorrido un igual número de veces. Como hemos visto antes, la pila puede realizar esta función de conteo. Más formal aún, un PDA es una 6-tupla (X*, N U X*, Inicio, #, {>, R], en el que: 1. 2. 3. 4. 5 6.

X* is X U {#}, el conjunto de símbolos de la cinta de entrada N U X* es el de los símbolos de la pila Inicio es el símbolo de inicio # es el símbolo de terminación {>,-} indica movimiento del apuntador de lectura R es el conjunto de las reglas del PDA

Como un ejemplo más práctico en lenguajes de programación, consideremos una versión simplificada de una expresión aritmética de Pascal. La gramática es ArithExp = (X, N, P, Inicio), en la cual X = {0,1, +, *, (,)}, N = {EXP, FAC, TERM}, el símbolo de inicio es EXP y las reglas de producción son: P: R l: EXP -> TERM I EXP + TERM R2: TERM -> FAC i TERM * FAC R3: FAC - > 0 1 1 1 (EXP)

(6.3.6)

Tres palabras válidas de L(ArithExp) son 1*0,1+0+1 y (1+1)*0. Con el uso del algoritmo NTB del listado (6.3.4), un PDA, para reconocer L(ArithExp), tiene: X* = {0,1,+,*,(,),#} N U X* = {0,1,+,*,(,),#, FAC,TERM,EXP) Start = EXP R: A E la-b: [<x, EXP] -+ [-, TERM] AE2a-b: [<7, TERM] -> [-, FAC] AE3a-c: [o, FAC] -+ [-,0] AE4a-f: [0,0] I [1,1] I [+,+] I [*, *] ->[>,£] AE5: [#,#] -> ¡Éxito!

(6,3.7)

I[-, EXP + TERM] I[-, TERM * FAC] I[-, 1] I [-, (EXP)] I [(, (] I [),)]

Los espacios entre los elementos de pila son para mayor legibilidad, y la I (o) es para ahorrar espacio. Las primeras dos reglas, AEla-b y AE2a-b, representan dos reglas cada uno, AE3a-c representa tres reglas y AE4a-f representa seis. Advierta que las reglas AE1-AE3 son no determinísticas. Ahora veamos el funcionamiento del PDA del listado (6.3.7) sobre la cadena de entrada (1 + 1) * 0. Esto se ilustra en la tabla 6.3.1. Sólo fines educativos - FreeLibros

302

PARTE

ni: Autómatas y lenguajes formales

TABLA 6.3.1 Reconocimiento de (1 + 1) * 0 por PDA(ArithExp) Entrada

Pila

Regla que se aplicará

(1+1)*0#

EXP#

A E la

(1+1)*0#

TERM #

AE2b

(1+1)*0#

TERM * FAC #

AE2a

(1+1)*0# *

F A C * FA C#

AE3c

(1+1)*0#

( E X P ) * FAC #

AE4e

(1+1)*0#

EXP) * FAC)

A E lb

(1+1)*0#

EXP + TERM) * FAC) #

A E la

(1+1)*Ü#

TERM + TERM) * FAC) #

AE2a

(1+1)*0#

FAC + TERM) * FAC) #

AE3b

(1+1)*0# *

1 + TERM) * FAC #

AE4b

(1+1)*0# *

+ TERM) * FAC #

AE4c

(1+1)*0# *

TERM) * FAC #

AE2a

(1+1)*0# *

FAC) * FAC #

AE3b

(1+1)*0# »

1) * FAC #

AE4b

(1+1)*0# *

) * FAC #

AE4f

(1+1)*0# *

* FAC #

AE4d

(1+1)*0#

FAC#

AE3a

(1+1)*0# *

0#

AE4a

(1+1)*0# ¡Éxito!

#

AE5

* * *

* * *

* *

*

El lector que haya trabajado a lo largo de la tabla 6.3.1 se habrá dado cuenta de que el indeterminismo de las reglas AE1-AE3 es una seria desventaja, y que el PDA puede tomar muchas rutas equivocadas antes de reconocer una cadena válida. Griffiths y Petrick presentan un algoritmo selectivo descendente que utiliza una matriz de precedencia generada en forma automática para ayudar a la determina­ ción de qué regla de PDA elegir cuando más de una se puede aplicar. También se ha dado otros algoritmos e informado de sus medidas de eficiencia. Algunos de éstos son ascendentes, la pila iniciada a #, e informan de un éxito cuando la cadena de entrada es agotada y la pila sólo contiene los símbolos de inicio y terminación. Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

303

En un PDA descendente, trabajaríamos a través de FACtores, TERMinos y EXPresiones hasta que una cadena de entrada sea reconocida como una EXPresión simple. Cohén [Cohén, 1991] proporciona un tratamiento extensivo de los PDA, rela­ cionándolos con diagramas de flujo en vez de pares de reglas.

Árboles de análisis sintáctico El análisis sintáctico (parsing), o el reconocimiento de palabras, se concibe a menudo como un árbol. Las ramas del árbol reflejan cuáles reglas de producción fueron aplicadas en el reconocimiento de la cadena. El análisis de a*b2 en la figura 6.3.1 puede ser retratado por el árbol de análisis mostrado en la figura 6.3.2. El primer renglón indica la aplicación de S —» aSb, y la segunda de S ab. Un transversal inorder (izquierda-raíz-derecha), del árbol resulta en aabb como el or­ den resultante de los terminales, como se desea. De manera semejante, el árbol de análisis sintáctico para (1 + 1 )* 0, siguiendo la ejecución del PDA(ArithExp) que se expone en la tabla 6.3.1, se muestra en la figura 6.3.3. Cuando un compilador realiza los pasos del análisis sintáctico sobre EXP

TER M

TERM

FAC

FAC

EXP

EXP

TERM

+

TER M

FAC

S FAC

a

b

S

a

b

FIGURA 6.3.2 Árbol de análisis sintáctico para a2b2

FIGURA 6.3.3 Árbol de análisis sintáctico en ArithExp para (1 + 1) * 0

Sólo fines educativos - FreeLibros

PARTE ni: Autómatas y lenguajes formales

304

un programa, un método común involucra la creación de un árbol de análisis de este tipo. Un árbol así, indica algo acerca de la semántica. Implica precedencia de operadores (que el operador + y la evaluación de las expresiones entre paréntesis vienen primero, y la multiplicación viene después). De aquí, es claro que el valor de la expresión es 0. Además, ¿qué hay acerca de la interrogante de la asociatividad de los operado­ res? Examinemos el árbol de análisis para 0 + 1 + 1, como se muestra en la figura 6.3.4. Nótese que se implica que el operador + izquierdo se aplicará primero, y el + derecho se aplicará más tarde. Como resultado, + se dejará asociativo. De aquí, se evalúa como (0 +1) +1. Se dejará como ejercicio demostrar que * es también asocia­ tivo por la izquierda en ArithExp.

Gramáticas ambiguas Supóngase que en lugar de utilizar las reglas para LN' en el listado (6.3.2), genera­ mos las cadenas de {anbn} empleando las reglas en el listado (6.3.8). S -+ aS2 I Sxb S„ —» a I aSab aS2b

(6.3.8)

El lenguaje generado es el mismo que el de LN', pero dos árboles diferentes re­ presentan análisis de a2b2, como se ilustra en la figura 6.3.5. Cuando una o más cadenas producen dos diferentes árboles de análisis, se dice que la gramática es ambigua.

EXP

E>

EXP

TERM

+

h

TERM

TERM

FAC

FAC

1

FAC

FIGURA 6.3.4 Asociatividad del operador + en 0 + 1 + 1

a

So

b

FIGURA 6.3.5 Dos análisis sintácticos para a V en una gramática ambigua

Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

305

Considere otra vez nuestra gramática ArithExp del listado (6.3.6). Supónga­ se que intentamos simplificar las producciones a la forma mostrada en el listado (6.3.9). EXP -> TERM T E R M - > 0 I 1 I TERM + TERM I TERM * TERM

(6.3.9)

Por desgracia, ahora son producidos dos árboles de análisis para 1 + 1 * 0 utili­ zando estas reglas sin paréntesis, como se ilustra en la figura 6.3.6. Si evaluamos la expresión del árbol izquierdo al usar aritmética ordinaria de base 2 y un recorri­ do transversal inorder del árbol, obtendríamos 1. El resultado para el árbol dere­ cho es 0. Los programas tienen semántica así como sintaxis, y el significado de una de­ claración (en este caso, el valor de la expresión) no debe ser ambiguo. Existe dos maneras comunes para hacer una expresión aritmética no ambigua: insistencia en paréntesis completos en la sintaxis del lenguaje, o el uso de una precedencia de opera­ dor que está integrada en el lenguaje. Se analiza la sintaxis de una expresión y des­ pués se evalúa en orden (de izquierda a derecha), con operaciones realizadas en el orden de su precedencia, con las de mayor jerarquía ejecutándose primero. En Ada, la jerarquía desde lo más alto a lo más bajo es: ** | abs | not * | / | lod | re» + | + | -| & - | /- |< | <= | >| >= and |op | xor

(exponenciación, valor absoluto, negación lógica) (m ultiplicación, división, m ódulo, residuo) (más o menos unitario) (sum a, resta, concatenación de arreglos) (operadores relaciónales) (operadores binarios lógicos)

EXP

EXP

FIGURA 6.3.6

Dos análisis sintácticos para 1 + 1 * 0 en un lenguaje de expresión ambigua Sólo fines educativos - FreeLibros

306

PARTE ni: Autómatas y lenguajes formales

Aplicaciones Las gramáticas libres de contexto tienen muchos usos prácticos, en la medida en que la sintaxis de los lenguajes de programación puede especificarse con el uso de ellas. El primero en utilizar CFG para la definición del lenguaje fue Algol 60, segui­ do por FORTRAN, Pascal, BASIC, PL/I, y por último, Ada, entre otros. Sin embar­ go, cada uno de estos lenguajes no tiene construcciones libres de contexto. Una de éstas es que en los lenguajes tipificados, un tipo de variable debe declararse antes de que sea utilizada en un programa. La descripción BNF por lo regular enuncia una sección de declaración de variable como opcional, para incluir (sub)programas sin variables. Una descripción de lenguaje oficial incluirá algún otro método aparte de BNF para describir tales características. Los compiladores son en particular re­ ceptivos a las CFG con sus implementaciones como pilas, de modo que tantos len­ guajes como sean posibles se definen con el uso de una CFG.

Formas normales Las formas normales son métodos de descripción de lenguaje que siguen ciertas reglas. Uno de sus usos importantes es en la construcción de pruebas acerca de propiedades de lenguaje. Para muchos lenguajes, podemos suponer que se en­ cuentran especificados en forma normal y limitar nuestra prueba a estas construc­ ciones. Las formas normales pueden no ser en particular fáciles de leer o de com­ prender, pero son más sencillas de analizar que descripciones de lenguaje más informales. Cualquier lenguaje libre de contexto puede ser descrito mediante cualquiera de las formas normales que se menciona a continuación.

Forma normal de Chomsky (CNF; Chomsky Normal Form) Se dice que una gramática está en forma normal de Chomsky si todas sus reglas de producción son de una de dos formas: 1. 2.

Nj —>N2N3, en el que N. es una no terminal N —» t, en el cual N es una no terminal y t es una terminal simple

Describamos nuestra CFG para LN' en CNF. Recuerde del listado (6.3.5) que LN' es el lenguaje de palabras de la forma anbn, y su gramática libre de contexto se compone de las dos reglas: (1) S —»aSb y (2) S ab. Una CNF equivalente para esta gramática es: C l) C2) C3) C4) C5)

S -»A C C SB S AB A a B —>b Sólo fines educativos - FreeLibros

CAPÍTULO

6: Lenguajes formales

307

Y una derivación de a3b3 es: CI C2 CI C2 C3 C4 C4 S -» AC -> ASB AACB AASBB AAABBB -» aAABBB

.

C5 —> aaabbb En la notación anterior una flecha indica cuál regla fue utilizada para producir el lado derecho a partir del izquierdo. La CNF hace el análisis de lenguaje particularmente fácil, debido a que sólo se tiene que preocupar de las palabras producidas a través de producciones de dos clases. La CFG de dos reglas para LN' fue reescrita en cinco reglas CNF. Esto ocurre con regularidad, de manera que las gramáticas CNF tienden a ser más largas. Forma normal de Backus (BNF; Backus Normal Form) Una forma normal más legible es la Forma Normal de Backus (BNF). La BNF tam­ bién es conocida como Forma Backus-Naur (Backus-Naur Form); aquí se reconoce las contribuciones de Peter Naur como el editor del informe de ALGOL 60, el cual fue escrito en BNF. Como se describió en el capítulo 0, BNF es un metalenguaje utilizado para describir sistemas de producción para generar lenguajes libres de contexto. Cada lenguaje que se crea con el uso de BNF incluye un conjunto de terminales, un con­ junto de no terminales y una lista de producciones. Las terminales de BNF se indi­ can de diversas maneras en diferentes referencias de lenguaje. Utilizaremos una cadena en minúscula y en negritas. Como se muestra a continuación, las no termi­ nales se encuentran encerradas entre picoparéntesis. Los metasímbolos de BNF (como se utilizan en este texto) se muestran en el listado (6.3.10). Sím bolo ::= I