Moacyr Francischetti Corrêa

1 Conteúdo Programático

1.1 Apresentação do Conteúdo

Todo programa que você já escreveu passou por um compilador antes de virar algo que a máquina executa. Esse programa intermediário leu o seu texto, decidiu que ele fazia sentido, reclamou quando não fazia, e produziu outra coisa no lugar. Nesta disciplina você vai escrever um desses.

O percurso tem uma lógica simples de enunciar e exigente de cumprir. Um compilador é uma sequência de transformações: texto vira sequência de símbolos, símbolos viram estrutura em árvore, a árvore é verificada quanto ao sentido, e o resultado verificado vira código executável. Cada uma dessas transformações corresponde a um modelo matemático preciso, estudado décadas antes de existirem os compiladores que hoje o utilizam. Aprender a teoria e aprender a implementação, aqui, é a mesma atividade vista de dois ângulos.

O conteúdo se organiza em três blocos encadeados. O primeiro percorre as linguagens regulares e os autômatos finitos, e desemboca no analisador léxico. O segundo sobe para as linguagens livres de contexto e os autômatos de pilha, e desemboca no analisador sintático. O terceiro trata do que a gramática não consegue exprimir — significado, tipos, escopo, execução — e desemboca no código gerado. Cada bloco termina com uma peça de software funcionando, e as três peças se somam num compilador completo.

flowchart TD
    subgraph EIXO1["Linguagens regulares e autômatos finitos"]
        M01["Módulo 1<br/>Panorama"]
        M02["Módulo 2<br/>Expressões regulares"]
        M03["Módulo 3<br/>Autômatos determinísticos"]
        M04["Módulo 4<br/>Não determinismo e Thompson"]
        M05["Módulo 5<br/>Determinização e minimização"]
        M06["Módulo 6<br/>Limites do modelo regular"]
        M07["Módulo 7<br/>Análise léxica"]
    end

    subgraph EIXO2["Linguagens livres de contexto e análise sintática"]
        M08["Módulo 8<br/>Gramáticas livres de contexto"]
        M09["Módulo 9<br/>Autômatos de pilha"]
        M10["Módulo 10<br/>Análise descendente"]
        M11["Módulo 11<br/>Análise ascendente"]
    end

    subgraph EIXO3["Síntese: do significado ao código executável"]
        M12["Módulo 12<br/>Análise semântica"]
        M13["Módulo 13<br/>Representações intermediárias<br/>e ambientes de execução"]
        M14["Módulo 14<br/>Geração de código"]
        M15["Módulo 15<br/>Otimização e integração"]
    end

    M01 --> M02 --> M03 --> M04 --> M05 --> M06 --> M07
    M07 --> M08 --> M09 --> M10 --> M11
    M11 --> M12 --> M13 --> M14 --> M15

    M06 -. "o modelo regular falha<br/>no aninhamento" .-> M08
    M05 -. "o motor de autômatos<br/>vira o analisador léxico" .-> M07
    M03 -. "as mesmas tabelas de transição<br/>reaparecem como código gerado" .-> M14

As setas pontilhadas do diagrama merecem atenção porque revelam a costura entre os blocos. A falha do modelo regular diante de estruturas aninhadas, demonstrada no sexto módulo, é o que obriga a subida para as gramáticas livres de contexto no oitavo. O motor de autômatos construído até o quinto módulo não é descartado quando o analisador léxico aparece no sétimo: é exatamente ele, reaproveitado. E as tabelas de transição estudadas logo no terceiro módulo reaparecem no décimo quarto como formato do código gerado. Nada do que se constrói cedo é jogado fora depois.

O artefato que atravessa o semestre. Todo o conteúdo é ancorado na construção de uma linguagem pequena, chamada Peneira, feita para descrever padrões em texto e reagir ao que encontrar. O professor constrói a versão de referência ao longo dos módulos, e cada grupo constrói a sua. A escolha dessa linguagem tem um motivo técnico específico: o compilador dela produz, como resultado, um motor de autômatos. Isso faz a teoria aparecer duas vezes no mesmo programa — uma vez para reconhecer os símbolos da própria linguagem, outra vez para reconhecer os padrões que o usuário declarou. O mesmo código serve às duas finalidades. Quando você perceber esse reaproveitamento funcionando, terá entendido a disciplina inteira.

1.2 Estrutura de Estudo e Profundidade

Cada módulo dispõe de seis aulas, distribuídas de forma constante ao longo do semestre. As duas primeiras são de exposição teórica, conduzidas pelo professor, e as quatro restantes são de tutoria, dedicadas ao desenvolvimento do Projeto Integrador em grupo, com o professor circulando entre as equipes. Essa proporção não é acidental: a maior parte do tempo está reservada à prática porque é implementando que os modelos formais deixam de ser notação e passam a ser compreensão.

A consequência prática dessa divisão é que a exposição teórica precisa ser econômica. Um módulo não comporta o tratamento exaustivo de um assunto, e tentar dar tudo em profundidade máxima produziria cobertura superficial de tudo. Por isso cada tema recebe uma indicação explícita de profundidade, e essa indicação é um compromisso, não uma sugestão.

Os três níveis de profundidade usados neste documento

Instrumental — o tema é tratado até o ponto em que você consegue implementá-lo sozinho, sem consultar a solução. É o nível dos algoritmos que entram no compilador: a construção de Thompson, a determinização, o cálculo dos conjuntos que orientam a análise descendente. Espera-se que você saiba executar o algoritmo à mão em um exemplo pequeno e escrever o código que o executa em geral.

