Verificação de Tipos
• Verificação de erros semânticos.
• Verificação estática (e não dinâmica)
– Estática: em tempo de compilação
– Dinâmica: em tempo de execução
• Objetivo: detecção de alguns tipos de erros
Tipos de Verificações Estáticas
• Verificação de tipos: soma de variáveis de tipos
incompatíveis, atribuição de expressões
incompatíveis com variáveis.
• Verificações de fluxo de controle: goto entre
procedimentos, break em C sem while/for/switch.
• Verificações de unicidade: identificadores, labels.
• Verificações ligadas a nomes: mesmo nome
indicando início e fim de bloco, em Ada.
Verificador de Tipos
tokens
parser
Gerador de
Verificador
código
de tipos
intermediário
árvore
árvore
sintática
sintática
Tarefas do verificador de tipos
• Tipo dos operandos são compatíveis com
tipo do operador
• Só ponteiros são derreferenciados
• Só arrays são indexados
• Número e tipo de argumentos passados a
uma função estão corretos
Informações geradas pelo
verificador de tipos
• Além do uso pelo próprio type checker,
várias informações de tipos são mantidas
para uso em passos posteriores, inclusive
geração de código.
• Exemplo: overloading do ‘+’.
Overloading, coerção e
polimorfismo
• Overloading: mesmo símbolo ou nome usado para
representar operações diferentes. Exemplo: 2 + 2
vs. 2.0 + 2.0
• Coerção: conversão implícita (ou explícita) de um
tipo para outro.
Exemplo: 2 + 3.5
• Polimorfismo: corpo (código) de uma mesma
função é usado para lidar com tipos difrentes.
Sistemas de Tipos
• Podem ser definidos formalmente ou
informalmente.
• Define os tipos válidos e as regras para se
atribuir tipos às construções da linguagem.
Sistemas de Tipos
• Report do Pascal: “Se os dois operandos dos
operadores aritméticos de adição, subtração e
multiplicação são do tipo inteiro, então o resultado
é do tipo inteiro.”
• Manual de Referência do C: “O resultado do
operador unário & é um ponteiro para o objeto
referido pelo operando. Se o tipo do operando for
‘…’ o tipo do resultado é ‘ponteiro para …’”
• Cada expressão tem um tipo associado a ela.
Tipos básicos e tipos construídos
• Tipos básicos (atômicos): boolean, character,
integer, real.
• Subrange (1..10) e tipos enumerados
(verao,inverno,outono, primavera) podem ser
tratados como tipos básicos.
• Tipos construidos: arrays, registros, conjuntos (são
formados de outros tipos construidos ou básicos)
• Ponteiros e funções podem ser vistos como tipos
construídos.
Expressões de Tipos
• Tipos em uma linguagem são expressos por
“expressões de tipos”: tipos básicos ou
construtores de tipos aplicados a outras
expressões de tipos.
• Os construtores possíveis variam de acordo
com a linguagem.
Tipos em uma Linguagem
• Tipos básicos: boolean, integer, char, real,
type_error, void.
• Nome de uma expressão de tipos
Tipos em uma Linguagem:
Construtores de tipos
• Tipo Array: var A: array[1..10] of integer
• Tipo Produto: T1  T2
• Tipo Registro: é um tipo produto com nomes:
type row = record
address: integer;
lexeme: array [1..15] of char;
end;
é o mesmo que
record((address  integer) 
(lexeme  array(1..15,char))
Construtores de Tipos (cont.)
• Tipo Ponteiro: var p: ^row
declara uma variável do tipo pointer(row)
• Tipo Função: mapeiam valores de um domínio D
para um domínio destino R, i.e. D  R.
Exemplo: a função mod tem tem tipo
int  int  int
– Por razões de implementação, às vezes os tipos
suportados como resultado de uma função são limitados
em algumas linguagens.
Tipos podem ser representados
por grafos



int

int
int
char

pointer
char

int
pointer
int
char
Sistemas de Tipos
•
•
•
Coleção de regras para atribuir expressões de
tipo a várias partes de um programa.
Verificação de tipos pode sempre ser feita
dinamicamente, se junto com os dados vierem
sempre informações de tipos.
Um sistema de tipos sound elimina a
necessidade de verificações dinâmicas, porque
permite detectar estaticamente se erros de tipos
podem ocorrer em um programa.
Sistemas de Tipos (cont.)
•
•
Uma linguagem é dita fortemente tipada
(strongly typed) se ela garante que erros de
tipo não podem ocorrer durante a
execução.
Na pratica, algumas verificações só
podem ser feitas dinamicamente.
Exemplo: índices de arrays.
Especificação de um type checker
simples
PD;E
D  D ; D | id : T
T  char | integer | array [ num ] of T | ^T
E  literal | num | id | E mod E | E [ E ] | E^
• Exemplo:
key : integer;
key mod 1999
Especificação de um type checker
simples (cont.)
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 T
{T.type=array(1..num.val, T1.type)}
T  ^T1
{T.type = pointer(T1.type)}
Especificação de um type checker
simples (cont.)
E  literal {E.type = char}
E  num {E.type = integer}
E  id
{E.type = lookup(id.entry)}
E  E1 mod E2 {if (E1.type == integer &&
E2.type == integer)
E.type = integer
else E.type = type_error }
Especificação de um type checker
simples (cont.)
E  E1 [ E2 ] {if (E2.type == integer &&
E1.type == array(s,t))
E.type = t
else E.type = type_error }
E  E1^ {E.type = if (E1.type == pointer(t))
t
else type_error }
Verificação de tipos de comandos
(statements)
S  id = E {S.type = if (id.type == E.type)
void
else type_error }
S  if E then S1
{S.type = if (E.type == boolean)
S1 .type
else type_error }
Verificação de tipos de comandos
(statements) (cont.)
S  while E do S1 {S.type = if (E.type == boolean)
S1.type
else type_error }
S  S1 ; S2
{S.type = if (S1.type == void &&
S2.type == void)
void
else type_error }
Verificação de funções
T  T1  T2
{T.type = T1.type  T2.type}
E  E1 ( E2 ) {E.type = if (E2.type == s &&
E1 .type == s  t)
t
else type_error }
Equivalência de tipos
•
•
Geralmente é usada equivalência estrutural.
Às vezes é necessário fazer modificações, por
exemplo:
–
–
–
Em várias linguagens, os índices de arrays em um
tipo são ignorados em passagem de parâmetros.
Tratamento de nomes de tipos e tipos sinônimos
(equivalência estrutural x equivalência por nomes).
A função de equivalência deve tratar tipos recursivos!
Ciclos na representação de tipos
type link = ^cell;
cell = record
info : integer;
next : link;
end;

info
cell = record


integer next
pointer
Ciclos na representação de tipos
(cont.)
•
C evita ciclos na representação de tipos
usando equivalência estrutural para todos
os tipos exceto records (structs).
Ciclos na representação de tipos
(cont.)
•
struct cell { int info;
struct cell *next;
};
cell = record


info

integer next
pointer
Cell