Moacyr Francischetti Corrêa

1 Prefácio

Bem-vindo. Este material foi escrito para acompanhar você durante um semestre inteiro de construção — e ele parte de uma premissa que convém deixar clara logo de saída: você aprende compiladores construindo um, não lendo sobre um. Tudo aqui, do formato das aulas ao desenho do projeto, decorre disso.

Antes de começar, vale explicar as escolhas que moldaram este material. Não por formalidade: quando você entende por que uma aula é conduzida de determinada maneira, participa dela de outro jeito, e o resultado muda. Este prefácio trata das razões pedagógicas por trás do curso, do ambiente em que você vai trabalhar, de como o material está organizado, e do que esperar de cada um dos quinze módulos.

1.1 O que esta disciplina faz com quem a cursa

Há disciplinas que acrescentam ferramentas ao seu repertório. Esta muda a forma como você enxerga o que já usa.

Depois dela, uma mensagem de erro de compilação deixa de ser um obstáculo e passa a ser informação de uma fase específica de um sistema que você conhece por dentro. Você lê “erro de sintaxe” e sabe qual componente falhou, por que ele falhou ali, e por que ele não poderia ter detectado outra coisa. Lê sobre uma linguagem nova e percebe imediatamente quais decisões de projeto os autores tomaram e o que elas custaram. Encontra um formato de dados esquisito no trabalho e, em vez de improvisar uma pilha de condicionais, escreve um analisador correto em uma tarde.

Há um efeito ainda mais amplo, que vale nomear. Esta é uma das poucas disciplinas do curso em que você constrói um sistema completo — não um exercício, não um módulo isolado, mas um programa com várias fases que se comunicam, com decisões de arquitetura tomadas no início e sustentadas por meses. Sair de um semestre tendo feito isso, em equipe, muda a confiança com que você encara o próximo sistema grande. Essa mudança é difícil de medir e é, provavelmente, o que mais fica.

1.2 A filosofia por trás das escolhas

Todo o desenho deste curso responde a uma constatação incômoda: assistir a alguém explicar algo produz sensação de compreensão sem produzir compreensão. Você sai da aula achando que entendeu, e descobre que não entendeu quando tenta fazer. A distância entre reconhecer uma explicação e conseguir reproduzir o raciocínio é enorme, e ela só se fecha praticando.

As escolhas metodológicas abaixo existem para fechar essa distância. Cada uma resolve um problema específico.

1.2.1 Material feito para estudo autônomo

O texto deste material é dissertativo e explicativo, e não uma coleção de tópicos. A razão é simples: tópicos funcionam como lembrete para quem já sabe e são inúteis para quem está aprendendo. Uma lista de propriedades de um autômato não ensina nada; o texto que explica de onde cada propriedade vem, e o que aconteceria se ela não valesse, ensina.

A consequência é que o material é mais longo do que um resumo e pode ser lido sem o professor ao lado. Isso é intencional. Você não precisa esperar a aula para entender algo, e não fica dependente da presença de alguém para avançar.

1.2.2 Construir o código junto, e estudar o exemplo depois

Boa parte do conteúdo implementável é escrita ao vivo em sala pelo professor, do zero, com você digitando junto no seu próprio ambiente e vendo cada decisão ser tomada e justificada em voz alta. Concluída a construção, o artefato permanece disponível como exemplo resolvido para consulta.

Essa combinação resolve dois problemas de uma vez. A construção ao vivo mostra o processo — as hesitações, os caminhos descartados, a ordem em que as coisas foram feitas — que o código pronto esconde por completo. E o exemplo resolvido que fica depois resolve o problema oposto: estudar uma solução completa e correta, com calma, exige muito menos esforço mental do que descobri-la sozinho, e é comprovadamente mais eficiente para quem está aprendendo do que enfrentar um problema aberto cedo demais. É a razão pela qual você recebe um modelo antes de construir o seu.

1.2.3 O apoio que diminui

Um exemplo resolvido é excelente no começo e prejudicial se durar demais: quem só estuda soluções prontas nunca desenvolve a capacidade de produzir a própria. Por isso o suporte é retirado aos poucos.