Conceitual — o objetivo é entender, comparar e decidir, sem exigência de implementação. É o nível dos assuntos em que a capacidade de escolha importa mais que a capacidade de construção: os métodos ascendentes de análise sintática, a alocação de registradores por coloração, a coleta automática de lixo. Espera-se que você saiba explicar como funciona, dizer quando se aplica e interpretar o comportamento de uma ferramenta que o implemente.

Panorâmica — reconhecimento e vocabulário, suficientes para leitura autônoma posterior. É o nível dos temas que a disciplina precisa situar mas não pode desenvolver. Espera-se que você saiba que existe, o que resolve, e onde procurar quando precisar.

Há uma assimetria proposital entre os dois eixos da disciplina. O eixo de linguagens formais é tratado com rigor de demonstração: definições formais, teoremas enunciados, provas conduzidas em sala. O eixo de compiladores é tratado com rigor de engenharia: decisões justificadas, estruturas de dados escolhidas, casos de erro previstos. Não se trata de um eixo ser mais sério que o outro, e sim de cada um ter o seu padrão de qualidade próprio. Uma demonstração de não regularidade que “quase” funciona não vale nada; um analisador léxico que trata quase todos os casos de erro pode ser perfeitamente aceitável numa primeira versão.

Todo o trabalho da disciplina acontece dentro do horário de aula, e nada aqui pressupõe estudo prévio: as aulas teóricas são construídas para funcionar com quem chega sem ter lido, e os momentos de discussão em duplas sobre questões conceituais operam inteiramente dentro da exposição. O material escrito de cada módulo existe como referência permanente — para consultar durante a tutoria, para retomar um ponto que passou rápido, e para reler depois com calma. Usá-lo assim, no seu próprio ritmo, costuma render mais do que qualquer tentativa de adiantar leitura.

1.2.1 Módulo 1: Panorama da Compilação e Linguagens Formais

Escreva um programa com um ponto e vírgula faltando e o compilador aponta a linha exata. Escreva um programa que soma um texto a um número e ele reclama de novo, mas por um motivo completamente diferente. Escreva um programa que entra em laço infinito e ele não diz nada — compila em silêncio e o problema só aparece na execução. Três erros, três destinos distintos. Entender por que o compilador percebe os dois primeiros e não pode perceber o terceiro é entender a arquitetura inteira da disciplina.

O estudo começa pela definição do problema. O que significa compilar, e o que distingue um compilador de um interpretador, de um montador e de um tradutor entre linguagens de alto nível — distinções que na prática se misturam, já que sistemas reais frequentemente combinam as abordagens. Em seguida vem a decomposição clássica em fases, com a separação entre a parte que analisa o texto de entrada e a parte que sintetiza a saída, e o argumento de engenharia que justifica essa separação: cada uma das duas metades pode ser trocada independentemente da outra.

O segundo movimento do módulo apresenta o mapa teórico. A hierarquia de Chomsky organiza as gramáticas em quatro tipos, e a cada tipo corresponde uma classe de linguagens e um modelo de máquina capaz de reconhecê-las. Você verá o mapa inteiro de uma vez, sabendo de antemão que a disciplina percorrerá com detalhe apenas os dois níveis inferiores, e entenderá por que são justamente esses dois que interessam à construção de compiladores.

O módulo fecha com a apresentação do artefato que será construído: o problema que a linguagem Peneira resolve, a forma dos seus programas, e a razão de o resultado da compilação ser um motor de autômatos. Também se organiza o ambiente de trabalho e a estrutura do projeto, de modo que a primeira linha de código possa ser escrita já no módulo seguinte.

Profundidade: panorâmica em todos os tópicos. Nada é esgotado aqui. O critério de sucesso é você conseguir situar qualquer assunto do semestre no mapa e explicar, em uma frase, o que o compilador que vai construir faz.

1.2.2 Módulo 2: Alfabetos, Linguagens e Expressões Regulares

Você já usou expressões regulares para procurar algo num arquivo. Provavelmente aprendeu por imitação, copiando padrões que funcionavam. Este módulo mostra que aquilo tem uma teoria por baixo, e que a teoria é mais simples e mais bem comportada que a notação bagunçada das ferramentas — e explica, de passagem, por que certos padrões que você tentou escrever nunca funcionaram e nunca funcionariam.

O estudo parte dos objetos mais elementares. Símbolo, alfabeto, cadeia e as operações sobre cadeias: concatenação, potência, reverso, prefixo, sufixo e subcadeia. A cadeia vazia e suas propriedades, que são fonte recorrente de erro em demonstrações. Em seguida, linguagens como conjuntos de cadeias, com as operações herdadas da teoria dos conjuntos e as operações próprias: concatenação de linguagens, fecho de Kleene e fecho positivo. Aqui aparece a primeira ideia contraintuitiva importante — o fecho de Kleene de qualquer linguagem contém a cadeia vazia, inclusive o fecho do conjunto vazio.

Sobre essa base entram as expressões regulares, apresentadas como notação finita capaz de descrever conjuntos infinitos. Sintaxe, semântica definida por indução sobre a estrutura da expressão, e as identidades algébricas que permitem simplificar e comparar expressões. Um cuidado necessário: a notação das bibliotecas de programação inclui construções que não são regulares, como retrovisores, e isso não é detalhe de implementação — é a diferença entre uma classe de linguagens e outra. Saber distinguir o que é regular do que apenas se parece com regular evita conclusões erradas mais adiante.

O módulo termina especificando a mini-linguagem de expressões regulares que o artefato condutor vai aceitar, com escolhas deliberadas sobre o que incluir e o que deixar de fora.

