INSTITUTO TECNOLOGICO SUPERIOR

DE ALVARADO

INGENIERÍA EN SISTEMAS COMPUTACIONALES

MATERIA:

LENGUAJES DE AUTÓMATAS II

SEMESTRE-GRUPO:

NOVENO SEMESTRE

PRODUCTO ACADÉMICO:

ANTOLOGÍA LENGUAJES DE AUTÓMATAS II

PRESENTA:

RAMON PRIETO CANO

DOCENTE:

ALFONSO ROSAS ESCOBEDO

H. Y G. ALVARADO, VER. ENE-JUN 2018

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

INDICE

INTRODUCCION.......................................................................................................................1

PROPOSITO Y CONTENIDO..................................................................................................2

OBJETIVO.................................................................................................................................4

COMPETENCIAS PREVIAS Y RELACION CON CURSOS ANTERIORES Y

POSTERIORES.........................................................................................................................4

CONTENIDO..............................................................................................................................4

COMPETENCIAS A ALCANZAR EN EL CURSO...............................................................6

UNIDAD 1 ANÁLISIS SEMÁNTICO..............................................................................7

UNIDAD 2 GENERACIÓN DE CÓDIGO INTERMEDIO.......................................18

UNIDAD 3 OPTIMIZACIÓN...................................................................................................26

UNIDAD 4 GENERACIÓN DEL CÓDIGO OBJETO..........................................................35

BIBLIOGRAFIA.......................................................................................................................44
ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

INTRODUCCION

El desarrollo de software se puede dividir en 2 grandes categorías. El

software comercial y el software científico. La presente materia proporciona las
bases para crear software científico. Es común pensar que el estudiante normal
nunca tendrá acceso a desarrollar software científico, sin embargo, esto es un
error ya que cada día las necesidades se van ampliando y todo va siendo más
accesible. Tenemos el clásico ejemplo de la robótica. Actualmente ya hay
tiendas donde venden accesorios para hacer un pequeño robot de juguete. Eso
antes no se veía y ahora ya es común.

Por lo mismo, es importante proporcionarle al alumno las bases para que él se

introduzca con profundidad en el mundo de los compiladores. Esta materia
abre horizontes impresionantes ya que se conoce a fondo las etapas por las
que atraviesa la creación de un lenguaje de computación. Desde la etapa léxica
hasta la etapa de generación de código, el estudiante debe profundizar en
conocimientos que colindan con la parte electrónica de la computadora, el
lenguaje ensamblador, el lenguaje máquina.

Esta materia es una aventura racional. Algunos pensarán que es un tormento

cerebral, pero los inteligentes sabrán apreciar todas las competencias que se
desarrollan en esta materia.

Cabe mencionar que esta materia es la 2ª. Parte de la materia Lenguajes y

autómatas, por lo tanto, se debe dedicar cierto tiempo a dar un repaso práctico
a la 1ª. Parte de la materia que consistió en las 2 primeras fases de los
compiladores: fase léxica y fase sintáctica.

Si no se da este repaso se corre el peligro de que el alumno no entienda ésta

segunda parte ya que van muy ligadas.

PROGRAMACION LENGUAJE Y AUTOMATAS II 1

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Es muy recomendable utilizar un compilador didáctico. Se recomienda

ampliamente el compilador desarrollado por Kenneth Louden. En la bibliografía
al final de este documento se encuentra con la referencia número 3 y número
12. Esto debido a que el alumno debe conocer un compilador ya hecho para
así entender al 100% todos los conceptos.

PROPOSITO Y CONTENIDO

En esta asignatura se debe desarrollar el análisis semántico, la generación de

código, la optimización y la generación del código objeto para obtener el

PROGRAMACION LENGUAJE Y AUTOMATAS II 2

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

funcionamiento de un compilador. Esta asignatura busca proveer al estudiante

de herramientas, conocimientos y habilidades necesarias para desarrollar un
compilador con base en los conocimientos previos de la asignatura lenguajes y
autómatas I. La aportación de esta materia es relevante en el ámbito del
desarrollo de software de sistemas.

Es indispensable distinguir que la carrera de Ingeniería en Sistemas

Computacionales se basa no sólo en el desarrollo de software comercial y
administrativo, sino también en el desarrollo de software científico. Esta
materia se ubica en la segunda categoría y es indispensable desarrollar
software en estos campos para preparar a los egresados y tengan la
posibilidad de cursar posgrados de alto nivel.

La asignatura trata de concretar un traductor iniciado en la materia previa para

que el estudiante comprenda que es capaz, mediante técnicas bien definidas,
de crear su propio lenguaje de programación. La aportación de la asignatura al
perfil del egresado será específicamente la siguiente:

 Desarrollar, implementar y administrar software de sistemas o de

aplicación que cumpla con los estándares de calidad buscando
como finalidad apoyar la productividad y competitividad de las
organizaciones.

 Integrar soluciones computacionales con diferentes tecnologías,

plataformas o dispositivos.

 Diseñar e implementar interfaces hombre – máquina y máquina –

máquina para la automatización de sistemas.

 Identificar y comprender las tecnologías de hardware para proponer,

desarrollar y mantener aplicaciones eficientes.

PROGRAMACION LENGUAJE Y AUTOMATAS II 3

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

OBJETIVO

Desarrollar software de base: traductor, intérprete o compilador.

COMPETENCIAS PREVIAS Y RELACION CON CURSOS ANTERIORES Y

POSTERIORES

 Definir, diseñar, construir y programar las fases del analizador

léxico y sintáctico de un traductor o compilador.

 Su relación con materias anteriores: Fundamentos de

programación, Tópicos avanzados de programación, Fundamentos
de Ingeniería de Software, Lenguajes y autómatas I.

 Su relación con materias posteriores:

Sistemas programables

 Las competencias logradas en esta materia son: razonamiento

deductivo e inductivo, análisis – síntesis.

CONTENIDO

UNIDAD 1 Análisis semántico

1.1. Arboles de expresiones.

1.2. Acciones semánticas de un analizador sintáctico.

1.3. Comprobaciones de tipos en expresiones.

PROGRAMACION LENGUAJE Y AUTOMATAS II 4

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

1.4. Pila semántica en un analizador sintáctico.

1.5. Esquema de traducción.

1.6. Generación de la tabla de símbolo y de direcciones.

1.7. Manejo de errores semánticos.

UNIDAD 2 Generación de código intermedio.

2.1 Notaciones

2.1.1 Prefija

2.1.2 Infija

2.1.3 Postfija

2.2 Representaciones de código Intermedio.

2.2.1 Notación Polaca

2.2.2 Código P

2.2.3 Triplos

2.2.4 Cuádruplos.

2.3 Esquema de generación.

2.3.1 Variables y constantes.

2.3.2 Expresiones.

2.3.3 Instrucción de asignación.

2.3.4 Instrucciones de control.

PROGRAMACION LENGUAJE Y AUTOMATAS II 5

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

2.3.5 Funciones

2.3.6 Estructuras

UNIDAD 3 Optimización

3.1 Tipos de optimización.

3.1.1 Locales.

3.1.2 Ciclos.

3.1.3 Globales.

3.1.4 De mirilla.

3.2 Costos.

3.2.1 Costo de ejecución. (memoria, registros, pilas)

3.2.2 Criterios para mejorar el código.

3.2.3 Herramientas para el análisis del flujo de datos.

UNIDAD 4 Generación de código objeto

4.1 Registros.

