Análise Semântica

Análise Semântica

Ánálise Semântica

Análise Semântica:

• liga definição de variáveis ao seu tipo;
• verifica se cada expressão tem um tipo correcto;
• traduz de síntaxe abstracta para representação mais simple.

Tabela de Símbolos (Ambiente)

Mapeamento de Ids para Tipos e Localização:

• Cada variável tem um scope aonde é visivel.
• Ex: let  D  in  E  end variáveis tipos e funções em D só são visiveis em E.
• Ambiente é um conj. de ligações (bindings) representados por |->.
• Ex: sigma₀ = { g |->string, a |->int }

  function f(a:int, b:int, c:int) =
    (print_int(a+c);
     let var j := a+b
         var a := "hello"
     in print(a); print_int(j);
     end;
     print_int(b)
    )
  

• sigma₁ = sigma₀ + {a |->int, b |->int, c |->int }
• sigma₂ = sigma₁ + { j |->int }
• sigma₃ = sigma₂ + { a |->string }

Tabela de Símbolos: Implementação

Primeiro, notar que sigma₁ + sigma₂ != sigma₂ + sigma₁:

• Estilo funcional: nós mantemos sigma₁ enquanto criamos sigma₂ e sigma₃.
  • sigma₁ está disponível se voltarmos a precisar dele.
• Estilo imperativo: modificar sigma₁ directamente até ficar sigma₂: alteração destrutiva.
  • Existe um único ambiente e uma pilha de undo que usamos para recuperar alterações destrutivas.
• Qualquer estilo pode ser usado, depende da:
• linguagem a compilar;
• linguagem a usar;
• ser funcional, imperativa, lógica, orientada a objectos,

Múltiplas Tabelas de Símbolos

Algumas linguagens permitem ambientes múltiplos:

• Vimos exemplo de contextos em Tiger.
• Em ML tb temos vários ambientes activos ao mesmo tempo.
• Em Java podemos ter declarações para a frente:

  package M;
  class E { static int a = 5; }
  class N {
   static int b = 10;
   static int a = E.a + b;
  }
  class D { static int d = E.a + N.a; }
  

  O ambiente de N pode usar variáveis de M e de D!
• No estilo imperativo uma solução muito eficiente são tabelas de hash
• Encadeamento externo permite implementar eliminação fácilmente.

Notas de Implementação

• Estilo Funcional:
  • Copiar o vector da tabela de hash é caro (vectores grandes).
  • Alternativa: usar árvores binárias de procura:
  
• Evitar comparações de strings: converter String para symbol, de forma a poder usar comparação de ponteiros.
• Trail (pilha auxiliar) é usada para eliminar bindings.

Bindings

Tiger tem dois espaços de nomes:

• Tipos;
• Funções e variáveis

• tipos básicos: int e string;
• tipos compostos: arrays; records com nomes e tipos de campos.
• qualquer novo tipo é diferente: comparação pelo endereço do tipo.
• type c = a: declaração de tipos iguais é legal.
• nil pertence a qualquer tipo record: usamos um tipo especial para nil.
• Ter cuidado com tipos mutuamente recursivos: manter lugar.

Bindings: Exemplo

struct Ty_ty_
  { enum{Ty_record, Ty_nil, Ty_int, Ty_string,
        Ty_array, Ty_name, Ty_void} kind;
    union {Ty_fieldList record;
           Ty_ty array;
           struct {S_symbol sym; Ty_ty;} name;
    } u;  }
Ty_ty Ty_Nil(void);      Ty_ty Ty_Int(void);
Ty_ty Ty_String(void);   Ty_ty Ty_Void(void);

Ty_ty Ty_Record(Ty_fieldlist fields);
Ty_ty Ty_Array(Ty_ty ty);
Ty_ty Ty_Name(S_symbol sym, Ty_ty ty);

struct Ty_tyList_ {Ty_ty head;Ty_tyList tail;}
Ty_tyList Ty_tyList(Ty_ty head,Ty_tyList tail);

struct Ty_field_ {S_symbol name; Ty_ty ty;}
Ty_field Ty_Field(S_symbol name; Ty_ty ty);

struct Ty_fieldList_ {Ty_field head; 
                      Ty_fieldList tail;}
Ty_fieldList Ty_FieldList(Ty_field head;
                          Ty_fieldList tail);

Ambientes

Em Tiger temos ambientes para tipos e valores:

let type a = int
    var a : a = 5
    var b : a = a
  in b + a
end

• Para cada identificador de tipo, basta saber o tipo Symb |->Ty_ty.
  • base_tenv com tipos prédefinidos.
• Para cada indentificador de valor, precisamos de saber
  1. É função?
     • Quais os seus parâmetros e tipos de resultados?
     • Guardado em FunEntry
  2. É variável?
     • Qual o seu tipo?
     • Guardado em VarEntry
  3. base_venv contém funções pré-definidas

Verificação de Tipos: Expressões

Verifica o tipo dos elementos que aparecem na árvore sintáctica:

• Função mutuamente recursiva sobre a árvore.
• Para expressões transExp(venc,tenv,Exp resulta em expty, com expressão e o tipo.
• Type-checking de adição em inteiros:

  case A_opExp;
    A_oper oper = a->u.op.oper;
    struct expty left = transexp(venv,
           tenv,a->u.op.left);
    struct expty right = transexp(venv,
           tenv,a->u.op.right);
    if (oper == A_plusOp) {
      if (left.ty->kind != Ty_int)
        Em_error(a->u.op.left->pos,
               "integer required");
      if (right.ty->kind != Ty_int)
        Em_error(a->u.op.right->pos,
               "integer required");
      return(expTy(NULL,Ty_Int));
    }
  

Verificação de Tipos

• Variáveis: Se id está no ambiente e ligado a VarEntry, o seu tipo é o de VarEntry.
  • Se tipo da forma NameType devemos percorrer o tipo taé encontrar o tipo "genuíno".
• Chamadas de funções: verificar os tipos dos argumentos e retornar o tipo da função.
• Declarações obrigam a começar um novo contexto e adicionar novos bindings.
  • Problema: declarações recursivas.
• Tipos: recorrer sobre a estutura do tipo.
  • Problema: declarações recursivas.
• Funções:

  function f(a: ta, b: tb,) : rt = body

  1. procura o tipo de rt no ambiente actual;
  2. retorna lista com os tipos formais;
  3. Constroi a entrada FunEntry para a função;
  4. Entrar os parâmetros formais no ambiente de valores;
  5. Processar o corpo;
  6. endScope().

  A_fundec f = d->u.function->head;
  Ty_ty resultTy = tylook(tenv,f->result,
                   f->pos);
  Ty_tyList formalTys = makeFormalTyList(
                   tenv,f->params);
  S_enter(venv,f->name,E_FunEntry(
                   formalTys,resultTy));
  S_beginScope(venv);
  {A_fieldList l=f->params;
   Ty_tyList t = formalTys;
   for(;l;l=l->tail,t=t->tail)
     S_enter(venv,l->head->name,
             E_VarEntry(t->head)); 
  }
  S_endScope(venv);
  

Verificação de Tipos: Recursão

O que fazer com tipos ou funções que se chamam mútuamente?

type list = {first: int, rest: list}

1. primeiro pôr cabeçalhos no ambiente e, construindo e₁: cabeçalho é type list =
2. processar e₁ com cabeçalhos:

   {first: int, rest: list}
   

3. a tradução de tipos deve parar logo que encontre um Ty_Name, senão pode encontrar um NULL.
4. agora, podemos colocar o novo tipo no campo ty.

Análise Semântica