Distinguir
Árvore concreta, AST e suas finalidades.
Centro de Estudos, Desenvolvimento e Inovação em Software — CEDIS | UnB
Estruturas de dados e representação interna do código-fonte
AST e tabela de símbolos · Semana 6 · teoria
CEDISRoteiro da aula
- 01Do código-fonte à representação interna
- 02Árvore sintática abstrata
- 03Tabela de símbolos e escopos
- 04Integração com Flex e Bison
- 05Erros, memória e aplicação ao projeto
CEDISObjetivos de aprendizagem
Interpretar
Nós, relações, precedência e travessias.
Modelar
Entradas e escopos da tabela de símbolos.
Integrar
Flex, Bison, AST e análise semântica.
CEDISPipeline até a representação interna
O parser normalmente constrói a AST; o analisador semântico percorre e anota essa árvore enquanto cria e consulta símbolos.
- Flex reconhece lexemas e retorna tokens.
- Bison reconhece produções e dispara ações.
- A AST preserva a estrutura relevante.
- A tabela registra nomes, tipos e escopos.
CEDIS
Árvore concreta e AST não são a mesma coisa
A AST elimina detalhes sintáticos que não alteram o significado estrutural do programa.
- Pontuação pode desaparecer.
- Categorias intermediárias podem ser condensadas.
- Operadores e relações relevantes permanecem.
CEDISatividade
Atividade 1 — Raiz da expressão
Qual operador ocupa a raiz da AST de a + b * 2?
CEDISO que uma AST precisa representar?
Expressões
Operadores, operandos e precedência.
Declarações
Tipo, identificador e inicialização.
Comandos
Atribuição, seleção, repetição e retorno.
Estruturas
Blocos, listas, funções e chamadas.
CEDISA precedência aparece na forma da AST
A árvore de a + b * 2 evidencia que a multiplicação é agrupada antes da soma.
- Folhas representam valores ou identificadores.
- Nós internos representam operações ou construções.
- A forma da árvore orienta análises e geração de código.
CEDISatividade
Atividade 2 — O que a AST remove?
Qual elemento normalmente não precisa aparecer na AST de uma chamada de função?
CEDISAST de uma declaração
Código-fonte
int soma = a + b * 2;
- Declaração de variável
- Tipo int
- Identificador soma
- Expressão inicializadora
Estrutura abstrata
- Nó de declaração
- Filho tipo: int
- Filho identificador: soma
- Filho expressão: + com subárvore *
CEDISAnatomia de um nó de AST
Categoria
Número, identificador, operação, declaração ou comando.
Dados
Valor, nome, operador, tipo ou posição no código.
Filhos
Referências para operandos, corpo, condição ou lista.
Anotações
Tipo inferido, símbolo resolvido ou informação de geração.
CEDISTipos de nós para uma linguagem pequena
Folhas
NO_NUMERO e NO_IDENTIFICADOR.
Expressões
NO_OPERACAO e NO_CHAMADA.
Declarações
NO_DECLARACAO e NO_PARAMETRO.
Comandos
NO_ATRIBUICAO, NO_IF e NO_WHILE.
CEDISTravessias da AST
1
Pré-ordem
Processa o nó antes dos filhos.
2
Em ordem
Útil em árvores binárias de expressões.
3
Pós-ordem
Processa os filhos antes do nó.
4
Aplicação
Tipos, impressão, liberação e geração de código.
CEDISPor que precisamos de uma tabela de símbolos?
Declaração
Registrar identificadores e impedir redeclarações inválidas.
Uso
Confirmar que um nome foi declarado e está visível.
Tipos
Recuperar o tipo para verificar expressões e atribuições.
Geração
Associar endereços, deslocamentos ou informações de destino.
CEDISInformações de uma entrada
Identidade e contexto
- Nome do símbolo
- Categoria: variável, função ou parâmetro
- Escopo de declaração
- Linha ou posição de origem
Semântica e geração
- Tipo declarado
- Parâmetros e retorno
- Estado de inicialização
- Endereço ou deslocamento
CEDISOperações essenciais
1
Entrar no escopo
Criar ou ativar um novo contexto.
2
Inserir
Registrar a declaração no escopo atual.
3
Buscar
Consultar do escopo interno para o externo.
4
Sair do escopo
Descartar ou desativar o contexto local.
CEDISEstruturas de implementação
Tabela hash
Busca média rápida e implementação comum.
Pilha de tabelas
Uma tabela por escopo ativo.
Árvore de escopos
Preserva relações pai–filho.
Lista encadeada
Simples, mas menos eficiente em tabelas grandes.
CEDIS
Escopos aninhados e ocultação
Uma declaração local pode ocultar temporariamente outra declaração com o mesmo nome em um escopo externo.
- Busca começa no escopo atual.
- Se não encontrar, sobe ao escopo pai.
- Redeclaração deve ser avaliada no escopo correto.
CEDISatividade
Atividade 3 — Informação indispensável
Qual informação é indispensável para validar o uso de um identificador?
CEDISatividade
Atividade 4 — Ordem da busca
Ao buscar um identificador, qual escopo deve ser consultado primeiro?
CEDISFluxo integrado do projeto
Os valores semânticos atravessam o parser e se transformam em nós conectados da AST.
- Flex retorna tokens e yylval.
- Bison reduz produções.
- Ações criam nós da AST.
- A análise semântica consulta símbolos.
CEDIS%union, %token e %type
Valores dos tokens
- NUM pode carregar um inteiro.
- ID pode carregar uma string.
- Flex atribui valores em yylval.
Valores dos não terminais
- expr pode carregar NoAST*.
- decl pode carregar NoAST*.
- %type associa o campo correto da union.
CEDIS
Construção da AST em ações do Bison
Cada redução pode produzir um nó e devolver seu endereço como valor semântico da produção.
- $$ representa o lado esquerdo.
- $1, $2 e $3 representam símbolos do lado direito.
- Os filhos formam a nova subárvore.
CEDISatividade
Atividade 5 — Valor de $$
Em uma ação do Bison, o que representa $$?
CEDISErros identificados com essas estruturas
Não declarado
Uso de identificador ausente nos escopos visíveis.
Redeclaração
Novo símbolo incompatível no mesmo escopo.
Tipos incompatíveis
Operação ou atribuição entre tipos inválidos.
Uso prematuro
Leitura antes de inicialização ou definição.
CEDISMemória e ciclo de vida
Criar
Alocar nós e verificar falhas de malloc.
Possuir
Definir quem é responsável por cada string e nó.
Percorrer
Usar funções recursivas defensivas.
Liberar
Desalocar AST, símbolos e estruturas auxiliares.
CEDISConexão com o projeto da equipe
Próximo incremento
- Definir tipos mínimos de nós.
- Criar funções construtoras.
- Fazer o parser devolver a raiz.
- Implementar tabela e escopos.
Materiais
- GitHub: https://github.com/sergioaafreitas/COMP1
- Vídeos: youtu.be/wINY109MG10
- youtu.be/Dd3DWRpqI40
- youtu.be/knV86FlSXJ8
CEDISReferências e materiais
- TREMBLAY, J. P.; SORENSON, P. G. Theory and Practice of Compiler Writing. Seções sobre árvores e tabelas de símbolos.
- WIRTH, N. Compiler Construction. Capítulos sobre parsing, símbolos e escopos.
- GNU Bison Manual. Semantic Values and Semantic Actions.
- Repositório da disciplina: https://github.com/sergioaafreitas/COMP1
- Material-base: Estruturas de dados e representação interna de código-fonte — Semana 6.
CEDISSíntese
A AST organiza o significado estrutural do programa; a tabela de símbolos resolve nomes, tipos e escopos. Juntas, sustentam a análise semântica e as etapas posteriores.