flowchart LR
A["Conjuntos,<br/>relações e funções"] --> D["Definições formais<br/>de autômatos"]
A --> E["Minimização<br/>por partições"]
B["Técnicas de<br/>demonstração"] --> F["Equivalência<br/>entre modelos"]
B --> G["Prova de que uma<br/>linguagem não é regular"]
C["Estruturas<br/>de dados"] --> H["Tabela de transições,<br/>pilha, tabela de símbolos"]
I["Grafos dirigidos<br/>e percursos"] --> J["Determinização,<br/>fecho vazio, poda"]
K["Maturidade de<br/>programação"] --> L["O projeto inteiro,<br/>módulo a módulo"]
M["Vocabulário de<br/>arquitetura"] --> N["Ambientes de execução<br/>e geração de código"]
1 Módulo 0: Nivelamento — A Bagagem Necessária
Bem-vindo. Este é o único módulo do semestre que não ensina nada de novo: ele existe para acordar o que você já sabe. Percorra os seis blocos, marque os que descrevem algo que você não lembra bem e concentre a revisão só nesses. É material de consulta — você vai voltar aqui no meio do semestre.
1.1 O problema: duas competências, uma disciplina
Numa semana eu peço que você demonstre que certa linguagem não pode ser reconhecida por determinado modelo de máquina — não é para argumentar que parece difícil, é para provar que é impossível. Na semana seguinte eu peço que você implemente, numa linguagem que expõe a gestão de memória, o algoritmo que reconhece as linguagens que podem. As duas exigências vêm de lugares bem diferentes da sua formação, e é raro que estejam igualmente vivas em quem chega ao sexto termo.
Já vi estudante excelente em programação travar diante de um enunciado com três quantificadores alternados, e já vi estudante confortável com demonstrações escrever um programa que vazava memória a cada expressão regular compilada. Nenhum dos dois casos é falta de capacidade: é falta de aquecimento. Um autômato finito é, literalmente, uma quíntupla cujos componentes são conjuntos e funções; se ler uma tupla dessas custa esforço, todo o seu esforço vai para decifrar a forma e não sobra atenção para o conteúdo, que é a ideia inteira. Nada disso é novo, e por isso esta revisão é enviesada de propósito — enfatiza o que os próximos módulos vão cobrar e passa rápido pelo resto.
Uma pergunta honesta antes de seguir. Quando foi a última vez que você escreveu uma demonstração completa e entregou para alguém conferir? Se a resposta for “primeiro termo”, você acabou de descobrir onde investir o tempo desta revisão.
1.2 A língua das definições: conjuntos, relações e funções
Abra a definição formal de qualquer modelo desta disciplina e encontra a mesma estrutura: uma tupla de conjuntos e funções. Isso não é preciosismo — é o que permite dizer, sem ambiguidade, o que muda ao trocar de modelo. A diferença inteira entre determinístico e não determinístico cabe no tipo de um componente: a função de transição deixa de devolver um estado e passa a devolver um conjunto de estados. Toda a distinção conceitual vira uma mudança de contradomínio.
A distinção entre pertinência e inclusão parece trivial e aqui morde, porque os elementos de um conjunto frequentemente são conjuntos: na determinização, um estado do autômato construído é um conjunto de estados do original, e confundir as duas notações produz demonstrações que não fecham.
O vazio merece atenção desproporcional ao tamanho. Ele é subconjunto de todo mundo, não é a mesma coisa que o conjunto cujo único elemento é o vazio, e uma afirmação universal sobre os seus elementos é verdadeira por vacuidade — o que faz o estado morto do autômato determinizado se comportar corretamente sem tratamento especial. Guarde também a diferença entre a linguagem vazia e a linguagem cujo único elemento é a cadeia de comprimento zero: concatenar com a primeira zera tudo, com a segunda não muda nada.
Uma relação binária é apenas um conjunto de pares, e das propriedades usuais a transitividade gera a operação de frequência mais incômoda: o fecho reflexivo e transitivo, que se calcula acrescentando pares até não haver mais o que acrescentar. Esse padrão — repetir até nada mudar — é o padrão de cálculo mais frequente do semestre.
Agora o ponto que mais rende. Uma relação de equivalência é reflexiva, simétrica e transitiva, e suas classes formam uma partição. A recíproca também vale, e é aí que está o valor: toda partição é uma equivalência disfarçada.
flowchart TD
P0["Partição inicial:<br/>não finais | finais"]
P1["Refinamento 1:<br/>separa estados que,<br/>lendo o mesmo símbolo,<br/>caem em blocos diferentes"]
P2["Refinamento 2:<br/>repete o teste sobre<br/>os blocos recém-criados"]
P3["Estabilizou:<br/>nenhum bloco se parte mais"]
Q["Autômato mínimo:<br/>um estado por bloco"]
P0 --> P1 --> P2 --> P3 --> Q
P3 -. "cada partição refina a anterior;<br/>o conjunto de estados é finito,<br/>logo a sequência para" .-> P0
Por que insisto? Porque o algoritmo clássico de minimização parte de uma partição grosseira — finais de um lado, não finais de outro — e a refina até estabilizar. Quem sabe que partição é equivalência disfarçada entende que o algoritmo constrói a maior equivalência compatível com o comportamento do autômato; quem não sabe executa os passos certos e não sabe o que obteve. O mesmo vocabulário reaparece num teorema adiante, que caracteriza as linguagens regulares contando classes de equivalência sobre cadeias.
Sobre funções, duas distinções voltam. Contradomínio não é imagem: os estados fora da imagem da transição que também não são iniciais são inalcançáveis e podem sumir sem alterar a linguagem. E total não é parcial: a definição de autômato determinístico exige transição total, cômodo nas demonstrações, enquanto implementações reais frequentemente a deixam parcial. A conversão é barata — acrescenta-se o estado morto, absorvente, para onde vão as transições ausentes.
Fecho com o conjunto das partes, cuja notação lembra o tamanho: o algoritmo de subconjuntos constrói um determinístico cujos estados vivem ali, então n estados podem virar 2^n. E uma calibração final: o conjunto das cadeias sobre um alfabeto finito é enumerável e o das linguagens não é, e como todo programa é uma cadeia finita, existem muito mais linguagens do que programas capazes de reconhecê-las. Os resultados de impossibilidade que virão não são acidentes de engenhosidade: são aritmética de cardinais.
1.3 Demonstrar: o que conta como prova
Esta é a competência que mais separa quem atravessa a primeira metade da disciplina com tranquilidade de quem sofre nela.
Uma demonstração estabelece a verdade de uma afirmação a partir de afirmações já aceitas, por passos individualmente verificáveis por quem lê. Ela não é verificação em exemplos, porque testar dez casos nada diz sobre os infinitos restantes, nem explicação persuasiva, porque um argumento pode ser convincente e errado. Repare na assimetria: para refutar uma afirmação universal basta um contraexemplo; para estabelecê-la, exemplo nenhum serve.
Na prova direta supõe-se a hipótese e chega-se à conclusão, e toda a habilidade está em escolher o que desdobrar primeiro. A heurística que quase sempre funciona é desdobrar as definições antes de tentar qualquer coisa esperta. A contraposição inverte e nega a implicação, dando a mesma afirmação, e o sintoma que sugere usá-la é hipótese pobre com conclusão rica.
Erro de higiene lógica que produz estrago real
A contraposição de “se P então Q” é “se não Q então não P”. Ela não é “se não P então não Q”, que é outra coisa e não decorre do original. É o erro lógico mais comum em prova de estudante, e difícil de flagrar no próprio texto porque as duas frases soam igualmente naturais em português.
Na prova por contradição supõe-se a negação do que se quer demonstrar e deriva-se um absurdo. Escreva os três movimentos explicitamente — enuncie a negação com precisão, derive consequências até a contradição, declare e conclua —, porque a parte mal executada é quase sempre a primeira. A demonstração mais importante da primeira metade do semestre, a de que certa linguagem não pode ser reconhecida por autômato finito algum, tem essa forma: provas de impossibilidade são sempre assim, porque não se exibe um objeto que não existe.
De indução você precisa das duas formas, e a forte é mais conveniente aqui, porque muitos argumentos se apoiam em subestruturas de tamanho arbitrário. Mais importante ainda é a indução estrutural: sempre que um conjunto é definido recursivamente, a propriedade se demonstra com um caso por regra de construção — e praticamente tudo aqui é definido assim.
Repara nisso, que é a ponte entre a matemática e o seu código. A estrutura de uma função recursiva sobre um objeto é idêntica à da demonstração por indução estrutural sobre ele: a função que percorre uma árvore tem um caso por construtor, e a prova de correção tem os mesmos casos. Esquecer um caso vira buraco visível.
Agora o alerta que motiva o bloco. Vários enunciados centrais têm alternância de quantificadores com três ou mais níveis. O caso emblemático tem quatro: existe um número, tal que para toda cadeia longa o bastante, existe uma decomposição com certas restrições, tal que para todo expoente a cadeia bombeada continua na linguagem. Demonstrar que uma linguagem não é regular consiste em negar isso, trocando cada quantificador pelo outro.
flowchart LR
A["Adversário escolhe N<br/>(para todo N)"] --> B["Você escolhe a cadeia w,<br/>já sabendo N<br/>(existe w)"]
B --> C["Adversário escolhe<br/>a decomposição admissível<br/>(para toda decomposição)"]
C --> D["Você escolhe o expoente i,<br/>sabendo tudo o que veio antes<br/>(existe i)"]
D --> E["A cadeia bombeada<br/>cai fora da linguagem:<br/>contradição"]
Internalize a negação como um jogo, porque isso torna a ordem operacional em vez de simbólica. O adversário escolhe o número e você não sabe qual, então seu argumento tem de valer para qualquer um. Você escolhe a cadeia em função dele, então escolha a que mais atrapalha. O adversário escolhe a decomposição, então cubra todas as admissíveis. E você escolhe o expoente por último, sabendo tudo. Quem inverte um passo produz demonstração que parece certa e não é, e o pior é que a conclusão costuma ser verdadeira, o que faz o erro passar despercebido. Se houver um único tópico deste módulo em que vale investir tempo extra, é este: não porque a técnica seja difícil, mas porque o erro é silencioso.
Fecho com dois defeitos. Indução cujo passo não invoca a hipótese quase sempre tem buraco. E a demonstração por notação, símbolos parecendo argumento, se detecta com um teste implacável: pegue cada passo e pergunte qual definição, hipótese ou teorema o autoriza.
1.4 Estruturas de dados: o critério de escolha
Um compilador é um passeio guiado pelas estruturas clássicas, com a particularidade de que cada uma aparece onde o padrão de uso a favorece. Nada disso será reensinado; tudo será usado. Por isso o que quero recuperar não é implementação, e sim o critério de escolha.
flowchart TD
L["Analisador léxico"] --> LT["Tabela de transições:<br/>vetor indexado por<br/>estado e símbolo"]
S["Analisador sintático"] --> SP["Pilha<br/>(explícita ou pilha<br/>de chamadas da recursão)"]
S --> SA["Árvore sintática:<br/>nós de aridade variável"]
Sem["Análise semântica"] --> ST["Busca por chave:<br/>tabela de símbolos<br/>com escopos aninhados"]
G["Geração de código"] --> GP["Percurso em pós-ordem<br/>da árvore"]
V["Máquina de execução"] --> VP["Pilha de avaliação"]
Uma distinção organiza o resto: tipo abstrato de dados é a especificação de valores e operações pelo comportamento observável, e estrutura de dados é uma realização concreta. Se o compilador conversar só com o tipo abstrato, trocar a realização é tarefa local; se não, a troca contamina o projeto inteiro.
A pilha você conhece; o que quero que retenha é o papel dela aqui. Na análise sintática ela é a memória de um modelo de máquina: o autômato de pilha é um autômato finito acrescido de uma pilha, e é essa memória que lhe dá poder de reconhecimento estritamente maior — toda a diferença entre reconhecer parênteses balanceados e não reconhecer mora ali. Num analisador de descida recursiva não haverá pilha explícita no código, porque a pilha de chamadas do programa realiza a pilha do modelo; perceber isso torna a análise descendente compreensível em vez de mágica, e explica o laço infinito diante de recursão à esquerda.
Sobre árvores, importa a distinção entre percursos. A pré-ordem serve quando a informação flui de cima para baixo, como a propagação do escopo ao descer em blocos aninhados. A pós-ordem serve quando ela flui de baixo para cima, e é o padrão da geração de código: para gerar o código de uma soma é preciso já ter gerado o dos operandos. Registre que a pós-ordem de uma árvore de expressão é exatamente a notação pós-fixa, que por sua vez é a sequência de instruções de uma máquina de pilha.
A tabela de símbolos é o exemplo mais claro de por que escolher pelo padrão de uso e não pelo hábito. O padrão é assimétrico: um nome é inserido uma vez e consultado uma vez por uso. Some os escopos aninhados, que são eles próprios uma pilha, e o compromisso fica legível.
| Realização | Inserção | Consulta | Observação para este uso |
|---|---|---|---|
| Vetor com busca linear | constante | linear | Só para escopos pequenos |
| Vetor ordenado, busca binária | linear | logarítmica | Ruim: inserções intercaladas com consultas |
| Árvore de busca balanceada | logarítmica | logarítmica | Boa; mantém ordem, diagnósticos determinísticos |
| Tabela de dispersão | constante média | constante média | Usual; ordem de iteração imprevisível |
A última coluna carrega o que costuma faltar. A dispersão vence no critério óbvio e traz um custo escondido: a ordem de iteração não é a de declaração, então mensagens de erro geradas iterando sobre a tabela saem em ordem imprevisível, o que quebra os seus testes. A solução é banal — guardar a ordem de declaração à parte — mas só para quem previu o problema.
Pior caso é garantia, não previsão
A determinização tem pior caso exponencial, e há famílias de linguagens que o realizam. A reação treinada é descartar o algoritmo, e seria um erro: esse pior caso é atingido por autômatos de estrutura muito particular, que não é a dos autômatos vindos de expressões regulares escritas por gente, e o algoritmo só constrói os subconjuntos alcançáveis a partir do inicial. Para decidir se um algoritmo serve é preciso saber que entradas ocorrem de fato, e ter resposta para quando o pior caso aparecer: impor um limite e emitir diagnóstico em vez de travar.
1.5 Grafos: um autômato é um grafo dirigido rotulado
Enuncio direto, porque a conexão nem sempre é percebida e, uma vez percebida, economiza um semestre de esforço. Os estados são vértices, as transições são arestas rotuladas, e reconhecer uma cadeia é percorrer um caminho cuja sequência de rótulos é a cadeia.
stateDiagram-v2
direction LR
[*] --> q0
q0 --> q1: a
q1 --> q1: a
q1 --> q2: b
q2 --> q1: a
q2 --> [*]
q3 --> q2: b
Com isso no lugar, muita coisa apresentada como algoritmo de autômato é reconhecível como algoritmo de grafo que você já conhece. O fecho de transições vazias é alcançabilidade restrita às arestas de rótulo vazio; a determinização é uma busca em largura no grafo dos subconjuntos; perguntar se a linguagem é vazia é perguntar se existe caminho da origem a um final, e perguntar se é infinita é perguntar se existe ciclo num trecho útil.
A escolha da representação é a primeira decisão de projeto de peso do semestre. Na tabela mantém-se uma matriz indexada por estado e símbolo, com espaço proporcional ao produto e consulta em tempo constante; nas listas de adjacência guarda-se por vértice só o que existe, com consulta proporcional ao grau. O determinístico final, executado sobre cada caractere da entrada, quer a tabela, porque a consulta é a operação do laço mais interno; já o não determinístico intermediário é esparso, e a tabela desperdiçaria memória em escala.
Um estado é inalcançável quando não há caminho do inicial até ele, e improdutivo quando dele não parte caminho até um final. Remover ambos é a poda, e o cálculo é o mesmo algoritmo em direções opostas: no grafo original a partir do inicial, e no grafo com arestas invertidas a partir dos finais.
A diferença operacional entre os dois percursos clássicos é surpreendentemente pequena: em largura os pendentes ficam numa fila, em profundidade numa pilha. Em largura você ganha ordem crescente de distância à origem, o que dá numeração estável ao autômato determinizado. Em profundidade você ganha detecção de ciclo, e detectar a recursão à esquerda antes de rodar o analisador evita um laço infinito difícil de diagnosticar. Guarde o esqueleto genérico: mantenha um conjunto de processados e uma coleção de pendentes, retire um pendente, processe, insira os vizinhos ainda não processados, repita até esvaziar.
Por fim a ordenação topológica, que existe se e somente se o grafo é acíclico e resolve ordem de avaliação quando há tarefas com dependências. Aqui está a parte em que muita gente para: havendo ciclo, o que se perde é apenas a estratégia de ordenar e avaliar uma vez, e a alternativa é o ponto fixo — aplicar a regra repetidamente até nada mudar. É por isso que certos conjuntos calculados sobre gramáticas não vêm de varredura ordenada.
1.6 Programar de verdade: representação, memória e tipos
O programa que você vai construir é de médio porte, cumulativo ao longo de todos os módulos, numa linguagem que expõe a gestão de memória. As exigências são previsíveis: conforto com estruturas encadeadas e com a distinção entre valor e referência; conforto com alocação e liberação; capacidade de dividir o programa em módulos com interfaces explícitas; e disciplina de tipos.
Insisto numa decisão de representação, porque as consequências são longas. A alternativa intuitiva é cada estado ser um objeto alocado, com as transições guardando referências; funciona até certo ponto. Os problemas chegam em fila: guardar um conjunto exige uma ordem sobre referências, que não é estável entre execuções; copiar exige um mapa de originais para cópias, porque o grafo tem ciclo; e liberar exige decidir quem é dono de quem num grafo cíclico, o caso em que a contagem de referências falha.
flowchart TB
subgraph PONTEIRO["Estados por ponteiro"]
A1["Comparar:<br/>identidade ou conteúdo?"]
A2["Guardar conjunto:<br/>ordem instável<br/>entre execuções"]
A3["Copiar grafo cíclico:<br/>exige mapa original → cópia"]
A4["Liberar:<br/>quem é dono de quem?"]
end
subgraph INDICE["Estados por índice num vetor"]
B1["Comparar:<br/>igualdade de inteiros"]
B2["Guardar conjunto:<br/>vetor de bits"]
B3["Copiar:<br/>copia o vetor"]
B4["Liberar:<br/>o vetor morre inteiro"]
end
PONTEIRO --> INDICE
Agora a alternativa: os estados vivem num vetor, e um estado é um índice inteiro nesse vetor. Comparar é comparar inteiros; um conjunto de estados vira um vetor de bits, e a união de conjuntos fica barata; copiar é copiar o vetor; e a memória é liberada de uma vez. Há um custo: índice não carrega tipo, então nada impede usar um índice de estado onde se esperava um de símbolo. A mitigação é encapsular cada família de índices num tipo próprio, ainda que seja só um envoltório de inteiro — custa pouco e impede uma classe inteira de defeitos silenciosos.
O assunto da propriedade não some: haverá árvores, tabelas e listas alocadas dinamicamente. O hábito a recuperar é declarar, para cada estrutura, quem é o dono e qual é o tempo de vida — com essas duas perguntas respondidas por escrito, os defeitos clássicos deixam de ser possíveis por construção.
Nomeio ainda uma noção que uso o tempo todo: o invariante de representação é a condição sobre o estado interno de um tipo que vale logo após qualquer construtor e é preservada por toda operação pública. Escrevê-lo diz o que verificar quando algo der errado, e é o enunciado da prova informal de correção que você faz ao escrever cada operação — supondo o invariante na entrada, ele vale na saída, mesma estrutura do passo indutivo.
Sobre modularização, um ponto que se aprende tarde: numa arquitetura de fases, a interface entre duas fases é uma estrutura de dados, não um conjunto de funções — o léxico entrega tokens, o sintático entrega uma árvore, o gerador entrega instruções. Um teste operacional: cada fase deve poder ser exercitada sozinha, com entrada construída à mão, sem executar as anteriores. Se isso for difícil, a interface está errada.
Ligue o modo estrito no primeiro arquivo, não depois. Ativar verificações rigorosas sobre uma base já escrita produz dezenas de diagnósticos de uma vez, e a reação natural é desativá-las de novo; ativadas desde o começo, conformar-se custa uma linha por vez. Numa base que cresceu convivendo com avisos, ninguém lê nenhum — e aí o aviso do defeito real passa despercebido. O projeto do semestre compila sem nenhum aviso sob configuração estrita.
1.7 A máquina do outro lado: vocabulário de arquitetura
O compilador traduz para alguma coisa, e essa coisa é uma máquina. A parte final do semestre fica opaca para quem não tem presente o que é registrador, o que é conjunto de instruções e como um programa se organiza na memória enquanto executa. Como este é provavelmente o seu pré-requisito mais recente, a revisão pode ser breve.
O modelo que estrutura praticamente todo computador de uso geral em serviço é o de programa armazenado, descrito por John von Neumann no relatório preliminar sobre o EDVAC, de 1945: instruções e dados residem na mesma memória endereçável. A consequência que interessa a quem escreve compilador é que o programa gerado é apenas mais um conteúdo de memória — o que torna possível gerar código em tempo de execução e, no limite, escrever compiladores que compilam a si mesmos.
Registradores são posições de armazenamento internas ao processador, poucas e rápidas, contra uma memória principal ampla e lenta; é essa desproporção que torna difícil decidir quais valores residem em registrador em cada ponto. O conjunto de instruções é a especificação completa das operações, dos formatos de codificação, dos registradores visíveis e dos modos de acesso à memória, e a palavra que interessa aí é contrato: quem projeta o processador pode mudar tudo por baixo desde que ele seja honrado. Duas filosofias aparecem sob os rótulos de conjunto complexo e conjunto reduzido: a primeira favorece instruções numerosas e especializadas, a segunda, poucas instruções regulares com acesso à memória restrito a carga e armazenamento — e no reduzido a seleção de instruções é mais simples, com pressão maior sobre a alocação de registradores. Complete o vocabulário com os modos de endereçamento, com atenção ao modo com deslocamento, que realiza o acesso a variável local.
flowchart TB
subgraph MEM["Memória de um programa em execução"]
C["Código<br/>(instruções, somente leitura)"]
D["Dados estáticos<br/>(tempo de vida = o do programa)"]
H["Área de alocação dinâmica<br/>(tempo de vida arbitrário)"]
P["Pilha de execução<br/>(cresce e diminui<br/>com as chamadas)"]
end
subgraph ATIV["Registro de ativação"]
R1["Parâmetros"]
R2["Variáveis locais"]
R3["Endereço de retorno"]
end
P --> ATIV
R2 -. "acesso por deslocamento<br/>constante em relação<br/>a um registrador" .-> R3
Um programa em execução organiza a memória em código, dados estáticos, pilha de execução e área de alocação dinâmica. O registro de ativação é o bloco alocado na pilha no momento da chamada e liberado no retorno, com parâmetros, variáveis locais e endereço de retorno. O acesso às locais se faz por deslocamento constante em relação a um registrador — e é por isso que a tabela de símbolos precisa associar a cada variável local um deslocamento, informação que não existe no programa-fonte e que o compilador calcula.
A distinção que mais produz confusão adiante
A pilha de execução não é a mesma coisa que a pilha como tipo abstrato de dados: elas só têm em comum a disciplina. A pilha abstrata é uma estrutura que o seu programa usa; a pilha de execução é uma região de memória gerida pela convenção de chamada, sobre a qual o compilador gera código. O sintoma de quem confundiu as duas é achar que o compilador “usa uma pilha” para gerenciar chamadas, quando ele emite instruções que manipulam memória com disciplina de pilha.
Fecho com a distinção que reaparece na hora de escolher o alvo. Numa máquina de pilha, as instruções aritméticas tomam os operandos do topo de uma pilha de avaliação e ali depositam o resultado; numa máquina de registradores, elas nomeiam origem e destino. Gerar código para a primeira a partir de uma árvore de expressão é quase imediato: percorra em pós-ordem, empilhando o valor de cada folha e emitindo a operação de cada nó interno, sem decisão a tomar porque não há registrador a escolher. Gerar para a segunda é otimização combinatória. Daí a estratégia que muitos sistemas adotam: gerar primeiro para uma máquina de pilha abstrata do próprio projeto e só depois traduzir para uma máquina real.
1.8 Amarrando: como usar este módulo
Volto ao problema com que abri. As duas competências que a disciplina cobra não são independentes. Olhe o cálculo de alcançabilidade: ele é o fecho reflexivo e transitivo do bloco de relações, calculado pelo padrão de repetir até nada mudar, implementado com a coleção de pendentes do bloco de estruturas de dados, e demonstrado correto pelo argumento de estabilização em domínio finito do bloco de demonstrações. Um algoritmo, quatro pré-requisitos simultâneos — e é assim que o semestre vai cobrá-los.
| Pré-requisito | Onde é cobrado | Como aparece |
|---|---|---|
| Conjuntos, relações e funções | Do segundo ao nono módulo | Definições formais; minimização por partições |
| Técnicas de demonstração | Equivalência entre modelos; limites das regulares | Correção dos algoritmos; não regularidade |
| Estruturas de dados | Autômatos, análise sintática, semântica, execução | Tabela de transições, pilhas, tabela de símbolos |
| Grafos dirigidos e percursos | Autômatos e otimização | Fecho vazio, determinização, poda |
| Maturidade de programação | O projeto inteiro | Do primeiro arquivo ao compilador |
| Vocabulário de arquitetura | Ambientes de execução e geração de código | Registro de ativação, máquina de destino |
A tabela produz uma conclusão desconfortável e útil: os pré-requisitos mais exigentes se concentram no começo e são os mais caros de recuperar depois, com o projeto já andando. Vale ainda a distinção que atravessa todos os blocos: aqui revisamos notação e critério, não implementação — não é preciso reimplementar uma árvore balanceada, é preciso saber por que se escolheria uma. A exceção é o bloco de programação, cuja verificação é escrever código: um programa pequeno que compile limpo sob a configuração estrita do projeto vale mais, como aferição, do que qualquer questão respondida.
Uma última coisa, e é a mais útil que tenho a dizer. Quando um algoritmo dos próximos módulos parecer opaco, é provável que a opacidade esteja em um dos seis blocos revisados aqui, e a tabela acima existe para localizar qual. A dificuldade que o estudante atribui ao assunto novo é, com frequência incômoda, dificuldade com o vocabulário antigo.
O próximo módulo abandona a revisão e entra no assunto: delimita o que significa compilar, mostra a decomposição do compilador em fases e desenha o mapa teórico dentro do qual todo o resto se situa. O critério de sucesso lá não vai ser saber operar, e sim saber situar — diante de qualquer algoritmo novo, dizer em que ponto do edifício ele se encaixa e a que pergunta ele responde.