2. Tema 2 Generación de código intermedio.

En esta etapa, el compilador toma el código fuente escrito por el usuario y lo

transforma en una secuencia de instrucciones que se pueden ejecutar por una
computadora.
La generación de código intermedio en un compilador consiste en una parte crucial
del proceso de compilación. Esto implica la traducción de las instrucciones escritas en
un lenguaje de programación fuente a un código intermedio, que luego se utiliza para
generar el código objeto.
Durante la generación de código intermedio, los errores de sintaxis y semántica no
corregidos previamente pueden ser detectados, permitiendo al compilador generar
un código óptimo para la plataforma de destino.
El código intermedio se compone de instrucciones abstractas simples, en lugar de
instrucciones de una CPU específica. Estas instrucciones abstractas se pueden
representar con una representación de árbol abstracto (AST) o una representación
sintáctica abstracta (SSA).
Estas representaciones permiten que el compilador inspeccione e interprete el código
fuente, detecte errores semánticos, optimice el código para la plataforma de destino y
genere código objeto final.
La verificación y corrección de errores semánticos, incluye cosas como la verificación
de tipos, la verificación de compatibilidad de argumentos y otras tareas de validación
de lógica. Si el compilador detecta un error semántico, generará un mensaje de error
útil para el usuario que incluirá información detallada sobre el error y cómo
solucionarlo. Una vez que el compilador detecta y corrige los errores semánticos,
generará el código intermedio apropiado para ser ejecutado por una computadora.
Esto generalmente se realiza mediante la generación de código de máquina, un
lenguaje de bajo nivel que es entendido directamente por la computadora.
El código de máquina se puede generar directamente a partir del código fuente
escrito por el usuario, o el compilador puede generar un código intermediario más
abstracto que luego se traduzca al código de máquina.

2.1. Notaciones.

Durante la traducción a notaciones simples, el compilador puede aplicar reglas

semánticas para verificar la semántica del código.
Esto incluiría verificar que los ciclos se utilicen correctamente, que se produzcan los
resultados esperados para las funciones y que se cumplan los requisitos para el uso de
variables. En ambos casos, el compilador puede generar un informe de errores para
informar al usuario sobre los errores semánticos detectados.
Este informe de errores puede incluir información como el lugar exacto del código
donde se detectó el error, el tipo de error y la descripción de este. Esta información
ayuda al usuario a corregir los errores de manera rápida y eficiente.
En resumen, los compiladores pueden detectar errores semánticos a través de la
aplicación de reglas semánticas durante la generación de código intermedio o la

32
traducción a notaciones simples. Esto se logra mediante la verificación de tipos de
datos, nombres de símbolos, uso de ciclos, resultados de funciones y requisitos de
variables. Si se detectan errores, el compilador genera un informe de errores para
informar al usuario y ayudarlo a corregir los errores de manera rápida y eficiente.

2.1.1. Prefija.

Los errores semánticos en un compilador se pueden manejar usando una variedad de

herramientas. Una de ellas es la notación prefija. Esta herramienta analiza los símbolos
y palabras de un programa y los reordena en una estructura jerárquica usando una
notación prefija.
Esto permite al compilador entender el código como si fuera un árbol de sintaxis y
significa que el compilador puede detectar errores semánticos en el programa, como
variables no declaradas o errores de lógica en los cálculos. Esta herramienta es muy
útil para detectar cualquier error en el flujo lógico del programa. Otra herramienta que
se puede usar para detectar errores semánticos es la lógica formal. Esta herramienta
analiza el programa usando un lenguaje lógico para detectar errores semánticos. Esto
permite al compilador entender el programa a un nivel más profundo, lo que ayuda a
identificar errores sutiles en la lógica, como variables no declaradas o errores de lógica
en los cálculos. Esta herramienta es muy útil para detectar cualquier error lógico en el
programa.
Finalmente, se puede usar la depuración para detectar errores semánticos. Esta
herramienta se utiliza para detectar errores en tiempo de ejecución del programa.
Esto significa que el compilador ejecuta el programa paso a paso y detecta errores
semánticos, como variables no declaradas o errores de lógica en los cálculos.
La notación prefija es una notación para expresiones aritméticas en la que los
operadores preceden a los operandos. Esta notación es similar a la notación posfija,
excepto que los operadores aparecen antes de los operandos en lugar de después.
Por ejemplo
la expresión infija 2 + 3 se escribiría como
+ 2 3 en notación prefija.
Esta notación es útil para expresiones más complejas que contienen varios
operadores, ya que los operadores se pueden aplicar en el orden correcto sin
necesidad de usar paréntesis.
Por ejemplo
la expresión infija 2 + 3 × 4 se escribiría como
+ 2 × 3 4 en notación prefija.
Esta notación también se conoce como notación polaca anterior y se utiliza
comúnmente en lenguajes de programación como APL, y también para la evaluación
de expresiones aritméticas en árboles de expresión.
La notación prefija es una de las tres notaciones principales para representar
expresiones aritméticas. Las otras dos son la notación infija (en la que los operadores
se escriben entre sus operandos) y la notación posfija (en la que los operadores se
escriben después de sus operandos). En general, la notación prefija es menos intuitiva

33
que la notación infija, ya que los operadores aparecen antes de sus operandos
correspondientes. Esta notación también es más fácil de evaluar para el ordenador, ya
que los operadores se aplican en el orden correcto sin necesidad de usar paréntesis.
Sus características principales son:

• Los operadores conservan el mismo orden que la notación infija equivalente.

• No requiere de paréntesis para indicar el orden de precedencia de operadores
ya que él es una operación.
• Se evalúa de izquierda a derecha hasta que encuentra el primer operador
seguido inmediatamente de un par de operando.
• Se evalúa la expresión binaria y el resultado se cambia como un nuevo
operando. Se repite hasta que nos quede un solo resultado.
• El orden es operador, primer operando, segundo operando.

2.1.2. Infija.