4.2 Lenguaje ensamblador.

4.3 Lenguaje máquina.

4.4 Administración de memoria.

COMPETENCIAS A ALCANZAR EN EL CURSO

PROGRAMACION LENGUAJE Y AUTOMATAS II 6

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Al término del curso el participante logrará las siguientes competencias:

Unidad 1: Análisis Semántico.

Diseñar mediante el uso de árboles de expresiones dirigida por la sintaxis un

analizador semántico para un meta-compilador.

Unidad 2: Generación de código intermedio.

Aplicar las herramientas para desarrollar una máquina virtual que ejecute
código intermedio a partir del código fuente de un lenguaje prototipo.

Unidad 3: Optimización.

Conocer e Identificar los diferentes tipos de optimización que permita eficientar

el código intermedio.

Unidad 4: Generación del código objeto.

Utilizar un lenguaje de bajo nivel para traducir el código construido a lenguaje

máquina para su ejecución.

UNIDAD 1 ANÁLISIS SEMÁNTICO.

Competencia específica de la unidad:

Diseñar mediante el uso de árboles de expresiones dirigida por la sintaxis un

analizador semántico para un meta-compilador.

PROGRAMACION LENGUAJE Y AUTOMATAS II 7

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

CONTENIDO TEMATICO

En este capítulo analizamos la fase del compilador que calcula la información

adicional necesaria para la compilación una vez que se conoce la estructura
sintáctica de un programa. Esta fase se conoce como análisis semántico
debido a que involucra el cálculo de información que rebasa las capacidades
de las gramáticas

libres de contexto y los algoritmos de análisis sintáctico estándar, por lo que no

se considera como sintaxis. La información calculada también está
estrechamente relacionada con el significado

final, o semántica, del programa que se traduce. Como el análisis que realiza
un compilador es estático por definición (tiene lugar antes de la ejecución),
dicho análisis semántico también se conoce como análisis semántico estático.
En un lenguaje típico estáticamente tipificado como C. el análisis semántico
involucra la construcción de una tabla de símbolos para mantenerse al tanto de
los significados de nombres establecidos en declaraciones e inferir tipos y
verificarlos en expresiones y sentencias con el fin de determinar su exactitud
dentro de las reglas de tipos del lenguaje.

El análisis semántico se puede dividir en dos categorías. La primera es el

análisis de un programa que requiere las reglas del lenguaje de programación
para establecer su exactitud y garantizar una ejecución adecuada. La
complejidad de un análisis de esta clase requerido por una definición del
lenguaje varía enormemente de lenguaje a lenguaje. En lenguajes orientados
en forma dinámica, tales como LISP y Smalltalk, puede no haber análisis
semántico estático en absoluto, mientras que en un lenguaje como Ada existen
fuertes requerimientos que debe cumplir un programa para ser ejecutable.

PROGRAMACION LENGUAJE Y AUTOMATAS II 8

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Otros lenguajes se encuentran entre estos extremos (Pascal, por ejemplo. no

es tan estricto en sus requerimientos estáticos como Ada y C, pero no es tan
condescendiente como LISP).

La segunda categoría de análisis semántico es el análisis realizado por un

compilador para mejorar la eficiencia de ejecución del programa traducido. Esta
clase de análisis por lo regular se incluye en análisis de "optimización", o
técnicas de mejoramiento de código. Investigaremos algunos de estos métodos
en el capítulo sobre generación de código, mientras que en este capítulo nos
enfocaremos en los análisis comunes que por exactitud son requeridos para
una definición del lenguaje. Conviene advertir que las técnicas estudiadas aquí
se aplican a ambas situaciones. También que las dos categorías no son
mutuamente excluyentes, ya que los requerimientos de exactitud, tales como la
verificación de tipos estáticos, también permiten que un compilador genere
código más eficiente que para un lenguaje sin estos requerimientos. Además,
vale la pena hacer notar que los requerimientos de exactitud que aquí se
comentan nunca pueden establecer Ia exactitud completa de un programa, sino
sólo una clase de exactitud parcial. Tales requerimientos todavía son
útiles debido a que proporcionan al programador información para mejorar
la seguridad y fortaleza del programa.

El análisis semántico estático involucra tanto la descripción de los análisis a

realizar como la implementación de los análisis utilizando algoritmos
apropiados. En este sentido, es semejante al análisis léxico y sintáctico. En el
análisis sintáctico, por ejemplo, utilizamos gramáticas libres de contexto en la
Forma Backus-Naus (BNF, por sus siglas en inglés) para describir la sintaxis y
diversos algoritmos de análisis sintáctico descendente ascendente para
implementar la sintaxis. En el análisis semántico la situación no es tan clara, en
parte porque no hay un método estándar (como el BNF) que permita
especificar la semántica estática de un lenguaje, y en parte porque la cantidad
y categoría del análisis semántico estático varía demasiado de un lenguaje a
otro. Un método para describir el análisis semántico que los escritores de

PROGRAMACION LENGUAJE Y AUTOMATAS II 9

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

compiladores usan muy a menudo con buen efecto es la identificación de

atributos, o propiedades, de entidades del lenguaje que deben calcularse y
escribir ecuaciones de atributos o reglas semánticas, que expresan cómo el
cálculo de tales atributos está relacionado con las reglas gramaticales del
lenguaje. Un conjunto así de atributos y ecuaciones se denomina gramática
con atributos.

Las gramáticas con atributos son más útiles para los lenguajes que obedecen
el principio de la semántica dirigida por sintaxis, la cual asegura que el
contenido semántico de un programa se encuentra estrechamente relacionado
con su sintaxis. Todos los lenguajes modernos tienen esta propiedad. Por
desgracia, el escritor de compiladores casi siempre debe construir una
gramática con atributos a mano a partir del manual del lenguaje, ya que rara
vez la da el diseñador del lenguaje. Aún peor, la construcción de una gramática
con atributos puede complicarse innecesariamente debido a su estrecha
adhesión con la estructura sintáctica explícita del lenguaje. Un fundamento
mucho mejor para la expresión de los cálculos semánticos es la sintaxis
abstracta, como se representa mediante un árbol sintáctico abstracto. Incluso.
el diseñador del lenguaje, también suele dejar al escritor del compilador la
especificación de la sintaxis abstracta.

Los algoritmos para la implementación del análisis semántico tampoco son tan
claramente expresables como los algoritmos de análisis sintáctico. De nuevo,
esto se debe en parte a los mismos problemas que se acaban de mencionar
respecto a la especificación del análisis semántico. No obstante, existe un
problema adicional causado por la temporización del análisis durante el
proceso de compilación. Si el análisis semántico se puede suspender hasta
que todo el análisis sintáctico (y la construcción de un árbol sintáctico
abstracto) esté completo, entonces la tarea de implementar el análisis
semántico se vuelve considerablemente más fácil y consiste en esencia en la
especificación de orden para un recorrido del árbol sintáctico. junto con los
cálculos a realizar cada vez que se encuentra un nodo en el recorrido. Sin

PROGRAMACION LENGUAJE Y AUTOMATAS II 10

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

embargo, esto implica que el compilador debe ser de paso múltiple. Si. por otra
parte, el compilador necesita realizar todas sus operaciones en un solo paso
(incluyendo la generación del código), entonces la implementación del análisis
semántico se convierte en mucho más que un proceso a propósito para
encontrar un orden correcto y un método para calcular la información
semántica (suponiendo que un orden correcto así exista en realidad).
Afortunadamente, la práctica moderna cada vez más permite al escritor de
compiladores utilizar pasos múltiples para simplificar los procesos de análisis
semántico y generación de código.

