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

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II Introducción 2.1 Estructura de un Compilador 2.1.1 Función del analizador léxico 2.1.2 Función del analizador sintáctico

2.1.3 Tabla de Símbolos

2.1.4 Función del analizador Semántico

2.1.5 Etapa de análisis

2.1.6 Etapa de Síntesis

UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

> 2.1.4 Función del Analizador Semántico

> Un compilador no sólo tiene que revisar la corrección sintáctica del código fuente, sino también si la semántica corresponde a la del lenguaje de programación, esto significa que el análisis semántico debe garantizar que se consideren todas las reglas dependientes del contexto del lenguaje de programación.

> Un ejemplo de una de estas reglas dependientes del contexto es que los identificadores en lenguajes como PASCAL o MODULA-2 se tienen que declarar antes de usarse. Las tablas de símbolos se emplean para revisar si un identificador ya ha sido declarado, así, las tablas de símbolos y su uso pueden considerarse como parte del proceso de análisis semántico y, por ende, es obvio que el análisis semántico puede efectuarse en paralelo con el análisis sintáctico (o debe efectuarse en paralelo al menos en ciertas situaciones).

> En general, el análisis semántico de un compilador usa la información del análisis sintáctico en combinación con las reglas semánticas del lenguaje de programación para generar una representación interna del código fuente que se va a compilar. Esta generación de una representación interna supone que el compilador debe interpretar el significado del código fuente y, por tanto, que el compilador analice semánticamente las estructuras sintácticas del código fuente al ser reconocidas por el analizador léxico y el analizador sintáctico, la representación interna es un código intermedio que será enviado al generador de código.

> Códigos intermedios

> Con el término código intermedio se refiere a una estructura de código cuya complejidad está entre el código fuente en lenguaje de alto nivel y el código de máquina; por lo tanto, los códigos intermedios se pueden considerar como una interfaz entre el generador de código y las fases previas del compilador.
> Podemos imaginar los códigos intermedios como el código de máquina de una computadora hipotética (ideal). El uso de este nivel de máquina abstracta tiene las siguientes ventajas:

> El propio compilador es independiente de la máquina destino y por tanto es más transportable, ya que todas las características del hardware destino están consideradas en el generador de código; es más fácil llevar a cabo algunas estrategias de optimización (por ejemplo, aquellas que dependen de la asignación de registros) en el código intermedio que en el código fuente.

> Sin embargo, el código que puede generarse a partir del código intermedio por lo general será menos eficiente que el código de máquina generado directamente, debido al nivel de traducción adicional. En lo que sigue presentaremos tres clases de código intermedio de uso común en los compiladores.

> Notación posfija

> La notación posfija es una notación muy simple en la cual se coloca un operador en el extremo derecho de una expresión, es decir, después de los operandos, en vez de estar entre ellos. Por ejemplo, la expresión:

> x + y – x * y

> En notación posfija es:

> x y + x y *-

> ya que xy+ representa la expresión infija x + y, y xy* representa x * y, etcétera y la expresión final x y + x y *- representa la expresión originalmente dada.

> Por lo regular, la notación posfija se emplea en máquinas de pilas, ya que puede manejarse con gran facilidad usando una pila. Al analizar una notación posfija de izquierda a derecha, cada vez que se detecta un operando se mete en la pila. La ocurrencia de un operador con m operandos significa que el n-ésimo operando estará m – n posiciones por debajo de la cima de la pila; o sea, el m-ésimo operando estará en la cima de la pila. Después se sacan los operandos de la pila y se mete el resultado de la operación.

> Por ejemplo, supongamos que x es 1 y y es 2 en la expresión anterior, la cual se evaluará con los siguientes pasos:

1. empilar(1);
2. empilar(2);
3. + requiere dos operandos; se sacan de la pila los dos elementos superiores, se suman y el resultado se mete en la pila: empilar(3);
4. empilar(l);
5. empilar(2);
6. * requiere dos operandos; se sacan de la pila los dos elementos superiores, se multiplican y el resultado se mete en la pila: empilar(2);
7. - requiere dos operandos; se sacan de la pila los dos elementos superiores (es decir, x+y y x*y), se restan y el resultado se mete en la pila: empilar(l).

> Código de tres direcciones

> El código más popular es el código de tres direcciones, cuyo nombre proviene de que sus proposiciones por lo general constan de tres direcciones o registros para dos operando s o argumentos y el resultado. La forma representativa del código de tres direcciones es:

> res := arg1 op arg2

> Donde res, arg1 y arg2 pueden ser constantes (sólo arg1 y arg2), o identificadores definidos por el programador, o variables auxiliares definidas por el compilador, mientras que op es un operador arbitrario. Las variables auxiliares definidas por el compilador sirven para manejar expresiones más complejas que contienen más de un operador; en otras palabras, las expresiones con operadores múltiples se dividen en una secuencia de expresiones que contienen sólo un operador y que operan con variables auxiliares.

> Si consideramos la forma representativa del código de tres direcciones antes presentada, podemos distinguir cuatro elementos básicos: op, arg1, arg2 y res, que suelen representarse como sigue:

> Donde por lo regular arg1, arg2 y res son apuntadores a entradas de la tabla de símbolos. En ese caso, esta forma se denomina cuádrupla.

> El código de tres direcciones, al igual que el de dos direcciones que veremos más adelante, permite que la traducción a código para máquinas de registro sea muy simple ya que los operandos muchas veces son el resultado de operaciones anteriores. De esta manera, las referencias a los resultados de las operaciones previas se dan explícitamente, mientras que en el código posfijo, las referencias las da la pila en forma implícita.

> Supongamos que op puede ser MUL, ADD, SUB y STO para representar los operadores *, +, - y :=. Entonces la proposición z : = x + y - x * y produce el siguiente código de tres direcciones o secuencia de cuádruplos:

> 1: ADD x y va1
> 2: MUL x y va2
> 3: SUB val va2 va3
> 4: STO va3 z

> Como puede verse en este ejemplo, el resultado (res) por lo general es una variable auxiliar (es decir, una variable temporal). Para el empleo del código de tres direcciones se requiere el uso de algoritmos muy elaborados para .manejar las variables auxiliares (esta gestión de nombres se suele llevar a cabo con la tabla de símbolos).

> Sin embargo, puede evitarse el uso de variables auxiliares con los códigos de dos direcciones.

> Código de dos direcciones

> Las variables auxiliares en los códigos de dos direcciones se usan para almacenar temporalmente resultados necesarios para proposiciones subsecuentes. La idea es evitar el uso de estas variables auxiliares haciendo referencia a la proposición cuyo resultado sería la variable auxiliar, cuando se usa dicha variable auxiliar como operando (arg1 o arg2). Por lo tanto, el campo de resultado del código de direcciones ya nos necesario y los campos arg1 y arg2 pueden contener apuntadores a la tabla de símbolos y apuntadores a la secuencia de proposiciones de dos direcciones. Entonces la forma general del código de dos direcciones es la siguiente:

> Esta forma también se conoce como triple.

> El ejemplo anterior, Z := x + y - x * y, se transformará en el siguiente código de dos direcciones:

> 1: ADD x y
> 2: MUL x y
> 3: SUB (1) (2)
> 4: STO (3) Z

> Donde los números entre paréntesis representan apuntadores a la secuencia de proposiciones de dos direcciones.

> Para aclarar las diferencias entre el código de dos direcciones y el de tres direcciones, consideremos la proposición := r.os + 1: . Y comparemos los triples con los cuádruplos:

Triples | Cuádruplos
1. (*, r, s) 2. (*, r, t) 3. (+, (1), (2) ) 4. (:=, (3), x) | 1. (*, r, s, va1) 2. (*, r, t, va2) 3. (+, va1, va2, va3) 4. (:=, va3, x, --)

> Otros códigos

> Otra representación intermedia del código fuente es un árbol de análisis sintáctico donde se elimina toda la información redundante. A este tipo de árbol le llama árbol de sintaxis abstracta, donde cada hoja de un árbol de sintaxis abstracta representa un operando y los nodos internos representan los operadores. También es posible generar la notación prefija de una expresión, en forma similar a la notación posfija. La notación prefija de una expresión puede generarse recorriendo de izquierda a derecha el árbol de análisis sintáctico e imprimiendo un operador la primera vez que se detecte, mientras que en la notación posfija se imprimirá el operador la última vez que se encuentre.

> El código P fue diseñado para compiladores del lenguaje PASCAL y es quizás el código intermedio más destacado. Se denomina máquina P a la máquina abstracta reflejada por este código intermedio, el cual es un computador hipotético de pila con cinco registros y una memoria. Otra forma de código intermedio es el llamado código ensartado.

> En el código ensartado de Bell -también denominado código ensartado directo se establece una correspondencia entre cada operación y una llamada a subrutina, de esta manera, el código ensartado genera una lista de direcciones lineales para estas subrutinas.