Es una expresión aritmética escrita de manera tal que cada operación se escribe con
los dos operandos al lado del operador.
Ejemplo: 5 + 3
En esta notación, los dos números se encuentran al lado del operador "+", lo cual
significa que se quiere sumar 5 más 3.
Otro ejemplo: 8 × 5
En este caso, los dos números se encuentran al lado del operador "×", lo cual significa
que se quiere multiplicar 8 por 5.
Esta notación se conoce como notación infija, ya que los operadores se encuentran
entre los operandos.
La notación infija se contrasta con la notación prefija o notación polaca inversa, en la
cual los operadores se encuentran antes de los operandos.
Por ejemplo, en la notación prefija, la operación anterior se escribiría como "× 8 5". La
notación infija es la más comúnmente usada en matemáticas, ya que es la más
intuitiva para la mayoría de los matemáticos.

2.1.3. Postfija.

También hay una notación posfija, en la cual los operadores se encuentran después de
los operandos. Por ejemplo, en la notación posfija, la operación anterior se escribiría
como "8 5 ×".
Estas notaciones se utilizan en computación para facilitar el procesamiento de los
operadores y operandos.
Es una notación para representar expresiones aritméticas en la que los operandos
preceden a los operadores.

Los operandos se escriben antes de los operadores, en lugar de entre paréntesis como
se suele hacer en la notación infija.

Esto significa que los operadores aparecen después de sus operandos

correspondientes.
34
Por ejemplo

la expresión infija 2 + 3 se escribiría como

2 3 + en notación posfija.

Esta notación es útil para expresiones más complejas que contienen varios
operadores, ya que los operadores se pueden aplicar en el orden correcto sin
necesidad de usar paréntesis.

Por ejemplo

la expresión infija 2 + 3 × 4 se escribiría como

2 3 4 × + en notación posfija.

Esta notación también se conoce como notación polaca inversa o notación polaca
posterior. Se utiliza comúnmente en lenguajes de programación como Lisp, y también
se utiliza para la evaluación de expresiones aritméticas en árboles de expresión.

En general, la notación posfija se considera más fácil de usar que la notación infija, ya
que los operadores no tienen que estar entre los paréntesis. Esta notación también es
más fácil de evaluar para la computadora, ya que los operadores se aplican en el orden
correcto sin necesidad de usar paréntesis.

2.2. Representaciones de código Intermedio.

Representación de código intermedio (CIR) es una representación intermedia del

código objeto generado por un compilador.
El código intermedio está compuesto por instrucciones simples que representan las
instrucciones de un lenguaje de programación de alto nivel.
Estas instrucciones se utilizan para representar un programa de alto nivel en forma de
una secuencia de operaciones elementales. Puede ser utilizada como una forma de
optimizar el código antes de generar el código objeto final.
El CIR también puede ser utilizado para la depuración de errores de lenguaje de
programación de alto nivel. El compilador puede generar una representación del
código de alto nivel, que incluye el número de línea y el código de alto nivel original.
Esto permite que los errores de lenguaje de alto nivel sean detectados y corregidos
con mayor facilidad.
La representación de código intermedio se utiliza comúnmente en compiladores de
lenguajes de alto nivel como C, C++ y Java.
El compilador primero traduce el código de alto nivel a una representación en
lenguaje intermedio, luego genera el código objeto a partir de esta representación.
Esto permite que el compilador optimice el código antes de generar el código objeto.
Por ejemplo, el compilador puede reordenar instrucciones para aumentar el
rendimiento, o eliminar instrucciones redundantes.

35
¨La fase de generación de código intermedio se encarga de traducir el programa a
una representación de código intermedio para que luego ésta pueda ser transformada
en las fases subsiguientes a un código ejecutable en una determinada arquitectura
física¨ (Vélez Reyes, Javier).

Figura 1. Vélez Reyes, Javier (2010). Esquema de Generación de Código Intermedio (Diseño).
Procesadores de Lenguajes. Ingeniería Técnica Superior de Ingeniería Informática.
Departamento de Lenguajes y Programas Informáticos. Editorial UNED.

2.2.1. Notación Polaca.

La notación polaca es una forma de notación matemática que permite expresar

operaciones matemáticas sin usar paréntesis.
En lugar de usar paréntesis para indicar la prioridad de las operaciones, los operadores
se escriben antes de sus dos operandos. Esto permite una sintaxis más simple que la
notación tradicional, y también hace que sea más fácil de interpretar por una
computadora.
La notación polaca se basa en la expresión de operaciones binarias, como la suma, la
resta, la multiplicación y la división.
Cada operación se escribe como una palabra clave, seguida de los dos operandos. Por
ejemplo, la suma se escribe como "suma" seguida de los dos números a sumar.
Esta notación se puede extender a operaciones más complejas usando paréntesis,
como en la notación tradicional.
La notación polaca se inventó en 1924 por el matemático polaco Jan Łukasiewicz. Se
ha convertido en un estándar en programación de computadoras, donde se utiliza
para escribir algoritmos y expresiones matemáticas.
Esta notación es especialmente útil para la ejecución de operaciones aritméticas por
parte de una computadora, ya que elimina la necesidad de usar paréntesis para
indicar la prioridad de los operadores. Esto permite un código más compacto y legible.
La notación polaca es un tipo de notación matemática en la que se escriben los
operadores entre los operandos, en lugar de antes y después de ellos. Para compilarla,
una forma de hacerlo es recorrer la cadena de entrada de izquierda a derecha.

36
Algoritmo:
- Para cada token encontrado:
- si es un operador, tomar los últimos dos elementos de la pila de operandos y
realizar la operación correspondiente. Después de la operación, el resultado se
coloca en la pila de operandos.
- si es un operando, se coloca en la pila.
Al final, la pila debería contener un solo elemento, el resultado de la operación.
Si la pila contiene más de un elemento, esto significa que el número de operadores no
fue el correcto para el número de operandos.
Por ejemplo, para compilar la expresión "2 + 3 * 5", el compilador debería realizar los
siguientes pasos:
1. Leer el token "2": se coloca en la pila de operandos.
2. Leer el token "+": tomar los últimos dos elementos de la pila (2 y 3) y realizar la
operación de suma. El resultado se coloca en la pila.
3. Leer el token "*": tomar los últimos dos elementos de la pila (5 y 7) y realizar la
operación de multiplicación. El resultado (35) se coloca en la pila.
4. La pila contiene un solo elemento, el resultado de la operación (35). El compilador ha
terminado de compilar la expresión.
En general, la notación polaca es una forma útil de escribir expresiones matemáticas
para que sean fácilmente compiladas por un compilador. Esto se debe a que no hay
ambigüedad en la forma en que se escriben las operaciones. Además, al leer el código
fuente de izquierda a derecha, el compilador puede realizar la operación
correspondiente sin tener que preocuparse por el orden de las operaciones. Esto hace
que sea más fácil para el compilador procesar la expresión y generar el código de
salida correcto.
Algoritmo para la notación polaca generada a través de un autómata con pila.
▪ Representar la expresión en forma de árbol sintáctico.
▪ Recorrer el árbol en postorden
Ejemplo: a + b * c-d