Profundidade: instrumental. Espera-se fluência de leitura e escrita de expressões regulares, e capacidade de demonstrar equivalências simples por manipulação algébrica, sem recurso a autômatos.

1.2.3 Módulo 3: Autômatos Finitos Determinísticos

Uma máquina com memória finita, que lê um símbolo por vez e nunca volta atrás, parece fraca demais para ser útil. É, de fato, o modelo mais limitado que estudaremos. E ainda assim é o que está por trás de todo analisador léxico de todo compilador em uso hoje. A limitação, aqui, é a fonte da utilidade: por ser tão restrito, o modelo admite implementação extremamente eficiente e análise completa.

O estudo começa pela definição formal do autômato finito determinístico como quíntupla — conjunto de estados, alfabeto, função de transição, estado inicial e conjunto de estados finais. Cada componente é examinado pelo papel que cumpre. Em seguida, a noção de configuração instantânea e a extensão da função de transição de símbolos para cadeias, definida por indução, que é o que permite dizer com precisão o que significa uma cadeia ser aceita. A linguagem reconhecida pelo autômato é então definida sem ambiguidade.

O segundo movimento é de representação. Diagrama de estados e tabela de transição são duas faces do mesmo objeto, e a passagem de uma à outra precisa ser automática para você. O diagrama serve ao raciocínio humano; a tabela serve à máquina. Vem então o projeto de autômatos a partir de descrições informais de linguagens, que é a habilidade central do módulo e se desenvolve por prática deliberada. Atenção especial a dois pontos que costumam ser negligenciados: o estado de erro, que existe mesmo quando não é desenhado, e a completude da função de transição.

O módulo fecha na implementação. A tabela de transição como estrutura de dados, o laço de reconhecimento em sua forma mais enxuta, e uma decisão de projeto que se repetirá: estados são representados por índices inteiros em um vetor, nunca por ponteiros ou referências. O motivo é prático — autômatos são grafos com ciclos, e grafos com ciclos manipulados por ponteiro são a origem mais comum de defeitos de memória em compiladores escritos à mão.

Profundidade: instrumental, com ênfase na correspondência entre a definição matemática e a estrutura de dados. Ao final você deve conseguir olhar uma tabela de transição e enxergar o diagrama, e vice-versa.

1.2.4 Módulo 4: Não Determinismo e a Construção de Thompson

Imagine uma máquina que, diante de uma escolha, faz todas as opções ao mesmo tempo e aceita se qualquer uma delas der certo. Parece trapaça, e parece que deveria ser mais poderosa que a máquina determinística do módulo anterior. Não é — e a demonstração de que não é figura entre os resultados mais elegantes da teoria da computação, além de ser diretamente responsável por você conseguir transformar uma expressão regular em código executável.

O estudo apresenta primeiro o autômato finito não determinístico, com a função de transição levando a conjuntos de estados em vez de a um estado único, e depois a variante com transições vazias, que permitem mudar de estado sem consumir símbolo algum. A pergunta que organiza o módulo é por que introduzir um modelo aparentemente mais complicado, e a resposta é de engenharia: o não determinismo é conveniente para especificar e inconveniente para executar, e por isso especificamos com ele e executamos com o outro.

O conceito técnico central é o fecho vazio de um conjunto de estados, com o algoritmo que o calcula. É peça que reaparece no módulo seguinte, dentro da determinização, e convém dominá-la isoladamente antes. Em seguida enuncia-se a equivalência entre os dois modelos como teorema, com o sentido fácil da demonstração feito em sala e o sentido difícil adiado para o módulo cinco, onde o algoritmo correspondente será construído.

A segunda metade é dedicada à construção de Thompson, que traduz cada operador de expressão regular em um fragmento de autômato não determinístico. O aspecto que merece atenção é a composicionalidade: cada fragmento tem exatamente um estado inicial e um estado final, e essa uniformidade é o que permite compor fragmentos sem casos especiais. A implementação traduz a árvore da expressão regular, produzida no módulo dois, no autômato correspondente — o primeiro momento em que duas peças do projeto se encaixam.

Profundidade: instrumental. Ao final do módulo, a ponte entre notação e máquina está construída e funcionando, o que corresponde à primeira metade do caminho até o analisador léxico.

1.2.5 Módulo 5: Determinização e Minimização

O autômato não determinístico produzido no módulo anterior funciona no papel e é impraticável na máquina. Este módulo o transforma em algo executável e depois o encolhe até o menor tamanho possível — e o resultado dessa segunda etapa tem uma propriedade notável: é único. Dois autômatos mínimos que reconhecem a mesma linguagem são o mesmo autômato, a menos de renomeação dos estados. Isso transforma um problema aparentemente difícil, decidir se duas especificações descrevem a mesma coisa, em um procedimento mecânico.

O estudo começa pela construção de subconjuntos, que converte o autômato não determinístico em determinístico tomando conjuntos de estados como estados novos. O tratamento das transições vazias entra aqui, usando o fecho estudado no módulo anterior. A análise de complexidade merece franqueza: o número de estados pode crescer exponencialmente no pior caso, existem famílias de linguagens que exibem esse crescimento, e ainda assim o comportamento típico em expressões regulares reais é modesto. Saber que o pior caso existe e que raramente ocorre é diferente de ignorá-lo.

Segue-se a eliminação de estados inalcançáveis e, então, o assunto principal: minimização. A noção de estados equivalentes e distinguíveis é construída com cuidado, porque é onde a intuição costuma falhar. O algoritmo de particionamento de Moore é apresentado e implementado, refinando sucessivamente uma partição inicial até o ponto fixo. O refinamento de Hopcroft é apresentado pela ideia e pela complexidade, sem exigência de implementação. Enuncia-se então a unicidade do autômato mínimo, e discute-se o que esse resultado permite decidir.

O módulo encerra com a exportação do autômato para um formato de visualização gráfica. Não é enfeite: um autômato de trinta estados é ilegível em tabela e compreensível em diagrama, e a visualização passa a ser instrumento de depuração pelo resto do semestre.

Profundidade: instrumental para a construção de subconjuntos e para a minimização de Moore; conceitual para Hopcroft, cujo interesse aqui está na análise de complexidade e não na implementação.

1.2.6 Módulo 6: Limites das Linguagens Regulares

Tente escrever uma expressão regular que reconheça parênteses balanceados. Você vai conseguir para dois níveis de aninhamento, para três, para dez — e nunca para todos. Não por falta de habilidade: é impossível, e este módulo mostra como se demonstra uma impossibilidade dessas. Saber que um modelo não dá conta de um problema é o que justifica trocar de modelo, e é exatamente essa demonstração que abre a segunda metade da disciplina.

O estudo trata primeiro das propriedades de fechamento. A classe das linguagens regulares é fechada sob união, concatenação, fecho de Kleene, complemento e interseção, e cada afirmação vem acompanhada da construção que a demonstra — o complemento por inversão dos estados finais em um autômato determinístico completo, a interseção pelo produto de autômatos. Além do valor teórico, essas construções são ferramentas de prova: demonstrar que uma linguagem não é regular frequentemente passa por combiná-la com outra regular e chegar a um absurdo.

O centro do módulo é o lema do bombeamento. Ele é apresentado primeiro pela intuição — um autômato com um número finito de estados, processando uma cadeia suficientemente longa, necessariamente repete algum estado, e o trecho entre as duas passagens pode ser repetido à vontade. Depois vem o enunciado formal, com atenção especial à sua estrutura lógica de alternância de quantificadores, que é onde a maioria das demonstrações erradas nasce. O uso correto é na forma contrapositiva, e convém pensar o argumento como um jogo entre dois adversários: o oponente escolhe o comprimento e a decomposição, você escolhe a cadeia e a potência que produz a contradição.

Aplicam-se então as técnicas aos exemplos canônicos, com destaque para a linguagem dos parênteses balanceados, pelo elo direto com o compilador. O teorema de Myhill-Nerode é apresentado como caracterização alternativa, em tratamento conceitual, pelo que oferece de complementar: enquanto o lema serve para provar que algo não é regular, Myhill-Nerode caracteriza exatamente o que é.

O fechamento é prático e memorável: o motor de autômatos construído nos módulos anteriores é confrontado com um padrão de parênteses balanceados e falha, como a teoria previu. A falha demonstrada é o argumento que motiva o modelo do módulo oito.

Profundidade: conceitual com exigência de demonstração. Espera-se que você produza uma prova de não regularidade completa e correta, ainda que sobre linguagens simples. Prova “quase certa”, aqui, é prova errada.

1.2.7 Módulo 7: Análise Léxica

Cinco módulos de teoria convergem em uma peça de software. O analisador léxico é a primeira fase real do compilador, e ele não é nada além do motor de autômatos que você já construiu, embrulhado em uma interface e cercado de decisões práticas que a teoria não menciona — e que são exatamente onde os compiladores reais gastam a maior parte do esforço.

O estudo situa primeiro o analisador léxico dentro do front-end e define sua interface com o analisador sintático, que é a de um produtor sob demanda: o analisador sintático pede o próximo símbolo, o analisador léxico o entrega. Definem-se então os quatro conceitos que se confundem com facilidade — o padrão, que descreve uma classe; o lexema, que é o trecho concreto do texto; o símbolo léxico, que é a categoria produzida; e o atributo, que carrega a informação adicional necessária às fases seguintes.

Vêm em seguida as duas regras de desempate que todo analisador léxico precisa implementar. A regra do casamento mais longo resolve o caso em que um padrão casa um prefixo do que outro casaria. A regra de prioridade resolve o caso em que dois padrões casam exatamente a mesma cadeia, e sua aplicação mais visível é a distinção entre palavras reservadas e identificadores. Discutem-se as duas estratégias usuais de implementar essa distinção e o compromisso entre elas.

O módulo trata então do que a teoria ignora: espaços em branco, comentários com e sem aninhamento, fim de arquivo, e a detecção de erros léxicos com produção de mensagens que indiquem posição e causa provável. Aborda-se também o buffer de entrada e o efeito do retrocesso sobre o desempenho, num tratamento breve mas suficiente para justificar as escolhas de implementação.

Fecha-se com os geradores automáticos de analisadores léxicos, apresentados agora e não antes por decisão deliberada: quem implementou a construção de subconjuntos entende o que o gerador faz, e quem não implementou apenas o utiliza. O módulo culmina na implementação do analisador léxico da linguagem condutora, reutilizando integralmente o módulo de autômatos já pronto.

Profundidade: instrumental e integradora. Os geradores automáticos recebem tratamento conceitual — você precisa saber o que fazem e quando usá-los, não escrever um. Este módulo fecha o primeiro ciclo completo do projeto.

1.2.8 Módulo 8: Gramáticas Livres de Contexto

O módulo seis provou que expressões regulares não descrevem aninhamento. Toda linguagem de programação tem aninhamento em toda parte: blocos dentro de blocos, expressões dentro de expressões, chamadas dentro de chamadas. Precisamos de um formalismo mais forte, e ele existe desde os anos cinquenta — é o mesmo formalismo com que os manuais de qualquer linguagem de programação descrevem sua sintaxe, ainda que quase ninguém repare nisso ao consultá-los.

O estudo define a gramática livre de contexto pelos seus quatro componentes: variáveis, terminais, produções e símbolo inicial. O nome do formalismo é explicado, porque esclarece: a substituição de uma variável não depende do contexto em que ela aparece. Definem-se então derivação, derivação mais à esquerda e mais à direita, e a árvore de derivação, com a relação precisa entre elas — a árvore abstrai a ordem das substituições, e cada árvore corresponde a exatamente uma derivação de cada tipo.

O tópico mais consequente do módulo é a ambiguidade. Uma gramática ambígua admite duas árvores distintas para a mesma cadeia, e isso significa que a mesma entrada tem dois significados possíveis — situação inaceitável em uma linguagem de programação. Estudam-se os dois exemplos clássicos, o das expressões aritméticas sem precedência declarada e o do condicional sem alternativa obrigatória, e as técnicas de eliminação: estratificação da gramática em níveis por precedência de operadores e resolução da associatividade pelo lado da recursão. Menciona-se, em tratamento conceitual, que existem linguagens inerentemente ambíguas, para as quais nenhuma gramática não ambígua existe, e que a ambiguidade de uma gramática arbitrária é indecidível.

Segue-se a simplificação de gramáticas — remoção de símbolos inúteis, produções vazias e produções unitárias — e as formas normais de Chomsky e de Greibach, apresentadas pelo que garantem e pelos algoritmos que as aplicam, sem uso direto no projeto. O módulo fecha com a escrita da gramática da linguagem condutora, com justificativa explícita de cada escolha que a mantém não ambígua e adequada à análise descendente do módulo dez.

Profundidade: instrumental para escrita, transformação e desambiguação de gramáticas; conceitual para as formas normais e para os resultados de indecidibilidade.

1.2.9 Módulo 9: Autômatos de Pilha

Se o autômato finito falha por ter memória limitada, a correção óbvia é dar-lhe memória. Mas dar memória irrestrita produziria uma máquina universal, poderosa demais para ser analisável. A solução histórica é dar memória de um tipo bem particular — uma pilha — e o resultado é exatamente o modelo que reconhece as linguagens livres de contexto. Além disso, este módulo traz a primeira surpresa genuína do curso: aqui, ao contrário do caso regular, o não determinismo importa de verdade.

O estudo define o autômato de pilha, com o alfabeto de pilha, o símbolo inicial de pilha e as transições que consultam simultaneamente o estado, o símbolo de entrada e o topo da pilha. Examinam-se as duas convenções de aceitação, por estado final e por pilha vazia, e demonstra-se que são equivalentes em poder — resultado técnico simples e bom exercício de construção.

O núcleo teórico é a equivalência entre gramáticas livres de contexto e autômatos de pilha, com as construções nos dois sentidos. A construção que parte da gramática é a mais instrutiva porque prefigura diretamente o analisador sintático do módulo dez: a pilha guarda o que ainda falta reconhecer, e cada expansão de variável substitui o topo pelo lado direito da produção. Quem entende essa construção entende o analisador descendente antes de vê-lo.

Vem então o resultado que distingue este nível da hierarquia: autômatos de pilha determinísticos são estritamente menos poderosos que os não determinísticos. Há linguagens livres de contexto que nenhum autômato de pilha determinístico reconhece. A consequência prática é grande e será sentida nos dois módulos seguintes — como não podemos, na prática, executar não determinismo em tempo razoável, a análise sintática real se restringe a subclasses determinísticas, e é por isso que existem famílias de métodos com poderes diferentes em vez de um método único.

Completa-se o quadro com o lema do bombeamento para linguagens livres de contexto, agora com duas subcadeias bombeadas simultaneamente, e com as propriedades de fechamento da classe, que reservam outra surpresa: a classe é fechada sob união mas não sob interseção nem complemento, ao contrário do caso regular. O módulo termina retomando a hierarquia de Chomsky com dois níveis já percorridos, e dá um panorama dos níveis restantes, mencionando a máquina de Turing e a existência de problemas indecidíveis.

Profundidade: conceitual, com formalização rigorosa e sem implementação do modelo abstrato. A realização concreta correspondente é o analisador sintático do módulo seguinte, e é lá que o código aparece.

1.2.10 Módulo 10: Análise Sintática Descendente

Este é o módulo em que a árvore aparece. Até aqui o compilador trabalhava com uma sequência linear de símbolos; a partir daqui trabalha com estrutura, e é a estrutura que carrega o significado do programa. É também o módulo mais denso do semestre, e o segundo grande marco de implementação.

O estudo enquadra a análise sintática como o problema de construir a árvore de derivação de uma cadeia segundo uma gramática, e a estratégia descendente como a construção da raiz para as folhas, seguindo uma derivação mais à esquerda guiada pelo próximo símbolo da entrada. Antes do algoritmo, porém, é preciso preparar a gramática: a recursão à esquerda torna o método impossível, porque produz recursão infinita, e sua eliminação é apresentada nos casos imediato e indireto. A fatoração à esquerda resolve o caso em que duas produções começam igual e a decisão não pode ser tomada com um símbolo de antecipação.

Vêm então os conjuntos de primeiros e de seguidores, com os algoritmos de cálculo por ponto fixo e o tratamento das variáveis que derivam a cadeia vazia — ponto de erro frequente que merece atenção deliberada. Com eles constrói-se a tabela de análise, e define-se a condição que caracteriza as gramáticas tratáveis por este método. A leitura dos conflitos na tabela é apresentada como diagnóstico: um conflito não é falha do algoritmo, é informação sobre a gramática, e normalmente indica ambiguidade, recursão à esquerda remanescente ou necessidade de fatoração.

Seguem-se as duas realizações do método. O analisador descendente recursivo, com uma função por variável da gramática, é notável pela transparência: a estrutura do código espelha a estrutura da gramática de forma tão direta que se pode ler uma na outra. O analisador dirigido por tabela, com pilha explícita, é comparado a ele quanto a legibilidade, desempenho e facilidade de modificação. A implementação do projeto segue o caminho recursivo, por essa transparência.

O módulo trata ainda da recuperação de erros sintáticos, em modo pânico e em nível de frase, com a discussão de um critério de qualidade frequentemente ignorado: um analisador que reporta um erro real seguido de vinte erros falsos é pior que um que reporta apenas o primeiro. Fecha-se com a construção da árvore sintática abstrata como saída da fase, distinguindo-a da árvore de derivação concreta, e com a implementação do analisador sintático da linguagem condutora.

Profundidade: instrumental e aprofundada, o nível mais alto de exigência do eixo sintático. Espera-se domínio completo do cálculo dos conjuntos, da construção da tabela e da implementação recursiva.

1.2.11 Módulo 11: Análise Sintática Ascendente

O método do módulo anterior é o que você vai implementar. Este é o que a maioria dos compiladores de produção usa. A diferença não é de moda: os métodos ascendentes reconhecem uma classe estritamente maior de gramáticas, e essa vantagem tem um preço em complexidade de construção e em legibilidade que justifica, em um curso, aprender primeiro o outro.

O estudo apresenta a estratégia ascendente como a redução da entrada ao símbolo inicial, construindo a árvore das folhas para a raiz. As operações de deslocamento e redução são definidas, junto ao papel da pilha, que aqui guarda o que já foi reconhecido — inversão exata em relação ao método descendente, onde a pilha guardava o que faltava reconhecer. O conceito de alça, o trecho que a próxima redução consumirá, organiza o restante.

Constrói-se então a maquinaria: itens, autômato de itens e o conjunto canônico de conjuntos de itens, com as operações de fechamento e transição. Sobre essa base apresentam-se os quatro métodos da família como uma escala crescente de poder e de custo — o mais simples, o que usa os conjuntos de seguidores para decidir reduções, o que os refina por estado, e o canônico completo. Para cada nível, explica-se qual conflito ele resolve e por que o nível anterior não resolvia. É essa progressão, e não a memorização das tabelas, o que se espera que fique.

Os conflitos de deslocamento-redução e de redução-redução são estudados como o principal instrumento de diagnóstico prático. Discutem-se as estratégias de resolução, incluindo declarações de precedência e associatividade, e o caso clássico do condicional sem alternativa obrigatória, cuja resolução usual é deliberadamente assimétrica.

O módulo fecha com a comparação fundamentada entre as duas famílias, quanto a poder expressivo, legibilidade do código produzido, qualidade das mensagens de erro e esforço de manutenção. Trata-se também dos geradores de analisadores sintáticos e da leitura dos relatórios de conflito que produzem, que é a habilidade que o profissional efetivamente usa.

Profundidade: conceitual com exercício de traçado manual. Espera-se que você construa tabelas para gramáticas pequenas com lápis e papel e interprete conflitos, mas não que implemente um gerador. O objetivo é decisão informada e leitura de ferramentas.

1.2.12 Módulo 12: Análise Semântica

Um programa pode estar sintaticamente perfeito e ainda assim não fazer sentido: usar uma variável que não foi declarada, somar um texto a um número, chamar uma função com o número errado de argumentos. A gramática não detecta nada disso, e não por deficiência da técnica — é resultado teórico que essas verificações estão fora do alcance de gramáticas livres de contexto. Esta fase existe para cuidar de tudo que a estrutura sozinha não garante.

O estudo abre com a distinção entre correção sintática e correção semântica, ilustrada por programas que passam pelo analisador sintático e não deveriam passar adiante, e com o argumento de por que essas verificações não podem ser incorporadas à gramática.

O componente central é a tabela de símbolos. Que informação armazenar sobre cada nome, que estruturas de dados servem à operação de consulta que domina o uso, e as operações de inserção, busca e remoção. Trata-se então dos escopos aninhados e das regras de visibilidade, com as duas estratégias usuais de implementação — pilha de tabelas, uma por escopo aberto, ou tabela única com encadeamento por nome — e o compromisso entre elas quanto a custo de entrada e saída de escopo.

Vem em seguida a tradução dirigida por sintaxe, que é o arcabouço conceitual da fase. Atributos sintetizados, que sobem na árvore, e herdados, que descem; gramáticas de atributos como especificação declarativa; esquemas de tradução com ações intercaladas às produções. A ordem de avaliação é tratada com cuidado, porque depende do grafo de dependências entre atributos e nem toda especificação é avaliável em um único percurso.

A verificação de tipos ocupa a última parte. Sistema de tipos, regras de inferência apresentadas na notação usual, equivalência estrutural e por nome, conversões implícitas e seus riscos. Discutem-se os percursos sobre a árvore sintática abstrata como forma de organizar as verificações, e a estratégia de recuperação que permite reportar vários erros semânticos em vez de parar no primeiro. A implementação cobre a tabela de símbolos e as verificações da linguagem condutora — que todo padrão referenciado tenha sido declarado, que as operações sobre valores casados sejam aplicáveis ao tipo do casamento, e que as comparações ocorram entre operandos compatíveis.

