• Author / Uploaded
• Edgardo Jesus Ruiz Garcia

Citation preview

Procesadores de Lenguajes Ingeniería Técnica superior de Ingeniería Informática Departamento de Lenguajes y Sistemas informáticos

Análisis semántico II Comprobación de tipos

Javier Vélez Reyes [email protected] Departamento de Lenguajes Y Sistemas Informáticos UNED

Análisis semántico. Comprobación de tipos Objetivos

Objetivos › Aprender qué es la comprobación de tipos › Entender qué es un sistema de tipos › Conocer los elementos constituyentes de un sistema de tipos › Conocer qué es una expresión de tipos › Aprender a escribir expresiones de tipos › Aprender las diferencias entre comprobación estática y dinámica › Entender qué es la equivalencia de tipos › Aprender las diferencias entre los distintos tipos de equivalencia de tipos › Entender qué es y como funciona la conversión de tipos › Entender qué es la sobrecarga y qué tipos de sobrecarga existen › Aprender a implementar un comprobador de tipos › Conocer las principales estructuras de datos y artefactos necesarios

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Índice

Índice › Introducción

› Apertura de ámbito inicial

› Símbolos

› Declaración de constantes

› Tipos

› Declaración de tipos

› Ámbitos de declaración

› Declaración de variables

› El sistema de tipos

› Declaración de subprogramas

› ¿Qué es el sistema de tipos?

› Expresiones

› Tipos primitivos

› Sentencias

› Constructores de tipos

› Cierre de ámbitos

› Equivalencia de tipos

› Temas avanzados de un comprobador de tipos

› Verificación de tipos sobre operadores

› Inferencia de tipos

› Verificación de tipos sobre subprogramas

› Sobrecarga de subprogramas

› Construcción de un comprobador de tipos

› Recuperación de errores semánticos

› Qué es un comprobador de tipos

› Desarrollo paso a paso

› Artefactos de un comprobador de tipos

› Bibliografía Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Introducción

Análisis semántico La fase de análisis semántico tiene por objetivo analizar los componentes del árbol de análisis sintáctico que representan el programa con el fin de comprobar que se respetan ciertas reglas semánticas que dan un significado coherente a las construcciones del lenguaje SWhile Las responsabilidades son… WHILE

E E

DO

>

S

› Registrar declaraciones › Inferir tipos

E

› Comprobar tipos

Foco de atención

› Comprobar corrección semántica

El analizador semántico va comprobando la coherencia semántica del árbol de análisis sintáctico según se va construyendo

Analizador semántico SWhile

WHILE E





E

DO

>

E

S

 Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Introducción

Conceptos esenciales Los lenguajes modernos se articulan a partir de una estructura de bloques donde se pueden hacer declaraciones que luego serán referenciadas a lo largo del programa

Símbolos El ejercicio de creación de un programa consiste en la declaración de una colección de símbolos con nombres que representan entidades semánticas utilizadas a lo largo del código Un símbolo de un programa es cualquier elemento con nombre que el programador haya establecido como válido dentro de él a través de una declaración El tipo de símbolos que pueden declararse en un programa es una característica propia del lenguaje. No obstante puede identificarse ciertos tipos de símbolos recurrentes tales como constantes, variables, funciones, procedimientos o parámetros

Algunos lenguajes permiten elidir la declaración de los símbolos y utilizan reglas de inferencia para determinar los símbolos que son utilizados a lo largo del programa

CONST MAX = 10; TYPE TVector = ARRAY [1..10] OF REAL; VAR v, w : TVector; i : INTEGER; PROCEDURE Leer (VAR m: TVector); VAR i : INTEGER; FUNCTION Validar (VAR v: INTEGER): INTEGER; BEGIN Validar := v mod 10; END; BEGIN FOR i := 1 TO 10 DO m [i] := Validar (Read (i)); END; END; FUNCTION suma (m, n: TVector) : TVector; VAR i : INTEGER; vSuma : TVector; BEGIN WHILE (i < MAX) DO vSuma [i] := m[i] + n[i]; INC (i); END; suma := vSuma; END; BEGIN Leer (v); Leer (w); v := suma (v, w); END.

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Introducción

Conceptos esenciales Los lenguajes modernos se articulan a partir de una estructura de bloques donde se pueden hacer declaraciones que luego serán referenciadas a lo largo del programa

Tipos Cada símbolo del lenguaje lleva asociado un tipo. El tipo de un símbolo se utiliza para proporcionar información al compilador de cómo debe tratar semánticamente al mismo y qué operaciones debe permitir realizar sobre él Un tipo es un descriptor semántico que permite cualificar al símbolo al que está vinculado de manera que condiciona su interpretación semántica y restringe las operaciones que se pueden realizar sobre él Todo lenguaje dispone de una colección de tipos primitivos y también de ciertos mecanismos semánticos para construir nuevos tipos a partir de otros previamente definidos

En aquellos lenguajes donde la tipificación no es explícita los símbolos adquieren un tipo tan pronto como sea posible aplicando reglas de inferencia de tipos

CONST MAX = 10; TYPE TVector = ARRAY [1..10] OF REAL; VAR v, w : TVector; i : INTEGER; PROCEDURE Leer (VAR m: TVector); VAR i : INTEGER; FUNCTION Validar (VAR v: INTEGER): INTEGER; BEGIN Validar := v mod 10; END; BEGIN FOR i := 1 TO 10 DO m [i] := Validar (Read (i)); END; END; FUNCTION suma (m, n: TVector) : TVector; VAR i : INTEGER; vSuma : TVector; BEGIN WHILE (i < MAX) DO vSuma [i] := m[i] + n[i]; INC (i); END; suma := vSuma; END; BEGIN Leer (v); Leer (w); v := suma (v, w); END.

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Introducción

Conceptos esenciales Los lenguajes modernos se articulan a partir de una estructura de bloques donde se pueden hacer declaraciones que luego serán referenciadas a lo largo del programa

Ámbitos de declaración y alcance de visibilidad Cada símbolo se declara dentro de un bloque acotado por ciertas construcciones sintácticas. Se entiende que dentro de dicho bloque la declaración tiene vigencia y puede ser utilizada mientras que fuera no existe y pueden declararse otros símbolos incluso aunque compartan el mismo nombre Un ámbito es un bloque acotado sintácticamente dentro del cual los símbolos allí declarados tienen vigencia En lenguajes estilo Pascal las construcciones sintácticas que representan creaciones de nuevos ámbitos, a parte del global, son únicamente la declaración de funciones y procedimientos

En lenguajes estilo C, además de las funciones y el ámbito global, cualquier bloque de sentencias acotado entre llaves constituye un ámbito de declaración nuevo

CONST MAX = 10; TYPE TVector = ARRAY [1..10] OF REAL; VAR v, w : TVector; i : INTEGER; PROCEDURE Leer (VAR m: TVector); VAR i : INTEGER; FUNCTION Validar (VAR v: INTEGER): INTEGER; BEGIN Validar := v mod 10; END; BEGIN FOR i := 1 TO 10 DO m [i] := Validar (Read (i)); END; END; FUNCTION suma (m, n: TVector) : TVector; VAR i : INTEGER; vSuma : TVector; BEGIN WHILE (i < MAX) DO vSuma [i] := m[i] + n[i]; INC (i); END; suma := vSuma; END; BEGIN Leer (v); Leer (w); v := suma (v, w); END.

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Introducción

