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 |
|---|---|
|
|
Atributos Sintetizados
Atributos Herdados
Gramáticas L&S
Em uma gramática S-attributed todos os atributos são sintetizados;
Uma gramática é dita L-attributed se a árvore de parse for percorrida sempre da esquerda para direita em deep-first:
- valores herdados são passados para os filhos da esquerda para direita;
- regras semânticas aplicadas imediatamente durante o parse.
- essencial para compiladores e interpretadores de uma passagem.
A gramática S-attributed é um caso especial das gramáticas L-attributed .
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.
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.
Verificando Tipos
Verificação de 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.
Estaticamente Tipadas
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.
Dinamicamente Tipadas
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 vez que um tipo seja atribuído a um determinado identificador, este identificador não poderá ser usado com tipos diferentes.
Fracamente Tipadas
A cada uso do identificador é possível atribuir um tipo diferente de acordo com as necessidades do programador.
Informações Semânticas
| Informação | Forma | Uso |
|---|---|---|
| Tabelas de Símbolos | Declarações | Expressões e declarações |
| Informação de tipo | Expressões e declarações | Operações |
| Constantes e variáveis | Expressões e declarações | Expressões e declarações |
| Registradores e Memórias | Compilador/interpretador | Geração de código |
| Valores literais | Constantes e variáveis | Expressões e declarações |
Verificação de Tipos
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..
Tabelas de Símbolos
Principais Funções
Mapeia identificadores para:$\text{𝑡𝑦𝑝𝑒, 𝑐𝑎𝑡, localização, outras propriedades}$
Mantém as operações necessárias para abertura e fechamento de escopos e localização de itens.
Queremos as complexidade $O(1)$ para encontrar qualquer atributo.
Usamos informações adicionais para manter o fluxo de código: operações de entrada e saída de escopo, por exemplo.
Em compiladores de múltiplos passos, a tabela de símbolos deve persistir durante todos os ciclos.
Linked Lists ou Hash Tables
Tabela de Símbolos - item
Tabela de Símbolos - itens
Tabela de Símbolos - Implementação
Para cada novo escopo: push uma tabela de símbolos novas no item (stack).
Crie a tabela de símbolos como a uma pilha feita com linked lists de tabelas de símbolos.
Os identificadores mais novos ficam no topo da pilha.
Busca: procure na pilha de tabelas de símbolos de cima para baixo.
Integrando a verificação semântica no parser
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
Tipos, e mais tipos
Definição de Tipos
Um tipo é uma classificação que representa um conjunto específico de dados. Esta classificação define as operações que podem ser realizadas com estes dados.
Definição de Sistema de Tipos
Um conjunto de regras para garantir a aplicação e verificação de tipos em artefatos de uma linguagem de programação.
Anotação de Tipos
Tipos de Tipos
Inferência
Exemplos: Sistemas de Tipos
Tipos são conjuntos
Por que tipos?
Só de Curiosidade
Exemplo de anotação
Só para lembrar 2!
Estáticos versus Dinâmicos
Exemplo: "a" + 1
Propriedades do Sistema de Tipos
Fluxo de Verificação
Matemática, sempre acaba na Matemática.
Para Pensar
Enumeração
Tuplas
Tuplas - Considerações
Vetores
União
Coproduto
Funções
Variant, Union
Variant, Union - Considerações
Cada campo usa o mesmo espaço de memória então o tamanho da union é o tamanho do maior campo definido.
Só Podemos usar um campo de cada vez. Se atribuirmos valores, ainda que corretos, para cada um dos campos em sequencia, apenas a última atribuição terá sentido.
Uma herança dos tempos que a memória era muito cara e reduzida.
Nestes tempos a uninion era uma forma bem razoável de manter uma metáfora consistente nos seus programas.
Structs
Structs - Considerações
As structs são representadas como um bloco de memória, grande o suficiente para armazenar todos os campos.
O campos são ordenados de acordo com a a ordem de declaração.
O compilador irá determiner o tamanho total e a posição dos campos em memória. Durante a execução o programa não entende a estrutura da struct.
Ou seja, a struct, como a definimos só existe em forma de artefato de Código e metáfora.
Vantagem das Structs
Sistema de Tipos: Definição.
Como fazer isso?
Em Linguagem Natural
Em Linguagem Natural - Exemplo
Uma declaração é bem formatada se:
Sua variável alvo está bem formatada;
Sua expressão fonte está bem formatada, e os tipos declarados da fonte e do alvo coincidem;
Uma condicional é bem formatada se sua expressão de teste for do tipo bool e tanto a opção then quanto a opção else estão bem formatadas.
O Python (CPython) é definido desta forma.
Cálculo de Sequentes
Cálculo de Sequentes - Exemplo
Como podemos verificar os tipos nas seguintes declarações em cálculo de sequentes?
$\text{𝑓𝑙𝑜𝑎𝑡 𝑓(𝑓𝑙𝑜𝑎𝑡 𝑥, 𝑓𝑙𝑜𝑎𝑡 𝑦) \{ 𝑟𝑒𝑡𝑢𝑟𝑛 𝑥+𝑦; \}}$
$𝑥 : 𝑓𝑙𝑜𝑎𝑡, 𝑦 : 𝑓𝑙𝑜𝑎𝑡 ⊢ 𝑥+𝑦 : 𝑓𝑙𝑜𝑎𝑡$
$\text{𝑖𝑛𝑡 𝑔(𝑖𝑛𝑡 𝑥, 𝑖𝑛𝑡 𝑦) \{ 𝑟𝑒𝑡𝑢𝑟𝑛 𝑥+𝑦; \}}$
$𝑥 : 𝑖𝑛𝑡, 𝑦 : 𝑖𝑛𝑡 ⊢ 𝑥+𝑦 : 𝑖𝑛𝑡$
Regras de Atribuição
Usamos o cálculo de sequentes para definir as regras de atribuição, verificação e checagem de tipos.
Lemos: se 𝐸1 tem tipo int e 𝐸2 tem tipo int então E1+E2 tem tipo int
Cálculo de Sequentes - Exemplo
Análise de Sequentes
Equivalência
Material de apoio
Você pode baixar o material de apoio clicando aqui
Referências
AHO, A. V. et al. Compiladores: princípios, técnicas e ferramentas. 2º. ed. Boston, MA, USA: Pearson Education Inc. , 2007.
Appel, Andrew W. Modern Compiler Implementation in Java, 2nd ed. Cambridge, 2002. (Editions in ML and C also available; the “tiger books”)
CASS, S. The 2016 Top Programming Languages. IEEE Spectrum, 2016. Disponível em:
Grune, Dick, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen. Modern Compiler Design. Wiley, 2000
Hogg, Jim. CSE-P501 Compilers. Washington University, 2005