A pesar de este estado algo desordenado del análisis semántico, es muy útil
para estudiar gramáticas con atributos y cuestiones de especificación. ya que
esto redundará en la capacidad de escribir un código más claro, más conciso y
menos proclive a errores para análisis semántico, además de permitir una
comprensión más fácil de ese código. Por lo tanto, el capítulo comienza con un
estudio de atributos y gramáticas con atributos. Continúa con técnicas para
implementar los cálculos especificados mediante una gramática con atributos,
incluyendo la inferencia de un orden para los cálculos y los recorridos del árbol
que los acompañan. Dos secciones posteriores se concentran en las áreas
principales del análisis semántico: tablas de símbolos y verificación de tipos. La
última sección describe un analizador semántico para el lenguaje de
programación TlNY.

ATRIBUTOS Y GRAMATICAS CON ATRIBUTOS

Un atributo es cualquier propiedad de una construcción del lenguaje de

programación. Los atributos pueden variar ampliamente en cuanto a la
información que contienen, su complejidad y en particular el tiempo que les
torna realizar el proceso de traducción/ejecución cuando pueden ser
determinados. Ejemplos típicos de atributos son El tipo de <latos de una
variable El valor de una expresión La ubicación de una variable

PROGRAMACION LENGUAJE Y AUTOMATAS II 11

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

en la memoria El código objeto de un procedimiento El número de dígitos

significativos en un número Los atributos se pueden establecer antes del
proceso de compilación (o incluso la construcción de un compilador). Por
ejemplo, el número de dígitos significativos de un número se puede establecer
(o por lo menos dar un valor mínimo) mediante la definición de un Lenguaje.

