Análisis Semántico y Chequeo de Tipos



Descargar 26,87 Kb.
Fecha de conversión13.09.2017
Tamaño26,87 Kb.

Análisis Semántico y Chequeo de Tipos

Resumen

¿Dónde estamos?

  • Analizador Léxico (Scanner)
  • Analizador Sintáctico (Parser)
  • Token Stream
  • Arbol de Parseo
  • Programa (character stream)

¿Dónde estamos?

  • Analizador Léxico (Scanner)
  • Analizador Sintáctico (Parser)
  • Token Stream
  • Arbol de Parseo
  • Programa (character stream)
  • Analizador Semántico
  • Generador de Código Intermedio
  • Representación Intermedia + Tabla de Símbolos

¿Qué es la semántica de un programa?

  • Sintáxis
    • Cómo se ve un programa
    • Representación textual o estructura
    • Es posible dar una definición matemática precisa
  • Semántica

Por qué hacer análisis semántico

  • Asegurarnos que el programa cumple con la definición del lenguaje de programación
  • Proveer mensajes de error útiles al usuario

Resumen

  • Oscar Bonilla Universidad Galileo
  • Introducción
  • Tablas de Símbolos
  • Chequeo Semántico
  • Chequeo de Tipos
  • Semántica de un Programa Orientado a Objetos
  • Tipos Polimórficos

Tabla de Símbolos

  • Un lugar para guardar toda la información adicional acerca del programa
    • Representaciones intermedias: expresiones, statements, control de flujo, etc.
    • Tabla de Símbolos: Tipos, variables, scope, etc.

Scope

  • Un nombre puede tener significados distintos en lugares distintos
    • Tipos, variables, etc tiene scope (ámbito)
  • Tenemos que mantener una tabla de símbolos para cada scope

Operaciones en la tabla de símbolos

  • make_table(parent_table)  symbol_table
  • scope(id)  symbol_table
  • lookup_variable(id, symbol_table)  variable
  • lookup_type(id, symbol_table)  type
  • get_type(variable)  type
  • add_type(id, symbol_table, type)  type
  • add_variable(id, symbol_table, type)  variable

Siguiente Clase

  • Todo acerca de tablas de símbolos
    • Scopes y visibilidad
    • Información que se mantiene en la tabla de símbolos
    • Implementación de tablas de símbolos

Resumen

  • Oscar Bonilla Universidad Galileo
  • Introducción
  • Tablas de Símbolos
  • Chequeo Semántico
  • Chequeo de Tipos
  • Semántica de un Programa Orientado a Objetos
  • Tipos Polimórficos

Chequeo Semántico

  • Chequeos estáticos vs. Chequeos dinámicos
  • Chequeos estáticos
    • Chequeos de control de flujo
    • Chequeos de unicidad
    • Chequeos de Tipo

Chequeos de Control de Flujo

  • El control de flujo del programa es sensitivo al contexto
  • Ejemplos:
    • Declaración de una variable debe ser visible al usarla (en scope)
    • Declaración de una variable debe estar ántes de usarla
    • Cada camino de salida (exit path) retorna un valor del tipo correcto
  • ¿Qué más?

Chequeos de Unicidad

  • Uso (y mal uso) de identificadores
    • No se puede representar en una CFG (mismo token)
  • Ejemplos:

Chequeos de Tipo

  • Los chequeos semánticos más extensos
  • Ejemplos:
    • Que el número de argumentos haga match con el número de parámetros formales y que los tipos correspondientes sean equivalentes
    • Si se llama como expresión, debe retornar un tipo
    • Cada acceso a una variable debe hacer match con la declaración (arreglo, estructura, etc.)
    • Los identificadores en una expresión deben ser “evaluables”
    • LHS de una asignación debe ser “asignable”
    • En una expresión los tipos de las variables, tipos de retorno de métodos y de operadores deben ser “compatibles”

Chequeos Dinámicos

  • Chequeos de límites de arreglos
  • Chequeo de dereferencia del Null Pointer

Resumen

  • Oscar Bonilla Universidad Galileo
  • Introducción
  • Tablas de Símbolos
  • Chequeo Semántico
  • Chequeo de Tipos
  • Semántica de un Programa Orientado a Objetos
  • Tipos Polimórficos

Sistemas de Tipos

  • Un sistema de tipos es usado para el chequeo de tipos
  • Un sistema de tipos incorpora
    • Construcciones estáticas del lenguaje
    • Noción de tipos
    • Reglas para asignar tipos a construcciones del lenguaje

Expresiones de Tipos

  • Un tipo compuesto es denotado por una expresión de tipo
  • Una expresión de tipo es
    • Un tipo básico
    • La aplicación de un constructor de tipo a otras expresiones de tipo

Expresiones de Tipos: Tipos Básicos

  • Tipos atómicos definidos por el lenguaje
  • Ejemplos:
    • Enteros
    • Booleanos
    • floats
    • caracteres
  • type_error
    • Tipo especial que produce un error
  • void
    • Tipo básico que denota “la ausencia de un valor”

Expresiones de Tipo: Nombres

  • Ya que las expresiones de tipos pueden ser nombradas, un nombre de tipo es una expresión de tipo

Expresiones de Tipo: Productos

  • Si T1 y T2 son expresiones de tipo, T1  T2 es también una expresión de tipo

Expresiones de Tipo: Arrays

  • Si T es una expresión de tipo, un array(T, I) es también una expresión de tipo
    • I es una constante entera que denota el número de elementos de tipo T
    • Ejemplo:
      • int foo[128];
      • array(integer, 128)

Expresiones de Tipo: Function Calls

  • Matemáticamente una función mapea
    • Elementos de un conjunto (el dominio)
    • A elementos de otro conjunto (el contradominio)
  • Ejemplo
    • int foobar(int a, boolean b, int c)
    • integer  boolean  integer  integer

Expresiones de Tipo: Otras

  • Records
    • Estructuras y clases
    • Ejemplo
      • class { int i; int j;}
      • integer  integer
  • Lenguajes Funcionales
    • Funciones que toman funciones y retornan funciones
    • Ejemplo
      • (integer  integer)  integer  (integer  integer)

Un lenguaje simple con tipos

  • Oscar Bonilla Universidad Galileo
  • Un lenguaje que tiene una secuencia de declaraciones seguidas de una sola expresión
    • P  D; E
    • D  D; D | id : T
    • T  char | integer | array [ num ] of T
    • E  literal | num | id | E + E | E [ E ]
  • Programa Ejemplo
    • var: integer;
    • var + 1023

Un lenguaje simple con tipos

  • Oscar Bonilla Universidad Galileo
  • Un lenguaje que tiene una secuencia de declaraciones seguidas de una sola expresión
    • P  D; E
    • D  D; D | id : T
    • T  char | integer | array [ num ] of T
    • E  literal | num | id | E + E | E [ E ]
  • ¿Cuáles son las acciones del parser para este lenguaje?

Acciones del Parser

  • Oscar Bonilla Universidad Galileo
    • P  D; E
    • D  D; D
    • D  id : T { addtype(id.entry, T.type); }
    • T  char { T.type = char; }
    • T  integer { T.type = integer; }
    • T  array [ num ] of T1 { T.type = array(T1.type, num.val); }

Acciones del Parser

  • Oscar Bonilla Universidad Galileo
    • E  literal { E.type = char; }
    • E  num { E.type = integer; }
    • E  id { E.type = lookup_type(id.name); }

Acciones del Parser

  • Oscar Bonilla Universidad Galileo
    • E  E1 + E2 { if E1.type == integer and
    • E2 .type == integer then
    • E.type = integer
    • else
    • E.type = type_error
    • }
  • 24

Acciones del Parser

  • Oscar Bonilla Universidad Galileo
    • E  E1 [E2 ] { if E2.type == integer and
    • E1 .type == array(s, t) then
    • E.type = s
    • else
    • E.type = type_error
    • }

Equivalencia de Tipos

  • ¿Cómo sabemos si dos tipos son iguales?
    • Mismo entrada de tipo
    • Ejemplo:
      • int A[128];
      • foo(A);
      • foo(int B[128]) { … }
      • Dos entradas de tipo distintas en dos tablas de símbolos distintas
      • Pero deberían ser iguales

Equivalencia Estructural

  • Si la expresión de tipo de dos tipos tiene la misma construcción, entonces son equivalentes
  • “Misma Construcción”
    • Tipos base equivalentes
    • Mismo conjunto de constructores de tipo son aplicados en el mismo orden (e.d. árbol de tipos equivalente)

Coerción de Tipos

  • Conversión implícita de un tipo a otro tipo
  • Ejemplo
    • int A;
    • float B;
    • B = B + A
  • Dos tipos de coerción
    • widening conversions
    • narrowing conversions

Widening conversions

  • Conversiones sin pérdida de información
  • Ejemplos:
    • integers a floats
    • shorts a longs

Narrowing conversions

  • Conversiones que pueden perder información
  • Ejemplos:
    • integers a chars
    • longs a shorts
  • Raro en lenguajes

Type casting

  • Conversión explícita de un tipo a otro
  • Tanto widening como narrowing
  • Ejemplo
    • int A;
    • float B;
    • A = A + (int)B
  • Typecasting ilimitado puede ser peligroso

Pregunta:

  • Oscar Bonilla Universidad Galileo
  • ¿Podemos asignarle un solo tipo a todas las variables, funciones y operadores?
  • ¿Qué hay de +, cuál es su tipo?

Overloading

  • Algunos operadores pueden tener más de un tipo.
  • Ejemplo
    • int A, B, C;
    • float X, Y, Z;
    • A = A + B
    • X = X + Y
  • Complica el sistema de tipos
    • Ejemplo
    • A = A + X
      • ¿Cuál es el tipo de + ?

Resumen

  • Oscar Bonilla Universidad Galileo
  • Introducción
  • Tablas de Símbolos
  • Chequeo Semántico
  • Chequeo de Tipos
  • Semántica de un Programa Orientado a Objetos
  • Tipos Polimórficos

Clases

  • Una clase es un tipo de datos abstracto
  • Contiene
    • Datos (campos)
    • Acciones (métodos)
    • Restricciones de acceso
  • Cada instancia de una clase va a crear un objeto separado
    • Con su propia copia de las variables instanciadas (compos)
    • Comparte las acciones (métodos)

Clase Ejemplo

  • Oscar Bonilla Universidad Galileo
  • class vehicle {
  • int num_wheels;
  • void print_num_wheels( ) { … }
  • }
  • campo
  • método
  • vehicle A;
  • A.print_num_wheels( )
  • El Objeto es un parámetro implícito de la llamada del método

Herencia

  • Extiende las clases al permitirles relaciones de supertipo/subtipo
  • Soporta reuso de código incremental
    • Partes comúnes en un supertipo común
    • Diferencias individuales en cada subtipo

Ejemplo de Herencia

  • Oscar Bonilla Universidad Galileo
  • class SUV extends vehicle {
  • int rollover_speed;
  • int get_rollover_speed( ) { … }
  • void print_rollover_speed( ) { … }
  • }
  • La clase SUV es una subclase de la clase vehicle
  • La clase vehicle es una superclase de la clase SUV
  • Una instancia (objeto) de la clase SUV contiene
    • Todos los campos de la clase vehicle
    • Todos los campos de la clase SUV
  • Los métodos tanto en SUV como en vehicle son visibles a la clase SUV

Herencia

  • Herencia Sencilla
    • Cuando cada clase está restringida a tener una sola superclase inmediata (máximo)
  • Herencia Múltiple
    • Cuando cada clase puede tener más de una superclase inmediata

Jerarquía de Herencia

  • La relación subclase/superclase
    • Definida por los “extends”
    • Puede ser modelada mediante un grafo acíclico dirigido (DAG)

Jerarquía de Herencia

  • Oscar Bonilla Universidad Galileo
  • Car es un hijo de vehicle (subclase inmediata)
  • Vehicle es un padre de SUV (superclase inmediata)
  • 4wd es un descendiente de vehicle (subclase)
  • Vehicle es un ancestro de 2-door (superclase)
  • vehicle
  • SUV
  • car
  • motorbike
  • 4wd
  • 2wd
  • 4-door
  • 2-door
  • 5-door

Reglas de Control de Acceso

  • Conjunto de tipos de control de acceso usados por un lenguaje OO genérico (e.d. Espresso)
    • Visibilidad en scope
    • Acceso a datos
    • Acceso a métodos públicos
    • Acceso a métodos privados
  • Muchos lenguajes OO tienen controles de acceso más complicados

Visibilidad en Scope

  • Las variables y los campos de una clase pueden ser declarados en cualquier parte en el programa en la que se permita una declaración y la definición de la clase esté visible
  • Si un campo en una subclase y superclase usa el mismo nombre
    • La resolución de nombres se hace usando reglas de scope
    • Se trata el scope de la subclase dentro del scope de la superclase

Acceso a Datos

  • Los campos de datos de una clase sólo pueden ser accesados por los métodos definidos en esa clase
  • Una variación más permisiva:

Acceso a métodos públicos

  • Todos los métodos públicos de una clase pueden ser invocados por cualquier método que pueda declarar una variable o un campo del tipo de la clase

Acceso a métodos privados

  • Los métodos privados de una clase sólo pueden ser invocados por:
    • Los métodos de esa clase
    • Los métodos de cualquier clase que sea descendiente de la clase

