potencia - pearson

Capítulo 3 Autómatas finitos 31

Potencia

L → [a-z A-Z]D → [0-9]IDE → L(L|D)4

010

L|D L|D L|D L|D DEL3 4 5 6

L2

Observación: Este operador se utiliza cuando un elemento de entrada debe recibirse un de-terminado número de veces, por ejemplo, si un identificador debe recibir una letra seguida de cuatro caracteres (ya sean letras o dígitos). El diagrama de transiciones correspondiente presenta una serie de concatenaciones.

Otro ejemplo del diseño de diagramas de transiciones es una expresión aritmética con dos operandos, en donde el resultado se asigna a un identificador. Los operandos pueden ser constantes numéricas o identificadores válidos. El patrón que define la expresión aritmética es la siguiente:

31Letra

Letra

Letra Letra

LetraLetra

Dígito

=

−

− −

Dígito

Dígito

Dígito

Dígito

Dígito

Dígito

FDC

FDCop-ar

op-ar

2

8

9

4 7

6

5

Figura 3.3 Diagrama de transiciones para una expresión aritmética.

Id → Letra (Letra|Dígito | _ )*

Letra → [a – z, A – Z]. Dígito → (0 – 9)Cn → Dígito Dígito*

op-ar → (+, −, *, /)Operador de asignación =

ID, abreviamos el nombre de la definición regular del identificador

40 Teoría de autómatas. Un enfoque práctico

3.5 Conversión de un AFnd A AFd

Es posible convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) con un conjunto de pasos que se detallan a continuación de definir primero el autómata se analizará.

La expresión regular para este autómata es de un identificador válido de programación, con el siguiente patrón que debe seguir la cadena para ser aceptada como tal:

letra(letra | digito)* digito

Los pasos para convertir de un AFND a AFD son:

1. Identificar el autómata.

dígito

dígito

letra

letraq11 2 3

Figura 3.8 Diagrama de transiciones de un AFND con ∑ = {letra, dígito}

Éste es un AFND, ya que en un estado 1 no tiene dirección de salida si el símbolo es un dígito y en estado 2 existen dos flechas indicando diferentes direcciones para dígito.

2. Definir los elementos que componen el AFND.

Q = {1, 2, 3}

∑= {letra, dígito}

q0 = 1

F = {3}

3. Aplicar el conjunto potencia al conjunto de estados (S) proporcionado por todos los subconjuntos del S y la cantidad de subconjuntos está representada por |P(Q)| = 2|Q|.

|Q| = 3

|P(Q)| = 23 = 8

