Análise Semântica

Frank Coelho de Alcantara -2021

Muito Além da Sintaxe

Algumas perguntas precisam ser respondidas:

A variável já foi declarada?

O tipos são consistentes nesta declaração?

O parâmetros chamados estão corretos?

Um ponteiro pode estar fora do espaço de memória?

A resposta não é simples!

As respostas dependem dos valores não da sintaxe;

Tanto perguntas quanto respostas não são locais;

Respostas podem precisar de computação.

Tarefas importantes

Para cada expressão: identificar quais são os tipos;

Para cada declaração: que informação precisamos para que este artefato possa ser usado em outros lugares.

Para cada artefato de linguagem: precisamos saber quais são as regras semânticas que precisamos e vamos verificar;

O código deve estar perfeito antes da tradução!

Gramática de Atributos

Uma gramática de atributos conecta a sintaxe com a semântica;

Cada regra de produção possui uma regra semântica com ações para modificar os valores de símbolos não terminais.

Um símbolo não terminal pode ter qualquer numero de atributos e não há limites para estes atributos.

Na forma:

Regras de Produção: $<𝑨> ::= <𝑩> <𝑪>$
Regras Semânticas: $𝑨.𝒂ttb := …; 𝑩.𝒂ttb := …; 𝑪.𝒂ttb := …$

As regras semânticas são usadas pelo compilador para permitir a análise estática ou para produzir a árvore sintática abstrata ainda durante o parse. A isso chamamos TRADUÇÃO SINTÁTICA DIRETA

Exemplo Gramática de Atributos

Regras de Produção	Regras Semânticas
$E1 = E2+T$ $E1 = E2-T$ $E = T$ $T1 = T2*F$ $T1 = T2/F$ $T = F$ $F1 = -F2$ $F = (E)$ $F = unsigned\_int$	$E1.attb = E2.attb+T.attb$ $E1.attb = E2.attb-T.attb$ $E.attb = T.attb$ $T1.attb = T2.attb*F.attb$ $T1.attb = T2.attb/F.attb$ $T.attb = F.attb$ $F1.attb = -F2.attb$ $F.attb = (E.attb)$ $F.attb = unsigned\_int.attb$

Atributos Sintetizados

Um atributo é dito sintetizado quando é computado a partir do seu valor e do valor dos seus filhos. Um atributo sintetizado $𝑋.𝑎$ em função de alguma combinação de $𝑌_𝑖.𝑎$ (bottom-up).

símbolo meramente ilustrativo, sem valor didático

Atributos Herdados

Um atributo é dito herdado quando é computado a partir do seu valor e do valor dos seus pais e irmãos. Um atributo herdado $𝑋.𝑎$ em função de alguma combinação de $𝑋.𝑎$ e algum $𝑌𝑗.𝑎$ (top-down).

Exemplo

Vamos determinar os atributos para uma linguagem aritmética simples com as regras de produção e atributos explicitados a seguir.

$PROGRAM \rightarrow DECL$ $STMT$
$DECL \rightarrow 𝑖𝑛𝑡$ $𝑖𝑑$
$STMT \rightarrow EXP⁡ = EXP$
$EXP \rightarrow 𝑖𝑑 | EXP + EXP | 1$

$env$ (ambiente, e.g. tabela de símbolos): sintetizada por $DECL$ e herdado por $STMT$;
$type$ (tipo da expressão); sempre sintetizado;
$cat$ ( categoria variável $[var, lvalue] \times valor [val, rvalue])$: sempre sintetizado.
$error$ para destacar possíveis erros.

Exemplo: atribuição

Vamos determinar os atributos para uma linguagem aritmética simples com as regras de produção e atributos explicitados a seguir.

$PROGRAM \rightarrow DECL$ $STMT \Rightarrow PROGRAM.env = DECL.env STMT.env$
$DECL \rightarrow 𝑖𝑛𝑡$ $𝑖𝑑$ $\Rightarrow DECL.env = \{identifier, int, var\}$
$EXP⁡ \rightarrow 1 \Rightarrow EXP.cat = val \wedge EXT.type=int$
$EXP \rightarrow 𝑖𝑑 \Rightarrow id.type = EXP.env.lookup(id) \wedge$
$ EXP.type = id.type \wedge EXP.cat = id.cat$
$EXP \rightarrow EXP1 + EXP2 \Rightarrow EXP.cat = val \wedge EXP1.env = EXP.env \wedge $
$ EXP1.env = EXP.env \wedge$
$EXP.type = EXP1.type = EXP1.type \wedge$ $error=\text{"Tipos diferentes"}$
$STMT \rightarrow EXP⁡1 = EXP2 \Rightarrow EXP2.env = STMT.env \wedge EXP1.env = STMT.env$
$\wedge$ $error=\text{"Tipos diferentes"} \wedge$ $ error=\text{"Se"} cat = val"$