Conceptos esenciales Los lenguajes de programación articulan la definición de programas a través de la declaración de símbolos convenientemente tipificados que luego son referenciados a lo largo del código

Anidamiento de ámbitos

ámbito nivel 1

Cuando dos ámbitos se encuentran sintácticamente anidados uno dentro de otro, desde el más interno tienen visibilidad todas las declaraciones de símbolos realizadas en el ámbito más externo. Si dentro del ámbito interno se declara un nuevo símbolo con el mismo nombre que un símbolo en el ámbito externo, la declaración que pasa a tener vigencia es la realizada dentro del ámbito interno. Esto es cierto para cualquier nivel de anidamiento

ámbito nivel 1

Regla de anidamiento más cercano Dadas varias declaraciones diferentes para el mismo nombre en distintos ámbitos anidados, la declaración que ámbito nivel 0

se aplica a una referencia es aquélla que se encuentre en el bloque anidado más próximo a la misma

PROCEDURE Leer (VAR m: TVector); VAR i : INTEGER; FUNCTION Validar (VAR v: INTEGER): INTEGER; BEGIN Validar := v mod 10; END; BEGIN FOR i := 1 TO 10 DO m [i] := Validar (Read (i)); END; END; FUNCTION suma (m, n: TVector) : TVector; VAR i : INTEGER; vSuma : TVector; BEGIN WHILE (i < MAX) DO vSuma [i] := m[i] + n[i]; INC (i); END; suma := vSuma; END;

ámbito nivel 2

CONST MAX = 10; TYPE TVector = ARRAY [1..10] OF REAL; VAR v, w : TVector; i : INTEGER;

BEGIN Leer (v); Leer (w); v := suma (v, w); END.

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Introducción

¿Qué es la comprobación de tipos? La labor de comprobación de tipos consiste en conferir a las construcciones sintácticas del lenguaje la semántica de tipificación que acabamos de describir y en realizar todo tipo de comprobaciones de dicha índole. Por su naturaleza, sin embargo, ésta se encuentra repartida entre la fase de análisis semántico y la generación de código intermedio S

Tipos de comprobaciones semánticas 

I. Comprobaciones estáticas

WHILE

DO

S

E > E

Tema 7

Las comprobaciones estáticas recogen el compendio de todas aquellas tareas de carácter semántico que, por su naturaleza, pueden ser realizadas directamente durante la fase de compilación mediante el uso de los artefactos y mecanismos propios de dicha fase. Este tipo de comprobaciones son beneficiosas puesto que confieren seguridad a la ejecución del programa



II. Comprobaciones dinámicas

E

Tema 8-9

Las comprobaciones dinámicas son aquellas que no se realizan durante la fase de compilación y se delegan al momento de la ejecución del programa. Ello requiere generar código ejecutable específicamente diseñado para realizar tales comprobaciones. Los lenguajes con una carga excesiva de comprobaciones dinámicas generan programas más largos, lentos e inseguros en ejecución

Análisis semántico

√

S

WHILE

E

DO

S

E > E

Generación código intermedio LD a t1 LD b t2 GRT t3 t1 t2 BRZ t3 L1 …

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Introducción

¿Qué es la comprobación de tipos? La labor de comprobación de tipos consiste en conferir a las construcciones sintácticas del lenguaje la semántica de tipificación que acabamos de describir y en realizar todo tipo de comprobaciones de dicha índole. Por su naturaleza, sin embargo, ésta se encuentra repartida entre la fase de análisis semántico y la generación de código intermedio

Tipos de comprobaciones semánticas estáticas I. Gestión de declaraciones Se encarga de registrar todas las declaraciones realizadas por el programador a lo largo de los distintos ámbitos. Esta tarea implica el registro de tipos y la comprobación de que no se produce ninguna colisión de nombres con los identificadores de otras declaraciones

CONST MAX = 10; TYPE TVector = ARRAY [1..10] OF REAL; VAR v, w : TVector; i : INTEGER; PROCEDURE Leer (VAR m: TVector);

II. Verificación de tipos Comprueba la compatibilidad de tipos de todas las expresiones del código fuente recuperando la información durante la gestión de declaraciones. Además se asegura de que no existe en el programa ninguna referencia a ningún símbolo no declarado

Validar := v mod 10; WHILE (i < MAX) DO ... v := suma (v, w);

III. Inferencia de tipos En lenguajes sin tipificación de variables o con sobrecarga se aplican tareas de inferencia de tipos en el nivel gramatical de las expresiones para resolver el tipo de datos de la expresión resultante en función del contexto de evaluación

CONST MAX = 10;

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

¿Qué es el sistema de tipos? El documento que recoge toda la información relativa a la tipificación de un lenguaje de programación, desde sus tipos primitivos, hasta sus tipos estructurados pasando por sus reglas de combinación operacional, recibe el nombre de sistema de tipos El sistema de tipos de un lenguaje es una especificación de alto nivel que describe de forma precisa el conjunto de reglas y restricciones semánticas de tipificación que se aplican sobre las construcciones sintácticas del lenguaje

Niveles de tipificación El sistema de tipos de un lenguaje condiciona, de manera directa, la seguridad de los programas en tiempo de ejecución. En efecto, cuantas más comprobaciones se hagan en tiempo de compilación, menor será la probabilidad de fallo en ejecución. El nivel de construcción del sistema de tipos permite clasificar a los lenguajes en 2 categorías Lenguajes fuertemente tipificados

Niveles de tipificación

La tipificación fuerte implica un nivel de construcción elevado y es propia de lenguajes de programación seguros como Pascal, Ada o Modula

Lenguajes débilmente tipificados La tipificación débil implica pocas restricciones en el sistema de tipos y delega la mayor parte de la comprobación al tiempo de ejecución. Es propia de lenguajes de scripting como Groovy o Javascript

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

¿Qué es el sistema de tipos? El documento que recoge toda la información relativa a la tipificación de un lenguaje de programación, desde sus tipos primitivos, hasta sus tipos estructurados pasando por sus reglas de combinación operacional, recibe el nombre de sistema de tipos El sistema de tipos de un lenguaje es una especificación de alto nivel que describe de forma precisa el conjunto de reglas y restricciones semánticas de tipificación que se aplican sobre las construcciones sintácticas del lenguaje

Expresiones de tipos Para definir el sistema de tipos de un lenguaje de manera formal, sistemática e independientemente de las sintaxis propia del mismo se utilizan expresiones de tipos. Cada tipo primitivo tiene una expresión de tipo asociada. Cada constructor de tipo tiene también una expresión de tipo. Cada tipo definido mediante la composición de constructores de tipos y tipos primitivos tiene a su vez una expresión de tipos Una expresión de tipos es un mecanismo formal utilizado por los sistemas de tipos para representar el tipo de una construcción sintáctica propia del lenguaje

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Tipos primitivos Los tipos primitivos de un lenguaje determinan la colección de tipos de datos originales que el lenguaje pone a disposición del programador para componer estructuras de datos más complejas. La variedad de tipos primitivas es una característica propia del lenguaje pero en general se distinguen cuatro categorías: ordinales, reales, lógicos y de carácter Tipo

Descripción

Rango

Expresión de tipos

Operaciones

Representación numérica corta sin signo 0 a 255

ENTERO

+ – * / mod = > <

Representación numérica con signo

ENTERO

+ – * / mod = > <

Representación numérica larga sin signo 0 a 65535

ENTERO

+ – * / mod = > <

Real

Representación flotante corta con signo

2.9E-39 a 1.7E38

REAL

+ – * / = > <

Double

Representación flotante larga con signo

5.0E-324 a 1.7E308

REAL

+ – * / = > <

Representación lógica

False, True

LOGICO

AND OR XOR NOT

Char

Representación de carácter

ASCII

CARÁCTER

-

String

Representación de cadena

-

CADENA

-

Byte Integer Word

Boolean

-32768 a 32767

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Constructores de tipos Los constructores de tipos son mecanismos sintácticos del lenguaje que permiten combinar otras construcciones de tipos, primitivos o compuestos, para generar estructuras más complejas. Los tipos así generados se llaman tipos complejos, tipos compuestos o tipos definidos por el usuario Ejemplo

Descripción

Expresión de tipos

TVector = ARRAY [1..10] OF INTEGER

Representa una formación lineal de elementos de un mismo tipo de base

ARRAY (1..10, ENTERO)

TPunto = RECORD BEGIN X: INTEGER; Y: INTEGER END;

Representa una estructura de datos constituida por una colección de campos con nombre de distinto tipo

RECORD ( (X x ENTERO) x (Y x ENTERO) )

^ TPunto

Representa un puntero a un área de memoria reservada para almacenar datos de un determinado tipo de base

POINTER (TPunto)

TConjunto = SET OF INTEGER

Representa un conjunto no ordenado de elemento de un mismo tipos de datos de base

SET (ENTERO)

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Constructores de tipos Los constructores de tipos son mecanismos sintácticos del lenguaje que permiten combinar otras construcciones de tipos, primitivos o compuestos, para generar estructuras más complejas. Los tipos así generados se llaman tipos complejos, tipos compuestos o tipos definidos por el usuario Ejemplo

Descripción

Expresión de tipos

TPalos = (OROS, COPAS, ESPADAS, BASTOS);

Representa una colección de etiquetas que se comportan como constantes simbólicas de valor numérico

ENUM (OROS, COPAS, ESPADAS, BASTOS)

(INTEGER; INTEGER)

Representa una tupla de datos constituida por una colección ordenada de datos de distinto tipo

(ENTERO) x (ENTERO)

FUNCTION suma (m, n: TVector): Tvector;

Representa una declaración de función con parámetros y tipo de retorno definido

(Tvector x TVector)  TVector

PROCEDURE Leer ( n: TVector);

Representa una declaración de procedimiento con parámetros definidos

(Tvector)  TVector

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Constructores de tipos Los constructores de tipos son mecanismos sintácticos del lenguaje que permiten combinar otras construcciones de tipos, primitivos o compuestos, para generar estructuras más complejas. Los tipos así generados se llaman tipos complejos, tipos compuestos o tipos definidos por el usuario

Ejercicios Una vez que se conoce la expresión de tipos de los principales tipos del lenguaje y de los constructores de tipos pueden construirse las expresiones de tipos para diferentes tipos definidos por el usuario TLista = RECORD BEGIN vector: ARRAY [1..10] OF INTEGER; longitud: INTEGER; END; TTabla = ARRAY [1..100] OF ^TLista;

TPEntero = ^ INTEGER; TMatriz = ARRAY [1..3][1..6]; TPersona = RECORD BEGIN nombre: STRING; edad : INTEGER; END; FUNCTION mayor (a, b: INTEGER): INTEGER; FUNCTION ordenar (p: TPEntero) : TPEntero;

TCjtoTablas = SET OF ^TTabla;

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Equivalencia de tipos De cara a realizar comprobaciones estáticas, resulta interesante definir la equivalencia entre dos tipos complejos del lenguaje. Esta definición puede formularse en términos del nombre que reciben sendos tipos dentro del código o entre las expresiones de tipos subyacentes. Esto permite distinguir entre dos formas de entender la equivalencia lo cual es una característica intrínseca del lenguaje

I. Equivalencia nominal TYPE T1 = ARRAY [1..10] OF INTEGER; T2 = ARRAY [1..10] OF INTEGER; T3 = T1

Se dice que dos tipos de datos T1 y T2 son nominalmente equivalentes si responden a una misma entrada dentro del registro de

T1

tipos realizado por el compilador durante la gestión de declaraciones

T2

T3

No equivalente Equivalente

T1

Equivalente

T2

No equivalente Equivalente

T3

Equivalente

No equivalente

No Equivalente Equivalente

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Equivalencia de tipos De cara a realizar comprobaciones estáticas, resulta interesante definir la equivalencia entre dos tipos complejos del lenguaje. Esta definición puede formularse en términos del nombre que reciben sendos tipos dentro del código o entre las expresiones de tipos subyacentes. Esto permite distinguir entre dos formas de entender la equivalencia lo cual es una característica intrínseca del lenguaje

II. Equivalencia estructural TYPE T1 = ARRAY [1..10] OF INTEGER; T2 = ARRAY [1..10] OF INTEGER; T3 = T1

Se dice que dos tipos de datos son estructuralmente equivalentes si son el mismo tipo básico o están formadas mediante

la

aplicación

del

T1

mismo

T2

T3

constructor de tipos sobre expresiones de

T1

Equivalente

Equivalente

Equivalente

tipos estructuralmente equivalentes

T2

Equivalente

Equivalente

Equivalente

T3

Equivalente

Equivalente

Equivalente

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Equivalencia de tipos De cara a realizar comprobaciones estáticas, resulta interesante definir la equivalencia entre dos tipos complejos del lenguaje. Esta definición puede formularse en términos del nombre que reciben sendos tipos dentro del código o entre las expresiones de tipos subyacentes. Esto permite distinguir entre dos formas de entender la equivalencia lo cual es una característica intrínseca del lenguaje

II. Equivalencia estructural boolean equivale (TypeIF s, TypeIF t) {

Se dice que dos tipos de datos son

if (s == t) return true;

estructuralmente equivalentes si son el

if ((s == ARRAY (s1, s2) && t == ARRAY (t1,t2)) || (s == (s1 x s2) && t == (t1 x t2)) ||

mismo tipo básico o están formadas mediante

la

aplicación

del

(s == (s1  s2) && t == (t1  t2)))

mismo

return equivale (s1,t1) && equivale (t2, t2);

constructor de tipos sobre expresiones de

if ((s == Pointer (s1) && t == Pointer (t1)) || (s == Set (s1) && t == Set (t1))

tipos estructuralmente equivalentes

return equivale (s1,t1);

Ojo con las definiciones de tipos recursivos



return false }

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Verificación de tipos sobre operadores La mayoría de operadores de un lenguaje de programación pueden operarse satisfactoriamente sobre un subconjunto de tipos primitivos del lenguaje. Esto desencadena una serie de conceptos tan interrelacionados entre si que conviene abordarlos conjuntamente

I. Sobrecarga de operadores

Se

dice

que

un

operador

está

sobrecargado cuando se puede utilizar para operar sobre un subconjunto de tipos de datos primitivos del lenguaje

Pascal

Fortran

2 + 3

2 + 3

4.2 + 3.8

4.2 +. 3.8



La capacidad de poder utilizar un mismo operador para articular diferentes operaciones en función de los tipos de datos involucrados se llama sobrecarga de operadores. Es frecuente sobrecargar los operadores aritméticos y relacionales de un lenguaje

En estos ejemplos en Pascal puede verse como el sistema de tipos del lenguaje, define el operador suma de forma sobrecargada ya que puede ser evaluado en el contexto de 2 subexpresiones de tipo entero o tipo flotante, entre otros. Otros lenguajes, como Fortran utilizan por el contrario operadores diferentes

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Verificación de tipos sobre operadores La mayoría de operadores de un lenguaje de programación pueden operarse satisfactoriamente sobre un subconjunto de tipos primitivos del lenguaje. Esto desencadena una serie de conceptos tan interrelacionados entre si que conviene abordarlos conjuntamente

II. Compatibilidad de tipos

Se dice que dos tipos son compatibles entre si, con respecto a un operador, si son equivalentes

o

satisfactoriamente

si

se a

pueden

través

de

operar dicho

Pascal

C

2 + 3.5

‘a’ + 3.5

4.2 * 3

4.2 * 3



La capacidad de sobrecarga de los operadores de un lenguaje, introduce el concepto de compatibilidad de tipos, que se aplica cuando dichos tipos pueden ser satisfactoriamente operados a través de un operador sobrecargado

En los ejemplos en Pascal puede verse como los operadores sobrecargados suma (+) y producto (*) definen los tipos entero y real como compatibles entre sí, mientras que en C resultan compatibles el tipo carácter, entero y flotante con respecto a los mismos operadores

operador

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Verificación de tipos sobre operadores La mayoría de operadores de un lenguaje de programación pueden operarse satisfactoriamente sobre un subconjunto de tipos primitivos del lenguaje. Esto desencadena una serie de conceptos tan interrelacionados entre si que conviene abordarlos conjuntamente

III. Coerción de tipos

La coerción de tipos es el proceso mediante el cual el sistema de tipos convierte la subexpresión menos restrictiva hacia la más restrictiva cuando ambas son de distinto tipo

Pascal

C

2 + 3.5

‘a’ + 3.5

4.2 * 3

(int) 4.2 * 3



La compatibilidad de tipos permite operar expresiones de tipos diferentes pero comúnmente fuerza conversiones de tipo hacia el tipo más restrictivo. Este efecto recibe el nombre de conversión o coerción de tipos

En los ejemplos de Pascal ambas operaciones operan entre reales y por tanto los operandos enteros se convierten a real. Igual ocurre con la primera expresión en C que convierte el carácter ‘a’ a entero y de ahí a flotante para poder operarse. Estas conversiones se llaman implícitas. Sin embargo la ultima fuerza a convertir el flotante a entero con perdida de información. Esta conversión es explícita

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Verificación de tipos sobre operadores La mayoría de operadores de un lenguaje de programación pueden operarse satisfactoriamente sobre un subconjunto de tipos primitivos del lenguaje. Esto desencadena una serie de conceptos tan interrelacionados entre si que conviene abordarlos conjuntamente operador

+

Byte

Integer

Word

Real

Double Boolean Char String …

Byte

Byte

Integer

Word

Real

Double

Error

Error

Error

Integer Integer

Word

Real

Double

Error

Error

Error

Integer

tipos

Word

Word

Word

Word

Real

Double

Error

Error

Error

Real

Real

Real

Real

Real

Double

Error

Error

Error

Double Double Double

Error

Error

Error

Double

Constructores de tipos

Double Double

Boolean

Error

Error

Error

Error

Error

Error

Error

Error

Char

Error

Error

Error

Error

Error

Error

Error

Error

String

Error

Error

Error

Error

Error

Error

Error

Error

Coerción o error

... Matriz de compatibilidad para el operador +

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Sistemas de tipos

Elementos de un sistema de tipos La descripción del sistema de tipos de un lenguaje de programación se articula, fundamentalmente, mediante la definición de los tipos primitivos y constructores compuestos, sus reglas de composición, las operaciones permitidas sobre cada uno de ellos y el tipo de resultado que provocan

Verificación de tipos sobre subprogramas La sobrecarga es un término que puede ser igualmente aplicado sobre los procedimientos y funciones declarados en un programa. Esto permite soportar diferentes implementaciones de un mismo subprograma con igual identificador pero diferente, número, tipo u orden de parámetros formales en su declaración. La implementación invocada dependerá de los tipos aplicados en la expresión de llamada La sobrecarga de subprogramas es la capacidad de un lenguaje de permitir la declaración de varios procedimientos o funciones con el mismo nombre pero distinto, número, tipo u orden de parámetros formales

TYPE TVector = ARRAY [1..10] OF INTEGER TMatriz = ARRAY [1..10][1..5] OF INTEGER VAR v, w: Tvector; m, n : TMatriz; PROCEDURE sumar (m, n: TMatriz; VAR r:TMatriz); ...



PROCEDURE sumar (v, w: TVector; VAR r:TVector); ...

El procedimiento de suma está sobrecargado. La sobrecarga de subprogramas es más propia de lenguajes orientados a objetos que de lenguajes estructurados. En ese contexto se llama polimorfismo

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

¿Qué es un comprobador de tipos? Una vez descritas las responsabilidades y características de un sistema de tipos, es preciso implementarlo en la practica a través de los mecanismos proporcionados por los esquemas de traducción dirigidos por la sintaxis. A la parte de un compilador que implementa el sistema de tipos se le llama comprobador de tipos Un comprobador de tipos es la parte del compilador que se encarga de implementar el sistema de tipos del lenguaje a través de mecanismos de traducción dirigida por la sintaxis

Ejemplo expresion ::= expresion:e1 MAS expresion:e2 t2 =



{: t1 =

No: si:

En el caso de las expresiones es necesario recuperar el tipo de cada subexpresión y comprobar su compatibilidad con respecto al operador que las combina. Si no son compatibles se emite un mensaje de error semántico

:}

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte ScopeManager

SymbolTable

Scope

TypeTable

SymbolIF

TypeIF

SemanticErrorManager SymbolBase

SymbolBase

SymbolConstant

SymbolProcedure

TypePointer

SymbolVariable

SymbolFunction

TypeSimple

TypeArray

SymbolParameter

TypeRecord

TypeEnum

TypeUnion

TypeSet

TypeProcedure

TypeFunction

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Tipos primitivos y constructores de tipos Las clases que implementan el interfaz TypeIF representan los tipos primitivos del lenguaje y cada uno de los constructores de tipos del mismo. El primer paso es determinar los atributos y métodos necesarios para caracterizarlos (entendemos que los nombres de cada clase son autoexplicativos) TypeBase -String name -ScopeIF scope + String getName () + void setName (String name) + ScopeIF getScope () + void setScope (ScopeIF scope) + int getSize() + boolean equals () + hashcode () + toString ()

Propiedad name y scope Todos los tipos contienen un nombre y un ámbito de declaración por tanto pueden factorizarse en la clase abstracta TypeBase e implementar sendos métodos de consulta y modificación

Equivalencia de tipos Para mantener limpio el código del esquema de traducción en Cup se recomienda implementar la equivalencia de tipos – nominal o estructural – en este método

Sobrescritura de métodos de Object Igualmente se recomienda la implementación de los métodos hashcode y toString heredados de clase Object. Consulte tema 6 para obtener detalles

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Tipos primitivos y constructores de tipos Las clases que implementan el interfaz TypeIF representan los tipos primitivos del lenguaje y cada uno de los constructores de tipos del mismo. El primer paso es determinar los atributos y métodos necesarios para caracterizarlos (entendemos que los nombres de cada clase son autoexplicativos) TypeSet

TypeRecord

TypeEnum

TypeProcedure

TypePointer

-String name

-String name

-String name

-String name

-String name

-ScopeIF scope

-Map fields

-List values

-List parameters

-TypeIF base

-TypeIF base

-ScopeIF scope

-ScopeIF scope

-ScopeIF scope

-ScopeIF scope

TypeArray

TypeSimple

TypeUnion

TypeFunction

-String name

-String name

-String name

-TypeIF rType

-ScopeIF scope

-ScopeIF scope

-Map baseFields

-ScopeIF scope

-int min

-int size

-Map variants

-int max

-ScopeIF scope

-TypeIF base

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Símbolos Las clases que implementan la interfaz SymbolIF representan símbolos que han sido declarados por el usuario programador dentro del lenguaje. Para cada tipo de símbolo también conviene identificar los atributos propios que lo caracterizan de manera preliminar SymbolBase -String name -TypeIF type -ScopeIF scope + String getName () + void setName (String name) + ScopeIF getScope () + void setScope (ScopeIF scope) + TypeIF getType () + void setType (TypeIF type) + boolean equals () + hashcode ()

Propiedad name y scope Todos los símbolos contienen un nombre y un ámbito de declaración por tanto pueden factorizarse en la clase abstracta SymbolBase e implementar sendos métodos de consulta y modificación

Propiedad Tipo De forma similar, todos los símbolos declarados tienen un tipo, ya sea declarado explícitamente o inferido luego el tipo es otra propiedad que puede factorizarse en esta clase

Sobrescritura de métodos de Object Igualmente se recomienda la implementación de los métodos hashcode y toString heredados de clase Object. Consulte tema 6 para obtener detalles

+ toString ()

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Símbolos Las clases que implementan la interfaz SymbolIF representan símbolos que han sido declarados por el usuario programador dentro del lenguaje. Para cada tipo de símbolo también conviene identificar los atributos propios que lo caracterizan de manera preliminar SymbolConstant

SymbolVariable

SymbolProcedure

SymbolParameter

-String name

-String name

-String name

-String name

-TypeIF type

-TypeIF type

-TypeIF type

-TypeIF type

-Number value

-ScopeIF scope

-ScopeIF scope

-ScopeIF scope

-ScopeIF scope

-Integer Address SymbolFunction -String name



-TypeIF Type -ScopeIF scope

Al igual que en el caso de los tipos, estas definiciones serán potencialmente extendidas cuando avancemos en la construcción del compilador

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Gestor de errores semánticos y trazabilidad Cuando se detecta un error semántico durante el proceso de compilación, el comprobador de tipos debe emitir un mensaje de error. El gestor de errores proporciona métodos para informar de errores recuperables y no recuperables así como para trazar la ejecución del comprobador semántico exp ::= exp:e1 MAS exp:e2 {:

SemanticErrorManager

TypeIF t1 =

+ void semantiDebug (String message)

TypeIF t2 =

+ void semanticInfo (String message)

semanticErrorManager.semanticDebug (“Tipo de e1:” + t1);

+ void semanticWarn (String message)

semanticErrorManager.semanticDebug (“Tipo de e2:” + t2);

+ void semanticError (String message)

if (t1.isCompatible (t2, TypeIF.MAS)) {

+ void semanticFatal (String message)

... } else semanticErrorManager.semanticFatalError (“tipos incompatibles”); :}

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Tablas de tipos Una tabla de tipos es una estructura de datos de tabla hash donde se registran todas las declaraciones de tipos realizadas por el usuario programador en un determinado ámbito TypeTable (continúa)

TypeTable Private ScopeIF scope;

public void addType (String id, TypeIF type){

private Map tTable;

type.setScope (this.scope); tTable.put (id, type);

public TypeTable (ScopeIF scope) { this.scope = scope;

} public boolean containsType (String id) {

tTable = new HashMap ();

return tTable.containsKey (id);

}

}

public TypeIF getType (String id) {

public boolean containsType (TypeIF type) {

return tTable.get (id);

String id = type.getName ();

}

return containsType (id);

public void addType (TypeIF type) { String id = type.getName ();

} ...

addType (id, type); }

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Tablas de símbolos Una tabla de símbolos es una estructura de datos de tabla hash donde se registran todas las declaraciones (no tipos) realizadas por el usuario programador en un determinado ámbito SymbolTable(continúa)

SymbolTable Private ScopeIF scope;

public void addSymbol (String id, SymbolIF symbol){ symbol.setScope (this.scope);

private Map sTable;

sTable.put (id, symbol); public SymbolTable() { sTable = new HashMap ();

} public boolean containsSymbol (String id) { return sTable.containsKey (id);

} public SymbolIF getSymbol (String id) { return sTable.get (id);

} public boolean containsSymbol (SymbolIF symbol) {

}

String id = symbol.getName ();

public void addSymbol (SymbolIF symbol) {

return containsSymbol (id);

String id = symbol.getName ();

}

addSymbol (id, symbol);

...

}

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Artefactos de un comprobador de tipos

Consúltese el documento directrices de implementación

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Ámbitos de declaración El ámbito es un artefacto que representa un ámbito de declaración dentro de un programa. Estructuralmente es un contenedor que mantiene una referencia a la tabla de símbolos y la tabla de tipos asociada con dicho ámbito Scope

Nombre del ámbito En bloques con nombre, como procedimientos y funciones, contiene el nombre del bloque

-String name -int id -int level -symbolTable -typeTable

Tabla de símbolos y tipos Cada ámbito contiene una referencia a una tabla de símbolos y otra de tipos inicialmente vacía asignadas por construcción

+ String getName () + int getId () + int getLevel () + SymbolTableIF getSymbolTable () + TypeTableIF getTypeTable ()

Identificador de ámbito Cada ámbito dispone de un identificador único asignado, correlativamente, por construcción

Nivel de anidamiento del ámbito El nivel de anidamiento indica el grado de profundidad en el que se encuentra el bloque sintáctico asociado al ámbito comenzando por 0 para el ámbito global

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Artefactos de un comprobador de tipos

Consúltese el documento directrices de implementación

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Gestor de ámbitos El gestor de ámbitos es un artefacto que mantiene una relación de todos los ámbitos creados durante el proceso de compilación. Este objeto es una única instancia en el compilador y sirve para gestionar la búsqueda de símbolos y tipos a través de los ámbitos activos Crea un nuevo ámbito, anónimo o con nombre. Aplicable cuando se entra en un bloque Recupera el último ámbito abierto o aquél en cierto nivel de profundidad de los actualmente abiertos Busca símbolos o tipos a lo largo de los ámbitos activos, comenzando por el más reciente y avanzando en la jerarquía de ámbitos padre

ScopeManager + void openScope () + void openScope (String name) + void closeScope () + ScopeIF getCurrentScope () + ScopeIF getScope (int level) + List getAllScopes () + SymbolIF searchSymbol () + TypeIF searchType () + boolean containsSymbol (String id) + boolean ContainsType (String id)

Cierra un ámbito. Aplicable cuando se abandona un bloque Recupera todos los ámbitos creados (abiertos o cerrados) durante el proceso de compilación. Útil en la generación de código final Indica si un símbolo o tipo se encuentra declarado dentro de algún ámbito activo

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Gestor de ámbitos La manera de gestionar los ámbitos activos es a través de una pila de ámbitos interna. Cada operación openScope crea un nuevo objeto Scope y lo apila sobre la pila. Cada operación closeScope, saca el ámbito de la cima de la pila

Ejemplo CONST MAX = 10; TYPE TVector = ARRAY [1..10] OF REAL; VAR v, w : TVector; i : INTEGER; ...



ScopeManager

... PROCEDURE Leer (VAR m: TVector); VAR i : INTEGER; ...



ScopeManager

FUNCTION Validar (VAR v: INTEGER): INTEGER; BEGIN Validar := v mod 10; END; ...



ScopeManager

Validar[2]

Global [0]

Leer[1]

Leer[1]

Global [0]

Global [0]

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica Consúltese el documento directrices de implementación

Artefactos de un comprobador de tipos

Antes de comenzar con la descripción de la implementación del comprobador de tipos para cada parte de la gramática de un lenguaje es necesario presentar la colección de artefactos que serán utilizados dentro de la misma. A continuación describimos aquellos que aparecen en el framework de soporte

Gestor de ámbitos La manera de gestionar los ámbitos activos es a través de una pila de ámbitos interna. Cada operación openScope crea un nuevo objeto Scope y lo apila sobre la pila. Cada operación closeScope, saca el ámbito de la cima de la pila

Ejemplo ... BEGIN FOR i := 1 TO 10 DO m [i] := Validar (Read (i)); END; END;



ScopeManager

... FUNCTION suma (m, n: TVector) : TVector; VAR i : INTEGER; vSuma : TVector; BEGIN ...



ScopeManager

Leer[1]

suma[1]

Global [0]

Global [0]



... BEGIN Leer (v); Leer (w); v := suma (v, w); END. ScopeManager

Global [0]

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Apertura del ámbito inicial

Declaración de constantes

program

::= cabecera cuerpo;

cabecera

::= PROGRAM ID:id PYC {:

dConstante ::= ID:id IGUAL rNumero:rn {: ScopeIF scope = scopeManager.getCurrentScope ();

String name = id.getLexema ();

SymbolTable sTable = scope.getSymbolTable ();

scopeManager.openScope (name);

String name = id.getLexema ();

// Insertar todos los TypeSimple en la TT

Object value = rn.getValue ();

:}; cuerpo

if (sTable.containsSymbol (name)) { ::= declaraciones bSentencias; {:

scopeManager.closeScope ();

:}

semanticErrorManager.semanticFatalError (...); } else {

declaraciones ::= bConstantes

TypeIF type;

bTipos

if (value instanceof Integer) type = TypeSimple.ENTERO;

bVariables

if (value instanceof Float)

dSubprogramas;

if (value instanceof Boolean) type = TypeSimple.LOGICO;

type = TypeSimple.REAL;

bConstantes

::= CONST dConstantes | ;

SymbolConstant sC = new SymbolConstant (name, value, type);

bTipos

::= TYPE dTipos

| ;

sTable.add (sC);

bVariables

::= VAR dVariables

| ;

dConstantes

::= dConstantes dConstante | dConstante;

:}; rNumero ::= NUM:n {: RESULT = new RNumero (n.getValue ()); :}

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Declaración de constantes | ID:id

Declaración de tipos dTipo ::= ID:id IGUAL tipo:t {:

{:

String name = id.getLexema ();

String name = id.getLexema (); if (scopeManager.containsSymbol (name))

{

TypeIF type = t.getType ();

SymbolIF s = scopeManager.searchSymbol (name);

type.setName (name);

if (s instanceof SymbolConstant) {

ScopeIF scope = scopeManager.getCurrentScope ();

SymbolConstant sC = (SymbolConstant) s;

TypeTableIF tTable = scope.getTypeTable ();

Object value = sC.getValue();

tTable.addType (name, type);

RESULT = new RNumero (value); } else semanticErrorManager.semanticFatalError (...);

:}; tipo ::= dArray:t

| dRecord:t {: RESULT = new Tipo (t.getType()); :} | rTipo:t

} else semanticErrorManager.semanticFatalError (...);

rTipo ::= INTEGER | REAL

:};

{: RESULT = new Tipo (t.getType()); :} {: RESULT = new Tipo (t.getType()); :}; {: RESULT = new RTipo (TypeSimple.ENTERO); :} {: RESULT = new RTipo (TypeSimple.REAL); :}

dTipos ::= dTipos dTipo | dTipo;

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Declaración de tipos

Declaración de tipos | OF rTipo:t {: RESULT = new RArray (t.getType()); :};

| ID:id {:

dRecord ::= RECORD BEGIN bCampos:t END {:

String name = id.getLexema (); if (scopeManager.containsType (name))

RESULT = new DRecord (t.getTypeRecord ());

{

TypeIF type = scopeManager.searchType (name);

:};

RESULT = new Rtipo (type);

bCampos ::= bCampos:t1 lCampos:t2 PYC {: TypeRecord tR1 = t1.getTypeRecord ();

} else

TypeRecord tR2 = t2.getTypeRecord ();

semanticErrorManager.semanticFatalError (...);

TypeRecord tR = new TypeRecord ();

:}

if (tr2.constainsSome (tR1)) semanticErrorManager.semanti...

dArray ::= ARRAY rArray:t PYC {:

else { tR.addAllFields (tR1);

RESULT = new dArray (t.getType ()); :};

tR.addAllFields (tR2);

rArray ::= CI rNumero::n1 DD rNumero:n2 CD rArray:t

RESULT = new BCampos (tR); }

{: Object min = n1.getValue (); Object max = n2.getValue ();

:} | lCampos:t {:

TypeIF tBase = t.getType ();

TypeRecord tR = t.getTypeRecord ();

TypeIF tArray = new TypeArray (min, max, tBase);

RESULT = new BCampos (tR); :};

RESULT = new RArray (tArray); :}

:};

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Declaración de tipos lCampos ::= ID:id DP rTipo:t {:

Declaración de variables dVariables ::= dVariables dVariable | dVariable;

String name = id.getLexema (); TypeIF type = t.getType ();

dVariable ::= ID:id DP rTipo:t {:

TypeRecord tR = new TypeRecord ();

String name = id.getLexema ();

tR.addField (name, type);

TypeIF type = t.getType ();

RESULT = new LCampos (tR, type);

ScopeIF scope = scopeManager.getCurrentScope ();

:}

SymbolTable sTable = scope.getSymbolTable ();

| ID:id COMA lCampos:t {:

if (!(sTable.containsSymbol (name))) {

String name = id.getLexema ();

SymbolVariable sV = new SymbolVariable (name, type);

TypeRecord tR = t.getTypeRecord ();

sTable.addSymbol (name, sV);

if (!(tR.containsField (name))) {

RESULT = new DVariables (type); } else semanticErrorManager.semanticFatalError (...);

TypeIF type = t.getType (); tR.addField (name, type); } else semanticErrorManager.semanticFatalError (...); :}

:} | ID:id COMA dVariables:t {:

:};

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Declaración de subprogramas dSubprogramas ::= dSubprogramas dSubprograma

Declaración de subprogramas tF.addParameterType (p.getType ()); }

| ;

dSubprograma ::= dProcedimiento | dFuncion;

tF.setReturnType (t.getType ());

dProcedimiento ::= pCabecera cuerpo;

ptTable.addType (name, tF);

dFuncion ::= fCabecera cuerpo;

psTable.addSymbol (name, sF);

fCabecera ::= FUNCTION ID:id PI pFormales:pfs PD DP rTipo:t {: String name = id.getLexema ();

} else semanticErrorManager.semanticFatalError (...); pFormales ::= lPFormales:lpf {: List lp = lpf.getParameters ();

if ((!scopeManager.containsSymbol (name)) &&

RESULT = new PFormales (lp);

(scopeManager.containsType (name))) { ScopeIF pScope = scopeManager.getCurrentScope ();

:}

SymbolTableIF psTable = pScope.getSymbolTable ();

| {: RESULT = new pFormales (); :} ;

TypeTableIF ptTable = pScope.getTypeTable ();

lPFormales ::= lPFormales:lpf PYC dPFormales:dpf {:

TypeFunction tF = new TypeFunction (name);

List lp = dpf.getParameters ();

SymbolFunction sF = new SymbolFunction (name, tF);

lpf.addAllParameters (lp);

ScopeIF scope = scopeManager.openScope (name);

RESULT = lpf;

SymbolTableIF sTable = scope.getSymbolTable (); for (SymbolParameter p : pfs.getParameters()) { sTable.addSymbol (p.getName (), p);

:}

:} | dPFormales:dpf {: List lp = dpf.getParameters (); RESULT = new LPFormales (lp); :};

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Declaración de subprogramas dPFormales ::= ID:id PD rTipo:t PYC {:

Expresiones exp ::= exp:e1 MAS exp:e2 {:

String n = id.getLexema ();

TypeIF t1 = e1.getType ();

TypeIF type = t.getType ();

TypeIF t2 = e2.getType ();

SymbolParameter sp = new SymbolParameter (n,type);

if (t1.isCompatible (t2, TypeSimple.MAS)) { TypeIF t = t1.cast (t2, TypeSimple.MAS);

RESULT = new DPFormales (sp, type);

RESULT =

:}

new Exp (t);

} else semanticErrorManager.semanticFatalError (...);

| ID:id COMA dPFormales:dpf {: String n = id.getLexema ();

:}

TypeIF type = dpf.getType ();

| exp MENOS exp {:...:}

SymbolParameter sp = new SymbolParameter(n,type);

| exp POR exp

{:...:}

dpf.addParameter (sp, type);

| exp DIV exp

{:...:}

RESULT = dpf;

| rNumero:rn {:

:};

Object value = rn.getValue ();

pCabecera ::= FUNCTION ID:id PI pFormales:pfs PD {:

TypeIF type;

> :};

RESULT = new Exp (type); :}

type = TypeSimple.REAL;

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Expresiones

Expresiones TypeIF type = sId.getType ();

| PI exp:e PD {:

RESULT = new

TypeIF type = e.getType (); RESULT = new Exp (type);

Referencia (type);

} else SemanticErrorManager.semanticFactalError (...);

:}

:}

| fCall:fc {:

| referencia:r PTO ID:id {:

TypeIF type = fc.getType ();

String name = id.getLexema ();

RESULT = new Exp (type);

TypeIF rType = r.getType (); if (rType instanceof TypeRecord) {

:}

TypeRecord tRec = (TypeRecord) rType;

| referencia:ref {:

if (tRec.containsField (name)) {

TypeIF type = ref.getType ();

Type innerType = tRec.getType (name);

RESULT = new Exp (type);

RESULT = new Referencia (innerType);

:}

} else SemanticErrorManager.semanticFactalError (...);

referencia ::= ID:id {:

} else SemanticErrorManager.semanticFactalError (...);

String name = id.getLexema (); if (scopeManager.contains (name)) {

:}

SymbolIF sId = scopeManager.searchSymbol (name);

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Expresiones

Expresiones TypeFunction tF = sF.getType ();

| referencia:r CI exp:e CD {: TypeIF eType = e.getType ();

List aParams = pa.getParameterTypes ();

if (eType.equals(TypeIF.ENTERO)) {

List fParams = tF.getParameters (); if (aParams.equals(fParams)) {

Type rType = r.getType ();

TypeIF returnType = tF.getReturnType ();

if (rType instanceof TypeArray) {

RESULT = new Fcall (returnType);

TypeArray arrayType = (TypeArray) rType;

} else SemanticErrorManager.semanticFatalError (...);

Type innerType = arrayType.getBaseType ();

} else SemanticErrorManager.semanticFatalError (...);

RESULT = new Reference (innerType);

} else SemanticErrorManager.semanticFatalError (...);

} else SemanticErrorManager.semanticFatal...; } else SemanticErrorManager.semanticFatal...;

:}; pActuales ::= pActuales:pa COMA exp:e {:

:}

TypeIF type = e.getType();

fCall ::= ID:id PI pActuales:pa PD {: String name = id.getLexema ();

pa.addParameterType (type);

if (scopeManager.containsSymbol (name)) {

RESULT = pa;

SymbolIF s = scopeManager.searchSymbol (name);

:}

if (s instanceof SymbolFunction) {

| exp:e {:

SymbolFunction sf = (SymbolFunction)s;

TypeIF type = e.getType ();

RESULT = new PActuales (type); :};

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Implementación de un comprobador de tipos sencillo en cup Una vez conocidos los artefactos necesarios para implementar un comprobador de tipos, podemos describir la forma del esquema de traducción para cada sección de una gramática. En nuestros ejemplos utilizaremos una estilo Pascal aunque es fácilmente trasladable a C. Como cup no admite atributos heredados la solución propuesta se verá someramente condicionada por este hecho

Sentencias

Sentencias

cuerpo ::= BEGIN lSentencias END PYC;

sentenciaAsignación ::= referencia:r

lSentencias ::= lSentencias sentencia | ;

TypeIF eType = e.getType ();

sentencia ::= sentenciaIf

TypeIF rType = r.getType ();

|

IGUAL exp:e PYC {:

if (rType instanceof TypeFunction ||

sentenciaWhile | sentenciaAsignacion |

rType instanceof TypeProcedure) {

pCall |

rType = rType.getReturnType ();

cuerpo;

ScopeIF currentScope = scopeManager.getCurrentScope(); if (!r.getScope().equals(currentScope))

sentenciaIf ::= IF PI exp:e PD THEN sentencia

semanticErrorManager.semanticFatalError (...);

ELSE sentencia {: TypeIF type = e.getType ();

}

if (!(type instanceof TypeSimple.LOGICO))

if (!(rType.isCompatible (eType, TypeIF.IGUAL))) semanticErrorManager.semanticFatalError (...);

semanticErrorManager.semanticFatalError (...); :}

:}

SentenciaWhile ::= WHILE PI exp:e PD DO sentencia {:

pCall ::= ID:id PI pActuales:pa PD PYC; {:

:}

:}

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Temas avanzados de un comprobador de tipos Una vez esbozado el esquema de traducción en cup para un comprobador de tipos sencillo sobre una gramática estilo Pascal, estamos en disposición de tratar algunos temas avanzados de interés que discutimos a continuación

Inferencia de tipos La inferencia de tipos es el proceso por el cual un comprobador de tipos infiere el tipo de una construcción gramatical a partir de su contexto. Esto es especialmente útil en lenguajes sin tipificación explícita Ejemplo I

dConstante

dConstante ::= ID:id IGUAL numero:n {: ...

ID

String name = id.getLexema ();

=

numero (3.5)



Object value = n.getValue (); TypeIF type; if (value instanceof Integer) type = TypeSimple.ENTERO; if (value instanceof Float)

type = TypeSimple.REAL;

if (value instanceof Boolean) type = TypeSimple.LOGICO; SymbolConstant sC = new SymbolConstant (name, value, type); sTable.add (sC);

El caso más sencillo de inferencia de tipos se produce en la declaración de constantes. En efecto, el tipo de la constante no se declara explícitamente sino que se infiere del valor asignado a la misma en la declaración

:};

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Temas avanzados de un comprobador de tipos Una vez esbozado el esquema de traducción en cup para un comprobador de tipos sencillo sobre una gramática estilo Pascal, estamos en disposición de tratar algunos temas avanzados de interés que discutimos a continuación

Inferencia de tipos La inferencia de tipos es el proceso por el cual un comprobador de tipos infiere el tipo de una construcción gramatical a partir de su contexto. Esto es especialmente útil en lenguajes sin tipificación explícita Ejemplo II

exp

exp ::= ID:id {: String name = id.getLexema ();

exp

+

exp

if (!scopeManager.containsSymbol (name)) { ScopeIF scope = scopeManager.getCurrentScope (); SymbolTable sTable = scope.getSymbolTable (); SymbolVariable sV = new SymbolVariable ();

numero (3.5) {Real}

ID {Byte, Word, Integer, Real, Double}

sv.setTypes (TypeSimple.ALL); } RESULT = new Exp (sV, TypeSimple.ALL); :}



sTable.addSymbol (name, sV);

En el caso de lenguajes construcción sintáctica únicos posibles valores numéricos, descartando String

sin tipificación, la infiere que los para ID son los Boolean, Char y

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Temas avanzados de un comprobador de tipos Una vez esbozado el esquema de traducción en cup para un comprobador de tipos sencillo sobre una gramática estilo Pascal, estamos en disposición de tratar algunos temas avanzados de interés que discutimos a continuación

Inferencia de tipos La inferencia de tipos es el proceso por el cual un comprobador de tipos infiere el tipo de una construcción gramatical a partir de su contexto. Esto es especialmente útil en lenguajes sin tipificación explícita Ejemplo II

exp

exp ::= exp:e1 MAS exp:e2 {: TypeIF t1 = e1.getTypes ();

exp

+

exp

TypeIF t2 = e2.getTypes (); t1.removeIncompatibles (t2, TypeIF.MAS); t2.removeIncompatibles (t1, typeIF.MAS); SymbolVariable e1Var = e1.getVariable();

numero (3.5) {Real}

ID {Byte, Word, Integer, Real, Double}

SymbolVariable e2Var = e2.getVariable(); if (e2Var != null) e1Var.setTypes (t2); if (t1.isEmpty() || t2.isEmpty) semanticErrorManager...; else { Types types = new Types (t1); types.addAllTypes (t2); RESULT = new Exp (types);



if (e1Var != null) e1Var.setTypes (t1);

En el caso de lenguajes construcción sintáctica únicos posibles valores numéricos, descartando String

sin tipificación, la infiere que los para ID son los Boolean, Char y

}

:}

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Temas avanzados de un comprobador de tipos Una vez esbozado el esquema de traducción en cup para un comprobador de tipos sencillo sobre una gramática estilo Pascal, estamos en disposición de tratar algunos temas avanzados de interés que discutimos a continuación

Sobrecarga de subprogramas Como ya se comentó anteriormente, existen lenguajes que dan soporte a la sobrecarga de subprogramas. Es decir permiten declarar varias versiones de funciones o procedimiento con igual nombre pero distinto numero, tipo u orden de parámetros. La implementación de esta capacidad se estudiará para funciones ya que para procedimientos resulta similar En la declaración…

En la invocación…

fCabecera ::= FUNCTION ID:id PI pFormales:pfs PD DP

fCall ::= ID:id PI pActuales:pa PD {:

rTipo:t {:

String name = id.getLexema ();

String name = id.getLexema (); TypeIF t =

TypeIF t = scopeManager.searchType (name);

TypeFunction tFun =

if (t instance of TypeFunction) {

tFun.addSignature (t);

TypeFunction tF = (TypeFunction) t;

...

List signatures = tF.getSignatures (); for () {



:}

if (scopeManager.containsSymbol (name)) {

} } }

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Temas avanzados de un comprobador de tipos Una vez esbozado el esquema de traducción en cup para un comprobador de tipos sencillo sobre una gramática estilo Pascal, estamos en disposición de tratar algunos temas avanzados de interés que discutimos a continuación

Recuperación de errores semánticos La recuperación de errores semánticos es algo menos frecuente que la de errores sintácticos. Sin embargo es posible realizarlo mediante una extensión conveniente del esquema de traducción dirigido por la sintaxis. En concreto se utilizan para expresiones y sentencias dos nuevos valores para el atributo de tipo: error y correcto. sentencia .tipo = error exp .tipo = error Boolean = tipo. exp

true

>

THEN

sentencia .tipo = Correcto

exp .tipo = ENTERO 4



IF

Los errores se almacenan como formas de tipo y se van acumulando para indicar qué partes del árbol de análisis sintáctico contiene error

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Construcción de comprobadores de tipos en la práctica

Desarrollo paso a paso La fase de análisis semántico requiere de la implementación del comprador de tipos del lenguaje que siga las directrices del sistema de tipos del lenguaje. En esta última sección hemos descrito cómo se implementa un comprobador de tipos sencillos. Ahora damos la secuencia de pasos a realizar 1. Implementación de artefactos en código abierto 1. Implementación de la tabla de símbolos 2. Implementación de la tabla de tipos 3. Implementación de todas las clases TypeIF necesarias

Se debe reflexionar cuidadosamente acerca de qué atributos son necesarios para caracterizar cada tipo y símbolo del lenguaje y cada elemento no gramatical

4. Implementación de todas las clases SymbolIF necesarias 5. Incorporación de atributos y constructores necesarios en cada no terminal 2. Implementación de las acciones semánticas del comprobador de tipos 1. Acciones para declaraciones 2. Acciones para expresiones 3. Acciones para sentencia 3. Prueba del comprobador de tipos 1. Ejecutar finalTestCase 2. Comprobar en la traza el estado de cada tabla de símbolos y tipo 3. Comprobar que se emiten los mensajes de error semántica ante códigos incorrectos Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Bibliografía

Material de estudio Bibliografía básica Construcción de compiladores: principios y práctica Kenneth C. Louden International Thomson Editores, 2004 ISBN 970-686-299-4

Javier Vélez Reyes [email protected]

Análisis semántico. Comprobación de tipos Bibliografía

Material de estudio Bibliografía complementaria Compiladores: Principios, técnicas y herramientas. Segunda Edición Aho, Lam, Sethi, Ullman Addison – Wesley, Pearson Educación, México 2008

Diseño de compiladores. A. Garrido, J. Iñesta, F. Moreno y J. Pérez. 2002. Edita Universidad de Alicante

Javier Vélez Reyes [email protected]