P(Q) = {ε, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

4. Realizar la tabla de transiciones, integrando los elementos obtenidos de P(Q), inclu-yendo el conjunto vacío, δ(ε, ∑) = ε.

Es importante observar que en cada estado (filas) existen transiciones por símbolo (co-lumna). Por ejemplo, para el conjunto de estados {1, 2, 3}, como referencia la fila 8:

Con el símbolo dígito en el estado 1, no llega ninigún estado {ε} con el símbolo dígito, en el estado 2, la dirección que puede seguir es hacia el estado 2 o al estado 3 este es un con-


junto de posibilidades {2, 3} y por último con el símbolo dígito y el estado 3 no proporción ningun estado {ε}. Realizando la operación de unión con los estados determinados por el conjunto de estados, símbolo se tendra que resultado de cada celda de la matríz de transición correspondiente a cada símbolo del alfabeto está representado por δ(P(Q), ∑) = Up en q de cada δ(q, símbolo).

δ ({1, 2, 3}, dígito) = {ε} ∪ {2, 3} ∪ {ε} = {2, 3}

Conjunto de estados Letra dígito

1 E ε ε

2 {1} {2} ε

3 {2} {2} {2, 3}

4 {3} ε ε

5 {1, 2} ε U {2} ε U {2, 3}

6 {1, 3} {2} U ε ε U ε

7 {2, 3} {2} U ε {2, 3} ε U

8 {1, 2, 3} {2} U {2} U ε ε U {2, 3} U ε

No se olvide que para este AFND el estado de aceptación es el estado 3.

5. Dibujar el diagrama de transiciones con una característica diferente, los estados serán los conjuntos resultantes de P(Q) = {ε, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}, excluyendo el conjunto vacío que es el estado error.

letra

letra

letra

letraletra

letraletra

dígitodígito

dígito

dígito

dígito

dígito

dígito

dígito

letra{1}

{1,2} {2,3} {1,2,3}

ε

q1{2} q1Ce5{1,3}

q1Ce5{3}

Figura 3.9 DT con estados resultantes de estados-símbolo.


6. Eliminar estados a los que no llega ningún simbolo o estados que no son accedidos por ningún símbolo es una forma de optimizar el diagrama.

q1

ε

{1} {2}

{2,3}letra

letra

letraletra

dígito

dígito

dígito

dígito

Figura 3.10 AFD resultante de un AFND.

Y se obtiene el autómata finito determinista, que en cada uno del conjunto de estados existe una salida para cada símbolo del alfabeto.

Realice la actividad 3.5

3.6 representACión de er usAndo un AFnd

Como ya se vio en tema de diagramas de transición, las expresiones regulares (E), son una forma más de expresar las cadenas (L), que se aceptan L(E).

Se puede construir un AFND para cualquier lenguaje que acepte la expresión regular L(E). Algunas variantes se precentan acontinuación:

E = ∅; no existe cadena que pueda ser representada por la expresión; por lo tanto no existe AF que lo pueda representar.

E = ε; Las cadenas que acepta esta expresión, son las vacías, es decir no contiene ningún símbolo y en el AF el estado inicial también es el estado de aceptación.

E = {x; x pertenece al alfabeto}; y si cumple con las condiciones de la expresión regular de la cadena se acepta.


Para la expresión regular (x|y)* xy, el alfabeto ∑ = {x, y}

Figura 3.11 Diagrama de transiciones para (x|y)* xy.

x

y

x yq1q1 q2q0

Las cadenas que acepta el AFND pueden ser: L(AFND) = L(ER) = {xy, xxyyxy, yyyyxy, …}

La cadena xy hace el recorrido al estado de aceptación iniciando en q0, en q0 sigue por la arista con etiqueta x, que corresponde al primer símbolo de la cadena, llega a q1, se lee el siguiente símbolo que es y, el cual tiene una salida a q2, no hay más símbolos en la cadena y el control del AF está en q2 por lo tanto la cadena xy se acepta en este AFND cumpliendo con la expresión regular.

Para la ER = (a|b|c)ca*, L(ER) = {aca, bcaa, cca, cc} y su diagrama de transiciones:

a

c

a

q1q1 q2b

c

q0

Figura 3.12 AFND para ER = (a|b|c)ca*

Para ER = Letra(Letra|Dígito)* ;

Letra −>(a, b, c, d, …, z, A, B, C, D, …, Z)Dígito −> (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)L(ER) = {sol23;, E1d2a3d;, x;}y su AFND:

;q1q0 q1 q2

Letra

Dígito

Letra

Figura 3.13. AFND para ER = Letra(Letra|Dígito)*.

En cualquier caso de un autómata finito no determinista que siga el patrón de una expresión regular, al momento de convertirlo en una matriz de transición los símbolos del alfabeto que no están representados en el diagrama del AFND se canalizarán a un estado de error.


3.7 MiniMizACión de estAdos en un AFd

El concepto de la minimización de estados en AFD es encontrar otro AFD pero con menor cantidad de estados que acepte el mismo lenguaje que el AFD original, el objetivo es hacer más eficiente el autómata finito.

Figura 3.14 Autómata finito determinista.

ε

1 2 3 4

dígito

dígitodígito

dígito

delimitadorletra

letra

letra

letra

En la figura 3.14 se observa un AFD de un identificador válido, en donde puede apli-carse minimización de estados, por ejemplo al estado 4 se llega si el símbolo leído es un de-limitador o un fin de cadena, aquí se puede eliminar este estado, ya que en la programación el ciclo de búsqueda de la cadena leída es hasta este fin de cadena y así eliminamos un estado por el número de tokens que acepta el lenguaje.

Otro aspecto para tomar en cuenta en la minimización es eliminar los estados que no son accesibles a ellos y las aristas que provienen de estos estados eliminados. Por ejemplo en la figura 3.9 que se eliminaron los estados nombrados por conjuntos estos son: {3}, {1, 2}, {1, 3} y {1, 2, 3} quedando solamente aquellos estados que representan el patrón que debe seguir la cadena para su aceptación como se muestra en la figura 3.10.

Otro término que se utiliza en la minimización de estados es la indistinguibilidad.Cuando existen caminos o direcciones a seguir en un diagrama de transiciones reali-

zando la misma función y llegan al estado de aceptación con el mismo resultado independi-entemente del camino que se seleccionó para el tratamiento de la cadena, lo que responde a que estos caminos son equivalentes, a estos estados se les llama indistinguibles. En el AFD de la figura 3.15


Figura 3.15 Autómata finito que acepta números enteros y reales con notación exponencial.

2 5

6

1 q1Ce54

q1Ce510

q1Ce57−

−

+

+q13

E

E

9

8

dígito

dígito

dígitodígito

dígitodígito

dígito

dígito

dígito

dígito.

En el AF de la figura 3.15, los estados 5 y 8 son indistinguibles, ya que a partir de estos independientemente la dirección que se tome se cumple la exponencialización, la optimi-zación del diagrama de transiciones es agrupar los estados con el mismo significado, en la figura 3.16 se muestra el resultado reduciendo considerablemente la cantidad de estados.

Figura 3.16 Autómata finito que acepta números y reales con notación exponencial

2.

1 q1Ce54

q1Ce57

−

+

q13

E

6

5

dígito

dígito

dígitodígito

dígito

dígito

dígito

Realice la actividad 3.6


3.8 ApliCACiones: deFiniCión de un CAso de estudio

1. Definir un AFD para la alarma de una casa, conectada a una central que da aviso al dueño o al departamento de seguridad para intervenir cuando se detecta un intruso que ha quebrantado la seguridad. Existen dos tipos de sensores: de movimiento y de puertas y ventanas. El estado inicial es la activación; el estado final es la desactiva-ción.

2. Diseñar un AF para un interruptor eléctrico. 3. Diseñar un AFD y su matriz de transiciones para una máquina expendedora de

refrescos. El valor del producto es de 10 pesos; la máquina sólo acepta monedas y no tiene manera de regresar cambio por el excedente de dinero depositado ni por la cancelación del proceso.

4. Elaborar los diagramas y las matrices de transiciones correspondientes para cada una de las expresiones regulares definidas para el diseño del lenguaje de programación de estudio.


Veamos ahora con más detalle cómo funciona cada analizador: el método descendente inicia con símbolo inicial y va convirtiendo los no terminales en el orden en que encuentra las producciones (transición del paso 1 al paso 2). Cada transición debe guardarse en una pila, de manera que en cualquier momento pueda darse marcha atrás; a continuación se compara con la cadena de entrada, y si no es igual se continúa con el análisis. En esa tran-sición queda un no terminal (ARG9) que, tomando en cuenta la producción número 13, se convierte a ARG8 ce, ARG8 con base en la producción 11 ARG8 se convierte ARG8 a cad ce, OPA, y así sucesivamente, hasta llegar a la cadena de entrada. En esta tabla se muestran solamente los cambios acertados; el número de conversiones es muy grande, ya que es preciso regresar mediante la pila cada vez que no se encuentren más posibilidades de deri-vación. Cuando esto ocurre y la pila está vacía, se presenta un error de sintaxis.

Por su parte, el método ascendente comienza en la cadena de entrada y realiza el siguien-te ciclo tomando en cuenta que NT es el número de tokens que la componen:

1. Se asigna a N = NT (siendo N por así decirlo el largo de la entrada) 2. Se busca la cadena de N tokens en el lado derecho de la gramática. 3. Si se encuentra se convierte al lado izquierdo. Si la cadena de tokens es igual al símbolo inicial se acepta. 4. De lo contrario. 5. Se vuelve a contar el número de tokens y se vuelve al paso 1. 6. De lo contrario se reduce N en 1. 7. Se inicia la Posición del token en 1. 8. Se buscan los N tokens a partir de la posición. 9. Si se encuentra se vuelve al paso 2. 10. De lo contrario se recorre la posición un token a la derecha siempre y cuando la

posición + N no sea mayor que NT y se regresa al paso 7. 11. Si N = 1, las posición = NT y no existe en el lado derecho de la gramática, se debe

marcar error.

Como puede ver, si la gramática está diseñada de forma general, el análisis requiere más pasos para llegar al objetivo; en cambio, si la gramática libre de contexto es específica, los analizadores no demandan tantos pasos para cumplir su función. Obviamente, para lograr que la gramática sea más específica se debe trabajar minuciosamente en el diseño y en el orden de las producciones.

El diseño de las gramáticas puede variar de muchas maneras, dependiendo de la creativi-dad del diseñador. Sin embargo, es imprescindible respetar las reglas para llevar a cabo el desarrollo de los analizadores.

Existen algunas instrucciones que requieren un parámetro llamado condición. La condición puede ser una operación lógica que contiene operaciones relacionales y aritméticas en sus operandos; a su vez, las operaciones relacionales pueden contener operaciones aritméticas. Expresado de otra manera, una condición puede ser cualquiera de las siguientes opciones:

A > 100 operación relacionalA = X * 5 operación relacional que contiene operación aritmética(A = Y+3) o (A > 15000) operación lógica que a su vez contiene operación relacional

De esta manera resulta más evidente por qué un buen programador puede utilizar la condición como un arma muy poderosa para eliminar la posibilidad de hacer la misma comparación en varias etapas, lo cual redunda en un ahorro de código de programación. Por


7.1 ConCeptos básiCos

Una vez más, comenzaremos por definir los términos que utilizaremos a lo largo de este capítulo:

Análisis. Distinción y separación de las partes de un todo hasta llegar a conocer sus principios y elementos.

Semántica. Estudio del significado de los signos lingüísticos y de sus combinaciones, desde un punto de vista sincrónico o diacrónico.

Analizador semántico. Fase de la compilación en donde se establece la distinción de cada elemento de entrada, y se analiza su significado desde el punto de vista del tipo de dato.

Instrucciones compuestas. También conocidas como “bloques”, son aquellas que apare-cen en el cuerpo de otra instrucción de orden superior. Se caracterizan por comenzar en un renglón y terminar en uno posterior. Un ejemplo son los ciclos.

El analizador semántico se puede establecer en una, dos o tres pasadas según las nece-sidades del diseñador. A continuación se explica cómo funcionan las distintas alternativas para decidir de cuántas pasadas debe constar el analizador.

a) Analizador de una pasada. Cuando la definición del lenguaje de programación di-señado incluye instrucciones de declaración de variables, se puede establecer un análisis de una pasada, incluyendo la actualización de los tipos de datos de los iden-tificadores en la tabla de símbolos correspondiente y en el archivo de tokens que fue generado por el analizador léxico, la verificación de instrucciones compuestas y la verificación de los tipos de datos.

b) Analizador de dos pasadas. Es recomendable utilizarlo cuando se quiere tener mayor seguridad del correcto funcionamiento del proceso. Cada pasada realiza por sepa-rado la verificación de instrucciones compuestas y la actualización de los tipos de datos de los identificadores en la tabla de símbolos correspondiente y en el archivo de tokens que fue generado por el analizador léxico.

c) Analizador de tres pasadas. Cuando el lenguaje de programación diseñado no cuenta con instrucciones de declaración de variables, se debe realizar la primera pasada para establecer el tipo de dato de cada identificador utilizado, lo cual se realiza con base en la primera ocurrencia localizada en el archivo de tokens generado por el analizador léxico; luego, la segunda pasada verifica que los tipos de datos estén bien utilizados en las instrucciones, y la tercera verifica las instrucciones compuestas.

Así pues, la primera pasada tiene como objetivo establecer el tipo de datos de los identificadores y constantes numéricas utilizados durante el desarrollo del programa fuente. Si el lenguaje cuenta con instrucciones de declaración de variables, éstas son rastreadas para almacenar el tipo de dato de los identificadores y constantes numéricas en las tablas de símbolos, así como en un archivo temporal generado por el analizador léxico que realizará el análisis semántico. Por otra parte si el lenguaje de programacion no cuenta con instrucciones de declaración de variables, se debe encontrar la primera ocurrencia de asignación al identificador para tomar ese tipo de dato como referencia. Por consiguiente, es necesario almacenarlo en la tabla de símbolos de identificadores y en el archivo temporal. Por otro lado, si la asignación es compleja —por ejemplo, una operación aritmetica—, se debe tomar en cuenta qué operador se está utilizando: si es suma o resta se toma el tipo de dato de los