Ejemplo: control de acceso de C++

  • Oscar Bonilla Universidad Galileo
  • Una clase puede ser friend de otra clase
  • Los métodos y campos pueden ser
    • private: visibles a funciones miembro y friends
    • protected: visibles a funciones miembro, friends, y clases derivadas (y sus friends)
    • public: pueden ser usados por cualquier función

Conversión automática de tipos

  • Una expresión de una clase es coercionada a una clase ancestro cuando se requiera
    • Pero no al revés
    • Llamado “up-casting”
    • Siempre legal porque la subclase contiene todos los campos de la superclase
  • Down-casting
    • Esto es más permisivo
    • Conversión explícita de una clase ancestro a una clase descendiente
    • Sólo tiene sentido si el objeto fue creado inicialmente como en la subclase, pero después convertido a la superclase
    • No puede chequearse en tiempo de compilación

Métodos Estáticos vs. Dinámicos

  • Consecuencia de up-casting
    • Implementación del método declarado en una superclase puede ser desconocida al momento de compilar
    • El método es sobreescrito en una subclase
    • Variaciones de Lenguajes
      • Todos los métodos no declarados estáticos pueden ser up-casted
      • Sólo los métodos declarados virtuales pueden ser up-casted
    • Análisis e implementación de métodos dinámicos
      • No se puede efectuar ningún chequeo semántico
      • Necesitamos soporte en tiempo de corrida (runtime) al generar el código

Herencia vs. Agregación

  • Una clase T2 es una agregación de una clase T1 si T2 contiene uno o más campos de tipo T1
    • A diferencia de la herencia, T2 no puede accesar campos o métodos privados en T1
  • ¿Cuándo heredear y cuándo agregar?
    • heredar: T2 es un T1
    • agregar: T2 tiene un T1

Ejemplo: Herencia vs. Agregación

  • Oscar Bonilla Universidad Galileo
  • SUV es un vehículo
  • SUV tiene un motor
  • class vehiculo {
  • }
  • class SUV extends vehiculo {
  • motor power_plant;
  • }

Herencia múltiple

  • Permite que una clase sea una extensión de múltiples clases
    • Lleva a semánticas más complicadas para subtipos

Ejemplo de Herencia Múltiple

  • Oscar Bonilla Universidad Galileo
  • class vehicle {
  • }
  • class yuppie_toys {
  • }
  • class SUV extends vehicle, yuppie_toys {
  • }

Jerarquía de Herencia Múltiple

  • Oscar Bonilla Universidad Galileo
  • Jerarquía de Herencia Múltiple es un DAG
  • Pregunta: ¿Sí tanto yuppie_toys como vehicle tienen un método price() cuándo SUV invoque a price, qué método se invoca?
  • vehicle
  • SUV
  • car
  • motorbike
  • 4wd
  • 2wd
  • 4-door
  • 2-door
  • 5-door
  • toys
  • yuppie_toy
  • teen_toy

Jerarquía de Herencia Múltiple

  • Oscar Bonilla Universidad Galileo
  • Es todavía más complicado cuándo hay un ancestro común
  • Pregunta: ¿Cuántas instancias de bti van a ser incluidas en la clase SUV?
  • vehicle
  • SUV
  • car
  • motorbike
  • 4wd
  • 2wd
  • 4-door
  • 2-door
  • 5-door
  • toys
  • yuppie_toy
  • teen_toy
  • big_ticket_items

Resumen

  • Oscar Bonilla Universidad Galileo
  • Introducción
  • Tablas de Símbolos
  • Chequeo Semántico
  • Chequeo de Tipos
  • Semántica de un Programa Orientado a Objetos
  • Tipos Polimórficos

¿Qué es un tipo polimórfico?

  • Procedimientos ordinarios permiten que el cuerpo sea ejecutado con argumentos de tipo fijo
  • Cada llamada a un procedimiento polimórfico ejecuta el cuerpo con el tipo de los argumentos
  • Beneficios del polimorfismo
    • Reuso de Código
    • Ejemplo
      • El mismo procedimiento puede aplicarse a una lista de enteros o a una lista de strings

Polimorfismo Paramétrico

  • Los procedimientos tienen tipos paramétrizados
  • Instanciamos el procedimiento con un tipo determinado de datos
  • Templates en C++
  • Ejemplo:
    • template class linked_list_elem {
    • T elem; linked_list_elem * next;
    • ...
    • }
    • lined_list_elem integer_list;
    • lined_list_elem foo_list;

Lecturas

  • Oscar Bonilla Universidad Galileo
  • Tigre
    • 6.1, Capítulos 7 y 8
  • Ballena
    • 4.1, 4.2, 4.3, 4.4, 4.5
  • Dragón
    • Capítulo 8


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal