O material começa pela visão clássica de compilação e depois faz uma correção importante: o compilador propriamente dito transforma código-fonte em código assembly; assembler e linker são ferramentas separadas que continuam o caminho até o executável.
EntradaCódigo-fontePrograma escrito na linguagem de origem.
Análise léxicaTokensReconhece os átomos da linguagem.
Análise sintáticaASTReconhece a estrutura segundo a gramática.
Semântica + IRCódigo intermediárioInterpreta significado e prepara representação intermediária.
Back endAssemblyOtimização e geração do código de destino.
Depois do compilador: assembly → assembler → código objeto → linker → executável.
O que reconhecer em cada etapa inicial
Análise léxicaReconhece tokens; no material, é relacionada a linguagens regulares e expressões regulares.
Análise sintáticaReconhece a estrutura da expressão; trabalha com gramáticas livres de contexto.
Análise semânticaVerifica o significado e a validade das expressões, incluindo uso de variáveis.
Geração de códigoVem depois das análises e produz representações até chegar ao assembly.
- Alfabeto Σ: conjunto finito de símbolos.
- Símbolo: elemento do alfabeto.
- Palavra: sequência de símbolos; o tamanho é denotado por |x|.
- ε: palavra vazia, de comprimento zero.
- Σ*: conjunto de todas as palavras possíveis sobre Σ.
- Linguagem L: subconjunto de Σ*. O problema implícito é reconhecer se uma palavra pertence ou não à linguagem.
Conexão com compiladores: o lexer reconhece padrões regulares; o parser precisa de estrutura livre de contexto.
Lexer
Expressões regulares definem os tokens válidos. O lexer lê o código-fonte e transforma o texto em uma sequência de tokens. Nos primeiros exemplos, a linguagem reconhecia INT, FLOAT e SOMA.
INT\d+ — um ou mais dígitos.
FLOAT\d+\.\d+ — dígitos, ponto e dígitos.
Lexer ≠ parser: 2++ pode ser tokenizado como INT SOMA SOMA e ainda assim ser sintaticamente inválido. Já um símbolo não previsto por nenhum token provoca erro léxico.
GLC
Uma Gramática Livre de Contexto é apresentada como G=(V, Σ, R, S): variáveis/não terminais, alfabeto/terminais, regras de produção e símbolo inicial.
S → X | S + X
X → a | b
Parser
O parser verifica se a sequência de tokens obedece à gramática. O material usa Lex/Flex para lexer e Yacc/Bison para parser; em Python, ambos aparecem na biblioteca PLY (Python Lex-Yacc).
Nessa aula não houve slides anexados. O resumo fornecido registra os seguintes pontos:
- Gramática para expressões com soma usando INT ou FLOAT, retomando a Aula 03.
- Árvore de Derivação Sintática: mostra quais regras da gramática foram usadas para derivar a expressão.
- AST (Árvore de Sintaxe Abstrata): mostra a estrutura da expressão sem carregar as regras de substituição da derivação; no material da disciplina, ela fica centrada nos terminais/tokens relevantes.
- Noção intuitiva de avaliação da AST.
- Modificação da gramática para permitir subtração.
- Modificação da gramática para permitir multiplicação, exigindo uma nova variável gramatical para organizar precedência.
Árvore de derivaçãoExpõe não terminais e regras usadas para chegar aos terminais.
ASTResume a estrutura sem mostrar todo o caminho de derivação.
Aula 05 · lacuna de fonte
Material da Aula 05 não foi anexado
Sem invenção: o caderno não atribui conteúdo específico à Aula 05. A Aula 06 informa que a gramática apresentada já resulta das duas aulas anteriores, e por isso o estado consolidado reaparece na sequência.
A gramática passa a ser organizada em “andares” para representar precedência. Operações de menor precedência são geradas em níveis mais altos e ficam mais próximas da raiz; por isso, são avaliadas mais tarde.
expr → expr + termo | expr - termo | termo
termo → termo * fator | termo / fator | fator
fator → INT | FLOAT
Leitura estrutural: soma/subtração ficam no nível de expr; multiplicação/divisão no nível de termo; números aparecem em fator.
A aula trabalha explicitamente a construção de árvore de derivação e AST para expressões como 4+7*3+8 e 2.5*4*5.
A árvore de derivação mostra todas as variáveis e regras aplicadas. A AST mantém a relação hierárquica relevante entre os terminais. Para 4+7*3+8, a multiplicação fica abaixo das somas, refletindo sua precedência.
Abaixo ficam duas árvores separadas para a mesma expressão. A primeira usa a gramática consolidada com stmt como símbolo inicial; a segunda é a AST já abstraída, contendo apenas os números e operadores relevantes.
1Árvore de derivaçãoComeça em stmt e mostra as regras da gramática
2ASTSomente números e operadores
A avaliação acontece “de baixo para cima”: primeiro resolve-se a multiplicação 7*3=21, depois 4+21=25 e por fim 25+8=33. O próprio material liga AST à análise semântica e à avaliação.
- Cada subtipo de Nó terá um método
avalia() que calcula o valor da subárvore.
- NoNum: retorna o valor do número armazenado.
- NoOperacao: avalia os filhos esquerdo e direito e aplica a operação.
Para dar prioridade máxima a expressões entre parênteses, a gramática passa a permitir que fator gere uma expressão parentizada:
expr → expr + termo | expr - termo | termo
termo → termo * fator | termo / fator | fator
fator → INT | FLOAT | ( expr )
Consequência: 4*(2+3) consegue derivar o conteúdo dos parênteses voltando recursivamente de fator para expr.
A linguagem deixa de processar apenas contas isoladas e passa a aceitar criação e uso de variáveis. O interpretador precisa ler uma sequência de linhas e manter estado entre elas.
stmt → expr | ID = expr
expr → expr + termo | expr - termo | termo
termo → termo * fator | termo / fator | fator
fator → INT | FLOAT | ID | ( expr )
ID[a-zA-Z]+ no material: identificadores compostos por letras.
Tabela de Símbolos (ST)Dicionário das variáveis existentes; pode guardar identificador e informações como valor, tipo e tamanho.
Análise semântica: a ST permite identificar uso de variável inexistente (erro) e, no caso de compiladores, variável não inicializada pode gerar warning.
Para suportar variáveis, a AST ganha novos tipos de nó e o método avalia() passa a receber a tabela de símbolos.
NoAtribuicaoRepresenta ID = expr. Guarda o identificador e a raiz da expressão a ser avaliada e associada à variável.
NoVarRepresenta o uso de uma variável dentro de uma expressão; consulta a ST para obter o valor associado.
raio = 3
area = 3.14*raio*raio
altura = 10
volume = area*altura
ST final:
raio → 3
area → 28.26
altura → 10
volume → 282.6
Fluxo mental: lexer reconhece ID e operadores → parser constrói a AST → avaliação consulta/atualiza ST → uso de identificador inexistente produz erro semântico.