Capítulo 7 Análisis semántico 95

identificadores o constantes numéricas para asignárselo al identificador en cuestión; de lo contrario, habrá que establecer los criterios convenientes para no provocar un error grave. Por ejemplo:

X = 53 Se le asigna el tipo de dato numérico entero a X Z = 54.87 Se le asigna el tipo de dato numérico real a Z Y = “hola” Se le asigna el tipo de dato cadena a Y R = X+5 Se le asigna el tipo de dato de X a R (si X no tiene tipo de dato, provocará un error de datos) P = 67 + 76 Se le asigna el tipo de dato numérico entero a P Q = 67.6 + 76 Se le asigna el tipo de dato numérico real a Q X = 90 / 5 Se le asigna el tipo de dato numérico real a X T = X / 5 Se le asigna el tipo de dato numérico real a T

La segunda pasada tiene como objetivo verificar que las instrucciones contenidas en los identificadores y constantes numéricas estén bien utilizadas desde el punto de vista del tipo de datos. No sería correcto iniciar un ciclo con un identificador tipo cadena o tipo numérico real.

La tercera pasada tiene como objetivo verificar que todas las instrucciones com-puestas que iniciaron terminen, lo cual se logra a través de contadores: cuando un ciclo comienza, el contador del ciclo se incrementa, y cuando el ciclo termina se reduce, de manera que cuando la pasada termine el contador deberá estar en 0; de lo contrario, tenemos un error de lógica.

