flowchart TB
subgraph reg["O que é regular"]
ER["Expressões<br/>regulares"] --> AFN["Autômato não<br/>determinístico"]
AFN --> AFD["Autômato determinístico<br/>mínimo"]
end
subgraph lc["O que é livre de contexto"]
GLC["Gramática livre<br/>de contexto"] --> AP["Autômato<br/>de pilha"]
end
LIM["Limite provado do<br/>reconhecimento regular"]
AFD --> LIM
LIM --> GLC
AFD --> LEX["Análise léxica"]
AP --> SIN["Análise sintática"]
LEX --> SIN
SIN --> SEM["Análise semântica"]
SEM --> AMB["Ambiente<br/>de execução"]
AMB --> COD["Geração de código"]
Conteúdo Programático
Apresentação do Conteúdo
Da notação que uma pessoa escreve ao código que uma máquina executa, sem caixa-preta no meio.
Em junho de 1968, as Communications of the ACM publicaram um artigo curto de Ken Thompson: Regular Expression Search Algorithm. O programa descrito ali lia uma expressão regular. Depois escrevia código de máquina do IBM 7094 para procurar aquele padrão num texto. Ele não interpretava a expressão. Compilava.
O que Thompson montou é o percurso adiante em miniatura. Uma notação declarativa entra de um lado. Uma máquina que executa sai do outro. No meio ficam uma teoria e um programa que a aplica, e são esses dois que você constrói.
Duas tradições convivem nas páginas seguintes, e a maioria dos textos as mantém em prateleiras separadas. A teoria das linguagens formais estabelece o que cada classe de máquina reconhece e, sobretudo, o que ela jamais reconhecerá. A construção de compiladores pega essa teoria e a converte em análise léxica, análise sintática, análise semântica, ambiente de execução e emissão de código. A costura entre as duas é literal. Um autômato finito é o que um analisador léxico executa; um autômato de pilha é o que um analisador descendente realiza. Manter os dois lados afastados tira de quem estuda a única evidência convincente de que a teoria serve para alguma coisa.
Uma decisão de método vale do primeiro ao último capítulo: nada é delegado a um gerador automático de analisadores. Onde a prática corrente esconderia o autômato dentro de uma ferramenta, aqui ele é construído, determinizado e minimizado à mão. A alternativa tem resultado conhecido. Sai-se do outro lado sabendo operar a ferramenta e sem saber o que ela faz. Escrever o próprio determinizador dá mais trabalho do que chamar um gerador. Também é a única forma de descobrir que ele é bem menor do que parecia.
O programa que acompanha o texto chama-se Peneira: uma pequena linguagem de reconhecimento de padrões. Você declara padrões. Escreve regras sobre o que fazer quando um deles casa. O compilador produz então um objeto executável: um vetor de autômatos determinísticos somado a um bytecode de pilha. Quem o roda é uma máquina virtual escrita junto.
A economia dessa escolha aparece cedo. O mesmo módulo de construção de autômatos serve a dois níveis do sistema ao mesmo tempo. Os símbolos da própria linguagem são reconhecidos por autômatos. Os padrões que alguém escreve nela também compilam para autômatos. Uma peça, duas alturas. É por isso que a teoria de autômatos comparece duas vezes no artefato, em vez de aparecer uma vez e sumir dentro do analisador léxico.
Estrutura de Estudo e Profundidade
Três arcos, e cada um só existe porque o anterior terminou provando que precisava existir.
Quatorze temas, três arcos. O primeiro esgota o que uma máquina de memória finita reconhece e termina demonstrando um limite. O segundo atravessa esse limite com uma classe de gramáticas mais expressiva e as máquinas que lhe correspondem. O terceiro toma a estrutura que os dois anteriores produziram e a converte em algo que roda.
| Arco | O que se constrói | O que se prova |
|---|---|---|
| Do padrão ao autômato mínimo | reconhecedores de expressões regulares, determinização, minimização | a equivalência entre as duas famílias de autômatos e o limite do reconhecimento regular |
| Da gramática à árvore | gramáticas livres de contexto, autômatos de pilha, análise descendente | a correspondência entre gramáticas e máquinas com pilha |
| Da árvore ao código | tabela de símbolos, verificação de tipos, ambiente de execução, emissão | que a tradução preserva o significado do texto de partida |
A profundidade é desigual de propósito. Onde há código escrito à mão, o tratamento é construtivo e detalhado. Algoritmos em forma implementável, decisões de representação discutidas, custo medido em memória e em passos. Onde a função é fixar um resultado ou marcar uma fronteira, o tratamento é formal. A demonstração é conduzida quando cabe no nível do texto. Quando o aparato exigido custaria mais do que rende, ela dá lugar a um argumento de plausibilidade. Um dos temas, a análise ascendente, recebe tratamento comparativo e não vira código, e a intenção ali é formar critério de escolha.
Como você reconhece que entendeu um tema? O teste é sempre o mesmo, e repetir a definição não passa nele. Execute a construção à mão sobre um caso pequeno. Depois abra o código que a implementa e localize, linha a linha, cada caso da definição que a originou. Quem faz as duas coisas na mesma tarde entendeu; quem faz só a primeira decorou.
Duas leituras são possíveis, e elas terminam em lugares diferentes. Quem lê apenas a prosa terá aprendido a teoria. Quem executa o que a acompanha terá aprendido a engenharia. As páginas adiante foram escritas supondo o segundo.
Linguagens formais e a arquitetura de um compilador
Alfabeto, cadeia, linguagem. Três palavras, e com elas se descreve um conjunto infinito de textos sem escrever nenhum deles. Sobre essa base entram as operações que combinam linguagens: união, concatenação, fecho de Kleene. Uma linguagem passa a ser um conjunto, e não um catálogo grande.
Em 1956, Noam Chomsky publicou nas IRE Transactions on Information Theory o trabalho Three Models for the Description of Language. A hierarquia que leva o seu nome saiu dali, e ela casa classes de gramáticas com classes de máquinas. Aqui a hierarquia aparece como tabela. Nos temas seguintes, vira código.
A outra metade do assunto é a anatomia do sistema que traduz. Análise e síntese, front-end e back-end, as fases em sequência e o artefato que cada uma consome e devolve. A compilação e a interpretação ficam nas duas pontas de um eixo, e as formas intermediárias se distribuem entre elas. A máquina virtual da Peneira mora justamente no meio desse eixo.
O tratamento é largo na parte de arquitetura e formalizante na parte de linguagens. A função é permitir que tudo o que vem depois seja localizado dentro de um todo. Ao fim, você deve conseguir descrever de memória o caminho completo de um trecho de programa, da primeira letra lida ao resultado da execução.
Expressões regulares e linguagens regulares
Você já escreveu uma expressão regular alguma vez? Consegue dizer que conjunto de cadeias ela denota, exatamente? A segunda pergunta é bem mais difícil que a primeira, e é ela que este assunto responde. A expressão regular passa a ser objeto matemático, com sintaxe e semântica próprias.
As propriedades de fechamento entram em seguida: combinar linguagens regulares produz linguagem regular, e isso é o que autoriza montar um reconhecedor por partes. Classes de caracteres, quantificadores e abreviações de uso corrente aparecem como açúcar sobre um núcleo pequeno.
Duas competências se esperam ao final. Escrever a expressão correta para uma especificação dada em prosa. E decidir, diante de duas expressões diferentes, se elas denotam a mesma linguagem. A segunda parece ociosa e reaparece com outro nome no assunto da minimização.
Autômatos finitos determinísticos
A máquina entra em cena. O autômato finito determinístico é definido como quíntupla, com função de transição total e um conjunto de estados de aceitação. Reconhecer uma cadeia passa a ser percorrer uma sequência de configurações, um símbolo por passo.
Projetar vale mais do que simular. Dada uma especificação em prosa, você desenha a máquina que a reconhece. Trata entradas inválidas com um estado de erro explícito. E justifica por que o conjunto de estados escolhido basta. Quem só sabe em que estado está não sabe quantas vezes já entrou nele. A frase parece uma limitação técnica menor e é a fronteira inteira desta classe.
Perceba o deslocamento que acontece aqui. A tabela de transição deixa de ser um desenho no papel. Vira estrutura de dados com decisões de representação: como indexá-la, quanto ela ocupa, o que acontece quando o alfabeto cresce. É a primeira vez no percurso em que uma escolha teórica cobra preço em memória, e a conta aparece na página.
Autômatos não determinísticos e a construção de Thompson
Volte ao artigo de 1968. O programa de Thompson traduzia expressão em máquina de forma mecânica. A peça que torna isso possível é justamente o não determinismo, apresentado em quase todo lugar como esquisitice teórica.
Transições vazias, aceitação por existência de caminho, fecho vazio como operação básica de simulação. Em seguida vem a construção de Thompson. Cada operador da expressão vira um bloco de máquina com uma entrada e uma saída, e os blocos se compõem conforme a estrutura da expressão. Concatenação, união, fecho. Três regras de composição, mais os casos base, e a tradução está pronta.
Aqui uma transformação teórica se apresenta pela primeira vez como algoritmo pronto para implementação, sem nenhuma adaptação. Não há passo criativo no meio do caminho. Há uma definição indutiva de um lado e uma função recursiva do outro, com correspondência de um para um entre os casos.
O tratamento é formal e construtivo. Ao final, você executa a construção à mão sobre uma expressão de tamanho moderado. Depois reconhece, no código que a implementa, cada caso da definição que a originou. Guarde a máquina obtida: ela é elegante, correta e lenta. Os dois problemas do assunto seguinte existem por causa da última qualidade.
Determinização e minimização
A construção de subconjuntos resolve o primeiro problema e, de quebra, demonstra um resultado maior: as duas famílias de autômatos reconhecem exatamente as mesmas linguagens. A explosão de estados vem logo atrás. Quando ela importa na prática, e quando é apenas um limite superior que ninguém encontra, é o que se discute ali.
Depois disso, a relação de indistinguibilidade entre estados fundamenta a noção de autômato mínimo. O refinamento de partições fornece o algoritmo que o obtém. O tratamento é formal onde a demonstração cabe e construtivo no que diz respeito aos algoritmos.
Observe o que a minimização faz com a pergunta que ficou pendente lá atrás. Duas expressões regulares diferentes denotam a mesma linguagem? Minimize os dois autômatos. Compare-os. O autômato mínimo é único a menos de renomeação de estados, de modo que duas máquinas mínimas iguais respondem sim, e duas máquinas mínimas diferentes respondem não. Uma pergunta que parecia exigir criatividade vira um procedimento de três passos. Esse é o padrão que se repete no percurso inteiro: um resultado teórico transforma uma questão aberta num algoritmo decidível, e a implementação vem quase de graça depois disso.
Uma especificação declarativa entra; uma máquina eficiente sai; cada passo intermediário fica justificado. O código correspondente é a peça mais reaproveitada de toda a implementação de referência.
O lema do bombeamento e os limites do reconhecimento regular
Existe alguma linguagem que nenhum autômato finito reconhece? A resposta é sim, e ela não depende de o autômato ser grande ou pequeno. Depende de ele ser finito.
A intuição cabe em duas frases. Memória finita implica que, em cadeias suficientemente longas, algum estado se repete. O trecho consumido entre as duas visitas pode ser repetido ou removido sem que a máquina perceba a diferença.
O lema do bombeamento formaliza essa intuição. A estrutura lógica do enunciado exige atenção especial, por uma razão prática. Trata-se de um argumento de refutação com alternância de quantificadores, e essa alternância é a fonte mais comum de erro em quem o aplica pela primeira vez. Existe um comprimento; para toda cadeia acima dele; existe uma decomposição; para todo número de repetições. Trocar a ordem desses quatro passos produz uma demonstração que parece correta e não prova nada.
Quem escolhe a cadeia, em cada passo, também importa. O comprimento vem do adversário, que é a máquina hipotética. A cadeia vem de você. A decomposição volta a ser do adversário. E o número de repetições que produz a contradição é escolha sua de novo. Essa alternância de turnos é o que torna o argumento um jogo, e quem enxerga o jogo para de decorar a demonstração.
O tratamento é formal, com a demonstração conduzida por inteiro e aplicada ao caso dos delimitadores balanceados. Esse caso não foi escolhido por elegância. Ele é o padrão que a Peneira precisa reconhecer e não consegue, e é a falha concreta desse reconhecedor que motiva a subida a uma classe mais expressiva.
O caso dos delimitadores balanceados também mostra onde a fronteira passa, e ela é mais estreita do que parece. Um autômato finito reconhece parênteses aninhados até uma profundidade fixa, desde que essa profundidade seja escolhida antes de a máquina existir. Três níveis, dez níveis, mil níveis: basta acrescentar estados. O que ele não reconhece é o aninhamento sem teto. A diferença entre “profundidade grande” e “profundidade ilimitada” parece filosófica e é a única que importa aqui. Uma linguagem de padrões que se recusasse a contar acima de mil aberturas continuaria regular, e continuaria inútil, porque ninguém sabe declarar esse limite antes de ver a entrada.
O fecho delimita com cuidado o que o resultado autoriza a concluir e o que não autoriza. O lema prova que uma linguagem não é regular; ele nunca prova que uma linguagem é regular. Confundir as duas direções é o erro clássico, e ele sobrevive a muitas demonstrações bem-sucedidas antes de ser descoberto. Sem um limite provado, tudo o que vem depois pareceria capricho de organização — e é por isso que este assunto vem antes da gramática, e não depois.
Análise léxica
A máquina teórica vira componente de software com interface definida. Token, lexema e padrão passam a ser três coisas distintas, e os símbolos de uma linguagem se especificam por expressões regulares. Até aqui, nada que os assuntos anteriores não tenham preparado.
O problema novo aparece quando vários padrões concorrem pela mesma posição do texto. A regra do casamento mais longo resolve parte dele; o desempate entre padrões que reconhecem a mesma cadeia resolve o resto, e a ordem de declaração passa a ter consequência semântica. Espaços, comentários e erros léxicos recebem tratamento explícito. A posição no texto viaja junto com cada símbolo, porque sem ela nenhuma mensagem de erro posterior consegue apontar onde o problema está.
A economia estrutural anunciada na apresentação fica visível neste ponto: o reconhecedor construído aqui é o mesmo módulo de autômatos dos assuntos anteriores, instanciado sobre outra especificação. A interação inicial com a tabela de símbolos entra em forma mínima, para ser retomada quando a análise semântica cobrar dela escopo aninhado e verificação de tipos.
Gramáticas livres de contexto
Provado o limite, o percurso sobe de classe. Gramática livre de contexto, derivações mais à esquerda e mais à direita, árvore de derivação como o objeto que registra a estrutura descoberta: quatro definições, e as três primeiras servem para tornar a quarta precisa.
A ambiguidade recebe o cuidado que merece — origem, consequências para a tradução, técnicas de eliminação. Precedência e associatividade de operadores aparecem como propriedades que se escrevem dentro da própria gramática, e não como remendo aplicado depois. Note que essa escolha tem preço: a gramática cresce e fica menos legível, em troca de o analisador não precisar de tabela auxiliar nenhuma.
A parte final é preparatória e decisiva. Remoção de recursão à esquerda, direta e indireta, e fatoração à esquerda. Sem essas transformações, o analisador do assunto seguinte entra em laço infinito na primeira derivação. O tratamento é formal e de projeto: o que se espera é escrever uma gramática adequada a uma linguagem pretendida, e não ler uma que já veio pronta.
Autômatos de pilha
Em agosto de 1960, no Mathematisch Centrum de Amsterdã, Edsger Dijkstra e Jaap Zonneveld concluíram o primeiro compilador de ALGOL 60. A linguagem admitia procedimentos recursivos, o que na época não era óbvio de implementar, e a solução foi guardar os retornos numa pilha. Dijkstra publicou o mecanismo no mesmo ano, em Recursive Programming, na Numerische Mathematik.
A pilha é uma estrutura pobre. Só topo, sem consulta ao meio, sem contagem. Essa pobreza é o que a torna útil como modelo: acrescentada a um autômato finito, ela dá exatamente o poder de que as gramáticas livres de contexto precisam, e nem um grau a mais.
O assunto define o autômato de pilha formalmente, apresenta os dois critérios de aceitação — estado final e pilha vazia — e demonstra a equivalência entre eles. O resultado central é a equivalência entre autômatos de pilha e gramáticas livres de contexto, que fecha para esta classe o mesmo tipo de correspondência anunciada pela hierarquia de Chomsky no primeiro assunto do percurso.
Um ponto contraria a intuição construída no arco anterior. Nesta classe, determinismo e não determinismo não são equivalentes. Há linguagens livres de contexto que nenhum autômato de pilha determinístico reconhece, e a consequência é direta sobre o que um analisador consegue decidir olhando poucos símbolos à frente. Quem entende isso já sabe por que existem duas famílias de analisadores sintáticos, e por que a escolha entre elas é técnica.
Este é o único assunto do percurso cuja realização em código acontece no seguinte, e não nele. A recursão só é barata porque alguém decidiu guardar o retorno numa pilha; o analisador descendente é essa decisão, escrita em outra linguagem. E a mesma pilha ainda reaparece uma terceira vez, no registro de ativação, quando o assunto for a memória de um programa em execução — três alturas do mesmo objeto, com três nomes diferentes.
Análise sintática descendente
A maior densidade de implementação do percurso está aqui. A estratégia descendente se apresenta pela correspondência entre não terminais e procedimentos, o que faz o reconhecedor recursivo-descendente parecer quase uma transcrição da gramática — desde que a gramática tenha passado pelas transformações anteriores.
Os conjuntos de primeiros e de seguidores são construídos e usados. A condição que caracteriza as gramáticas analisáveis com um símbolo de antecipação é enunciada e verificada sobre casos concretos. Em seguida vem a variante dirigida por tabela, para que a decisão de análise deixe de estar espalhada pelo código e passe a ser um dado que se pode imprimir e conferir.
Duas exigências pesam mais que a média. A árvore sintática abstrata precisa ser projetada como estrutura de dados própria, distinta da árvore de derivação. E o tratamento de erros precisa produzir mensagem útil a quem escreveu o texto de entrada, não a quem escreveu o analisador. A segunda separa um exercício de um artefato que outra pessoa consegue usar.
A diferença entre as duas árvores costuma passar despercebida, e ela decide o que as fases seguintes precisam saber. A árvore de derivação registra o processo: cada nó é um não terminal da gramática, e os nós de parênteses e vírgulas estão todos lá, ocupando espaço. A árvore sintática abstrata registra o resultado. Nela, um nó de soma tem dois filhos e nada mais; os parênteses que ditaram a associação já cumpriram seu papel e desapareceram. Duas gramáticas diferentes para a mesma linguagem produzem árvores de derivação diferentes e podem produzir a mesma árvore abstrata. Quem entrega a árvore de derivação às fases seguintes as obriga a conhecer a gramática, e amarra a análise semântica a uma decisão que deveria ser local ao analisador.
A recuperação de erros merece a mesma atenção, por um motivo menos técnico. Um analisador que para no primeiro erro obriga quem escreveu o texto a recompilar uma vez por engano digitado. Um analisador que segue adiante depois do erro pode inventar dezenas de erros derivados do primeiro, e isso é pior. As estratégias que o assunto apresenta — descarte até um símbolo de sincronização, inserção de símbolo faltante — têm o mesmo objetivo modesto: relatar dois ou três erros reais e calar sobre o resto.
Análise sintática ascendente
A outra família entra por comparação. Deslocamento e redução, pilha de análise, a noção de handle, o autômato de itens e as tabelas correspondentes construídas à mão em casos pequenos.
Os conflitos recebem tratamento diagnóstico. Um conflito é informação sobre a gramática, e ler essa informação é a competência a formar. Os geradores automáticos de analisadores comparecem aqui, e só aqui, para deixar claro o que eles automatizam e o que continua sendo decisão de quem projeta.
Esta é a única teoria do percurso que não vira código no artefato de referência, e a escolha é declarada. O que se exige ao final é critério: diante de uma linguagem concreta, argumentar qual das duas estratégias cabe.
Análise semântica
Que erros nenhuma gramática pega? Usar um nome que não foi declarado. Somar coisas de tipos incompatíveis. Chamar algo com um número errado de argumentos. Tudo isso é sintaticamente impecável e semanticamente inválido.
A organização se faz em torno de duas peças. A tabela de símbolos, com escopo aninhado, inserção e consulta. E o sistema de tipos, com verificação, inferência local e conversão. As gramáticas de atributos e os esquemas de tradução dirigidos pela sintaxe descrevem como a informação sobe e desce pela árvore. A distinção entre atributos sintetizados e herdados ganha consequência prática na ordem de avaliação, que precisa ser compatível com a estratégia de análise adotada.
Uma mudança de regime acontece aqui, e ela explica boa parte da complexidade que vem depois. Pela primeira vez o compilador precisa manter conhecimento acumulado sobre o texto inteiro, e não apenas sobre a posição corrente. A qualidade das mensagens de erro semântico é tratada como requisito técnico, e não como acabamento.
Ambientes de execução
Antes de gerar código, é preciso saber para dentro de que mundo ele vai. A memória de um programa em execução se organiza em quatro regiões — código, área estática, pilha e área dinâmica —, e o registro de ativação é detalhado com passagem de parâmetros, valor de retorno e endereço de retorno.
O acesso a nomes não locais é onde o escopo do assunto anterior reaparece, agora em tempo de execução. Alocação dinâmica e estratégias de recuperação de memória entram em vista geral, sem descer ao detalhe de implementação de coletores. As máquinas virtuais e os modelos de execução baseados em pilha fecham o assunto, e é esse o modelo que o artefato de referência adota como alvo.
Geração de código
Em 1957, a equipe de John Backus entregou o compilador de FORTRAN na IBM sob uma suspeita generalizada: código gerado por máquina seria lento demais para ser levado a sério. Naquele projeto, a otimização entrou como condição de aceitação. Backus contou a história em The History of FORTRAN I, II, and III, publicado pela ACM em 1978.
Daí vem o método que fecha o percurso. Representações intermediárias aparecem em duas formas, o código de três endereços e as formas baseadas em pilha, com a discussão de por que existe uma representação intermediária em vez de se traduzir a árvore direto para o alvo. Depois vem a tradução da árvore sintática abstrata para essa representação, caso a caso. Depois a seleção de instruções e a emissão para uma máquina definida.
Repare que a Peneira facilita e complica esse trabalho ao mesmo tempo. Facilita porque a máquina de destino é conhecida por inteiro: quem escreveu a máquina virtual foi você, e o repertório de instruções dela cabe numa página. Complica porque o objeto emitido tem duas naturezas. De um lado, tabelas de transição de autômatos determinísticos, que são dados. De outro, bytecode de pilha para as regras, que é programa. Emitir as duas coisas no mesmo arquivo obriga a decidir o formato do objeto antes de escrever a primeira linha do emissor, e essa é a decisão de projeto que mais cobra caro quando tomada às pressas.
As otimizações elementares e independentes de máquina vêm com critério de aplicabilidade, e não como lista de truques: propagação e dobramento de constantes, eliminação de subexpressões comuns e de código morto, redução de força em variáveis de indução. Cada uma tem uma condição de segurança, e a condição é o que se estuda. Aplicar uma otimização válida a um caso em que ela não vale produz um compilador que gera código errado — a pior falha possível, porque o programa compila, roda e responde com números plausíveis.
O que a máquina não faz, o tradutor faz por ela — e cobra em instruções. A exigência final é medir essa cobrança. Contar instruções emitidas antes e depois de uma otimização. Comparar duas decisões antigas pelo efeito que produzem no código final. Uma escolha de representação da árvore, feita lá atrás, custa ou economiza instruções aqui, e nenhum adjetivo substitui a contagem.
Considerações sobre Progressão e Integração
Nenhum dos quatorze assuntos entra por completude. Cada um resolve um problema que o anterior deixou aberto, e quase todos terminam abrindo o próximo. O reconhecedor de padrões precisa de uma máquina. A máquina precisa ser determinizada para ser rápida. A máquina determinizada tem um limite provado. O limite obriga a subir de classe. A classe nova exige gramáticas transformadas. As gramáticas transformadas produzem um analisador. O analisador produz uma árvore que a sintaxe sozinha não valida. A validação exige memória acumulada. A memória acumulada descreve um ambiente de execução. E o ambiente de execução é o alvo do código emitido.
Ler fora dessa ordem é possível. Significa aceitar a resposta antes de ter sentido a pergunta, o que costuma sair mais caro do que parece.
O projeto que acompanha o texto cresce junto com os capítulos, e não ao final deles. A cada assunto, uma parte do sistema passa a existir e continua existindo. O que se constrói no arco dos autômatos é literalmente o mesmo código que o arco seguinte reaproveita, e o que o analisador sintático produz é literalmente o que a análise semântica consome. Quem constrói acompanhando a leitura chega ao fim com um sistema inteiro em mãos. Quem adia a construção descobre, tarde, que o fim é apenas a última peça de algo que deveria ter sido montado ao longo do caminho.
Duas integrações merecem registro. A primeira é interna ao artefato: o mesmo componente de autômatos serve ao reconhecimento dos símbolos da linguagem de padrões e à compilação dos padrões escritos nela. Quem percebe isso deixa de tratar a teoria de autômatos como pré-requisito a ser vencido e passa a vê-la como a peça mais reaproveitada do sistema.
A segunda é externa, e alcança bem mais do que compiladores. Toda vez que um programa precisa ler algo estruturado — um formato de configuração, um protocolo, uma consulta, uma expressão escrita por alguém —, o problema tem esta mesma forma. A diferença entre resolvê-lo com uma cascata de condicionais frágeis e resolvê-lo com uma gramática e um analisador é exatamente o que estas páginas ensinam.
Volte ao artigo de 1968. Thompson escreveu um programa que lia uma notação e emitia código de máquina; o que você monta ao longo destes capítulos é a mesma coisa, com mais fases no meio e um limite provado no caminho. A diferença entre os dois está em quantas vezes a teoria precisou ser chamada para que o programa ficasse de pé.
Como o Conteúdo se Distribui na Oferta
O roteiro acima diz o que se aprende e em que ordem. Falta o calendário: em quanto tempo esse roteiro cabe e quando cada instrumento de avaliação incide. E o que se espera do estudante em cada etapa.
Quatorze módulos de conteúdo, um por semana. A semana da disciplina tem seis aulas. Quatro são teóricas; duas são de tutoria do Projeto Integrador.
As aulas teóricas apresentam o conteúdo do módulo e conduzem, ao vivo, a construção da implementação de referência. As de tutoria pertencem aos grupos. Ali cada equipe faz o próprio projeto avançar, com acompanhamento do professor e intervenção que diminui semana após semana. No começo o professor senta junto e mexe no teclado. No fim, passa, olha a tela e pergunta.
Nada é pedido fora do horário de aula. E nenhuma atividade proposta é alheia ao Projeto Integrador. Se uma tarefa não faz o projeto do grupo avançar, ela está competindo com ele pelo tempo do estudante. E costuma vencer, porque parece mais fácil.
O calendário reserva ainda cinco semanas. Elas cobrem feriados que caem no dia da disciplina, eventos institucionais e semanas de avaliação. Não recebem conteúdo novo e não são módulos. A entrega final do Projeto Integrador ocorre na semana seguinte à conclusão do último módulo de conteúdo. Essa semana conta como tempo de disciplina, não como módulo adicional. Se algum módulo esticar por duas semanas, a compensação sai da reserva. Nunca da supressão de conteúdo.
Antes do Primeiro Módulo
O que a turma já sabe no primeiro dia decide quanto o resto vai custar.
O percurso é precedido de um módulo de nivelamento, que recompõe quatro pré-requisitos conceituais de que a disciplina depende de forma direta. As estruturas de dados em que a árvore sintática, a tabela de símbolos e o reconhecedor descendente são construídos. A familiaridade com definições formais e com a leitura de uma demonstração, sem a qual o lema do bombeamento vira ritual decorado. A distinção entre sintaxe e semântica. E as noções de registrador, memória e conjunto de instruções, que reaparecem inteiras na geração de código.
Quanto disso a turma tem? E onde, exatamente, ela está mais frágil? Repare que nenhuma das duas perguntas se responde por impressão do professor. Antes que o primeiro módulo de conteúdo comece, a turma responde a uma sondagem diagnóstica dos pré-requisitos. Ela não compõe nota, e essa característica é o que a torna útil. Seu propósito é revelar, por tópico, onde a turma está, para que a ênfase do nivelamento seja calibrada com dado. Atribuir-lhe peso a converteria em prova. A turma estudaria para ela, e a informação que ela existe para produzir morreria na véspera.
Articulação com a Avaliação
O acompanhamento é contínuo, mas os instrumentos que compõem nota são poucos e declarados desde o primeiro dia de aula. A verificação individual de teoria é aplicada por blocos de módulos. As fronteiras dos blocos seguem o eixo teórico do percurso, jamais a aritmética de repartir quatorze módulos em partes iguais:
| Bloco | Módulos | Eixo verificado |
|---|---|---|
| Primeiro | do primeiro ao sexto módulo | linguagens regulares e autômatos finitos |
| Segundo | sétimo e oitavo módulos | análise léxica e gramáticas livres de contexto |
| Terceiro | do nono ao décimo primeiro módulo | análise sintática |
| Quarto | do décimo segundo ao décimo quarto módulo | análise semântica, ambientes de execução e geração de código |
Os blocos são desiguais de propósito: o segundo é o mais curto de todos porque reúne apenas os dois módulos que fazem a dobradiça entre o que é regular e o que é livre de contexto. Avaliá-lo junto de qualquer vizinho misturaria duas classes da hierarquia numa nota só, e o estudante sairia da devolutiva sabendo que errou sem saber em qual das duas classes tropeçou. São quatro aplicações no período, o que mantém a disciplina dentro da referência de poucos instrumentos com nota e muitos momentos de devolutiva.
Cada verificação é individual, feita em aula, sem consulta e sem uso de inteligência artificial, e mede exclusivamente a teoria do bloco — nunca a tarefa de projeto do grupo. Essa separação é o que torna o instrumento informativo. Um artefato coletivo bem-acabado esconde quem estudou a teoria e quem passou o período segurando o café da equipe. A devolutiva é imediata, pelo comentário que acompanha cada alternativa, e é esse retorno que mantém formativo um instrumento que, apesar de tudo, compõe nota.
Ao longo dos módulos, a evolução do projeto de cada grupo é acompanhada por entregas parciais. Ao final, o produto completo é defendido em arguição individual, na qual cada integrante responde tanto pela parte que escreveu quanto pelas consequências de decisões tomadas em fases vizinhas do artefato do próprio grupo. A dinâmica de grupo, o calendário relativo das entregas, a rubrica publicada com a proposta do trabalho e a política de integridade e de uso de inteligência artificial estão especificados no documento do Projeto Integrador, e não se repetem aqui.
O que se Espera em Cada Etapa
Três arcos, e o risco muda de natureza em cada um deles.
No arco dos autômatos, o estudante deve chegar às aulas de tutoria com o reconhecedor construído até onde a teoria já permitiu. O risco desta etapa tem nome: adiar o código porque o conteúdo parece abstrato demais para virar software. Quando a análise léxica chegar, ela será a instanciação de um módulo que precisa existir e funcionar.
No arco da gramática, espera-se a transição do reconhecimento para a estrutura. A gramática do projeto de cada grupo precisa estar escrita, transformada e defendida antes que o analisador seja implementado. Quem inverte essa ordem gasta a tutoria depurando recursão à esquerda em vez de projetar. E aí está o estrago: o defeito estava na gramática, e o grupo foi procurá-lo no código.
No arco da tradução, espera-se integração. As entregas parciais deixam de acrescentar peças isoladas. Passam a exigir que o sistema funcione ponta a ponta, ainda que sobre um subconjunto reduzido da linguagem. É também a etapa em que o estudante justifica decisões técnicas tomadas módulos antes, porque é isso que a arguição individual verifica.
Os comandos das atividades amadurecem junto com o percurso. Nos módulos iniciais eles pedem definir, explicar e exemplificar; nos intermediários, resolver, aplicar e comparar; nos finais, justificar, criticar e propor. Um conjunto de atividades em que todos os comandos fossem “defina” verificaria memória e devolveria uma turma capaz de recitar a definição de autômato finito determinístico sem conseguir escrever um. O que a disciplina avalia é a capacidade de sustentar um artefato inteiro e defender cada escolha feita dentro dele. Sorte não sobrevive à arguição.