> Traducción dirigida por la sintaxis

> El análisis semántico puede efectuarse en paralelo con el análisis sintáctico; es decir, puede efectuarse el análisis semántico cada vez que el analizador sintáctico reconoce una estructura sintáctica, o sea, una producción. De esta manera; las acciones del análisis semántico relacionadas con las producciones se incorporan al proceso de análisis sintáctico. Estas acciones semánticas generan código intermedio cada vez que se ejecutan. Así, la estructura sintáctica del código fuente dirige la traducción a código objeto o código intermedio, por lo cual hablamos de traducción dirigida por la sintaxis, casi todos los compiladores modernos son dirigidos por la sintaxis.

> Acciones semánticas

> Las acciones semánticas se asocian con las producciones de una gramática independiente del contexto, las cuales pueden considerarse como un fragmento de código que se ejecutará cuando el analizador sintáctico reconozca la producción apropiada.

> Por ejemplo, consideremos la producción de la gramática

> Go:

> TÉRMINO TÉRMINO * FACTOR (* A *)

> y supongamos que A es la acción semántica asociada, entonces, si se trata de un analizador sin táctico ascendente: se ejecutará A al reducir TÉRMINO * FACTOR a TÉRMINO; el analizador sintáctico descendente: se ejecutará A al expandir TÉRMINO o FACTOR.

> Comprobación de tipos

> La comprobación de tipos es una forma de asegurar que los identificadores relacionados sean de tipos compatibles. Dos identificadores se relacionan al formar el lado izquierdo y el derecho de un operador;
> al formar el lado izquierdo y el derecho de una proposición de asignación;
> al ser parámetros reales y formales.

> Las comprobaciones de consistencia que se efectúan antes de la ejecución del programa fuente (es decir, las que lleva a cabo el compilador) se denominan comprobaciones estáticas, mientras que aquellas realizadas durante la ejecución del programa objeto se llaman comprobaciones dinámicas o comprobaciones durante la ejecución. La revisión de la sintaxis es un ejemplo de comprobación estática, mientras que la comprobación de tipos es un ejemplo de comprobación que con frecuencia puede efectuarse en forma estática y que en ocasiones debe realizarse dinámicamente.

> Por ejemplo, consideremos la siguiente declaración:

> str: ARRAY [O. .80] OF CHAR;

> i : INTEGER;

> En general, no puede garantizarse estáticamente que se cumpla la condición 0 .. 80 al usar str[i]; es decir, esta comprobación debe efectuarse en forma dinámica.

> Sin embargo, es posible, por ejemplo, comprobar estáticamente si la asignación str[i] := ch; está permitida, o sea, si ambos lados de la proposición de asignación son de tipos compatibles. Para ello es necesario consultar la tabla de símbolos.

> A continuación se presenta un breve ejemplo de cómo introducir las reglas que permiten la comprobación de tipos de expresiones aritméticas. TipoE, TipoT y TipoF, las cuales representan el tipo de una expresión, término, etc.; en donde se emplean subíndices para distinguir entre varias ocurrencias de un mismo símbolo no terminal.

> Se usará el siguiente subconjunto de la gramática Go con las reglas correspondientes (suponiendo la semántica de PLlO):

> El procedimiento buscar_Tipo(...) se usa para determinar el tipo de un identificador por medio de la revisión de la tabla de símbolos. Por ejemplo, el tipo de una expresión formada por aplicar el operador "+" a una subexpresión y un término es entero si el tipo de la subexpresión y el término es entero; en caso contrario será un error de tipo. Ahora bien, la formulación de reglas para semánticas (tipo PASCAL) que establecen, por ejemplo, qué entero genera un resultado de tipo real, es obvia y puede verse cómo se propagará un tipo. Así, durante el proceso de análisis semántico, se puede determinar dónde se requieren cambios forzados de tipo (coerción) y qué operadores deben seleccionarse (por ejemplo, multiplicación entera o de punto flotante).

> Debemos señalar que no todos los lenguajes de programación permiten una comprobación estática de tipos como la que acabamos de exponer. En el lenguaje de programación APL, por ejemplo, el valor actual de una variable determina el tipo de la variable. Esto significa que el tipo de una variable puede cambiar durante la ejecución del programa y, por lo tanto, debe comprobarse durante la ejecución.

> Atrás Siguiente

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

##### Inicio

##### Créditos

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