Para la primera y tercera pasadas no es necesario contar con elementos anexos para lograr los objetivos. Sin embargo para la segunda, cuyo propósito es verificar la utilización de los tipos de datos en todas las instrucciones, se requiere una serie de reglas semánticas muy similares a la gramática libre de contexto que estudiamos en el capítulo anterior. En este caso, para lograr esto es necesario establecer una serie de conversiones para llegar a un conjunto de reglas semánticas adecuado.

7.2 árboles de expresiones y aCCiones semántiCas de un analizador sintáCtiCo

Los árboles de expresiones muestran las diversas posibilidades de uso de una instrucción desde el punto de vista de tipos de datos. El funcionamiento de las instrucciones resulta más evidente en una presentación gráfica, ya que de esa forma se comprenden los diversos caminos que puede tomar una declaración.

Usaremos los árboles de derivación que diseñamos en el capítulo 6, y los convertiremos en árboles de expresiones. De esta manera podremos ver en el árbol de expresión los elemen-tos contenidos en los árboles de derivación con un tipo de dato asignado. Trabajaremos con el siguiente árbol de sintaxis, en el cual se muestra una asignación a una variable; dicha variable puede ser simple o compuesta, en cuyo caso incluiría operaciones aritméticas en sus operandos:

Capítulo 7 Análisis semántico 111