Profundidade: instrumental para tabela de símbolos e verificações; conceitual aprofundado para gramáticas de atributos, com implementação restrita ao esquema efetivamente usado no projeto.

1.2.13 Módulo 13: Representações Intermediárias e Ambientes de Execução

Um compilador que traduzisse diretamente da árvore para o código de uma arquitetura específica funcionaria, e seria inútil para qualquer outra arquitetura. A solução da indústria é passar por uma representação intermediária, e o ganho é combinatório: com uma representação no meio, suportar cinco linguagens de origem e cinco arquiteturas de destino custa dez peças em vez de vinte e cinco. Este módulo trata dessa camada intermediária e do modelo de máquina que executará o resultado.

O estudo começa pela justificativa da representação intermediária e pelas formas usuais. A árvore sintática abstrata, já construída. A notação pós-fixada, que dispensa parênteses e casa naturalmente com máquinas de pilha. O código de três endereços, com suas variantes de quádruplas e triplas, e a comparação entre elas quanto a facilidade de reordenação. Menciona-se, em tratamento panorâmico, a forma de atribuição única estática, que é a base das infraestruturas modernas de compilação.

Segue-se a tradução das construções usuais para código de três endereços: expressões, atribuições, comandos condicionais e laços, com o tratamento de rótulos, desvios e o problema de preencher endereços ainda desconhecidos no momento da emissão.

A segunda metade trata dos ambientes de execução, isto é, de como o programa se organiza na memória enquanto roda. A divisão em código, dados estáticos, pilha e área de alocação dinâmica, e o que determina a alocação de cada dado em cada região. O registro de ativação, sua composição usual e o protocolo de chamada e retorno, com a divisão de responsabilidades entre chamador e chamado. Escopo estático e dinâmico vistos do lado da execução, com as cadeias de acesso e de controle. Gerência de memória, com alocação e liberação explícitas, fragmentação, e um panorama das técnicas de coleta automática de lixo.

O módulo fecha definindo o formato concreto do objeto produzido pelo compilador da linguagem condutora e o modelo de execução da sua máquina virtual — decisão de projeto que condiciona diretamente o módulo seguinte.

Profundidade: instrumental para as representações efetivamente usadas no projeto; conceitual para registros de ativação e coleta de lixo, cuja relevância aqui é o repertório para linguagens com procedimentos, ausentes na linguagem condutora.

1.2.14 Módulo 14: Geração de Código

A partir daqui o compilador para de analisar e começa a produzir. E há uma inversão bonita esperando neste módulo: o código gerado pelo nosso compilador contém, ele mesmo, os autômatos estudados na primeira metade do semestre. A teoria que abriu o curso volta como formato de saída, o que fecha um ciclo que poucos projetos didáticos conseguem fechar.

O estudo apresenta o problema da geração de código e seus três subproblemas clássicos: selecionar as instruções que realizam cada operação, decidir que valores ficam em registradores, e ordenar a avaliação para reduzir o número de valores vivos simultaneamente. Discute-se que os três interagem, que resolvê-los separadamente é subótimo, e que resolvê-los conjuntamente é intratável.

Comparam-se então os dois modelos de máquina de destino. A máquina de pilha, com instruções sem operandos explícitos, é simples de gerar código e menos eficiente. A máquina de registradores é o oposto. A escolha do projeto recai sobre a de pilha, pelas razões didáticas evidentes, e o módulo projeta o conjunto de instruções da máquina virtual da linguagem condutora — carga de constante, acesso ao casamento corrente, extração de valor, comparações, combinações lógicas e emissão de resultado.

Vem então a geração propriamente dita, por percurso sobre a árvore sintática abstrata, com o tratamento de expressões aninhadas e a implementação de curto-circuito nos operadores lógicos, que exige emissão de desvios e não apenas de operações. A alocação de registradores é apresentada em tratamento conceitual, pelo modelo de coloração de grafo de interferência e pelo que acontece quando as cores não bastam. Trata-se ainda de endereçamento e resolução de referências pendentes.

O fechamento é o ponto alto conceitual do módulo: a emissão dos autômatos determinísticos como tabelas de transição dentro do próprio objeto gerado. O programa objeto passa a ter duas partes — o vetor de autômatos, que são as máquinas do primeiro bloco do curso, e o bytecode das regras, que é o código convencional. As duas metades da disciplina aparecem lado a lado no mesmo arquivo de saída.

Profundidade: instrumental para a máquina de pilha e para a emissão das tabelas; conceitual para alocação de registradores e para as particularidades de arquiteturas reais.

1.2.15 Módulo 15: Otimização e Integração Final

O compilador já funciona. Este módulo pergunta se ele poderia gerar código melhor, e depois junta tudo para rodar de ponta a ponta sobre entrada real. É onde o semestre inteiro se resolve — e onde costuma ficar claro, para quem acompanhou, quanto do que parecia teoria abstrata em fevereiro virou código funcionando em junho.

O estudo apresenta primeiro a estrutura sobre a qual a otimização opera. Blocos básicos, com o algoritmo de identificação de líderes, e o grafo de fluxo de controle construído a partir deles. Sobre essa base vêm as otimizações locais, aplicáveis dentro de um bloco: dobramento de constantes, propagação de cópias, eliminação de subexpressões comuns e eliminação de código morto. Cada uma é apresentada com a condição que a torna segura, porque o requisito absoluto de qualquer transformação é preservar a semântica do programa — uma otimização que acelera o código e muda o resultado é um defeito, não uma melhoria.