37
Figura 2. Árbol de expresión para la expresión a + b * c-d. Código a b c * + d-

Ventajas y desventajas de la notación polaca

▪ Generación de código: simple, no utiliza registros.
▪ Optimización: es difícil de reordenar ya que hay que considerar el contenido de
la pila.
▪ Interpretación rápida: es muy fácil de interpretar ya que solo necesita una pila.
▪ Transportable: si, ya que todos los procesadores implementan una pila.

2.2.2. Código P.

El código P es un lenguaje de programación creado por el equipo de desarrolladores

de compiladores de la Universidad de Stanford.
Está diseñado para simplificar el diseño de compiladores y comprender cómo
funcionan los lenguajes de programación modernos. Está escrito en lenguaje C y tiene
una serie de características que lo hacen adecuado como lenguaje base para
compiladores.
Estas características incluyen una sintaxis sencilla, una sintaxis estándar, una
estructura de datos avanzada, una biblioteca de funciones y una arquitectura de
compilador de varias etapas.
El compilador de código P es un compilador de código fuente que se usa para
convertir un programa escrito en código P a lenguaje de máquina. Esta herramienta
se usa para crear programas eficientes que se ejecutan en diferentes plataformas y
para optimizar los programas para que se ejecuten de manera más rápida y eficiente.
Así también se usa para detectar los errores en el programa, al proporciona
información sobre cada línea de código para ayudar al programador a solucionar
errores de forma más rápida.
El código intermedio P (también conocido como P-code) es un lenguaje de
programación de bajo nivel diseñado para ser fácilmente convertible a código de
máquina. Fue desarrollado originalmente para su uso en el sistema operativo UCSD
Pascal en la década de 1970, pero también se ha utilizado en otros entornos de
programación.

El código intermedio P es un conjunto de instrucciones similares a las de una CPU,

pero que están diseñadas para ser independientes de la arquitectura de la CPU

38
subyacente. Esto significa que el código intermedio P puede ser traducido a código de
máquina para cualquier plataforma sin necesidad de reescribir todo el código.

El código intermedio P también es una forma útil de optimizar el código antes de su

compilación final. Los compiladores de lenguajes de alto nivel a menudo generan
código intermedio P antes de traducirlo a código de máquina. Al hacer esto, pueden
realizar optimizaciones adicionales y transformaciones de código para mejorar el
rendimiento del programa.

En resumen, el código intermedio P es un lenguaje de bajo nivel que se utiliza como

una forma intermedia de representar el código fuente antes de la generación del
código de máquina final. Es independiente de la plataforma y permite una mayor
optimización del código antes de su compilación final.

2.2.3. Triplos.

Una representación intermedia de tripletas es una estructura de datos que contiene

un conjunto de tripletas (sujeto, predicado, objeto) que describen relaciones entre
conceptos. Estas tripletas están diseñadas para ser usadas como una representación
intermedia para almacenar información en una base de datos y pueden ser usadas
para representar relaciones complejas entre objetos. Por ejemplo, una tripleta puede
describir una relación entre una persona y un lugar, como: (persona, vive en, lugar).
Estas tripletas son muy útiles para modelar relaciones complejas entre conceptos y
pueden ser usadas para almacenar información en una base de datos.
Un compilador puede representar tripletas en una forma intermedia de lenguaje de
máquina. Esto significa que el compilador analizará el código fuente y lo convertirá en
una secuencia de tripletas. Estas tripletas contienen instrucciones simples para la
computadora para ejecutar.
Las tripletas se componen de un operador, un operando izquierdo y un operando
derecho. El operador es la instrucción, el operando izquierdo es el argumento de la
instrucción y el operando derecho es el destino.
1. Operador: el tipo de operación que se realiza, como suma, resta, multiplicación,
división, asignación, entre otros.
2. Operando 1: el primer valor utilizado en la operación.
3. Operando 2: el segundo valor utilizado en la operación.

Por ejemplo, una tripleta podría ser: sumar, x, y; lo que significa que el valor de la
variable ¨x¨ se sumará con el valor de la variable ¨y¨ y el resultado se almacenará en la
variable ¨y¨.
El compilador también puede simplificar este proceso para hacer que sea más
eficiente, como reemplazar los nombres de variables por números o agrupar
instrucciones para reducir la cantidad de tripletas necesarias.
Las tripletas pueden utilizarse para crear una tabla de símbolos para mantener un
seguimiento de las variables y los valores asignados a ellas. Esta tabla es útil para el
compilador para realizar tareas como la verificación de tipos y generar código para la
máquina.

39
Esta tabla contendrá tripletas con los nombres de las variables, sus tipos y sus valores.
Esto le permitirá al compilador seguir el flujo de datos a través del programa y verificar
que los tipos de datos sean correctos.
Las tripletas también son utilizadas por el compilador para generar código en
lenguaje de máquina. Esto significa que el compilador convertirá las tripletas en
instrucciones máquina que puedan ejecutarse por la computadora.
Estas instrucciones son diferentes para cada tipo de computadora y se pueden crear
un conjunto específico para cada computadora. Esto significa que el compilador
tendrá que generar el código para cada computadora específica en la que se desea
ejecutar el programa.
En la compilación, una tripleta se representa como un conjunto de instrucciones de
tres direcciones, una para cada uno de los tres componentes de la tripleta. Estas
instrucciones están diseñadas para realizar operaciones con los tres componentes de
la tripleta para producir los resultados deseados. Por ejemplo, una tripleta que
represente una suma se representará como un conjunto de instrucciones que tomen
los dos operandos, los sumen y guarden el resultado en una ubicación de memoria.
Estas instrucciones se llaman instrucciones de tripleta y se usan para representar
cualquier cosa que un programador desee hacer con los operandos. En algunos
lenguajes de programación, como C, el compilador generará código de tripleta para
representar cada tripleta. Esto significa que cada instrucción se traduce a un conjunto
de instrucciones de tripleta para realizar la misma operación. Esto ayuda a simplificar
la compilación y hace que el código generado sea más eficiente.
Ejemplo Triplos
<operador> <operando1> <operando2>
Ejemplo: W * X + (Y + Z)
1. (*, W, X)
2. (+, Y, Z)
3. (+, (1), (2))
Control de flujo:
IF X>Y
THEN Z=X
ELSE Z=Y+1
1. (>, X, Y)
2. (Saltar si falso, (1), (5) )
3.( =, Z, X)
4. (Saltar,, (7))
5. (+, Y, 1)
6. (=, Z, (5))
7.- RET

40
El resultado se asocia al número de tripleta, cada tripleta se enumera con un número
consecutivo. Al hacer referencia a los números de cada tripleta se encierran en
paréntesis, para diferenciarlos de un número que está siendo usado como operando.
Como podemos ver, una tripleta es un conjunto de tres elementos que describen una
instrucción de un programa. Estas tripletas se usan para generar código intermedio,
que es un lenguaje que usan los lenguajes de programación para comunicarse entre
sí. Esto significa que el código intermedio se usa para traducir el código fuente escrito
por el programador en un lenguaje de programación particular a un lenguaje de
programación diferente. El código intermedio se compone de instrucciones de
lenguaje de máquina simples, como instrucciones de suma, resta, multiplicación y
división. Estas instrucciones se expresan como tripletas, que contienen los operandos,
las instrucciones y el resultado.
Las tripletas se usan para generar el código intermedio, que luego se compila para
generar el código de lenguaje de máquina.
El uso de tripletas para generar código intermedio permite a los programadores
escribir código fuente en cualquier lenguaje de programación y que el compilador lo
traduzca directamente a lenguaje de máquina. Esto hace que la codificación de
programas sea mucho más fácil y rápida. Estas tripletas se usan para generar código
intermedio, que es un lenguaje que usan los lenguajes de programación para
comunicarse entre sí.

Una tripleta en la compilación es una estructura de datos que generalmente consta

de tres elementos: el operador, el primer operando y el segundo operando. Para
generar una tripleta a partir de una expresión simple como "A + B", podrías utilizar una
representación de árbol sintáctico para organizar la información de manera más clara.

Aquí tenemos un ejemplo de cómo podríamos generar una tripleta desde una
expresión "A + B" en Python:

class Tripleta:
def __init__(self, operador, operando1, operando2):
self.operador = operador
self.operando1 = operando1
self.operando2 = operando2

def generar_tripleta(expresion):
operadores = ['+', '-', '*', '/']

for operador in operadores:

if operador in expresion:
operando1, operando2 = expresion.split(operador)
return Tripleta(operador, operando1.strip(), operando2.strip())

# Ejemplo de uso
expresion = "A + B"
tripleta = generar_tripleta(expresion)
print("Operador:", tripleta.operador)
print("Operando1:", tripleta.operando1)
print("Operando2:", tripleta.operando2)

41
En este ejemplo, se ha definido una clase Tripleta para representar la tripleta
resultante y una función generar_tripleta que toma una expresión y busca uno de los
operadores permitidos ('+', '-', '*', '/') en ella. Luego, se divide la expresión en dos
operandos y se crea una instancia de la clase Tripleta con el operador y los operandos
encontrados.

Hay que tener en cuenta que este ejemplo es muy simple y asume que la expresión
contiene un solo operador binario. Para expresiones más complejas con varios
operadores, paréntesis y precedencia de operadores, se necesita una implementación
más sofisticada que analice la expresión de manera más completa.

2.2.4. Cuádruplos.

Un cuádruplo es una forma de representar información en forma de estructuras de

datos. Está formado por cuatro elementos, conocidos como "componentes", que se
utilizan para describir una relación entre dos objetos.
Esta representación intermedia de cuádruplos es una forma sencilla de almacenar y
transmitir información relacional, lo que la hace ideal para aplicaciones como bases de
datos, sistemas de recomendación y análisis de datos. A diferencia de otras formas de
representación, como los diagramas de flujo o los árboles de decisión, los cuádruplos
permiten representar relaciones entre objetos de manera clara y concisa.
En la compilación, un cuádruplo es una representación intermedia de una instrucción
de programa que contiene cuatro elementos. Estos cuatro elementos son el operador,
los dos operandos y el resultado.
Esta representación intermedia se usa para ayudar a un compilador a generar código
objeto o código de máquina a partir de un programa fuente. Los cuádruplos se usan
principalmente para representar instrucciones de asignación, ciclos, llamadas a
funciones, condicionales y saltos a direcciones específicas.
Esta representación intermedia también se utiliza para proporcionar un análisis
estático del programa fuente.
Los cuádruplos están construidos a partir de una instrucción de programa y contienen
los siguientes elementos:
1. Operador: Es el símbolo utilizado para representar la operación que se realizará.
2. Operandos: Estos son los valores de entrada o variables implicadas en la operación.
3. Resultado: Esto es el valor que producirá la operación.
4. Dirección: Esto es la ubicación en la memoria donde se encuentra el resultado de la
operación.
Los cuádruplos se usan para ayudar al compilador a construir el árbol de sintaxis
abstracto (AST) de un programa. El AST es una representación abstracta de un
programa fuente. Los cuádruplos se usan para proporcionar al compilador información
sobre la estructura del programa y la relación entre los diferentes bloques de código.
Esta información ayuda al compilador a generar código objeto o código de máquina
de manera eficiente y con una menor cantidad de errores. Los cuádruplos también se
usan para ayudar al compilador a realizar análisis estáticos del programa fuente.

42
Esto le permite al compilador detectar errores en tiempo de compilación antes de que
el código se ejecute, ayuda a mejorar la calidad del código y reduce el tiempo de
depuración.
Un cuádruplo es una estructura de datos compuesta por cuatro elementos: operador,
dos operandos y un resultado.
Los cuádruplos se usan para representar instrucciones en lenguajes de programación.
Por ejemplo, la instrucción "x = y + z" se puede representar en un cuádruplo como (+, y,
z, x).
El primer elemento es el operador (+) y los siguientes elementos son los operandos (y,
z). El último elemento es el resultado (x). El cuádruplo indica que se debe sumar los
valores de y y z, y luego asignar el resultado a la variable x.
Esta representación intermedia es una forma de codificar instrucciones de manera
compacta y clara.
Ejemplo:
<operador> <operando1> <operando 2> <destino>
(A+B)*(C+D)-E
1. (+, A, B, T1)
2. (+, C, D, T2)
3. (*, T1, T2, T3)
4. (-, T3, E, T4)

2.3. Esquema de generación.

Un esquema de generación a partir de una gramática consiste en un conjunto de

reglas que describen cómo se combinan los elementos léxicos para formar palabras,
frases y oraciones.
Estas reglas se basan en la sintaxis de un idioma dado, lo que significa que definen la
forma en que se deben combinar los elementos para formar una estructura
gramaticalmente correcta.
Estas reglas se utilizan para generar oraciones de manera aleatoria, para ayudar a los
programadores a escribir código que produzca oraciones gramaticalmente correctas.
Un esquema de generación a partir de una gramática consta de los siguientes
elementos:
1. Un conjunto de símbolos léxicos: Estos símbolos son los elementos básicos de una
oración, como palabras reservadas, identificadores, constantes, operadores, etc. Que
conforman los tokens o unidades léxicas.
2. Un conjunto de reglas gramaticales: Estas reglas definen cómo se deben combinar
los elementos léxicos para formar frases y oraciones gramaticalmente correctas.
3. Un conjunto de reglas semánticas: Estas reglas definen el significado de una frase u
oración.

43
4. Un conjunto de herramientas de generación: Estas herramientas permiten a los
programadores generar oraciones de manera aleatoria a partir de un esquema de
generación.
Para generar cadenas de texto a partir de una gramática, se puede seguir el siguiente
esquema:

a) Definir una gramática formal: La gramática formal debe especificar las reglas
para construir cadenas de texto. Para ello, se pueden definir símbolos
terminales y no terminales, producciones, reglas de derivación, entre otros
elementos.
b) Identificar el símbolo inicial: El símbolo inicial es el punto de partida para la
generación de cadenas de texto. En general, se utiliza un símbolo no terminal
como símbolo inicial.
c) Aplicar las reglas de derivación: Las reglas de derivación indican cómo se
pueden transformar los símbolos no terminales en otros símbolos terminales y
no terminales. Para generar una cadena de texto, se puede aplicar una
secuencia de reglas de derivación partiendo del símbolo inicial hasta que se
obtengan únicamente símbolos terminales.
d) Repetir el paso anterior para generar más cadenas: Una vez que se ha generado
una cadena de texto, se puede repetir el proceso para obtener más cadenas
siguiendo los mismos pasos.

Es importante destacar que la generación de cadenas de texto a partir de una

gramática puede no ser única. Es decir, una misma gramática puede generar
múltiples cadenas de texto diferentes.

2.3.1. Variables y constantes.

Durante el proceso de compilación, el compilador traduce las variables y constantes

de un lenguaje de programación a un formato específico para su uso en la máquina.
Las variables son representaciones de información que pueden cambiar. Estos
incluyen cadenas, enteros, booleanos y objetos. Esto significa que el compilador
convierte los datos en lenguaje de máquina para que el procesador pueda leer la
información. Las constantes son valores que no cambian. Estos se utilizan para
representar información que no cambia, como números, caracteres, cadenas y objetos.
Además, se asignan códigos de bytes específicos a cada constante para permitir una
referencia rápida a la información.
El esquema de traducción de variables y constantes en un compilador consiste en un
proceso de conversión de los nombres y valores de variables y constantes en código de
máquina. Esta conversión se realiza a través de una tabla de símbolos que contiene
información acerca de los nombres y valores de las variables y constantes. Esta tabla
se actualiza durante el proceso de compilación para reflejar los nombres y valores de
variables y constantes. El compilador también realiza optimizaciones como la
sustitución de llamadas de función por llamadas directas al código de máquina para
mejorar el rendimiento de la aplicación. El proceso de traducción también incluye el
análisis de la sintaxis para identificar errores de programación, como la asignación de
un valor incorrecto a una variable o la inclusión de una constante que no está definida.
Si el compilador detecta un error, emitirá un mensaje de error y detendrá la
compilación.

44
El proceso de código intermedio para variables y constantes es el proceso de
traducción de instrucciones de lenguaje de alto nivel en instrucciones de lenguaje de
bajo nivel. Se realiza mediante una serie de pasos, comenzando con la identificación
de variables y constantes. Una vez que se hayan identificado estas variables y
constantes, el siguiente paso es asignarles una dirección de memoria. Esto permite
que el compilador sepa dónde buscar los datos cuando se ejecute el código. A
continuación, el compilador comenzará a generar instrucciones de código de bajo
nivel para cada línea de código de alto nivel. Estas instrucciones traducirán la lógica
del programa en instrucciones que el procesador pueda entender.
Finalmente, se compilará el código intermedio, lo que generará un archivo ejecutable,
listo para ejecutarse en el procesador.

2.3.2. Expresiones.

El proceso de traducción de expresiones requiere varios pasos.

El primer paso es analizar la expresión, lenguaje o autómata. Esto implica identificar
qué elementos se incluyen y cómo están relacionados.
Por ejemplo, en un lenguaje, se podrían identificar las palabras clave, las reglas
sintácticas y las estructuras de control.
Después de analizar la expresión, el siguiente paso es traducir los elementos de un
lenguaje a otro. Esto puede implicar la creación de un intérprete, un compilador o una
máquina virtual. Estos programas traducirán la expresión, lenguaje o autómata a un
lenguaje de programación específico.
Finalmente, se pueden realizar pruebas para verificar la exactitud de la traducción. Se
pueden usar herramientas de prueba para probar el código generado y asegurarse de
que produce los resultados esperados. Esto ayudará a garantizar que la traducción es
correcta.
Proceso:
1. El compilador comenzará leyendo la expresión de entrada y analizará su sintaxis.
2. El compilador interpretará la expresión para determinar su significado.
3. El compilador traducirá la expresión a un lenguaje de máquina.
4. El compilador generará código de máquina para ejecutar la expresión.
5. El compilador realizará pruebas para asegurarse de que el código generado es
correcto.
6. El compilador creará un archivo ejecutable que contenga el código de máquina
generado.
7. El compilador proporcionará información de depuración para ayudar a identificar y
solucionar errores.
8. El compilador mostrará la salida generada como resultado de la ejecución de la
expresión.
Rutina para la generación de código intermedio de una Expresión:
exp ::= exp:e1 MAS exp:e2 {:
Exp e = new Exp();
<<comprobación de tipos de e1 y e2>>
ScopeIF scope = scopeManager.getCurrentScope();

45
TemporalFactory tF = new TemporalFactory (scope);
IntermediateCodeBuilder cb = new …Builder (scope)
TemporalIF temp1 = e1.getTemporal ();
TemporalIF temp2 = e2.getTemporal ();
TemporalIF temp = tF.create ();
cb.addQuadruples (e1.getCode ());
cb.addQuadruples (e2.getCode ());
cb.addQuadruple (“ADD”, temp, temp1, temp2);
e.setTemporal (temp);
e.setCode (cb.create());
RESULT = e
:}

2.3.3. Instrucción de asignación.

El esquema de traducción de una instrucción de asignación generalmente sigue los

siguientes pasos:

1. Analizar la sintaxis de la instrucción de asignación para determinar la operación

que se está realizando, así como los operandos que se están utilizando.
2. Identificar el tipo de datos de los operandos para garantizar que sean
compatibles con la operación que se está realizando. Por ejemplo, si se está
asignando un valor numérico a una variable, se debe asegurar que la variable
sea de tipo numérico.
3. Verificar que la variable existe y tiene un tipo de dato compatible con el valor
que se le asignará para generar el código que realiza la operación de
asignación. Esto podría implicar la carga de valores de una ubicación de
memoria y la asignación de esos valores a otra ubicación de memoria. Por
ejemplo, para asignar el valor 5 a una variable "x", se podría generar el siguiente
código en lenguaje de ensamblador: MOV x, 5
4. En algunos casos, se pueden requerir conversiones de tipo o verificaciones de
error. Por ejemplo, si se está asignando un valor flotante a una variable entera,
se podría necesitar redondear el valor antes de asignarlo y verificar que el valor
flotante se encuentra dentro del rango de la variable entera.
5. Finalmente, se genera el código de salida que indica que la operación de
asignación se ha completado con éxito. Por ejemplo, en lenguaje de
ensamblador, se podría generar el siguiente código: MOV eax, 0 ; Indica éxito

El proceso puede variar dependiendo del lenguaje de programación o plataforma

específicos que se estén utilizando.

Un ejemplo de aplicación de este esquema podría ser la siguiente instrucción de

asignación en lenguaje C:

x = y + z;
Siguiendo el esquema, se realizarían las siguientes acciones:

1. La sintaxis de la instrucción de asignación es correcta.

2. La variable a la que se le asignará un valor es "x" y el valor es la suma de las
variables "y" y "z".

46
 3. Se verifica que la variable "x" existe y tiene un tipo de dato compatible con el
resultado de la suma de "y" y "z". Suponiendo que todas estas variables son de
tipo entero, la asignación es válida.
4. Se genera el código correspondiente para realizar la suma de "y" y "z" y asignar
el resultado a "x":

Mov r1, y
add r1, z
mov x, r1
El código exacto puede variar dependiendo del lenguaje de programación y la
arquitectura del procesador utilizado.
En términos generales, la traducción de una instrucción de asignación en la
compilación involucra los siguientes pasos:

1. Análisis léxico: El compilador divide la instrucción de asignación en tokens, que

son unidades básicas de sintaxis como palabras clave, identificadores,
operadores y constantes. En el caso de una instrucción de asignación, los
tokens pueden incluir el identificador de la variable, el operador de asignación y
la expresión que se asigna a la variable.
2. Análisis sintáctico: El compilador verifica que la estructura de la instrucción de
asignación sea gramaticalmente correcta y cumpla con la sintaxis del lenguaje
de programación, para verificar si los tokens forman una expresión válida de
acuerdo con la gramática del lenguaje de programación, por ejemplo, que
tenga la forma "variable = expresión".
3. Análisis semántico: El compilador verifica que la instrucción de asignación
tenga sentido en el contexto del programa y que los tipos de datos de la
variable y la expresión sean compatibles. Esto incluye verificar si el tipo de la
variable y la expresión que se le asigna son compatibles y si el identificador de
la variable se ha declarado previamente. Por ejemplo, que una variable de tipo
entero no reciba una expresión de tipo cadena.
4. Generación de código intermedio: El compilador genera una representación
intermedia de la instrucción de asignación en un lenguaje de bajo nivel que es
más cercano al lenguaje de la computadora. Esta representación intermedia
puede ser en forma de código de tres direcciones, código de máquina virtual o
código ensamblador.
5. Optimización de código: El compilador aplica diversas técnicas de optimización
al código intermedio para mejorar su eficiencia y reducir su tamaño. Por
ejemplo, puede eliminar código redundante o reorganizar las instrucciones
para aprovechar mejor la memoria caché.
6. Generación de código objeto: El compilador traduce el código intermedio
optimizado a código objeto que es código de máquina específico para la
plataforma de destino, como el código de ensamblador o el código binario, que
puede ejecutarse en el hardware de la computadora. Este código es la
representación final de la instrucción de asignación y es lo que se ejecutará en
el sistema objetivo.
7. Vinculación: Si la instrucción de asignación hace referencia a variables o
funciones definidas en otros archivos de código fuente, el compilador debe
vincular esos archivos para crear un archivo ejecutable completo.

47
 Con el proceso anterior se genera una representación en código intermedio de la
instrucción de asignación. Este código intermedio es independiente del lenguaje de
programación y de la arquitectura de la computadora y es una representación del
código fuente. Deben representar la secuencia de operaciones para que se lleve a
cabo la asignación. Esto es las operaciones para que se copie el valor del operando
derecho al operando izquierdo, en la ubicación de memoria que el compilador le
asignó.
Por ejemplo, si consideramos la siguiente instrucción de asignación en el lenguaje de
programación C:

x = y + z;

El proceso de generación de código intermedio para esta instrucción podría implicar

los siguientes pasos:

1. Análisis léxico y sintáctico: el compilador verifica que la sintaxis de la

instrucción sea válida.
2. Análisis semántico: el compilador verifica que las variables y y z tengan un tipo
de dato compatible con la variable x. Y que se encuentren declaradas.
3. Generación de código intermedio: el compilador genera código intermedio que
representa la asignación. Por ejemplo, podría generar código que almacene el
valor de y en un registro, luego sume el valor de z en ese registro y finalmente
almacene el resultado en la variable x.

Rutina para la generación de código intermedio para una Sentencia de asignación

sentenciaAsignacion ::= referencia:r IGUAL exp:e {:

SentenciaAsignacion sa = new SAsignacion ();

<<comprobación de tipos>>

ScopeIF scope = scopeManager.getCurrentScope();

TemporalFactoryIF tF = new TemporalFactory (scope);

TemporalIF eTemp = e.getTemporal ();

TemporalIF rTemp = r.getTemporal ();

TemporalIF rTempI = r.getTemporalIndex ();

TemporalIF rTempO = r.getTemporalOffset ();

TemporalIF temp = tF.create ();

IntermediateCodeBuilder cb = new …Builder (scope);

cb.addQuadruples (e.getCode ());

cb.addQuadruples (r.getCode ());

cb.addQuadruple (“MUL”, temp, rTempI, rSize);

cb.addQuadruple (“ADD”, temp, temp, rTemp);

48
cb.addQuadruple (“ADD”, temp, temp, rTempO);

cb.addQuadruple (“STP”, temp, eTemp);

sa.setCode (cb.create()); RESULT = sa; :}

2.3.4.Instrucciones de control.

La generación de código intermedio para una instrucción de control depende del tipo
de instrucción de control que se esté considerando. A continuación, se muestran
algunos ejemplos de generación de código intermedio para diferentes tipos de
instrucciones de control:

1. Instrucción de salto incondicional: Una instrucción de salto incondicional

simplemente salta a una etiqueta específica en el código. El código intermedio
generado para una instrucción de salto incondicional sería simplemente la
etiqueta a la que se debe saltar. Por ejemplo, si la instrucción de salto
incondicional es "goto label1;", el código intermedio generado sería "label1:".
2. Instrucción de salto condicional: Una instrucción de salto condicional salta a
una etiqueta específica si se cumple una determinada condición. El código
intermedio generado para una instrucción de salto condicional depende de la
condición. Supongamos que tenemos la siguiente instrucción de salto
condicional:

"if (a > b) goto label1;".

El código intermedio generado para esta instrucción podría ser:

t1 = a > b;
if t1 goto label1;
En este caso, el valor booleano de la expresión "a > b" se almacena en la
variable temporal "t1". Si el valor de "t1" es verdadero, se salta a la etiqueta
"label1".
3. Instrucción de retorno: Una instrucción de retorno devuelve un valor de una
función y sale de ella. El código intermedio generado para una instrucción de
retorno depende del valor de retorno y de si la función tiene un tipo de retorno.
Supongamos que tenemos la siguiente instrucción de retorno: "return a + b;". El
código intermedio generado para esta instrucción podría ser:

t1 = a + b;

return t1;

En este caso, el valor de la expresión "a + b" se almacena en la variable temporal

"t1" y se devuelve. Si la función no tiene un tipo de retorno, la instrucción de
retorno simplemente saldría de la función sin generar código intermedio
adicional.

En la compilación, la generación de código intermedio para una instrucción de

control, como una instrucción condicional "if" o una instrucción de bucle "while",
generalmente involucra los siguientes pasos:

49
 1. Evaluación de la expresión condicional: En primer lugar, se evalúa la expresión
condicional de la instrucción de control, para determinar si se debe o no
ejecutar el bloque de código asociado.
2. Generación de código para el bloque de código: Si se debe ejecutar el bloque
de código, se genera el código intermedio correspondiente para ese bloque.
Esto puede implicar la generación de código para una serie de instrucciones
individuales, cada una de las cuales realiza una tarea específica.
3. Generación de código de salto: Después de generar el código para el bloque de
código, se genera un código de salto para saltar a la siguiente instrucción
después del bloque de código, o para volver al inicio del bucle en el caso de una
instrucción de bucle.
4. Actualización de las direcciones de salto: Si se usaron saltos para implementar
la instrucción de control, se debe actualizar la dirección de salto en la
instrucción de salto para apuntar a la ubicación correcta en el código
intermedio.

2.3.5. Funciones.

La generación de código intermedio es un proceso importante en la compilación de

programas. A continuación, se describen los pasos generales para la generación de
código intermedio para una función:

1. Análisis léxico y sintáctico: El primer paso es analizar el código fuente de la

función para asegurarse de que esté bien formado. Esto se hace mediante el
análisis léxico y sintáctico.
2. Análisis semántico: Una vez que se ha analizado la sintaxis, se realiza un análisis
semántico para verificar que el código tenga sentido. Esto incluye la
verificación de tipos, la resolución de identificadores y la detección de errores
semánticos.
3. Creación del árbol de sintaxis abstracta (AST): A continuación, se crea un árbol
de sintaxis abstracta (AST) que representa la estructura de la función. El AST es
una estructura de datos que se utiliza para representar el código fuente en una
forma más manejable y fácil de procesar.
4. Generación de código intermedio: A partir del AST, se genera el código
intermedio. El código intermedio es una representación del código fuente en
un nivel más bajo que es más fácil de traducir en código de máquina. Este paso
incluye la generación de instrucciones de código intermedio, la asignación de
registros y la gestión de la pila de memoria.
5. Optimización de código intermedio: Después de generar el código intermedio,
se puede aplicar una serie de optimizaciones para mejorar su eficiencia y
rendimiento. Esto incluye técnicas como la eliminación de código muerto, la
propagación de constantes y la reorganización de instrucciones para minimizar
la cantidad de saltos de código.
6. Generación de código de máquina: Finalmente, se traduce el código
intermedio en código de máquina que puede ser ejecutado por la CPU. Este
proceso incluye la asignación de direcciones de memoria y la generación de
código de máquina para cada instrucción en el programa.

En resumen, la generación de código intermedio para una función es un proceso

complejo que involucra varios pasos, incluyendo análisis léxico y sintáctico, análisis
semántico, creación de AST, generación de código intermedio, optimización de código

50
intermedio y generación de código de máquina. Cada paso es esencial para crear un
código de máquina eficiente y funcional a partir del código fuente original.

La generación de código intermedio es una etapa importante en la compilación de

programas, que tiene lugar después del análisis sintáctico y semántico y antes de la
optimización y generación de código final. Durante esta etapa, se crea un código
intermedio que representa la función en un nivel más abstracto que el código fuente
original, pero aún no se ha traducido completamente a código de máquina.

El proceso de generación de código intermedio implica la transformación del árbol de

sintaxis abstracta (AST) generado durante el análisis sintáctico y semántico en un
conjunto de instrucciones intermedias que se ajusten a una representación uniforme y
fácilmente manejable. Estas instrucciones intermedias pueden ser más fáciles de
analizar y optimizar que el código fuente original.

Las instrucciones intermedias se organizan típicamente en un formato de tres

direcciones, en el cual cada instrucción tiene una forma "op a, b, c", donde "op" es una
operación como suma, resta, multiplicación, división, etc., y "a", "b" y "c" son registros o
variables temporales que se utilizan para almacenar los resultados y valores
intermedios.

Un ejemplo simple de una función en C y su correspondiente código intermedio en

formato de tres direcciones podría ser el siguiente:

Función en C:

int sum(int a, int b) {

return a + b;

Código intermedio en formato de tres direcciones:

Este código intermedio puede ser posteriormente optimizado y traducido a código de

máquina por el compilador, para producir un ejecutable final que implementa la
función de manera eficiente y correcta.

En este seudocódigo, hemos definido una estructura Cuadrupla para representar las
cuádruplas y una lista cuadruplas para almacenarlas. La función agregarCuadrupla se
utiliza para agregar cuádruplas a la lista.

51
Luego, hemos definido una función suma que realiza una suma y genera una
cuádrupla correspondiente. En el ejemplo de llamada a función, asignamos valores a x
y y, y luego llamamos a la función suma(x, y) para calcular la suma y almacenar el
resultado en z.

Finalmente, después de ejecutar la llamada a función, imprimimos las cuádruplas

generadas.

Ten en cuenta que este es un ejemplo simplificado para ilustrar el concepto de

funciones y llamadas a funciones utilizando cuádruplas en un contexto de
compilación. En un compilador real, las cuádruplas se utilizan para representar
instrucciones intermedias más complejas, y el manejo de funciones suele ser más
elaborado, incluyendo manejo de ámbito, paso de argumentos, gestión de la pila de
llamadas, entre otros aspectos.

52
 Aquí tenemos un seudocódigo que muestra cómo podríamos representar funciones y
llamadas a funciones utilizando cuádruplas en un contexto de compilación:

En este seudocódigo, se ha definido una estructura Cuadrupla para representar las

cuádruplas y una lista cuadruplas para almacenarlas. La función agregarCuadrupla se
utiliza para agregar cuádruplas a la lista.

Luego, se ha definido una función suma que realiza una suma y genera una cuádrupla
correspondiente. En el ejemplo de llamada a función, se asignan valores a ¨x ¨y ¨y¨, y
luego se llama a la función suma(x, y) para calcular la suma y almacenar el resultado
en z.

53
Finalmente, después de ejecutar la llamada a función, se imprimen las cuádruplas
generadas.

Tener en cuenta que este es un ejemplo simplificado para ilustrar el concepto de

funciones y llamadas a funciones utilizando cuádruplas en un contexto de
compilación. En un compilador real, las cuádruplas se utilizan para representar
instrucciones intermedias más complejas, y el manejo de funciones suele ser más
elaborado, incluyendo manejo de ámbito, paso de argumentos, gestión de la pila de
llamadas, entre otros aspectos.

2.3.6. Estructuras.

En el caso específico de una estructura en el código fuente, el compilador deberá

generar código intermedio que permita representar y manipular la estructura durante
la compilación. Esto implica identificar los miembros de la estructura, asignarles
direcciones de memoria y generar código para acceder a ellos.

Por ejemplo, si se tiene la siguiente definición de estructura en C:

El compilador deberá generar código intermedio que permita representar esta

estructura en la memoria y acceder a sus miembros. Esto puede involucrar la
asignación de direcciones de memoria para cada miembro, como se muestra a
continuación:

Luego, el compilador deberá generar código para acceder a los miembros de la

estructura, lo que puede implicar el uso de desplazamientos (offsets) desde la
dirección base de la estructura. Por ejemplo:

54
Estos son solo ejemplos de cómo se podría generar código intermedio para una
estructura durante la compilación. El código real generado dependerá del lenguaje
fuente, la arquitectura de la máquina objetivo y otros factores.
Generar cuádruplas para estructuras de control, como ciclos o bucles y condicionales,
en un compilador implica mantener un seguimiento de las etiquetas de inicio y
finalización de las estructuras, así como realizar saltos condicionales o incondicionales
según sea necesario. A continuación, se presenta un seudocódigo básico que muestra
cómo se podrían generar cuádruplas para un bucle while:

55
En este seudocódigo, se ha definido una estructura Cuadrupla para representar las
cuádruplas y una lista cuadruplas para almacenarlas. La función agregarCuadrupla se
utiliza para agregar cuádruplas a la lista.

Para representar un bucle while, se han utilizado etiquetas (ETIQUETA) para marcar el
inicio y el final del bucle. El bucle se ejecuta mientras la condición sea verdadera y se
evalúa en cada iteración. Cuando la condición se vuelve falsa, se genera un salto
condicional de regreso al inicio del bucle.

Este es un ejemplo simplificado de cómo podríamos generar cuádruplas para un bucle

while en un compilador. En un compilador real, habría que considerar más detalles,
como el manejo de ámbito, el control de flujo, la optimización, etc.

56