El proceso (te calcular un atributo y asociar su valor calculado con la

construcción del lenguaje en cuestión se define corno fijación del atributo. El
tiempo que toma el proceso de compilación cuando se presenta la fijación de
un atributo se denomina tiempo de fijación. Los tiempos de fijación de atributos
diferentes varían, e incluso el mismo atributo puede tener tiempos de fijación
bastante diferentes de un lenguaje a otro.

Definición de otro autor:

Análisis sintáctico, semántico y generación de código

Como lo hemos mencionado antes, la sintaxis trata con la forma de los

programas válidos, mientras que la semántica trata con su significado. Se dice
que la sintaxis de un lenguaje es aquella porción del mismo que puede ser
descrita de manera adecuada por medio de una Gramática Libre de Contexto
(GLC), mientras que la semántica es aquella porción del lenguaje que no puede
ser descrita de esta manera. El análisis semántico y la generación de código
intermedio pueden ser descritos en términos de la anotación o decoración de
un árbol sintáctico o árbol de análisis sintáctico (parse tree). Las anotaciones
de un árbol sintáctico son llamados “atributos”.

El analizador sintáctico recibe una serie de tokens del analizador léxico y los
organiza en un árbol sintáctico. La manera en que estos tokens son

PROGRAMACION LENGUAJE Y AUTOMATAS II 12

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

organizados está definida por un conjunto de reglas, potencialmente recursivas.

Este conjunto de reglas es la gramática libre de contexto.

En general, una GLC consiste de:

 Un conjunto finito N de símbolos no terminales.

 Un conjunto finito T de símbolos terminales.

 Un subconjunto finito P de [(N U T)* - T*] x (N U T)* llamado conjunto de

producciones, y Un símbolo inicial σ Є N.

La tarea del analizador sintáctico (parser) es determinar si una cadena de

entrada puede derivarse a partir del símbolo inicial, y si es así, cómo puede
hacerse. Hay dos maneras básicas de hacer esto:

 Análisis sintáctico descendente (top-down): puede verse como el intento

de encontrar la derivación más a la izquierda de un flujo de entrada
recorriendo el árbol sintáctico de arriba hacia abajo. Los tokens son
analizados de izquierda a derecha. Para manejar la ambigüedad se
suele utilizar lo que se conoce como opción inclusiva, expandiendo los
lados derechos de las reglas gramaticales. Los analizadores LL (Left-to-
right, Leftmost derivation) y Recursivos-descendentes son ejemplos de
este tipo de análisis.

 Análisis sintáctico ascendente (bottom-up): el analizador inicia con la

secuencia de entrada e intenta re-escribirla hasta llegar al símbolo
inicial. Intuitivamente el analizador intenta localizar el elemento más
básico, después los elementos que contienen éstos, y así
sucesivamente. Los analizadores LR (Left-to-right, Rightmost derivation)
son ejemplos de este tipo de analizadores, que también son conocidos
como Analizadores Desplaza-Reduce (Shift-Reduce).

PROGRAMACION LENGUAJE Y AUTOMATAS II 13

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Analizadores LL vs. LR

El acrónimo LL viene de Left-to-Right, Leftmost Derivation, lo que significa que

cuando se encuentra una regla de producción no terminal que contiene
componentes no terminales en su parte derecha, el componente no terminal de
más a la izquierda es sustituido por el lado derecho de su respectiva regla. Si
esa regla también contiene componentes no terminales, el proceso se repite.

Debido a este comportamiento, los árboles sintácticos generados por los

analizadores LL tienden a crecer más hacia la izquierda que hacia la derecha.
Para tratar de evitar ambigüedades, el analizador siempre lee el siguiente
símbolo en la cadena de entrada, y lo llama “look-ahead”. Por otro lado, el
analizador LL decide la regla de producción a utilizar, dependiendo de lo que
resta por analizar en la cadena de entrada. No mantiene información sobre el
progreso del análisis. Si surge alguna ambigüedad que no pueda ser resuelta
con el auxilio del símbolo “look- ahead”, el analizador produce un error. Aunque
es posible aumentar el número de símbolos “look-ahead”, el problema esencial
persiste; además de los símbolos “look-ahead”, no hay otro método para
recuperarse de ambigüedades en este tipo de analizadores.

Los analizadores LR (Left-to-right, Rightmost derivation) también utilizan

símbolos “look-ahead”, pero además mantienen información sobre el estado del
proceso de análisis. Para este registro utilizan una pila (stack) donde guardan
información del estado inmediato anterior. Cada regla de producción es
considerada un estado y cada regla que resulta en un símbolo no terminal es
considerada una transición a otro estado. Esto hace que los analizadores LR
sean más resistentes a las ambigüedades que los LL, pero pueden resultar en
analizadores que requieren más recursos (en términos de tiempo de
procesamiento y espacio de memoria).

PROGRAMACION LENGUAJE Y AUTOMATAS II 14

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Los analizadores LALR (Look Ahead LR) son una especialización de los
analizadores LR. Pueden manejar más GLC que el LR básico. Es un tipo de
analizador muy popular porque logra un buen balance entre el número de
gramáticas que puede manejar y su consumo computacional (en términos de
procesador y memoria). Las herramientas Yacc y Bison generan analizadores
sintácticos de este tipo.

Ejemplo de análisis sintáctico

Para ilustrar estos conceptos, supongamos que tenemos un lenguaje de

expresiones algebraicas escritas con los símbolos T = {x, y, z, +, *, (, )}, que
constituyen los símbolos terminales de la gramática. Los símbolos no-
terminales que utilizaremos son E para una expresión y T para términos que
constan de factores (símbolo no-terminal F), es decir, N={E,T,F}.

Una expresión algebraica puede consistir de un solo término: E → T O la suma

de una expresión y un término: E → E + T

Un término puede consistir de un factor, o del producto de un factor y un

término:

T→F

T→F*T

Un factor puede consistir de una expresión algebraica entre paréntesis o de

uno de los símbolos terminales:

F→(E)

F→xF→yF→z

PROGRAMACION LENGUAJE Y AUTOMATAS II 15

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Estas reglas, también llamadas producciones, definen el conjunto de todas las

cadenas válidas de este lenguaje.

Una expresión válida para este lenguaje es x * y + z * (x + y). El árbol

sintáctico correspondiente a esta expresión es el siguiente:

Figura 1. Árbol sintáctico de la expresión algebraica x * y + z * (x + y)

Gramática de atributos

Cuando describimos un lenguaje por medio de una GLC, no se puede decir

nada acerca de los significados de las expresiones. Para el manejo de los
significados es común usar una gramática de atributos, la cual asigna un valor
a cada símbolo (terminal y no-terminal) del lenguaje.

La gramática se incrementa con un conjunto de reglas de producción que

especifican como se relaciona cada símbolo con su valor. Para ilustrar el uso
de las gramáticas de atributos, supongamos la siguiente gramática de
expresiones algebraicas compuesta por constantes y que maneja precedencia
y asociatividad:

PROGRAMACION LENGUAJE Y AUTOMATAS II 16

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

E→E+T

E→E-T

E →T

T→T*FT→T/FT→F

F → -F

F→(E)

F → constante

Ahora presentamos la gramática de atributos para este lenguaje de

expresiones algebraicas:

1. E1→ E2 + T

» E1.val := suma(E2.val, T.val) 2. E1→ E2 - T

» E1.val := diferencia(E2.val, T.val)

3. E → T

» E.val := T.val 4. T1→ T2 * F

» T1.val := producto(T2.val, F.val) 5. T1→ T2 / F

» T1.val := cociente(T2.val, F.val)

6. T → F

» T.val := F.val 7. F1→ -F2

» F1.val := inverso(F2.val) 8. F → ( E )

» F.val := E.val

9. F → constante

» F.val := constante. Val

Como vemos, en estas reglas de la gramática de atributos, asignar significados

a las sentencias del lenguaje equivale a asignar una función que recibe como

PROGRAMACION LENGUAJE Y AUTOMATAS II 17

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

parámetros los componentes de la sentencia y regresa un valor que se asigna

a esa expresión.

Resumen

Hemos visto hasta ahora que el análisis sintáctico y el análisis semántico

utilizan algunas herramientas matemáticas para realizar sus funciones: árboles
sintácticos y gramáticas de atributos. Estas herramientas nos permiten definir la
sintaxis y semántica de un lenguaje y nos preparan para la generación de
código intermedio.

UNIDAD 2 GENERACIÓN DE CÓDIGO INTERMEDIO.

Competencia específica de la unidad:

Aplicar las herramientas para desarrollar una máquina virtual que ejecute
código intermedio a partir del código fuente de un lenguaje prototipo.

CONTENIDO TEMATICO

Código máquina

La aparición de los lenguajes de alto nivel mejoró la productividad de los

programadores al liberarlos de los detalles de bajo nivel de la computadora que
estaban programando. El compilador es quien se encarga de realizar la
conversión del código fuente en lenguaje de alto nivel al código máquina de la
computadora que ejecutará el programa. Es, por tanto, el compilador quien
ahora maneja los detalles de bajo nivel de la arquitectura a programar. Esto
implica que el desarrollo del compilador requiere del conocimiento de los
detalles de la arquitectura de la máquina destino. En este apartado
conoceremos la computadora abstracta para la que Tiny traduce sus
programas.

PROGRAMACION LENGUAJE Y AUTOMATAS II 18

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

La máquina abstracta

En este apartado describimos la computadora para la cual el compilador de

Tiny genera código objeto. Está diseñada para facilitar la traducción de un
lenguaje similar al Pascal a una arquitectura abstracta. Esta computadora es un
subconjunto de la computadora Dream (Dream machine) diseñada por Frank
DeRemer. Se trata de una computadora orientada a pila (stack) sin registros
direccionales, por lo que carece de instrucciones como “carga registro X con
…”; es decir, todas las instrucciones suponen que los datos están en la pila y
guardan los resultados en la pila.

Además, se han eliminado algunas restricciones normales en las máquinas

reales:

 Las instrucciones de ramificación no están limitadas a un determinado

rango.

 Todas las instrucciones tienen el mismo formato, y no dos o tres

formatos diferentes, como en la arquitectura IA32, por ejemplo.

La computadora tiene tres memorias diferentes y separadas entre sí:

 De código

 De datos

 De direcciones de retorno

PROGRAMACION LENGUAJE Y AUTOMATAS II 19

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Los límites de cada tipo de memoria están indicados por una serie de registros.
La siguiente figura ilustra estas memorias y sus registros límite:

La memoria de código se considera de sólo-lectura. Ningún programa puede

saltar (branch) fuera de su área de código, ya que todas sus instrucciones
están confinadas al rango de direcciones limitado por los registros CBR y CLR.
Ni el código ni las direcciones de retorno pueden modificarse ni copiarse,
debido a que todas las lecturas y escrituras a memoria están restringidas a
realizarse entre los registros GBR (Global Base Register) y STR (Stack Top
Register).

En otras palabras, en esta máquina es imposible ejecutar código que se auto

modifiqué.

PROGRAMACION LENGUAJE Y AUTOMATAS II 20

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

El límite de la memoria disponible está determinado por el registro SLR (Stack

Limit Register). Este registro simula el tamaño limitado de la memoria física de
las computadoras reales; sin embargo, para fines del compilador de Tiny,
supondremos que la máquina no tiene limitación de memoria, es decir, el
contenido de SLR es “infinito”.

Todo el direccionamiento de las variables globales y locales es relativo a GBR

(Global Base Register) o a LBR (Local Base Register), según corresponda. Por
tanto, la instrucción “LLV i” (Load Local Value i) significa “coloca en el tope de la
pila (push) el valor de la i- ésima palabra del marco local (local frame). Por
tanto, i puede verse como un desplazamiento (offset) a partir de LBR. La
ejecución de esta instrucción ajustará el registro del tope de la pila (STR). Otro
ejemplo es “SGVi” (Storage Global Value i), que significa “saca de la pila el
valor en el tope (pop) y almacénalo en la i-ésima palabra global”. De nuevo, la
ejecución de esta instrucción ajustará el STR, e i es el desplazamiento respecto
de GBR. Otro ejemplo más es “LIT i” (Literal i), que significa “coloca i en la pila”.

Con el fin de simplificar, asumimos que la ejecución del programa, una vez
cargado en memoria, inicia en la instrucción indicada en CBR; es decir,
asumimos que el cargador carga el programa a partir de esa localización. La
herramienta TWS incluye un intérprete que hace las veces de la máquina
abstracta.

Formato de instrucciones

El formato de las instrucciones de la máquina abstracta es el siguiente:

{etiqueta} [mnemónico de la instrucción] [0, 1 o 2 operando]

Donde la etiqueta es opcional, además vemos que hay instrucciones que no

manejan datos, otras que manejan un sólo dato y otras que manejan dos datos.

PROGRAMACION LENGUAJE Y AUTOMATAS II 21

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Es decir, en el conjunto de instrucciones encontramos instrucciones con 0, 1 o

2 campos de direccionamiento.

Conjunto de instrucciones

Las instrucciones que la máquina abstracta puede ejecutar son las siguientes:

De control del programa

NOP: Hacer nada

HALT: Detenerse (halt)

De transferencia de datos

LIT v: Cargar (Push) la Literal v en Local frame (Lf) de la memoria de datos.

LLV i: Cargar valor local (Load Local Value) i en Lf.

LGV i: Cargar valor global (Load Local Value) i en Lf. SLV i: Almacena valor
local i (Store Local Value i) en Lf. SGV i: Almacena valor global i.

LLA i: Cargar Dirección Local i (Load Local Address i) en Lf. LGA i: Cargar
Dirección Global i (Load Global Address i) en Lf. POP n: Extrae n valores (Pop
n values).

DUP : Duplica el tope de la pila.

SWAP : Intercambia los dos valores superiores de la pila.

Aritméticas y lógicas

UOP i: Operación unitaria i (Unary Operation i): const X = Pop Lf. Push (Unop
(i, X)) en Lf

PROGRAMACION LENGUAJE Y AUTOMATAS II 22

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

BOP i: Operación binaria i: const Xr, Xl = Pop Lf, Pop Lf Push (Binop(i,Xl,Xr)) en
Lf

De control de flujo

CALL n: Llamada a una subrutina. RTN n: Retorno de rutina.

GOTO L: I <- L Salto incondicional a L

COND L M: I <- if Pop Lf = True # Pop Stack. Si el valor es: then L # Verdadero,
salta a L

else M # Falso, salta a M. fi

CODE F: Push F on Lf # Carga el punto de entrada. SOS i: Llamada a la

función i del sistema operativo Donde

Unop (i, X) significa: case i of

UNOT: not(X) UNEG: -(X) USUCC: X+1 UPRED: X-1

Binop (i, Xl, Xr) significa: case i of

BAND: Xl and Xr BOR: Xl or Xr BPLUS: Xl + Xr BMINUS: Xl - Xr BMULT : Xl *

Xr

BDIV: Xl div Xr BMOD: Xl mod Xr BEQ: Xl = Xr BNE: Xl <> Xr BLE: Xl <= Xr

BGE: Xl >= Xr BLT: Xl < Xr

BGT: Xl > Xr

Llamadas al sistema

Para simplificar el manejo de los dispositivos de Entrada/Salida suponemos

que tenemos disponibles algunas llamadas al sistema operativo, a las cuales
se accede por medio de la instrucción SOS:

PROGRAMACION LENGUAJE Y AUTOMATAS II 23

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

SOS (Sistema operativo) i significa:

case i of
TRACEX: Trace Execution <- not Trace Execution DUMPMEM: Dump Memory
INPUT: readln(i) Push i on Lf INPUTC: readln(ch) Push Ord(ch) on Lf
OUTPUT: write (Pop Lf) OUTPUTC: write (Chr(Pop(Lf))) OUTPUTL: writeln
EOF: if eof(input) then Push True on Lf else Push False on Lf

Vemos que la máquina abstracta puede ejecutar las cuatro operaciones

aritméticas básicas: suma, resta, multiplicación y división, además la operación
módulo; también puede ejecutar las tres operaciones lógicas básicas: NOT,
AND y OR; puede ejecutar saltos condicionales e incondicionales. Cuenta con
llamadas al sistema operativo para las operaciones de Entrada/Salida y para
funciones de depuración.

Como sabemos, el compilador debe traducir del lenguaje de alto nivel a este
conjunto de instrucciones. Es, por tanto, necesario entender cómo utilizar este
lenguaje ensamblador para escribir programas en bajo nivel para la máquina
abstracta. A continuación, presentamos un par de ejemplos de traducción de
Tiny al ensamblador de la máquina abstracta.

Ejemplo 1

Vamos a mostrar la traducción del siguiente:

programa en Tiny: Program copy:

{Despliega en pantalla (eco) los primeros 10 números leídos con input}
Var count: integer; Begin
Count: =1;
While (count <= 10) do Begin
Output(read); Count: = count + 1; End

PROGRAMACION LENGUAJE Y AUTOMATAS II 24

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

End copy.

El código máquina para este programa se muestra abajo. Obviamente, los

comentarios no son generados por el generador de código.

LIT 0 # Espacio para Count LIT 1 # Asigna 1

SGV 0 # Count: = 1
L2 LGV 0 # Carga Count LIT 10 # Carga 10
BOP BLE # POP, Compara. Push resultado T/F COND L3 L4 # Pop stack, si V,
ve a L3, sino, ve a L4.
L3 SOS INPUT # Llamada al SO. Lee y coloca en la pila SOS OUTPUT #
Llamada al SO. Saca de la pila y despliega SOS OUTPUTL # Despliega un
avance de línea
LGV 0 # Carga Count LIT 1 # Carga 1
BOP BPLUS # Súmalos y guarda resultado en la pila SGV 0 # Saca de la pila y
almacena en Count
GOTO L2 # Regresa a L2
L4 HALT # Salta aquí cuando termines. Détente.

Ejemplo 2

Con el fin de ayudar al entendimiento de esta máquina estudiaremos otro

programa ejemplo, escrito en el lenguaje “Medium”, que es el lenguaje
intermedio para Tiny:

program fact: var m: integer;

function fact (n: integer): integer begin
If n > 0 then
fact: = n * fact (n – 1); else
fact: = 1;
m: = m + 1;
end; begin m: = 0;
output (fact (read), m); end fact.

PROGRAMACION LENGUAJE Y AUTOMATAS II 25

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

El código para la máquina:

LIT 0
GOTO L1 L2 LLV 1
LIT 0 BOP BGT
COND L3 L4 L3 LLV 1
LIT 0
LLV 1
LIT 1
BOP BMINUS CODE L2 CALL 3
BOP BMULT SLV 0
GOTO L5 L4 LIT 1
SLV 0 NOP
L5 LGV 0
LIT 1
BOP BPLUS
SGV 0
LLV 0
RTN 1
L1 LIT 0
SGV 0
LIT 0
SOS INPUT CODE L2 CALL 1
SOS OUTPUT LGV 0
SOS OUTPUT SOS OUTPUTL HALT

Es muy recomendable que traces con papel y lápiz la ejecución de estos dos
programas de ejemplo para que entiendas mejor la programación en bajo nivel
de la máquina abstracta.

PROGRAMACION LENGUAJE Y AUTOMATAS II 26

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

UNIDAD 3 Optimización.

Competencia específica de la unidad:

Conocer e Identificar los diferentes tipos de optimización que permita eficientar

el código intermedio.

CONTENIDO TEMATICO

Estrategias de optimización

La optimización del código es el proceso de "puesta a punto" (tuning) de la

salida de un compilador con el fin de minimizar o maximizar algún atributo del
programa objeto. Es común que la meta de la optimización sea minimizar el
espacio en memoria que ocupa del código o maximizar la velocidad de
ejecución.

Una forma de clasificar las estrategias de optimización del código se basa en el

alcance de la optimización: desde una sola instrucción (optimización local),
hasta un programa entero (optimización global). Técnicamente hablando es
más sencillo implementar estrategias locales que globales, aunque
normalmente el beneficio es menor que el obtenido con estrategias globales.

Algunos ejemplos de estrategias de optimización clasificadas por su alcance

son:

 Optimizaciones locales: Sólo toman en cuenta la información local de

una función.

PROGRAMACION LENGUAJE Y AUTOMATAS II 27

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

 Requieren menos tiempo de análisis.

 Optimización interprocedural o de programa completo: Requieren

analizar el programa completo. Un ejemplo de estrategia de este tipo es
el reemplazo de una llamada a función con el código de la función, lo
que reduce la sobrecarga normal de una llamada a función.

 Optimización de lazos: Se aplica sólo a las estructuras repetitivas, como

for () y while (). Este tipo de optimización puede tener un fuerte impacto
porque muchos programas dedican un buen porcentaje de su tiempo de
ejecución a este tipo de instrucciones.

Además de la clasificación por su alcance, las estrategias de optimización se

dividen en dos categorías generales:

 Independiente vs. dependiente del lenguaje de programación. La

optimización independiente del lenguaje de programación se basa en el
hecho de que muchos lenguajes de programación comparten estructuras
comunes. La optimización dependiente del lenguaje trata de aprovechar
las particularidades de cada lenguaje de alto nivel.

 Independiente vs. dependiente de la máquina destino. Muchas de las

mejores optimizaciones se logran explotando las características
particulares de la plataforma destino.

PROGRAMACION LENGUAJE Y AUTOMATAS II 28

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Obviamente las características de la plataforma destino también afectan las

estrategias de optimización. Entre estas características tenemos las siguientes:

 Número de registros internos en el CPU.

 Tipo de procesador: RISC vs. CISC.

 Número de unidades funcionales: coprocesador numérico o no,

pipelining, etcétera.

Para evitar complicar mucho al compilador de Tiny, la herramienta TWS no

maneja ningún tipo de optimización; sin embargo, muchos compiladores sí lo
hacen, ya que la posibilidad de obtener código optimizado siempre es un
atractivo más para cualquier compilador, independientemente del lenguaje a
traducir.

Detección de errores

Los errores de programación pueden clasificarse en tres categorías:

 Errores de compilación

 Errores de ejecución

 Errores lógicos

PROGRAMACION LENGUAJE Y AUTOMATAS II 29

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Errores de compilación

Son errores que aparecen cuando se está compilando el programa y

eventualmente ocasionan que se detenga el proceso de traducción.

Muchos de estos errores son causados por equivocaciones de captura, por

ejemplo, un mal deletreo de alguna palabra clave, mezcla incorrecta de
mayúsculas y minúsculas en los nombres de variables, o la falta de un signo de
puntuación, entre otros.

Son los errores más fáciles de corregir porque contamos con la ayuda del
compilador. Cuando el compilador detecta un error durante el analizador
sintáctico o no puede asignar significado a una expresión durante el análisis
semántico, genera un mensaje de error mostrando una breve descripción del
error y la línea del código fuente donde lo encontró. Normalmente el compilador
intenta seguir el proceso de traducción con el fin de detectar la mayor cantidad
posible de errores e informarlos al programador para que proceda a corregirlos.
Cuando aparecen varios errores de compilación, por lo general sólo el primer
error es real, los demás pueden no serlo.

Errores de ejecución

Son errores que aparecen mientras el programa está en ejecución.

Un ejemplo típico es la división entre cero; por ejemplo, supón que tienes la
siguiente expresión:

PROGRAMACION LENGUAJE Y AUTOMATAS II 30

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

velocidad = kilómetros / horas

Si la variable horas = 0 cuando se intente ejecutar la instrucción, la división no

puede calcularse y se genera un error de ejecución.

Errores lógicos

Causan que el programa no funcione correctamente y que arroje resultados

equivocados.

En este tipo de errores la compilación termina sin errores y el programa se

ejecuta sin errores de ejecución, pero arroja resultados no esperados, éstos
son los más difíciles de encontrar y corregir.

PRACTICA: Agregando la multiplicación al traductor inicial

En este apartado vamos a ilustrar la manera de expandir el lenguaje inicial

agregando la multiplicación de dos enteros. Esto requiere modificar los
siguientes componentes del traductor:

 El analizador léxico (lex.tiny)

 El analizador sintáctico (parse. tiny)

 El analizador semántico (constrainer)

 El generador de código (gencode)

PROGRAMACION LENGUAJE Y AUTOMATAS II 31

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Vamos a ver como se realiza este proceso:

Cambios al analizador léxico lex.tiny

Las reglas para las operaciones dentro del analizador léxico son las siguientes:

"+"{returnrule(yytext[0]);}
"-" { returnrule(yytext[0]);}

Para agregar el operador "*" se debe agregar la siguiente línea: "*"

{ returnrule(yytext[0]);}

Cambios al analizador sintáctico parser.tiny

A continuación, reproducimos la parte del analizador sintáctico que define las

operaciones aritméticas:

Expression ->Term
->Term LTE Term => "<="; Term ->Primary
->Primary '+' Term => "+"; Primary -> '-' Primary => "-"
-> READ => "read"
->Name
->INTEGER_NUM => "<integer>"
-> '(' Expression ')';
Name -> IDENTIFIER => "<identifier>";
Para introducir el operador de la multiplicación, se debe agregar un nuevo
productor de factor:

Expression ->Term
->Term LTE Term => "<="; Term ->Primary
->Primary '+' Term => "+"; Factor ->Primary
->Primary '*' Factor => "*"; Primary -> '-' Primary => "-"
-> READ => "read"
->Name

PROGRAMACION LENGUAJE Y AUTOMATAS II 32

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

->INTEGER_NUM => "<integer>"

-> '(' Expression ')';
Name -> IDENTIFIER => "<identifier>";

Modificaciones al constrainer

El constrainer consiste de la clase tws: constrainer y del archivo de cabecera

nodes.h, que definen los nodos del árbol que el constrainer y el generador de
código deben recorrer para realizar su trabajo. El archivo nodes.h contiene las
siguientes líneas:

addnode(ProgramNode,"program");
addnode(TypesNode, "types");
addnode(TypeNode, "type");
addnode(DclnsNode ,"dclns");
addnode(DclnNode, "dcln");
addnode(IntegerTNode,"integer");
addnode(BooleanTNode, "boolean");
addnode(BlockNode,"block");
addnode(AssignNode, "assign");
addnode(OutputNode, "output");
addnode(IfNode ,"if");
addnode(WhileNode ,"while");
addnode(NullNode , "null");
addnode(LENode ,"<=");
addnode(PlusNode ,"+");
addnode(MinusNode,"-");
addnode(ReadNode,"read");
addnode(IntegerNode,"<integer>");
addnode(IdentifierNode,"<identifier>");

Se debe agregar la siguiente línea para el nodo de la multiplicación: addnode

(MultNode,"*");

PROGRAMACION LENGUAJE Y AUTOMATAS II 33

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

El archivo de la clase tws: constrainer tiene el método expression(), que analiza

las expresiones en el AST y determina si están bien formadas. A continuación,
mostramos el fragmento de este método que verifica los nodos "+" y "-":

if ((nodename == PlusNode) or (nodename == MinusNode)){ Type1 =

expression(T->get_child(0));
if(T->get_degree()==2){
Type2 = expression(T->get_child(1));
}else{
Type2 = TypeInteger;
}
if( (Type1 != TypeInteger) or (Type2 != TypeInteger)){ error(T);
cout<< "ARGUMENTS OF '+', '-' etc. MUST BE OF TYPE\ INTEGER" <<endl;
}
returnTypeInteger;
}

Para manejar el nuevo nodo de multiplicación "*", se debe agregar el siguiente

código al método:

if (nodename == MultNode){
Type1 = expression(T->get_child(0));
Type2 = expression(T->get_child(1));

if( (Type1 != TypeInteger) or (Type2 != TypeInteger)){ error(T);

cout<< "ARGUMENTS OF '*', MUST BE OF TYPE\ INTEGER" <<endl;
}
returnTypeInteger;
}

Modificaciones al generador de código

PROGRAMACION LENGUAJE Y AUTOMATAS II 34

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

El código para las expresiones aritméticas es generado en la clase

tws::codegenerator, en el método expression(). A continuación, mostramos el
fragmento de este método que genera el código para el nodo "-":

if (name == MinusNode){
expression(T->get_child(0),CurrLabel);
if (T->get_degree() == 2){
expression(T->get_child(1),NoLabel);
codegen(NoLabel,BOPOP,BMINUS);
dec_framesize();
}else{
codegen(NoLabel,UOPOP,UNEG);
}
}

El código para el nodo "*" debe generarse de la siguiente manera:

if (name == MultNode){
expression(T->get_child(0),CurrLabel);
expression(T->get_child(1),NoLabel);
codegen(NoLabel,BOPOP,BMULT);
dec_framesize();
}

Donde BMULT es la instrucción en ensamblador para la multiplicación.

Recompilando el traductor

Una vez realizados todos los cambios anteriores en sus respectivos archivos
fuente, es necesario recompilar nuestro traductor. Esto lo hacemos por medio
de la utilería make, es decir, estando ubicados en el directorio tws simplemente
tecleamos:

PROGRAMACION LENGUAJE Y AUTOMATAS II 35

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

make

Probando la multiplicación

El último paso es capturar y compilar un programa que utilice la nueva

instrucción, por ejemplo:

{Archivo: mult.tiny } programmulti:

var factor1,factor2, producto : integer; begin
factor1 := read; factor2 := read;
producto = factor1 * factor2;
output(producto) endmulti.

Recuerda que compilas el programa con la instrucción: tc mult.tiny

UNIDAD 4 Generación del código objeto.

Competencia específica de la unidad:

Utilizar un lenguaje de bajo nivel para traducir el código construido a lenguaje

máquina para su ejecución.

Análisis del código objeto a crear

La función del compilador es traducir un programa escrito en un lenguaje fuente

(un lenguaje de alto nivel) a un programa equivalente en lenguaje máquina del
procesador destino. Este programa está escrito en código objeto. En esta
sección del Módulo 4 veremos cómo obtener el código objeto que se genera a
partir de algunas instrucciones en lenguaje fuente. A manera de recordatorio, a
continuación, están reproducidas las instrucciones en lenguaje ensamblador de
la máquina abstracta. Toda instrucción del lenguaje fuente debe traducirse a
una o varias de estas instrucciones.

Las instrucciones que la máquina abstracta puede ejecutar son las siguientes:

PROGRAMACION LENGUAJE Y AUTOMATAS II 36

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

De control del programa

NOP: Hacer nada

HALT: Detenerse (halt)

De transferencia de datos

LIT v: Cargar (Push) la Literal v en Local frame (Lf) de la memoria de

datos.
LLV i: Cargar valor local (Load Local Value) i en Lf.
LGV i: Cargar valor global (Load Local Value) i en Lf.
SLV i: Almacena valor local i (Store Local Value i) en Lf.
SGV i: Almacena valor global i.
LLA i: Cargar Dirección Local i (Load Local Address i) en Lf.
LGA i: Cargar Dirección Global i (Load Global Address i) en Lf.
POP n: Extrae n valores (Pop n values)
DUP: DUPlica el tope de la pila.
SWAP: Intercambia los 2 valores superiores de la pila.

Aritméticas y lógicas

UOP i: Operación unitaria i (Unary Operation i): const X = Pop Lf.

Push (Unop (i, X)) en Lf
BOP i: Operación binaria i: const Xr, Xl = Pop Lf, Pop Lf
Push (Binop(i,Xl,Xr)) en L

De control de flujo

CALL n: Llamad a una subrutina.

RTN n: Retorno de rutina.
GOTO L: I <- L Salto incondicional a L
COND L M: I <- if Pop Lf = True # Pop Stack. Si el valor es:
then L # Verdadero, salta a L else M # Falso, salta a M. fi
CODE F: Push F on Lf # Carga el punto de entrada.
SOS i: Llamada a la función i del sistema operativo

Para las operaciones aritméticas y lógicas tenemos que:

Unop (i, X) significa:

PROGRAMACION LENGUAJE Y AUTOMATAS II 37

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

case i of
UNOT: not (X)
UNEG: -(X)
USUCC: X+1
UPRED: X-1

Binop(i,Xl,Xr)
case i of
BAND : Xl and Xr
BOR : Xl or Xr
Código generado por
BPLUS : Xl + Xr el compilador de
BMINUS : Xl - Xr
Tiny
BMULT : Xl * Xr
BDIV : Xl div Xr
Cuando compilamos BMOD : Xl mod Xr un programa de Tiny
BEQ : Xl = Xr
se generan varios BNE : Xl <> Xr archivos a partir del
BLE : Xl <= Xr
programa fuente; estos archivos son:
BGE : Xl >= Xr
BLT : Xl < Xr
BGT : Xl > Xr
 _CONS: Creado por el
analizador semántico, contiene comentarios sobre el cumplimiento de
las restricciones de Tiny.

 _CGEN: Creado por el generador de código, con comentarios sobre la

traducción.

 Contiene además la traducción de las instrucciones del programa fuente,

enriquecido con algunos comentarios útiles para entender mejor el
proceso de traducción.

PROGRAMACION LENGUAJE Y AUTOMATAS II 38

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

 _TREE: Creado por el analizador sintáctico, contiene el árbol sintáctico

obtenido a partir del programa fuente.

 _CODE: Creado por el generador de código, contiene el programa

objeto, sin comentarios.

Es importante anotar que estos archivos se sobrescriben cada vez que compilo
un programa en Tiny. Esto es útil porque me permite analizar el código
generado por el compilador de Tiny para el último programa traducido, y se
evita el uso inmoderado del espacio en disco. A manera de ejemplo, vamos a
ver el código generado por el compilador de Tiny para el programa de prueba
p7, que se muestra a continuación:

Program x:
begin
output (3)
end x.

Recuerda que para compilar este programa debes ejecutar el programa

Cygwin. El comando para compilar este archivo, está ubicado en el directorio
tiny, es:

./tc tests/p7
En la siguiente figura se muestra el resultado de la compilación y ejecución de
p7. También se pueden observar los comandos "cd" para posicionarme en el
directorio de tiny:

A continuación, te muestro el contenido del archivo _CGEN creador por el

compilador de Tiny:

<<< CODE GENERATOR>>> Processing Node program, Label is

<<< CODE GENERATOR>>> Processing Node dclns, Label is
<<< CODE GENERATOR>>> Processing Node block, Label is
<<< CODE GENERATOR>>> Processing Node output, Label is
<<< CODE GENERATOR>>> Processing Node<integer>, Label is

PROGRAMACION LENGUAJE Y AUTOMATAS II 39

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

LIT 3
Incrementing Frame size to 1
SOS OUTPUT
Decrementing Frame size to 0
SOS OUTPUTL
HALT

Recuerda que el generador de código recorre el árbol sintáctico generado por

el analizador sintáctico y revisado por el analizador semántico, para ir
generando el código objeto.

Observa que el primer nodo analizado es el nodo program, después el nombre

del programa, que es un nodo de cln, posteriormente un nodo block (bloque),
cuyo inicio es indicado por el begin, después una instrucción de salida (output),
que recibe como parámetro un nodo entero (3, en este caso). Esta instrucción
output (3) se traduce por las instrucciones lit 3, sos output y sos outputl.
Posteriormente, la instrucción end x. que se traduce por halt.
El contenido del archivo _CODE es el siguiente:

LIT 3
SOS OUTPUT
SOS OUTPUTL
HALT

Fácilmente puede verse que es el mismo código objeto que aparece en el

archivo _CGEN, pero sin comentario alguno. Este archivo nos muestra el
contenido del archivo ejecutable que se "cargará" al intérprete de la máquina
abstracta para su ejecución.

 Ejemplo del código generado por el compilador de Tiny para una

estructura selectiva

PROGRAMACION LENGUAJE Y AUTOMATAS II 40

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

Para ilustrar el código generado por el compilador de Tiny para una estructura
selectiva, vamos a analizar brevemente el código generado por el siguiente
programa:

program
ejemplo2: begin
if (1<=2) then output (1) else output (2)
end ejemplo2.

El contenido del archivo _CGEN es el siguiente:

<<<CODE GENERATOR>>> Processing Node program, Label is

<<<CODE GENERATOR>>> Processing Node dclns, Label is
<<< CODE GENERATOR>>> Processing Node block, Label is
<<< CODE GENERATOR >>> Processing Node if, Label is
<<< CODE GENERATOR >>> Processing Node <=, Label is
<<< CODE GENERATOR>>> Processing Node <integer>, Label is LIT 1
Incrementing Frame size to 1

Observa el orden del recorrido del árbol sintáctico en el archivo _CGEN:

 Node program: Siempre debe iniciar con este nodo.

 Node dclns: Y continuar con éste, por el nombre del programa.

 Node block: Inicio del begin.

 Node if: En este ejemplo, primera instrucción del programa.

 Node <=: Operador relacional de la condición del if.

 Node <integer>: Entero 1, etcétera.

PROGRAMACION LENGUAJE Y AUTOMATAS II 41

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

El código ejecutable de este programa, que es el contenido del archivo _CODE,

es el siguiente:

LIT 1
LIT 2
BOP BLE
COND L1 L2
L1 LIT 1
SOS OUTPUT
SOS OUTPUTL
GOTO L3
L2 LIT 2
SOS OUTPUT
SOS OUTPUTL
NOP
L3 HALT

Que realiza las siguientes operaciones:

1. Coloca el número 1 en el tope de la pila (LIT 1).

2. Coloca el número 2 en el tope de la pila (LIT 2).

3. Realiza la operación binaria (con dos operando) BOP BLE (Branch if

less or equal, salta si es menor o igual), que compara los dos datos en el
tope de la pila.

4. Si la condición es verdadera (COND L1 L2), salta a L1, si no salta a L2.

5. L1: Coloca el 1 en el tope de la pila (LIT 1) y llama a la función output

(SOS OUTPUT) del SO, para desplegar el tope de la pila, llama a outputl
(SOS OUTPUTL), para desplegar un avance de línea y salta a L3
(GOTO L3), con lo que termina la ejecución del programa.

PROGRAMACION LENGUAJE Y AUTOMATAS II 42

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

6. L2: Coloca el 2 en el tope de la pila (LIT 2) y llama a la función output del

SO (SOS OUTPUT), para desplegar el tope de la pila, llama a outputl
(SOS OUTPUTL), para desplegar un avance de línea, ejecuta nada
(NOP) y termina (HALT) la ejecución del programa.

Ejemplo del código generado por el compilador de Tiny para una estructura
repetitiva. Para analizar brevemente el código generado por el compilador de
Tiny para una estructura repetitiva, vamos a revisar brevemente el código
generado para el siguiente programa:

Program mientras:
Var i: integer;
begin
while i <=5 do
begin
output(i);
i: = i+1;
end;
end mientras.

El código generado para este programa es el siguiente:

LIT 0
L1 LGV 0
LIT 5
BOP BLE
COND L2 L3
L2 LGV 0
SOS OUTPUT
SOS OUTPUTL
LGV 0
LIT 1
BOP BPLUS
SGV 0
GOTO L1
L3 HALT

Donde:

PROGRAMACION LENGUAJE Y AUTOMATAS II 43

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

1 LIT 0 es la instrucción que utiliza el compilador de Tiny para definir

una variable (en este caso la variable entera i).

2 LGV 0 (que en este ejemplo está etiquetada con L1), es la instrucción

para referirse a esa primera variable y cargarla en el tope de la pila.

3 Posteriormente carga el número 5 en el tope de la pila (LIT 5) y

compara con la operación BOP BLE (Salta si menor o igual). Si el
contenido de la variable i es menor o igual a 5, entonces salta a L2, si
no salta a L3 (COND L2 L3).

4 L2: Carga i en el tope de la pila (LGV 0), llama a output para que se
despliegue en pantalla (SOS OUTPUT) y despliega un "avance de
línea" llamando a outputl (SOS OUTPUTL).

5 Carga i en el tope de la pila (LGV 0) y el 1 en el tope de la pila (LIT

1).

6 Realiza la operación suma con los dos datos en el tope de la pila y

guarda el resultado en la variable i (BOP BPLUS).

7 Salta incondicionalmente a L1 (GOTO L1), que es la verificación de

la condición del while ().

8 L3: Termina (halt).

BIBLIOGRAFIA

1. Aho, Sethi, Ullman. Compiladores Principios, técnicas y

herramientasEd. Addison Wesley.
2. Lemone Karen A., Fundamentos de compiladores Cómo traducir al
lenguaje de computadora, Ed. Compañía Editorial Continental.

PROGRAMACION LENGUAJE Y AUTOMATAS II 44

ANTOLOGIA
Instituto Tecnológico Superior de Alvarado

3. Kenneth C. Louden. Construcción de compiladores Principios y

práctica.Ed.
4. Thomson.
5. Martin John, Lenguajes formales y teoría de la computación, ED. Mc
Graw Hill
6. Hopcroft John E., Introducción a la Teoría de Autómatas, Lenguajes y
Computación, ED. Addison Wesley
7. Guerra Crespo. Hector. Compiladores. Ed. Tecnologica didáctica.
8. Ronald Mak. Writing compilers and interpreters. Ed. Wiley Computer
Publishing.
9. Fischer, LeBlanc. Crafting a compiler with C. Ed. Cummings
Publishing Company, Inc.
10. Salas Parrilla, Jesús. Sistemas Operativos y Compiladores. McGraw
Hill.
11. Beck. Software de Sistemas, Introducción a la programación de
Sistemas. Addison-Wesley Iberoamericana.
12. Teufel, Schmidt, Teufel. Compiladores Conceptos Fundamentales.
Addison-Wesley Iberoamericana.
13. C. Louden, Kenneth. Lenguajes de programación Principios y
práctica. Thomson.
9 Levine Gutiérrez, Guillermo. Computación y programación moderna
Perspectiva integral de la informática. Pearson Educación.
10 Abel, Peter. Lenguaje ensamblador y programación para PC IBM y
11 compatibles. Pearson Educación.

PROGRAMACION LENGUAJE Y AUTOMATAS II 45