| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX Introdución 9.1 Máquina Virtual 9.2 Máquina Objeto 9.3 Administración de la memoria durante la ejecución

9.4 Código de 3 y 4 direcciones

9.5 Estructuras de control de flujo y de repetición (if then else, case, while, for)

PROBLEMARIO
Bibliografía

9.5 Estructuras de control de flujo y de repetición (if then else, case, while, for)

> La utilización de las condiciones y sus etiquetas asociadas, para generar el código de sentencias que alteran el flujo secuencial de ejecución en función del valor de tales condiciones. Estas sentencias son: IF, WHILE, CASE y REPEAT.

> La sentencia IF-THEN-ELSE

> El caso de la sentencia IF es el más simple. Aquí basta con indicar que la etiqueta de verdad de la condición está asociada al código a continuación del THEN, y la etiqueta de falso se asocia al código que puede haber tras el ELSE. En cualquier caso, una vez acabadas las sentencias del THEN se debe producir un salto al final del IF, porque no queremos que se ejecuten también las sentencias del ELSE. Por tanto, tras la sentencias del THEN, creamos una nueva etiqueta a la cual produciremos un salto, y colocamos el destino de tal etiqueta al final del código del IF. Esto puede apreciarse mejor con el siguiente ejemplo:

> A grosso modo, para hacer esto se necesita insertar dos acciones semánticas intermedias, una que visualice el código marcado en rojo y otra para el código marcado en azul. La etiqueta etq3 se almacena en una variable a la que llamaremos etqFINIF; así, las acciones semánticas necesarias quedarían como se indica a continuación (en este sencilla aproximación se supone que todo IF tiene un ELSE; más adelante se propondrá el caso general):

> Sin embargo, aquí aparece un problema que se convertirá en una constante en el resto de sentencias de control: ¿dónde se declara la variable etqFINIF? (Nótese que esta variable se ha escrito en cursiva en el ejemplo anterior debido a que aún no se ha declarado). Es evidente que cada IF distinto que aparezca en el programa fuente necesitará una etiqueta de fin de IF diferente. Por tanto, está claro que esta etiqueta no debe almacenarse en una variable global ya que la sentencia que hay en el ELSE podría ser otro IF, lo que haría necesario reducirlo por esta misma regla y machacaría el valor de la variable global antes de llegar a la acción semántica del final (en negro).

> Por otro lado, etqFINIF tampoco puede declararse en la acción semántica en azul (donde se le da valor pasándola como parámetro a la función nuevaEtq), ya que en tal caso se trataría de una variable local a un bloque de lenguaje C y no sería visible en la acción semántica del final.

> Por tanto, necesitar declararla en algún lugar tal que sea lo bastante global como para ser vista en dos acciones semánticas de la misma regla; pero también debe ser lo bastante local como para que los IF anidados puedan asignar valores locales sin machacar las etiquetas de los IF más externos. Es de notar que un metacompilador como JavaCC soluciona este problema mediante el área de código asociado a cada regla BNF; aquí se podría declarar la variable etqFINIF y utilizarla en cualquier acción semántica de esa misma regla. En caso de haber IF anidados, la propia recursión en las llamadas a las funciones que representan los no terminales se encargaría de crear nuevos ámbitos con copias de dicha variable.

> La solución adoptada por JavaCC nos puede dar alguna pista para solucionar el problema en PCYacc: necesitamos una variable local a la regla completa, que se pueda utilizar en todas sus acciones semánticas, pero que sea diferente si hay IF anidados. La solución consiste en utilizar el token IF como contenedor de dicha variable, asignándosela como atributo: el atributo del token IF es accesible por las acciones semánticas que hay tras él, y si hay, por ejemplo, tres IF anidados, cada uno de ellos tendrá su propio atributo. Asumiendo esto, la regla queda:

> La figura siguiente muestra el código generado para una sentencia de ejemplo. Nótese que si la parte ELSE no existe (el no terminal opcional se reduce por la regla épsilon), el código funciona correctamente, a pesar de no ser del todo óptimo.

> Sentencia WHILE

> El caso de WHILE y REPEAT es muy similar. En ambos es necesario colocar una etiqueta al comienzo del bucle, a la que se saltará para repetir cada iteración.

> En el caso de WHILE, a continuación se genera el código de la condición, ya que ésta debe evaluarse antes de entrar a ejecutar el cuerpo del bucle. La etiqueta de verdad se ubica justo antes de las sentencias que componen el cuerpo, que es lo que se debe ejecutar si la condición es cierta. Al final de las sentencias se pondrá un salto al inicio del bucle, donde de nuevo se comprobará la condición. La etiqueta de falso de la condición, se ubicará al final de todo lo relacionado con el WHILE, o lo que es lo mismo, al principio del código generado para las sentencias que siguen al WHILE. De esta manera, cuando la condición deje de cumplirse continuará la ejecución de la secuencia de instrucciones que siguen a la sentencia WHILE.

> Recordemos que la regla de producción asociada al WHILE es:

> sent : WHILE cond DO sent FIN WHILE

> por lo que los bloques de código de que disponemos para construir adecuadamente nuestro flujo son los que aparecen sombreados en la figura que a continuación se muestra. El resto de la figura siguiente muestra dónde deben ubicarse las etiquetas de la condición, así como la necesidad de crear una nueva etiqueta asociada al inicio del WHILE.

> Esta etiqueta tiene propiedades muy similares a las ya explicadas en el punto anterior con respecto a la sentencia IF. En otras palabras, se almacenará como atributo del propio token WHILE.

> De esta forma, el diagrama de bloques sigue exactamente la semántica de un bucle WHILE:

> - Se comprueba la condición.

> - Si es verdad se ejecuta sent1 y se vuelve al punto anterior, a comprobar la condición.

> - Si es falsa se sale del bucle y continúa el flujo por la sentencia que sigue al WHILE.

> Finalmente, las acciones semánticas asociadas a la regla de producción del WHILE quedarían:

> Sentencia REPEAT

> Recordemos la regla de producción asociada a la sentencia REPEAT:

> sent : REPEAT sent UNTIL cond, en la que puede observarse cómo la condición se evalúa tras haber ejecutado, al menos, un ciclo. El cuerpo se ejecutará mientras la condición sea falsa, o lo que es lo mismo, hasta que la condición se cumpla.

> Para que el código intermedio generado se comporte de la misma manera, lo ideal es que la etiqueta de falso de la condición se coloque al comienzo del cuerpo, y que la etiqueta de cierto permita continuar el flujo secuencial del programa.

> Así, a continuación de la etiqueta de falso se generaría el código de las sentencias, ya que la condición se evalúa al final. Tras las sentencias colocamos el código de la condición. Como la etiqueta de falso ya se ha puesto al comienzo del bucle, sólo queda poner la etiqueta de verdad tras el código de la condición, lo que dará un diagrama de bloques ideal como el que se presenta en la figura que a continuación se muestra.

> Sin embargo, conseguir generar código que obedezca al diagrama anterior. Resulta inviable, toda vez que la etiqueta de falso no se puede colocar antes de las sentencias del cuerpo ya que aún no se conoce su valor. En otras palabras, la etiqueta de falso se genera cuando se reduce la condición, cosa que sucede después de que necesitemos visualizar su etiqueta. Desde otro punto de vista, cuando se llega a conocer el valor de la etiqueta de falso, es tarde para visualizar su etiqueta, ya que ello tuvo que hacerse incluso antes de reducir las sentencias del cuerpo. Nótese cómo la siguiente acción es incorrecta porque se intenta acceder a un atributo que se desconoce en el momento de ejecutar dicha acción:

> Para solucionar este problema hacemos lo que se llama una indirección, o sea, creamos una nueva etiqueta de inicio del REPEAT y luego creamos un bloque de código en el que colocamos en secuencia:

> - El label de la etiqueta de falso.

> - Un goto a la etiqueta de inicio del REPEAT.

> El diagrama de bloques quedaría como se ilustra en la figura siguiente. Este código tan ineficiente se podría optimizar en una fase posterior.

> Las acciones semánticas asociadas a la regla de producción del REPEAT quedarían:

> El siguiente ejemplo es el código generado para una sentencia REPEAT simple:

> Sentencia CASE

> La sentencia CASE es la más compleja de traducir, ya que ésta permite un número indeterminado y potencialmente infinito de cláusulas CASO en su interior, lo cual obliga a arrastrar una serie de atributos a medida que se van efectuando reducciones. El objetivo semántico de esta sentencia es el mismo que el de la sentencia switch del lenguaje C, sólo que no es necesaria una cláusula break para romper el flujo al final de la sentencia asociada a cada caso particular.

> Por otro lado, y desde el punto de vista gramatical, no podemos utilizar una única regla de producción para indicar su sintaxis por lo que hay que recurrir a reglas recursivas a izquierda y declarar unos cuantos no terminales nuevos. La parte de la gramática que la reconoce es:

> Como puede observarse se han incluido dos posibilidades para el no terminal sent_case, una con la cláusula OTHERWISE y otra sin ella, ya que dicha cláusula es opcional. Ambas reglas podrían haberse sustituido por una sola en la que apareciese un no terminal nuevo que hiciera referencia a la opcionalidad del OTHERWISE, como por ejemplo:

> Pero la dejaremos tal y como se ha propuesto para mostrar, junto a la decisión tomada para el IF, cómo una misma cosa se puede hacer de diferentes formas y cómo afecta cada decisión a la hora de incluir las acciones semánticas para generar código intermedio.

> Además, la gramática propuesta permite construcciones como “CASE a OF FIN CASE”, en la que no se ha incluido ni una sola cláusula CASO. Desde nuestro punto de vista lo consideraremos válido, pero si quisiéramos evitarlo tendríamos que sustituir la primera de inicio_case y ponerla como:

> inicio_case : CASE expr OF CASO expr ‘:’ sent

> La figura siguiente muestra parte del árbol sintáctico que reconoce una sentencia CASE, en la que se puede apreciar la recursión sobre el no terminal inicio_case.

> Una vez vistos estos detalles, vamos a pasar ahora a la generación de código intermedio en sí. De lo primero que hay que percatarse es que la regla principal que se va a encargar de generar código es la que más aparece en el árbol sintáctico, esto es, la regla

> Recursiva de inicio_case:

> inicio_case : inicio_case CASO expr ‘:’ sent

> de tal manera que las acciones semánticas que asociemos a esta regla se ejecutarán repetidas veces durante la reducción de la sentencia CASE completa. Teniendo esto en cuenta vamos a dar una idea preliminar de la estructura del código intermedio que queremos generar, considerando que la estructura que controla cada bloque CASO debe ser siempre la misma (la estructura, pero no las variables y etiquetas que intervienen en cada CASO). Así pues, asociado al ejemplo del árbol anterior se tendrían unos bloques como los de la figura siguiente. En esta última figura se han marcado en diferentes color los bloques de código en función de qué regla de producción lo ha generado. En azul están los bloques generados por la segunda regla de inicio_case, en verde el generado por la primera regla de inicio_case, y en marrón el generado por la regla de sent_case que incluye la cláusula OTHERWISE. Asimismo, al margen de cada bloque expr de la figura, el nombre de la variable (temporal o no) en la que se asume que se almacena el resultado total de evaluar dicha expresión en tiempo de ejecución. Por último, los bloques rayados representan código intermedio que ya ha sido generado por otras reglas de producción; por tanto, todo lo que no está rayado debemos generarlo en acciones semánticas asociadas a las reglas de producción del CASE.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello