Representacion De Codigo Intermedio

2.2 Representaciones de código Intermedio.

Existen dos representaciones intermedias principales:

• Notación sufija

• Cuádruplas

Los operadores diádicos (o binarios) pueden especificarse mediante tres notaciones principales:

• Prefija: el operador diádico es analizado antes que sus operandos.

• Infija: el operador diádico es analizado entre sus operandos.

• Sufija: el operador diádico es analizado después que sus operandos.

En los lenguajes de programación clásicos, los operadores diádicos se representan usualmente en notación infija. La notación prefija permite al operador influir sobre la manera en que se procesan sus operandos, pero a cambio suele exigir mucha más memoria. La sufija no permite esa influencia, pero es óptima en proceso de memoria y permite eliminar el procesado de los paréntesis.

Los operadores monádicos sólo pueden presentarse en notación prefija o sufija.

Además, un árbol sintáctico puede representarse en forma de tuplas de n elementos, de la forma (operador, operando-1, ..., operando-k, nombre). Las tuplas pueden tener longitud variable o fija (con operandos nulos). Las más típicas son las cuádruplas, aunque éstas pueden representarse también en forma de tripletes.

2.2.1 Notación Polaca

Llamada también postfija o polaca inversa, se usa para representar expresiones sin necesidad de paréntesis.

Ejemplos:

a*b ab*

a*(b+c/d) abcd/+*

a*b+c*d ab*cd*+

Los identificadores aparecen en el mismo orden. Los operadores en el de evaluación (de izquierda a derecha).

Problema: operadores monádicos (unarios). O bien se transforman en diádicos (binarios) o se cambia el símbolo.

Ejemplo: -a se convierte en 0-a o en @a

a*(-b+c/d) ab@cd/+*

Existen dos problemas principales:

• Construir la notación sufija a partir de la infija.

• Analizar la notación sufija en el segundo paso de la compilación.

Rutina semántica para transformar de infijo a sufijo

Si el analizador sintáctico es bottom-up, hacemos la siguiente suposición: "Cuando aparece un no terminal V en el asidero, la cadena polaca correspondiente a la subcadena que se redujo a V ya ha sido generada".

Se utiliza una pila donde se genera la salida, inicialmente vacía. Las acciones semánticas asociadas a las reglas son:

E ::= E + T Push +

E ::= E - T Push -

E ::= T

T ::= T * F Push *

T ::= T / F Push /

T ::= F

F ::= i Push i

F ::= (E)

F ::= - F Push @

Análisis de la notación sufija

La gramática completa que permite analizar la notación sufija es:

<Operando> ::= id |

cte |

<Operando> <Operando> <Operador diádico> |

<Operando> <Operador monádico>

<Operador diádico> ::= + | - | * | / | ...

<Operador monádico> ::= @ | ...

Algoritmo de evaluación de una expresión en notación sufija que utiliza una pila:

• Si el próximo símbolo es un identificador, se pasa a la pila. Corresponde a la aplicación de la regla

• <Operando> ::= id

• Si el próximo símbolo es una constante, se pasa a la pila. Corresponde a la aplicación de la regla

• <Operando> ::= cte

• Si el próximo símbolo es un operador diádico, se aplica el operador a los dos operandos situados en lo alto de la pila y se sustituyen éstos por el resultado de la operación. Corresponde a la aplicación de la regla

• <Operando> ::= <Operando> <Operando> <Operador diádico>

• Si el próximo símbolo es un operador monádico, se aplica el operador al operando situado en lo alto de la pila y se sustituye éste por el resultado de la operación. Corresponde a la aplicación de la regla

• <Operando> ::= <Operando> <Operador monádico>

Ejemplo: calcular ab@cd/+*.

Extensión de la notación sufija a otros operadores

• La asignación, teniendo en cuenta que podemos no querer valor resultante. Además, no interesa tener en la pila el valor del identificador izquierdo, sino su dirección.

• a:=b*c+d abc*d+:=

• La transferencia (GOTO).

• GOTO L L TR

• La instrucción condicional

• if p then inst1 else inst2

se convierte en

p L1 TRZ inst1 L2 TR inst2

L1: L2:

• Subíndices:

• a[exp1; exp2; ...; expn]

se convierte en

a exp1 exp2 ... expn SUBIN-n

2.2.2 Código P

2.2.3 Triplos

2.2.4 Cuádruplos.

Una operación diádica se puede representar mediante la cuádrupla

(<Operador>, <Operando1>, <Operando2>, <Resultado>)

Ejemplo:

(*,A,B,T)

Una expresión se puede representar mediante un conjunto de cuádruplas. Ejemplo: la expresión a*b+c*d equivale a:

(*,a,b,t1)

(*,c,d,t2)

(+,t1,t2,t3)

Ejemplo: la expresión c:=a[i;b[j]] equivale a:

(*,i,d1,t1)

(+,t1,b[j],t2)

(:=,a[t2],,c)

Tripletes

No se pone el resultado, se sustituye por referencias a tripletes. Por ejemplo: la expresión a*b+c*d equivale a:

(1) (*,a,b)

(2) (*,c,d)

(3) (+,(1),(2))

mientras que a*b+1 equivale a:

(1) (*,a,b)

(2) (*,(1),1)

Tripletes indirectos: se numeran arbitrariamente los tripletes y se da el orden de ejecución. Ejemplo, sean las instrucciones:

a := b*c

b := b*c

Equivalen a los tripletes

(1) (*,b,c)

(2) (:=,(1),a)

(3) (:=,(1),b)

y el orden de ejecución es (1),(2),(1),(3). Esta forma es útil para preparar la optimización de código. Si hay que alterar el orden de las operaciones o eliminar alguna, es más fácil hacerlo ahí.

Generación automática de cuádruplas

En un análisis bottom-up, asociamos a cada símbolo no terminal una información semántica, y a cada regla de producción una acción semántica. Ejemplo, sea la gramática

E ::= E + T

E ::= E - T

E ::= T

T ::= T * F

T ::= T / F

T ::= F

F ::= i

F ::= (E)

F ::= -F

La regla F::=i asocia a F como información semántica el identificador concreto.

La regla F::=(E) asocia a

...