flowchart TB
subgraph distancia["Eixo 1 — distância semântica entre fonte e alvo"]
direction LR
M["montador<br/>correspondência quase um para um"] --> T["tradutor entre linguagens<br/>de alto nível"] --> C["compilador para<br/>código de máquina"]
end
subgraph tempo["Eixo 2 — quando a execução acontece"]
direction LR
AN["análise antes,<br/>execução depois"] --> CO["compilação"]
AF["análise e execução<br/>no mesmo momento"] --> IN["interpretação"]
end
distancia --> HIB["sistemas híbridos<br/>compilam para máquina virtual<br/>e interpretam o resultado"]
tempo --> HIB
1 Módulo 1: Panorama da Compilação e Linguagens Formais — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o mapa que abre o semestre; nada é demonstrado por inteiro, e para isso existem a versão completa do material deste módulo e o livro. Use este texto para conferir se você consegue situar cada assunto — que é o critério de sucesso do módulo.
Três programas quebrados. O primeiro esqueceu um ponto e vírgula e leva bronca imediata, com linha e coluna. O segundo soma um texto a um número e leva bronca depois, com outro vocabulário. O terceiro entra num laço infinito e não leva bronca nenhuma. Entenda por que são três destinos diferentes e você terá o semestre inteiro na cabeça antes de começá-lo.
1.1 O que significa compilar
Um compilador é um programa que lê programas: a entrada tem comportamento, a saída também, e o trabalho é transformar um no outro sem mexer no significado. Dadas a linguagem-fonte L_f e a linguagem-alvo L_a, um tradutor é uma função parcial T que leva cada programa p \in L_f ou a um programa T(p) \in L_a, ou a um conjunto não vazio de diagnósticos. Parcial de propósito: nem todo texto é programa, e o tradutor tem obrigação de dizer isso em vez de produzir lixo. Plural de propósito: quem reporta só o primeiro erro é insuportável de usar.
Escrevendo \llbracket p \rrbracket_{L}(x) para o resultado de rodar p sobre a entrada x, o contrato de correção é esta igualdade:
\llbracket T(p) \rrbracket_{L_a}(x) = \llbracket p \rrbracket_{L_f}(x).
Guarde essa linha: é ela que a otimização coloca sob pressão. Transformação que muda o resultado num único caso de borda não é otimização ousada, é defeito.
E a distinção que mais confunde cabe numa palavra: quando. O compilador não executa p; produz T(p), que roda depois. O interpretador recebe p e a entrada e devolve o resultado agora. Compilar paga a análise uma vez e amortiza; interpretar paga a cada execução, às vezes a cada volta do laço — em troca, quem interpreta sabe o valor de cada variável e o tipo real de cada objeto, e por isso aguenta linguagens muito dinâmicas. O montador tem fonte que já corresponde uma para uma às instruções da máquina: formalmente é compilador, e ganha nome próprio porque nada de difícil sobrou. Já o tradutor entre linguagens de alto nível precisa preservar estrutura, nomes e formatação, luxo que um gerador de código de máquina não tem.
Pare e pense. Diante de um sistema híbrido, qual é a pergunta produtiva? Não é “isso é compilador ou interpretador?”, e sim: o que foi decidido antes da execução e o que foi adiado?
1.2 As fases e a arquitetura por dentro
Se você sair daqui tendo decorado seis nomes, eu falhei. Uma fase se define por três coisas: o que recebe, o que produz e que erros só ela detecta. A terceira é a que salva na prática — em dúvida sobre onde colocar uma checagem, pergunte qual é a primeira fase que já dispõe da informação necessária.
flowchart LR
A["texto-fonte<br/>sequência de caracteres"] --> B["análise léxica"]
B --> C["sequência de tokens"]
C --> D["análise sintática"]
D --> E["árvore sintática"]
E --> F["análise semântica"]
F --> G["árvore anotada<br/>e tabela de símbolos"]
G --> H["geração intermediária"]
H --> I["representação intermediária"]
I --> J["otimização"]
J --> I
I --> K["geração de código"]
K --> L["código da máquina-alvo"]
subgraph analise["Análise (frente)"]
B
C
D
E
F
G
end
subgraph sintese["Síntese (retaguarda)"]
H
I
J
K
end
A análise léxica decide que pattern é uma palavra e não sete letras, que 123.45 é um número só, e joga fora espaço e comentário. O lexema é a subcadeia reconhecida; o token é o par categoria mais atributos, e entre eles está sempre a posição, porque as fases seguintes precisarão reportar erro e este é o único lugar onde a posição existe naturalmente. A sintática descobre o ponto e vírgula faltante, porque a sequência de tokens não deriva da gramática. A semântica é onde morre o meu segundo programa, e o adjetivo é generoso: ela não confere se o programa faz o que você queria, e sim condições de boa formação dependentes de contexto, do tipo “todo nome usado precisa ter sido declarado”.
Depois vem, em muitos compiladores, a representação intermediária, independente de fonte e de máquina. Parece trabalho a mais; o argumento é combinatório: para m linguagens e n máquinas sem ela, você escreve m \times n tradutores; com ela, m + n peças. A otimização vai de representação intermediária a representação intermediária com o mesmo significado; o nome é infeliz, porque ninguém produz o programa ótimo — achá-lo é indecidível. A geração de código se decompõe em três subproblemas entrelaçados: que instruções realizam cada operação, em que ordem emiti-las e que valores ficam em registradores.
| Fase | Recebe | Produz | Detecta |
|---|---|---|---|
| Léxica | caracteres | tokens | símbolo desconhecido, literal malformado |
| Sintática | tokens | árvore sintática | estrutura inválida, delimitador aberto |
| Semântica | árvore | árvore anotada, tabela de símbolos | nome não declarado, tipo incompatível |
| Geração intermediária | árvore anotada | representação intermediária | — |
| Otimização | intermediária | intermediária | — |
| Geração de código | intermediária | código da máquina-alvo | recurso insuficiente |
Há aí uma assimetria que quase ninguém diz em voz alta: a análise é reconhecimento, com teoria madura e algoritmos ótimos; a síntese é otimização combinatória, difícil no caso geral — se o tom do curso mudar na segunda metade, é o objeto que mudou, não você. Duas responsabilidades não pertencem a fase nenhuma e são usadas por todas: a tabela de símbolos e o tratamento de erros. E não confunda fase, unidade lógica definida pelas interfaces, com passagem, que é uma travessia completa da representação: o léxico costuma entregar um token por vez sob demanda do sintático, o que dá duas fases numa travessia só.
Dois marcos ensinam mais que qualquer “no início da computação”: o compilador de FORTRAN entregue em 1957 para o IBM 704, cujo objetivo declarado era gerar código competitivo com o de um bom programador humano, e o relatório de ALGOL 60, primeiro a publicar a sintaxe de uma linguagem como gramática formal.
flowchart LR
subgraph teoria["Linha da teoria"]
direction LR
TU["1936 · Turing<br/>modelo de computação<br/>e indecidibilidade da parada"] --> CH["1956 · Chomsky<br/>três modelos de descrição"]
CH --> CH2["1959 · Chomsky<br/>propriedades formais das gramáticas"]
CH2 --> RS["1959 · Rabin e Scott<br/>autômatos finitos e decisão"]
end
subgraph engenharia["Linha da engenharia"]
direction LR
HO["início dos anos 1950<br/>Grace Hopper · A-0 no UNIVAC I"] --> FO["1957 · Backus e equipe<br/>FORTRAN no IBM 704"]
FO --> AL["ALGOL 60 · notação de Backus e Naur<br/>sintaxe publicada como gramática"]
AL --> KN["1965 · Knuth<br/>tradução da esquerda para a direita"]
KN --> TH["1968 · Thompson<br/>expressão regular em autômato"]
TH --> BE["anos 1970 · Unix<br/>geradores de analisadores"]
end
CH2 -.-> AL
RS -.-> TH
1.3 O mapa teórico: gramáticas, linguagens e máquinas
A pergunta deste andar é: dada uma classe de linguagens, que máquina basta para reconhecê-las? Um alfabeto \Sigma é um conjunto finito e não vazio de símbolos; uma cadeia é uma sequência finita de símbolos de \Sigma, com \varepsilon de comprimento zero; e uma linguagem sobre \Sigma é qualquer subconjunto de \Sigma^*. A generalidade é o que dá poder ao aparato: tanto o conjunto dos programas corretos quanto o dos programas que terminam são linguagens nesse sentido, e a diferença entre eles está na dificuldade de decidir a pertinência. Todo compilador, na metade de análise, é um reconhecedor.
Como linguagem infinita não se descreve listando elementos, usamos descrições finitas: gramáticas geram, autômatos reconhecem. Uma gramática é G = (V, \Sigma, P, S), e a linguagem gerada é
L(G) = \{\, w \in \Sigma^* \mid S \Rightarrow^* w \,\}.
A ideia de Chomsky foi restringir progressivamente a forma das produções: tipo 0 irrestrita; tipo 1 com |\alpha| \le |\beta|, de modo que as formas sentenciais nunca encurtam; tipo 2 com um único não terminal à esquerda, e por isso substituição independente do contexto; tipo 3 na forma A \to aB ou A \to a. Vale \mathcal{L}_3 \subsetneq \mathcal{L}_2 \subsetneq \mathcal{L}_1 \subsetneq \mathcal{L}_0, com cada inclusão própria.
A separação que mais pesa está entre os dois primeiros andares. Em S \to a\,S\,b \mid \varepsilon, a única forma de introduzir um a também introduz um b à direita, e a linguagem gerada é o conjunto das cadeias a^n b^n — livre de contexto e não regular, porque o não terminal fica no meio, com terminal de cada lado, que é a assinatura do aninhamento. Já A \to a\,A \mid b gera a^n b, e não há nada a lembrar. A diferença é mínima na aparência e máxima nas consequências, porque a forma das produções determina quanta memória o reconhecimento exige.
Pergunta para levar adiante. Por que uma máquina com número finito de estados não reconhece as cadeias com tantos a quantos b, nessa ordem? Seria preciso lembrar quantos a foram vistos, e esse número é ilimitado. É essa frase que obriga todo compilador a ter duas fases de análise em vez de uma.
Cada classe corresponde a um modelo de máquina, e a tabela se lê como escala de memória: o autômato finito não guarda nada além do estado atual; o de pilha ganha memória ilimitada com disciplina restrita, que é o que casa delimitadores aninhados; os dois de cima têm acesso livre.
| Tipo | Gramática | Classe | Reconhecedor |
|---|---|---|---|
| 3 | regular | regulares | autômato finito |
| 2 | livre de contexto | livres de contexto | autômato de pilha não determinístico |
| 1 | sensível ao contexto | sensíveis ao contexto | autômato linearmente limitado |
| 0 | irrestrita | recursivamente enumeráveis | máquina de Turing |
Um detalhe que passa batido: para autômatos finitos o não determinismo não aumenta o poder de reconhecimento; para autômatos de pilha, aumenta. Daí vem metade das dificuldades da análise sintática, porque o compilador precisa de analisador determinístico e só trabalha com as subclasses que o admitem.
flowchart TB
subgraph T0["Tipo 0 — irrestritas · máquina de Turing"]
subgraph T1["Tipo 1 — sensíveis ao contexto · autômato linearmente limitado"]
subgraph T2["Tipo 2 — livres de contexto · autômato de pilha"]
subgraph T3["Tipo 3 — regulares · autômato finito"]
LEX["análise léxica<br/>categorias de tokens"]
end
SIN["análise sintática<br/>estrutura aninhada"]
end
SEM["condições dependentes de contexto<br/>verificadas por código, não por gramática"]
end
IND["território indecidível<br/>terminação e propriedades do comportamento"]
end
Percorreremos os dois andares de baixo com definição, demonstração e implementação: as regulares fundamentam a análise léxica, as livres de contexto fundamentam a sintática. Os dois de cima ficam panorâmicos — o sensível ao contexto é teoricamente adequado às condições dependentes de contexto e inviável na prática, então a engenharia as verifica com código escrito à mão. E a advertência: a hierarquia classifica por poder de descrição, não por custo, e não captura ambiguidade, que é propriedade da gramática e, para um compilador, é intolerável.
1.4 O que nenhum compilador pode fazer
Volto ao terceiro programa. O compilador não avisa do laço infinito não por preguiça de quem o escreveu, mas porque é impossível, com demonstração. Turing mostrou, em 1936, que não existe procedimento mecânico que decida, para todo programa e toda entrada, se a execução termina; o argumento é de autorreferência, e a impossibilidade é lógica, não tecnológica. E vai além da terminação: qualquer propriedade não trivial do comportamento de um programa é indecidível.
Critério prático para o semestre. Antes de fazer o seu compilador detectar alguma coisa, pergunte se ela é propriedade do texto ou do comportamento. Se for do comportamento, ou você aceita uma aproximação conservadora — “certamente não” ou “talvez sim”, errando sempre para o mesmo lado —, ou está tentando resolver o irresolvível.
1.5 A infraestrutura que vem antes da primeira fase
O impulso natural é começar pelo analisador léxico. Eu defendo que não: há uma camada que todas as fases usam e que, se não existir desde o primeiro dia, será improvisada ali e replicada mal nas seguintes.
flowchart TB
SRC["arquivo-fonte carregado uma vez<br/>com índice de início de cada linha"] --> POS["posição = deslocamento bruto<br/>convertido em linha e coluna por busca binária"]
POS --> DIAG["coleção de diagnósticos<br/>severidade · posição · mensagem"]
LEX["análise léxica"] --> DIAG
SIN["análise sintática"] --> DIAG
SEM["análise semântica"] --> DIAG
GER["geração de código"] --> DIAG
DIAG --> MAIN["programa principal<br/>consulta se há erros e decide parar ou seguir"]
MAIN --> SAI["saída no formato arquivo, linha, coluna,<br/>severidade e mensagem"]
A primeira peça é a posição: o par deslocamento bruto mais linha e coluna contadas a partir de um, duplicidade proposital porque as fases trabalham com deslocamento e as pessoas leem linha e coluna. Converter varrendo o texto custa tempo proporcional ao arquivo a cada erro reportado; indexe o início de cada linha uma vez, no carregamento, e converta por busca binária. É assim que a implementação de referência da Peneira começa:
struct Position {
std::size_t offset;
std::size_t line;
std::size_t column;
};
class SourceFile {
public:
static SourceFile fromText(std::string name, std::string text);
// Converte deslocamento em linha e coluna por busca binária no índice.
Position positionAt(std::size_t offset) const;
private:
std::vector<std::size_t> lineStarts_;
};Uma armadilha do nosso ambiente, em que o fim de linha usa dois caracteres: lido em modo texto, o par vira um caractere só e os deslocamentos deixam de bater com os bytes do arquivo. Leia em modo binário. A segunda peça é a política de reporte: ou você lança exceção e interrompe a fase, ou registra o problema numa coleção compartilhada e segue, deixando a decisão de parar para o programa principal. A segunda produz compilador utilizável, e fase que não decide sobre continuação pode ser testada isoladamente. Um diagnóstico é a tripla severidade, posição e mensagem. A terceira peça não é código, é política: nível alto de avisos, extensões não padronizadas desligadas e todo aviso convertido em erro — as flags exigidas aqui. Ligue no primeiro arquivo; ligar depois produz um muro de erros, e a reação natural diante do muro é desligar de novo.
1.6 O caso conduzido e o que o seu grupo entrega
Tudo aqui gira em torno de um caso conduzido: a Peneira, uma linguagem pequena para reconhecimento de padrões em texto, que declara padrões, escreve regras com condição e emite resultados rotulados. A razão da escolha vale mais que a escolha: num tema clássico, os autômatos viram encanamento escondido no analisador léxico; na Peneira, o produto da compilação é ele mesmo um motor de autômatos, e o mesmo módulo serve os dois níveis — o dos tokens da linguagem e o dos padrões declarados pelo usuário.
O critério da boa linguagem de estudo é o que interessa para você: pequena o bastante para caber no prazo e rica o bastante para exigir todas as fases — mais de uma categoria léxica, com pelo menos uma descrita por padrões; construção aninhada de profundidade arbitrária; nomes declarados num ponto e usados em outro; mais de um tipo de valor, com operação restrita a um deles; e efeito observável. Falhe num desses pontos e uma fase fica sem conteúdo. Este é o contrato do projeto do seu grupo, e a entrega do módulo é a proposta de domínio com exemplos escritos antes de qualquer formalização, mais o ambiente em modo estrito e o repositório de pé. Recusar a proposta por escopo grande demais é possibilidade real: recusar agora custa uma sessão de tutoria; recusar lá na frente custa o semestre.
1.7 Síntese
Compilar é traduzir sob um contrato de correção que é uma igualdade entre significados, e o que separa compilador de interpretador não é o que se faz, é quando se faz. Por dentro, o compilador se decompõe em fases definidas pelas interfaces e pelas responsabilidades de verificação; por baixo, há um mapa de quatro andares em que gramáticas geram e autômatos reconhecem, e nós moramos nos dois de baixo. Volte agora aos três programas: o primeiro morre na análise sintática, o segundo na semântica, e o terceiro não morre em lugar nenhum, porque pergunta sobre comportamento. Não pule a parte formal dos próximos módulos — é ela que permite escrever um analisador léxico que você sabe estar correto, em vez de um que passa nos testes de que você lembrou.