Exemplo: observações

Gramáticas de atributo são excelentes para estruturação da verificação semântica.

Estas regras podem ser estendidas para atender operações e declarações mais complexas.

Acrescente mais campos aos nós da AST para incluir mais atributos.

Isto é só um exemplo.

Problemas da Análise Semântica

Manter a informação necessária (criar, acessar e atualizar): tabelas de símbolos.

Integrar a análise semântica no parser: AST - Abstract Sintatic Tree.

Computação das expressões semânticas: análise de tipos..

Fazer com que todo o processo seja rápido, muito rápido..

Só para lembrar

Árvores sintáticas são representações internas do compilador, criadas pelo parser e usadas para geração de código.

Cada pai representa uma operação, cada filho representa um operando.

Construindo a Árvore

Análise Estática e Dinâmica.

Análise Semântica Dinâmica

O compilador, ou interpretador, gera código para aprimorar a análise sintática durante a execução do código.

índices de arrays dinâmicos estão dentro dos limites;
erros aritméticos (divisão por zero);
variável sendo usada antes da declaração.

Cada vez mais comum em sistemas mistos. A analise estática é mais simples.

Análise Estática - Fluxo

Verificação do fluxo de controle:

Os comandos que fazem o fluxo de controle deixar uma construção precisam ter algum local para onde transferir o controle;
Exemplo: O comando break em C faz com que o fluxo de controle saia do while, for ou do switch mais interno.

Análise Estática - Unicidade

Um artefato de código precisa ser definido exatamente uma vez:

um identificador precisa ser declarado univocamente no mesmo nível;
definição de escopo para identificadores;
campos de tipos complexos (structs, class) não podem ser repetidos.

Análise Estática - Identificadores

Algumas vezes, precisamos repetir os identificadores:

em ADA o nome do bloco deve aparecer no começo e no fim do bloco;
em C++ os constructors devem ter o mesmo nome da classe;

Análise Estática - Tipos

Compatibilidade entre operador e operando:

um array sendo somado a um inteiro;
um double sendo usado como índice em um array;
um string sendo usado no lugar de um char.

A verificação de tipos é o coração da análise semântica.

Por que verificar tipos

Segurança para execução.

Detecção de erros em tempo de compilação.

Metáforas mas expressivas: overload, por exemplo.

Fornecer informações para o otimizador de código.

Identificação de tipos

Classificação dos tipos

Estáticos: sua definição é realizada em tempo de codificação e a verificação em tempo de compilação;

Dinâmicos: sua definição pode, ou não, ser realizada em tempo de codificação mas, sua verificação é realizada em tempo de execução.

Primitivos: não possuem estrutura interna. Ex.: inteiro, real, booleano, carácter, string, intervalo e enumeração.

Compostos: possuem uma estrutura interna composta por tipos básicos e outros tipos compostos. Ex.: ponteiros, estruturas, registros, vetores e matrizes.

Construídos: são tipos, geralmente compostos, definidos pelo programador. Ex.: typedef.

Estáticamente Tipadas

Linguagens estáticamente tipadas são aquelas em que o tipo da variável é conhecido durante o tempo de compilação: C, C++, Fortran, Pascal, Scala.
Uma vez que a variável tenha sido declarada com um determinado tipo, não é possível utilizar este identificador com qualquer outro tipo. Deve ser emitido um erro, ou warning, caso isso ocorra.

Dinâmicamente Tipadas

Linguagens dinâmicamente tipadas são aquelas em que o tipo de um identificador é verificado durante o tempo de execução: Javascript, PHP, Phyton, Ruby e Lisp.
Os tipos são atribuídos aos identificadores em tempo de execução o que resulta em código mais difícil de otimizar. E força a verificação do tipo a cada uso do identificador.

Fortemente Tipadas

Uma linguagem fortemente tipada é aquela em que o identificador está preso a um determinado tipo de dado: Python, Java;
Uma vez que um tipo seja atribuído a um determinado identificador, este identificador não poderá ser usado com tipos diferentes.

Fracamente Tipadas

Uma linguagem fracamente tipada é aquela em que os identificadores não estão presos a um determinado tipo de dado. Por exemplo, o PHP;
A cada uso do identificador é possível atribuir um tipo diferente de acordo com as necessidades do programador.