Nos primeiros módulos, a tarefa do projeto vem com roteiro detalhado e critérios de aceitação prontos. Nos intermediários, o objetivo continua definido mas o caminho é seu, e os critérios passam a ser propostos pelo grupo. Nos finais, você recebe apenas o resultado esperado. A retirada é gradual e planejada, de modo que em nenhum momento você fique sem chão — mas ao fim do semestre você está construindo sozinho, e a transição terá sido tão suave que provavelmente passará despercebida até você olhar para trás.

1.2.4 Um projeto como fio condutor

O curso inteiro gira em torno de um projeto que o seu grupo constrói do segundo ao décimo quinto módulo. Não é um trabalho final, entregue no fim: é um sistema que cresce toda semana e cujas partes iniciais continuam em uso até o último dia.

Trabalhar assim ensina o que exercícios curtos não ensinam. Uma decisão ruim tomada no terceiro módulo cobra o preço no décimo, e você paga esse preço — que é exatamente o que acontece na vida profissional e nunca acontece em uma lista de exercícios, onde cada questão recomeça do zero. Aprender a conviver com as próprias decisões, e a saber quando refazer em vez de remendar, é parte do conteúdo.

1.2.5 Aprender resolvendo problemas, não recebendo soluções

Cada módulo abre com uma situação concreta que o conteúdo daquele módulo resolve, ou com uma limitação do que você já construiu. O conteúdo vem depois, como resposta a uma pergunta que já foi formulada.

A ordem importa. Quando a técnica chega antes do problema, ela parece arbitrária e é esquecida; quando chega como solução de uma dificuldade que você acabou de sentir, encaixa. Nesta disciplina isso é particularmente natural, porque a sequência de assuntos é literalmente uma cadeia de limitações superadas — cada modelo formal aparece porque o anterior demonstravelmente não dá conta.

1.2.6 Discutir com quem está ao lado

As aulas teóricas são interrompidas por questões conceituais que você responde primeiro sozinho, depois discute com um colega, depois responde de novo. A técnica foi desenvolvida pelo físico Eric Mazur, que percebeu que seus alunos passavam nas provas e continuavam sem entender os conceitos básicos da disciplina.

Ela funciona por uma razão específica: quem acabou de entender algo é melhor em explicá-lo a quem não entendeu do que o especialista. O especialista esqueceu onde estava a dificuldade — para ele o ponto é óbvio há tanto tempo que nem parece um ponto. O colega ao lado ainda lembra, porque tropeçou ali cinco minutos atrás. Some-se a isso que o professor descobre na hora onde a turma está travada, em vez de descobrir na correção da prova.

1.2.7 Revezar quem digita e quem revisa

Dentro do grupo, o trabalho de implementação é feito em pares, com papéis explícitos e revezamento em intervalos curtos: um escreve e verbaliza o que está fazendo, o outro revisa em tempo real e antecipa o próximo passo.

Isso não é sobre produtividade — é sobre distribuição do aprendizado. Sem revezamento, grupos convergem naturalmente para uma configuração em que a pessoa mais confortável com código faz tudo e as outras acompanham. O grupo entrega bem e aprende mal, e quem mais precisava praticar é justamente quem menos praticou. O revezamento existe para impedir esse arranjo, e é verificado durante as sessões.

1.2.8 Construir coisas de verdade

A disciplina segue a lógica de quem faz: você projeta, constrói, testa, quebra, conserta e mostra o que fez funcionando. O produto final não é um relatório sobre compiladores — é um compilador que roda.

Isso muda a natureza do erro. Em um trabalho escrito, errar é perder ponto. Em um artefato que precisa funcionar, errar é informação: o programa não roda, você descobre por quê, e a descoberta ensina mais do que o acerto teria ensinado. Quebrar coisas cedo e com frequência é parte do método, não um acidente.

1.2.9 Decidir o que construir

A escolha do que exatamente o seu grupo vai construir é de vocês. Há restrições — a linguagem que vocês projetarem precisa exercitar toda a teoria da disciplina, e precisa ser pequena o bastante para caber no semestre — mas dentro delas a decisão é do grupo, e ela é tomada logo no primeiro módulo, com informação incompleta.

Decidir com informação incompleta e depois viver com a decisão é uma habilidade que raramente é ensinada e sempre é exigida. Você vai propor, receber crítica, ajustar o escopo e defender as escolhas. O processo de convergir de uma ideia vaga para uma especificação executável é, ele mesmo, conteúdo.

1.2.10 Trabalhar em equipe de verdade

Os grupos têm dois ou três integrantes e composição fixa do primeiro ao último módulo. Não há troca no meio do caminho, e isso é deliberado.

Equipes que permanecem juntas atravessam as fases desconfortáveis — o desacordo sobre arquitetura, a semana em que nada funciona, a percepção de que alguém está contribuindo menos — em vez de dissolvê-las trocando de grupo. Atravessar essas fases é onde a competência de trabalho em equipe efetivamente se desenvolve. Para tornar isso visível e discutível, os integrantes avaliam a contribuição uns dos outros nas entregas de maior peso.

flowchart LR
    subgraph TEO["Duas aulas de teoria"]
        T1["Exposição interrompida<br/>por questões conceituais<br/>voto, discussão em dupla, novo voto"]
        T2["Construção de código ao vivo<br/>você digita junto<br/>o resultado fica como exemplo resolvido"]
    end

    subgraph TUT["Quatro aulas de projeto"]
        U1["Planejamento do incremento<br/>em equipe"]
        U2["Construção em pares<br/>revezando quem digita<br/>e quem revisa"]
        U3["Teste, correção<br/>e registro das decisões"]
    end

    TEO ==> TUT
    TUT -.->|"o que travou<br/>volta como dúvida"| TEO

    ANDAIME["Ao longo dos módulos<br/>o apoio diminui:<br/>de roteiro detalhado<br/>a apenas o resultado esperado"]
    ANDAIME -.-> TUT

    style T2 fill:#f4ecdd
    style U2 fill:#e8f4ea

1.3 O ambiente de trabalho

O projeto é desenvolvido em C++, compilado com o toolchain da Microsoft em ambiente Windows, a partir do Visual Studio Code. Convém explicar a escolha, porque ela tem consequência direta no seu dia a dia.

Um compilador manipula estruturas cheias de referências cruzadas e ciclos — um autômato é um grafo que aponta para si mesmo, e uma árvore sintática é uma teia de nós interligados. Construir isso em uma linguagem que expõe a gestão de memória obriga você a tomar decisões explícitas de representação que uma linguagem com coleta automática de lixo tomaria por você, em silêncio. Essas decisões são parte do que se aprende aqui, e por isso o custo de tomá-las é aceito de propósito.

O código do curso é escrito com tipagem forte e explícita, e precisa compilar sem nenhum aviso sob a configuração estrita adotada pela disciplina. Isso parece rigor excessivo no primeiro módulo e deixa de parecer no décimo: em um projeto que cresce durante um semestre, o aviso ignorado hoje é o defeito silencioso de daqui a dois meses.

Uma restrição importante do curso: nenhum gerador automático de analisadores léxicos ou sintáticos pode ser usado no projeto. Essas ferramentas existem, são excelentes, e você vai estudá-las nos módulos em que o assunto aparece — mas depois de já ter implementado à mão o que elas fazem. A razão é direta: quem gera o analisador com a ferramenta aprende a ferramenta; quem o constrói aprende a teoria que a ferramenta implementa. A ordem não é negociável, e ela é a diferença entre saber usar e saber por quê.

1.4 Como o material está organizado

Você tem à disposição mais de uma forma de acessar o mesmo conteúdo, e cada uma serve a um momento diferente do estudo.