Sabemos ya que la ejecución del método ascendente recursivo produce un archivo tem-poral, en este caso:

INICONCONINSICE02DESDCONFINDCE03SINOCE02CONCE03PRFIN

En este punto se procede a la concatenación para generar:

INI CON CON INSI CE02 DESD CON FIND CE03 SINO CE02 CON CE03 PRFIN

Ahora comienza la lectura de izquierda a derecha, tomando en cuenta las producciones del método JELU:

Producciones JELU Producción utilizada Método JELU

1 S → INI CON FIN INI CON CON INSI CE02 DESD CON FIND CE03 SINO CE02 CON CE03 PRFIN

2 INI → PRINI 6 INI CON INSI CE02 DESD CON FIND CE03 SINO CE02 CON CE03 PRFIN

3 FIN → PRFIN 7 INI CON INSI CE02 CON CE03 SINO CE02 CON CE03 PRFIN

4 CONS → INSI CON SINO 8 INI CON INSI CON SINO CE02 CON CE03 PRFIN

5 CON → CONS CON 4 INI CON CONS CE02 CON CE03 PRFIN

6 CON → CON CON 8 INI CON CONS CON PRFIN

7 CON → DESD CON FIND 5 INI CON CON PRFIN

8 CON → CE02 CON CE03 6 INI CON PRFIN

1 S

De esta manera, cuando se llega al símbolo inicial ya se tiene la certeza de que la sintaxis es correcta y, además, de que las instrucciones que se iniciaron se dieron por terminadas de la manera adecuada.


utilizar el temporal 1 para sustituir dos de los operandos de los registros 2 y 3. El triplo y el cuádruplo quedan como sigue:

Triplo Cuádruplo

Dato objeto

Dato fuente Operador Dato

objetoDato

fuente 1Dato

fuente 2 Operador

1 T1 ID01 = 1 T1 ID01 CE01 +

2 T1 CE01 + 2 T2 ID02 T1 −

3 T2 ID02 = 3

4 T2 T1 − 4

Instrucciones con operaciones algebraicas reducibles

En ocasiones es necesario hacer uso de las reglas algebraicas para disminuir el tiempo de ejecución cuando se encuentran operaciones que son algebraicamente reducibles. Obvia-mente, para ello es preciso contar con un banco de reglas algebraicas de las cuáles echar mano. Por ejemplo, las reglas más simples son:

X + 0 = XX * 1 = X

Código original Código optimizado

T1 = X + 0

T2 = Y − T1 + 10

T1 = X

T2 = Y − T1 + 10

En este ejemplo vemos que el temporal 1 tiene una operación susceptible de reducción algebraica. Para detectar estos casos se debe hacer un rastreo que encuentre semejanzas entre las operaciones aritméticas y el banco de expresiones algebraicas calificadas para ser redu-cidas, y posteriormente sustituirlas por la reducción algebraica correspondiente. Es muy importante hacer notar que es necesario consultar los contenidos de los identificadores y constantes en sus tablas de símbolos correspondientes.

T1 = ID01 + CE01T2 = ID02 − T1 + CE01

Triplo Cuádruplo

Dato objeto

Dato fuente Operador Dato

objetoDato

fuente 1Dato

fuente 2 Operador

1 T1 ID01 = 1 T1 ID01 CE01 +

2 T1 CE01 + 2 T2 ID02 T1 −

3 T2 ID02 = 3 T2 CE01 +

4 T2 T1 − 4

5 T2 CE01 + 5

Solución: Al analizar el contenido de la constante entera 1 que se utiliza en el registro 2 del triplo, descubrimos que su contenido es 0; entonces examinamos el operador con el que se está relacionando dicha constante numérica y, como el contenido también es 0 y se relaciona con un operador aritmético de suma o de resta, concluimos que la operación co-

potencia - pearson

Documents