Segue-se um panorama das otimizações globais e do papel da análise de fluxo de dados, com a noção de solução por ponto fixo sobre o grafo de fluxo e os exemplos de definições alcançáveis e variáveis vivas. O tratamento é panorâmico e serve para situar o assunto e permitir leitura posterior. Discute-se também o compromisso entre tempo de compilação, tempo de execução e agressividade das transformações, que é o que os níveis de otimização dos compiladores reais expõem ao usuário.

A segunda metade é de integração. A execução ponta a ponta sobre entrada real, com o casamento mais longo entre padrões concorrentes, a ligação das variáveis de casamento, a avaliação das condições de cada regra e a execução das ações. Revisita-se o tratamento de erros ao longo de todas as fases, agora com o sistema completo à vista, discutindo a qualidade das mensagens como atributo de projeto e não como detalhe: a diferença entre um compilador agradável e um compilador hostil está quase inteiramente aí.

O módulo encerra com uma retrospectiva que percorre o caminho da expressão regular até o programa executável, e com um panorama de temas adjacentes para estudo posterior — compilação sob demanda durante a execução, máquinas virtuais de linguagens de uso corrente e infraestruturas modernas de compilação, que reaparecem em disciplinas posteriores e na vida profissional.

Profundidade: instrumental para blocos básicos e otimizações locais; panorâmica para análise de fluxo de dados e otimização global. O peso do módulo recai sobre a integração e sobre o fechamento conceitual.

1.3 Considerações sobre Progressão e Integração

A progressão do conteúdo obedece a uma regra que vale a pena tornar explícita: nenhum módulo introduz um modelo formal sem que o módulo anterior tenha demonstrado a insuficiência do modelo em uso. As expressões regulares aparecem porque precisamos de notação finita para conjuntos infinitos. Os autômatos determinísticos aparecem porque precisamos executar essa notação. Os não determinísticos aparecem porque a tradução direta a partir da notação os produz. As gramáticas livres de contexto aparecem porque o modelo regular falhou, e falhou de forma demonstrada, não alegada. Os autômatos de pilha aparecem porque as gramáticas precisam de uma máquina. A análise semântica aparece porque a gramática não captura tudo. Cada passo é uma resposta a uma limitação concreta encontrada no passo anterior.

Essa regra tem uma consequência para o estudo: se em algum momento você não conseguir responder à pergunta “por que estamos vendo isto agora?”, há uma lacuna a recuperar, e ela está atrás, não à frente. Vale voltar antes de prosseguir, porque a disciplina não perdoa dívidas acumuladas — o módulo dez usa o que foi construído no oito, que usa o que foi demonstrado no seis.

Os três marcos de consolidação. O conteúdo tem três pontos em que uma peça completa fica pronta e o acúmulo anterior se torna verificável. O primeiro é o módulo 7, com o analisador léxico funcionando sobre o motor de autômatos dos módulos 2 a 6. O segundo é o módulo 10, com o analisador sintático produzindo a árvore, e o front-end inteiro operacional. O terceiro é o módulo 15, com o compilador completo executando programas reais. Esses marcos não são apenas organizacionais: são os momentos em que uma dificuldade não resolvida deixa de ser um incômodo e passa a ser um impedimento. Chegar a eles com pendências torna o bloco seguinte inviável.

A relação entre este roteiro teórico e o Projeto Integrador é de sincronia deliberada, e convém entender sua natureza. O conteúdo teórico é o eixo; o projeto existe para que a teoria seja exercitada em algo que funciona, e não o contrário. Cada módulo apresenta a teoria nas duas aulas de exposição e reserva as quatro de tutoria para que o grupo incorpore ao seu projeto aquilo que acabou de estudar. O que cada grupo deve produzir em cada módulo é assunto da especificação do Projeto Integrador, não deste documento, mas o encadeamento é o mesmo: o que se estuda no módulo é o que se constrói no módulo.

Vale registrar que dois módulos escapam a essa sincronia por natureza do assunto. O nono, sobre autômatos de pilha, trata do modelo abstrato cuja realização concreta é o analisador sintático do décimo — o código correspondente existe, mas aparece um módulo depois. O décimo primeiro, sobre análise sintática ascendente, é de formação conceitual: o projeto segue o caminho descendente, e o estudo dos métodos ascendentes serve à capacidade de avaliar alternativas e de trabalhar com ferramentas que os implementam. Nesses dois módulos, o tempo de tutoria é aproveitado para consolidar o que ficou pendente e para amadurecer decisões de projeto.

O apoio ao acúmulo de dívida técnica e conceitual está no módulo de nivelamento, disponível desde o início e recomendado a quem sentir insegurança com notação de conjuntos, demonstração por indução ou manipulação de estruturas de dados encadeadas. Ele não é remediação para quem ficou para trás: é recurso de consulta para todos, e o momento mais produtivo de usá-lo é antes dos módulos dois e três, não depois de tropeçar neles.

Por fim, uma observação sobre a natureza cumulativa do trabalho. Ao contrário de disciplinas organizadas em exercícios independentes, aqui tudo o que se constrói permanece e é usado de novo. O código escrito no módulo três roda ainda no módulo quinze. Isso premia decisões de projeto tomadas com cuidado no começo e cobra caro por atalhos — e essa cobrança, que é a experiência mais próxima do desenvolvimento profissional real que o curso oferece, é parte do que a disciplina pretende ensinar.