flowchart TD
    VOCE(["Você, ao longo do semestre"])

    VOCE --> A["Antes ou depois da aula teórica<br/>o livro da disciplina<br/>tratamento completo e aprofundado,<br/>em papel ou leitor digital"]
    VOCE --> B["Durante o trabalho no projeto<br/>o material do site<br/>versão reduzida, para consulta rápida<br/>quando a dúvida tem endereço"]
    VOCE --> C["Na véspera de uma avaliação<br/>o resumo de revisão<br/>o essencial do módulo<br/>em poucas páginas"]
    VOCE --> D["Para testar se entendeu<br/>os exercícios do módulo<br/>três níveis, do básico ao desafiador"]
    VOCE --> E["Para autoavaliação<br/>o banco de questões<br/>conceitos teóricos do módulo"]
    VOCE --> F["Como modelo do seu projeto<br/>a solução de referência do professor<br/>construída em sala, disponível depois"]

    style A fill:#f4ecdd
    style F fill:#e8f4ea

O livro da disciplina é o tratamento completo: texto longo, aprofundado, com o desenvolvimento inteiro de cada assunto. É o que ler quando você quer entender de verdade, com tempo, em papel ou em leitor digital.

O material do site é uma versão reduzida do mesmo conteúdo, pensada para consulta durante o trabalho. Quando você está no meio do projeto e precisa relembrar como funciona uma construção específica, é ali que se procura — o caminho até a informação é mais curto.

O resumo de revisão condensa o módulo ao essencial, em poucas páginas. Serve para retomada rápida e para verificar, antes de seguir adiante, se algum ponto ficou para trás.

Os exercícios de cada módulo vêm em três níveis, do básico ao desafiador, e existem para você testar sozinho se entendeu — não para nota. O banco de questões cumpre função parecida, com foco nos conceitos teóricos.

Por fim, a solução de referência do professor: o projeto construído em sala, disponível depois para estudo. É o seu modelo de como se faz, e vale voltar a ele quando o seu próprio projeto empacar — não para copiar, mas para ver como um problema parecido foi resolvido.

Todo esse material chega a você em várias formas — site, livro impresso, livro digital e ambiente virtual de aprendizagem —, e é o mesmo conteúdo em cada uma. Use a que for mais conveniente para o momento.

1.5 A progressão dos módulos

O semestre tem quinze módulos de seis aulas cada: duas de teoria e quatro de trabalho no projeto. A entrega final acontece na semana seguinte ao término do módulo 15.

A progressão obedece a uma regra única: nenhum modelo formal novo aparece antes de o anterior ter demonstrado sua insuficiência. Isso explica a ordem dos assuntos e, principalmente, explica por que os primeiros módulos são mais teóricos — é preciso construir o modelo simples e provar que ele tem teto antes que o modelo seguinte faça sentido.

Módulo 1 — Panorama da Compilação e Linguagens Formais. O mapa do semestre. O que significa compilar, como um compilador se divide em fases, e qual é a hierarquia de gramáticas que organiza toda a teoria do curso. É também o módulo em que os grupos se formam e escolhem o que vão construir.

Módulo 2 — Alfabetos, Linguagens e Expressões Regulares. O vocabulário formal. Você vai descobrir que as expressões regulares que já usa por imitação têm uma definição precisa, propriedades algébricas, e limites bem determinados — e que boa parte do que as bibliotecas oferecem sob esse nome não é, tecnicamente, regular.

Módulo 3 — Autômatos Finitos Determinísticos. A primeira máquina. Um modelo com memória finita, que lê um símbolo por vez e nunca volta atrás — limitado de propósito, e por isso analisável por completo e implementável com eficiência. Primeiro código do projeto.

Módulo 4 — Não Determinismo e a Construção de Thompson. Uma máquina que faz todas as escolhas ao mesmo tempo. Parece trapaça, parece mais poderosa que a anterior, e não é — e é justamente essa equivalência que permite transformar automaticamente uma expressão regular em um programa que a reconhece.

Módulo 5 — Determinização e Minimização. O fechamento do primeiro motor. Converter a máquina não determinística em executável, encolhê-la até o menor tamanho possível, e descobrir que esse menor tamanho é único — resultado que transforma a pergunta “estas duas especificações descrevem a mesma coisa?” em um procedimento mecânico.

Módulo 6 — Limites das Linguagens Regulares. O módulo da impossibilidade. Você vai demonstrar formalmente que existe algo que a ferramenta construída até aqui jamais conseguirá fazer, e vai vê-la falhar exatamente como a teoria previu. É o ponto de virada do semestre.

Módulo 7 — Análise Léxica. Tudo dos módulos anteriores converge em uma peça com nome próprio: a primeira fase real de um compilador. Junto com ela vêm as decisões práticas que a teoria não menciona — desempate entre padrões, comentários, mensagens de erro úteis. Primeiro marco de consolidação do projeto.

Módulo 8 — Gramáticas Livres de Contexto. Descrever não mais as palavras, mas como elas se combinam. Aqui aparece a ambiguidade, que é o problema central do projeto de linguagens: uma gramática que admite duas leituras para o mesmo programa é inaceitável, e desfazer isso é mais sutil do que parece.

Módulo 9 — Autômatos de Pilha. O modelo de máquina correspondente às gramáticas do módulo anterior, e a primeira surpresa genuína do curso: aqui, ao contrário do caso anterior, determinismo e não determinismo não são equivalentes. Este é um dos dois módulos sem tarefa de implementação no projeto — a entrega é teórica, e as sessões de trabalho servem para consolidar o que ficou pendente antes do módulo mais denso do semestre.

Módulo 10 — Análise Sintática Descendente. O módulo mais pesado, e o segundo marco. O texto vira estrutura em árvore, e o seu front-end fica completo. Também é onde entra a recuperação de erros — fazer o compilador continuar depois do primeiro problema, sem inventar vinte erros falsos em seguida.

Módulo 11 — Análise Sintática Ascendente. A família de métodos que a maioria dos compiladores de produção usa, e que você vai estudar sem implementar. Este é o segundo e último módulo sem tarefa de implementação: a entrega é um estudo comparativo aplicado à gramática do seu próprio grupo, e o objetivo é a capacidade de escolher entre alternativas e de ler o que uma ferramenta reporta.

Módulo 12 — Análise Semântica. O que a gramática não captura. Nome usado sem ter sido declarado, operação aplicada a um valor que não a comporta — coisas que nenhuma estrutura sintática consegue proibir e que exigem tabela de símbolos, escopos e verificação de tipos.

Módulo 13 — Representações Intermediárias e Ambientes de Execução. A ponte entre analisar e produzir. Por que compiladores passam por uma representação intermediária, e como um programa se organiza na memória enquanto roda. É um módulo de projeto no sentido literal: quase todo o trabalho é decidir e especificar.

Módulo 14 — Geração de Código. O compilador passa a produzir saída de verdade. E acontece o fechamento mais bonito do curso: os autômatos estudados no início do semestre reaparecem dentro do arquivo que o seu compilador gera.

Módulo 15 — Otimização e Integração Final. Blocos básicos, grafo de fluxo, transformações que melhoram o código sem alterar o que ele faz — e a integração de tudo, rodando ponta a ponta sobre entrada real. A entrega final e a apresentação acontecem na semana seguinte ao término deste módulo.

1.6 Uma palavra final

Este semestre vai exigir constância mais do que brilho. O projeto é cumulativo, os assuntos se encadeiam, e a estratégia de estudar tudo na véspera — que talvez tenha funcionado em outras disciplinas — não funciona aqui, porque não há como implementar a fase seis sem a cinco pronta.

A boa notícia é que a constância é suficiente. Não é preciso talento excepcional para construir um compilador em um semestre; é preciso comparecer, acompanhar a construção em sala, e não deixar dívida acumular. Quem faz isso chega ao fim com um sistema funcionando e uma compreensão que dificilmente se perde, porque foi construída em vez de memorizada.

Uma última recomendação prática: quando algo não fizer sentido, diga. Na aula, na discussão com o colega, na conversa com o professor durante o trabalho no projeto. A dúvida não formulada é a que vira dívida, e a dívida é a única coisa nesta disciplina que realmente atrapalha.

Bom semestre. Nos vemos no primeiro módulo.