Autor

Afiliações

Moacyr Francischetti Corrêa, Bacharel em Ciência da Computação, Licenciado em Computação, Especialista em Ciência de Dados e Inteligência Artificial, PhD em Biotecnologia in Silico

UNIMAR - Universidade de Marília

Projeto Integrador

A Implementação de Referência

A referência construída ao longo dos capítulos chama-se Peneira, e é o compilador de uma linguagem de reconhecimento de padrões em texto. O que ela produz é um motor de autômatos — uma tabela de transição por padrão declarado, mais um roteiro de instruções por regra — que uma máquina própria percorre sobre a entrada, casando o trecho mais longo que algum padrão reconheça. Programa que executa comandos, ali, nenhum.

A economia que sustenta a obra inteira está numa reutilização: o mesmo mecanismo de construção de autômato serve duas vezes e em dois níveis. Os elementos da própria linguagem Peneira nascem de expressões regulares convertidas em autômato, e os padrões que quem escreve declara nascem exatamente do mesmo caminho. Uma peça, dois usos — e é por isso que a teoria de autômatos aparece duas vezes no artefato, em vez de virar uma caixa fechada dentro do reconhecedor e nunca mais ser vista.

O alvo de execução do seu projeto é livre. Máquina virtual própria, roteiro de instruções interpretado ou código de máquina real: qualquer um deles atende, desde que exista de fato um artefato gravado pelo tradutor e lido depois por outra coisa. A referência escolheu a máquina própria porque ela torna a fronteira visível — o objeto emitido pode ser aberto, inspecionado e executado noutro momento, e essa separação é o que a leitura dos capítulos finais persegue.

Entender um algoritmo e fazê-lo funcionar sobre entrada que ninguém preparou são duas coisas. A primeira se verifica lendo. A segunda só se verifica construindo.

Por isso a leitura tem um par. Enquanto os capítulos avançam pela teoria das linguagens formais e pela engenharia de compiladores, você constrói um sistema completo: o compilador de uma linguagem sua. Quem escreve nessa linguagem descreve padrões sobre um domínio que você escolheu. O compilador transforma essa descrição num motor de reconhecimento, e o motor roda sobre entrada real do domínio.

A construção acompanha a leitura, e não vem depois dela. A razão é técnica. Muitas decisões estudadas aqui só mostram o preço quando alguém precisa tomá-las. A tabela de transição só ocupa memória depois de existir. A explosão de estados só assusta quando o processo demora. O tratamento de erro só parece importante quando outra pessoa usa o programa e recebe uma mensagem incompreensível. Quem adia a construção chega ao último capítulo com conceitos corretos e nenhuma experiência do que eles custam.

Em 1956, Noam Chomsky publicou Three Models for the Description of Language nas IRE Transactions on Information Theory. Ele era linguista, e as quatro classes saíram de restrições na forma das regras de uma gramática. A correspondência com máquinas veio depois, de outra direção. É dela que sai a razão pela qual um analisador léxico não casa parênteses. Entre um resultado de linguística matemática e uma linha de código que falha, poucas pontes são tão curtas — e atravessá-la com um sistema em construção nas mãos é outra experiência.

O Projeto que Acompanha esta Obra

Catorze peças que se encaixam.

O sistema que você constrói é cumulativo. Cada capítulo acrescenta uma peça, e a peça do capítulo seguinte se apoia diretamente nela. No fim da leitura, quem construiu junto tem um programa que recebe uma descrição escrita na sua linguagem, a compila, executa o resultado sobre uma entrada qualquer e produz saída. Nenhum gerador automático de analisadores participa disso, em ponto algum da cadeia.

O domínio da linguagem é escolha sua, e a escolha é larga. Os padrões podem falar de caracteres de um texto. Também podem falar de eventos registrados, de entradas de um controle, dos campos de um registro, das palavras de um comando ou dos bytes de um quadro de protocolo. O que muda de um domínio para outro é o alfabeto sobre o qual a máquina opera, o conteúdo do objeto produzido e o que o motor faz ao reconhecer.

O que não muda é a cadeia inteira estudada aqui. Sua escolha é livre sem ser arbitrária, e a seção seguinte diz quais propriedades ela precisa ter.

Existe também uma implementação de referência, construída ponta a ponta. Ela mostra o que um resultado maduro parece, e existe para ser estudada. Os capítulos a exibem funcionando, expõem as decisões que a moldaram e nomeiam as alternativas descartadas. O sistema que você constrói continua sendo o seu: sua linguagem, suas escolhas de representação, suas mensagens de erro. A referência é modelo de acabamento, não gabarito a transcrever.

flowchart TB
    A["Arco 1<br/>Do padrão ao autômato mínimo"] --> A1["Fica pronto:<br/>reconhecedor de padrões<br/>que roda sobre texto"]
    A1 --> B["Arco 2<br/>Da gramática à árvore"]
    B --> B1["Fica pronto:<br/>leitor da linguagem<br/>que produz estrutura"]
    B1 --> C["Arco 3<br/>Da árvore ao código"]
    C --> C1["Fica pronto:<br/>tradutor e motor<br/>que executam o resultado"]
    A1 -. reaproveitado por .-> C
    A1 -. reaproveitado por .-> B

O que a Sua Linguagem Precisa Ter

Seis propriedades. Duas delas ninguém percebe faltando até ser tarde.

Escolher o domínio é a primeira decisão do percurso, e a mais consequente. Ela determina se os capítulos seguintes vão encontrar no seu sistema o objeto de que precisam. Uma linguagem mal escolhida não trava a construção. O que ela faz é pior: deixa capítulos inteiros sem contrapartida.

Quem cai nisso termina implementando a teoria num canto que ninguém usa, ou não a implementando. As seis propriedades abaixo separam uma escolha que exercita a obra inteira de uma que exercita metade dela. Confira a sua contra elas antes de escrever a primeira linha de especificação. Corrigir o recorte no terceiro capítulo custa o triplo.

1. Quem usa a sua linguagem escreve padrões.

Não você, ao construir o sistema. O usuário, ao escrever um programa nela.

Esta é a propriedade que sustenta o arco inteiro dos autômatos, e a única cuja ausência não se percebe de imediato. Se o usuário nunca escreve um padrão, a construção de Thompson, a determinização e a minimização passam a servir apenas ao reconhecimento dos símbolos da sua própria linguagem. Viram preâmbulo de uma caixa fechada. O autômato deixa de ser o produto e vira detalhe interno, que é o modo mais comum de perder metade da obra sem notar.

2. Os símbolos da própria linguagem saem do mesmo motor.

O componente que compila os padrões do usuário é o mesmo que reconhece os símbolos do texto que ele escreveu, instanciado sobre outra especificação. Dentro do seu sistema, isso é a evidência de que a teoria de autômatos comparece em duas alturas diferentes.

Uma linguagem cujos símbolos exijam um reconhecedor escrito à parte (porque não cabem no seu próprio maquinário) está avisando algo. O maquinário ficou pequeno demais, e o aviso ainda custa pouco nesta altura.

3. A gramática tem aninhamento e exige transformação.

Alguma construção da sua linguagem precisa conter outra da mesma espécie. Expressões com parênteses e precedência são o caso mais barato de obter, e bastam.

Sem aninhamento, a gramática cabe numa lista de casos. A remoção de recursão à esquerda e a fatoração não têm o que transformar, e o analisador descendente vira uma cascata de condicionais que não ensina nada sobre a família de máquinas que ele realiza.

4. Há mais de um tipo, declaração antes do uso e escopo verificável.

Dois tipos bastam, e a distinção pode ser modesta. Um valor numérico e um textual já servem.

O que precisa existir são nomes que se declaram e depois se usam, para que haja algo a registrar numa tabela de símbolos. Precisa existir também ao menos uma forma de uso inválido que a sintaxe aceita e o significado recusa: referência a nome inexistente, comparação entre tipos incompatíveis, nome visível num lugar e não em outro. Sem isso, a análise semântica não tem o que verificar, e o capítulo correspondente passa em branco pelo seu sistema.

5. O produto é um objeto, e não uma resposta imediata.

O seu compilador não pode responder à entrada enquanto a lê. Ele produz um artefato — as tabelas dos autômatos mais as instruções que dizem o que fazer no reconhecimento — e um segundo componente executa esse artefato sobre a entrada real.

Essa separação é o que dá conteúdo ao capítulo sobre ambientes de execução e ao de geração de código. Um sistema que interpreta a descrição na hora, sem produzir objeto algum, chega ao fecho da obra sem ter nada a gerar.

6. O domínio oferece um pedido natural que a máquina finita não atende.

Precisa existir, no seu domínio, algo que qualquer usuário consideraria razoável pedir e que exige contagem irrestrita. Delimitadores balanceados servem. Um trecho que precisa reaparecer invertido adiante, também. Um campo cujo tamanho vem declarado no campo anterior, também.

É esse pedido que você submete ao seu próprio reconhecedor, no capítulo em que o sistema demonstra o que não consegue. Um domínio em que todo pedido plausível é regular deixa aquele capítulo sem demonstração, e a subida à classe seguinte passa a parecer capricho de organização.

O erro previsível. A escolha que mais tenta quem está começando é uma pequena linguagem imperativa: variáveis, atribuição, condicional, repetição. Ela satisfaz as propriedades 3, 4 e 5 com folga. E falha exatamente nas duas que sustentam a primeira metade da obra. O usuário não escreve padrão algum, e não há pedido natural fora do alcance da máquina finita, porque a linguagem não promete reconhecer coisa alguma. O resultado é um projeto respeitável que atravessa seis capítulos sem ter onde encostar. Se o seu recorte caminha para lá, troque o domínio por um em que descrever padrões seja a razão de a linguagem existir.

Repare no que fica livre, que é bem mais do que o que fica fixo. São decisões suas o domínio e o alfabeto sobre o qual os padrões operam. É sua a sintaxe concreta, até o último sinal de pontuação. São seus o núcleo mínimo de operadores e a lista de notações de conveniência que se reduzem a ele antes de qualquer processamento.

As seis propriedades dizem o que a sua linguagem precisa fazer existir, nunca a forma com que ela o faz. Também decide você a representação da tabela de transição, o conjunto de tipos, o formato do objeto produzido, a regra de desempate entre padrões concorrentes e o texto de cada mensagem de erro.

Um teste rápido, antes de fixar o recorte. Escreva à mão, em cinco linhas, um programa de exemplo na linguagem que você está imaginando. Depois responda a quatro perguntas. Onde nele há um padrão escrito por quem usa a linguagem? Que construção contém outra da mesma espécie? Que erro dá para cometer neste exemplo que só é detectável depois de consultar uma declaração feita acima? E que pedido razoável deste domínio você não consegue escrever aqui, por exigir contagem sem limite? Quatro respostas concretas significam recorte pronto. Uma resposta hesitante custa uma tarde agora e quatro capítulos depois.

O Ambiente em que o Sistema é Construído

O projeto é construído em C++, editado a partir do VS Code, com um sistema de build que descreve a compilação uma vez e a resolve em qualquer sistema operacional. Nada do que se constrói aqui depende da plataforma. O código usa apenas o padrão da linguagem e sua biblioteca, e por isso o mesmo fonte compila sob os três compiladores de maior circulação. É assim que ele se mantém verificável fora da máquina de quem o escreveu.

A escolha da linguagem conforma o que se aprende. Uma linguagem sem gestão automática de memória obriga quem constrói a decidir como representar grafos com ciclos — que é o que um autômato é. Tomada cedo, essa decisão atravessa todo o restante do sistema.

A recomendação que atravessa a construção inteira é usar C++ como um C melhorado. Contêineres e cadeias da biblioteca padrão para tudo o que for infraestrutura; estruturas explícitas para as tabelas de transição, que são o objeto de estudo. Estados representados por índices inteiros dentro de um vetor, e não por ponteiros, eliminam de saída a maior parte dos defeitos de memória sem esconder a máquina. Num percurso cujo assunto é justamente a máquina, escondê-la seria trocar o que se quer aprender pela conveniência de não pensar nisso.

O compilador é usado no modo mais rigoroso (avisos tratados como erros, verificação estrita de conformidade ligada). Isso incomoda no primeiro dia e economiza semanas depois. Num programa que manipula índices de tabela o tempo inteiro, um aviso ignorado sobre conversão implícita de tipo é um defeito adiado. Essa disciplina de escrita faz parte do que se demonstra ao mostrar o resultado, e por isso o código do projeto é explicitamente tipado em toda parte: parâmetros, retornos, campos e variáveis declaradas.

O build é organizado desde o primeiro capítulo, ainda que haja pouca coisa a compilar. Um sistema que cresce por acumulação precisa de um comando único que reconstrói tudo e roda a bateria de casos existente. Sem ele, a verificação de que a peça anterior continua funcionando deixa de acontecer. E ela é a única defesa contra o defeito mais caro deste tipo de projeto, que é a regressão silenciosa num componente considerado pronto.

flowchart LR
    L["Ler o capítulo<br/>até o fim"] --> P["Decidir a representação<br/>antes de digitar"]
    P --> E["Escrever a peça<br/>no repositório"]
    E --> T["Submetê-la a casos<br/>que deveriam falhar"]
    T --> R["Registrar por escrito<br/>a decisão e o motivo"]
    R --> V{"A peça anterior<br/>continua passando?"}
    V -- "sim" --> L
    V -- "não" --> D["Voltar à peça anterior<br/>antes de avançar"]
    D --> T

Como o Sistema Cresce, Capítulo a Capítulo

Doze etapas com código, duas sem, nenhuma reordenável.

O que segue descreve, para cada capítulo, o que passa a existir no sistema e o que caracteriza a etapa como concluída. A ordem não é sugestão. Repare que cada etapa consome o que a anterior produziu, e pular uma delas não adianta trabalho: transfere a dificuldade para um ponto em que ela custa mais caro.

Dois capítulos, assinalados adiante, são de natureza conceitual e não acrescentam peça ao sistema. Neles se constrói critério, e critério se demonstra em prosa.

flowchart TB
    subgraph obs["O que se observa de fora"]
        O1["Uma execução<br/>que produz saída"]
        O2["Um caso de erro<br/>com mensagem legível"]
        O3["Um caso de fronteira<br/>que antes quebrava"]
    end
    subgraph reg["O que fica escrito"]
        R1["A representação escolhida<br/>e a descartada"]
        R2["O custo que a escolha cobra"]
        R3["O que ainda não funciona"]
    end
    ETAPA["Etapa concluída"] --> obs
    ETAPA --> reg
    obs --> PROX["Só então a etapa<br/>seguinte começa"]
    reg --> PROX

Linguagens formais e a arquitetura de um compilador

Aqui passa a existir o contorno do que será construído: o domínio escolhido, a classe de padrões que o seu sistema aceitará, a forma da descrição escrita pelo usuário e o que o sistema produzirá ao processá-la. É um documento curto e consequente, porque tudo o que vem depois responde a ele. As seis propriedades enunciadas mais atrás são conferidas aqui, uma a uma, contra o recorte que você acabou de fixar. Duas coisas prontas fecham a etapa. Um exemplo escrito à mão de descrição válida na sua linguagem, com o que se espera que o sistema faça ao recebê-la. E o repositório de trabalho já montado, na estrutura definida mais adiante neste capítulo.

Expressões regulares e linguagens regulares

A primeira peça de código: a leitura de uma expressão de padrão e sua conversão numa estrutura em árvore. O trabalho de projeto está em decidir o núcleo mínimo de operadores que o sistema tratará de fato, e quais notações de conveniência serão reduzidas a esse núcleo antes de qualquer processamento. Essa decisão reduz drasticamente o tamanho de tudo o que vem depois. Três sinais fecham a etapa. Expressões suas são lidas corretamente. Expressões malformadas são recusadas com mensagem que aponta a posição do problema. E duas notações diferentes para o mesmo padrão produzem a mesma estrutura.

Autômatos finitos determinísticos

Entra em cena a máquina, e com ela a primeira decisão de representação que cobra preço em memória: como armazenar a função de transição. Perceba que a escolha é sua, e que ela é definitiva na prática. A etapa exige que o sistema execute uma máquina descrita à mão sobre uma cadeia de entrada, reportando aceitação ou recusa, e que trate explicitamente o símbolo sem transição prevista. A representação escolhida precisa de justificativa escrita. Quanto ela ocupa, em função do tamanho do alfabeto? A resposta entra ali, ao lado da alternativa descartada e da razão do descarte.

Autômatos não determinísticos e a construção de Thompson

A ponte entre a estrutura em árvore da primeira peça e a máquina da segunda. Aqui a construção teórica se transcreve quase diretamente em código, pela primeira vez no percurso. A sensação não se repete com frequência. Fecha quando toda expressão aceita pela sua leitura de padrões produz uma máquina não determinística. A simulação dessa máquina precisa reconhecer as cadeias certas. E um punhado de casos de teste compara o resultado da simulação com o que você determinou à mão.

Determinização e minimização

A peça mais reaproveitada de todo o sistema, e a que merece o cuidado maior. A conversão para uma máquina determinística e a redução ao número mínimo de estados transformam um reconhecedor correto porém lento em algo utilizável.

Duas armadilhas moram aqui, e as duas passam despercebidas por semanas. A primeira é conferir a equivalência entre a máquina original e a reduzida por inspeção visual dos diagramas. Duas máquinas com o mesmo desenho e um estado de aceitação trocado parecem iguais na tela, e discordam na primeira cadeia que ninguém pensou em testar. A verificação honesta compara as duas sobre um conjunto de cadeias, incluindo as que devem ser recusadas.

A segunda armadilha é acreditar na redução sem medi-la. Quantos estados havia antes, quantos há depois: os dois números precisam sair do próprio sistema, impressos, e não de uma contagem feita à mão numa tarde de bom humor.

Falta ainda construir de propósito um caso em que a determinização multiplica os estados. Ele existe, é pequeno de escrever, e ver o crescimento acontecer na sua máquina muda a leitura do capítulo. Com as três coisas feitas — equivalência verificada por comparação, números reportados pelo sistema, crescimento acentuado observado —, a etapa fecha.

O lema do bombeamento e os limites do reconhecimento regular

O capítulo em que o sistema demonstra o próprio limite. O que se acrescenta é uma demonstração executável: um padrão que exige contagem irrestrita, escrito na sua linguagem, submetido ao seu reconhecedor, com o resultado observado e explicado. Delimitadores balanceados são o caso canônico. Fecha com um caso reproduzível que evidencia a falha. Junto vai um texto curto: por que a falha é necessária, e não um defeito de implementação. É essa demonstração que justifica tudo o que vem em seguida.

Análise léxica

O reconhecedor deixa de ser programa isolado e vira componente com interface. O sistema passa a ler a descrição escrita pelo usuário, quebrando-a em símbolos. Quem faz esse reconhecimento é o mesmo componente dos capítulos anteriores, instanciado sobre outra especificação. Quatro sinais fecham a etapa. A descrição de exemplo é reconhecida por inteiro. Cada símbolo carrega a sua posição no texto de origem. Espaços e comentários são descartados. E um caractere inválido produz uma mensagem que diz onde ele está.

Gramáticas livres de contexto

A etapa de projeto mais exigente do percurso, e aquela em que a quantidade de código escrito engana. Passa a existir a gramática da sua linguagem, por extenso, sem recursão à esquerda e devidamente fatorada, com precedência e associatividade dos operadores expressas na própria estrutura das regras.

Note que a gramática precisa existir como dado que o seu programa percorre, e não como comentário ao lado do analisador. Comentário se desfaz na primeira correção feita só de um lado. Sendo dado, a gramática responde a perguntas: onde há recursão à esquerda, onde há prefixo comum entre alternativas, quantas derivações distintas ela admite para a mesma sentença. A gramática deriva o exemplo escrito no primeiro capítulo? A derivação aparece passo a passo? Cada transformação está registrada com a forma anterior ao lado da final? Três respostas afirmativas, e a etapa está fechada; uma negativa aponta exatamente onde voltar.

Autômatos de pilha

Capítulo conceitual, sem peça correspondente no sistema. A realização concreta do modelo estudado aqui é o analisador construído no capítulo seguinte, e antecipá-la significaria implementar antes de entender por quê. O que se acrescenta é entendimento verificável, em particular a razão pela qual, nesta classe de máquinas, o determinismo deixa de ser conveniência e passa a limitar o que se consegue reconhecer. A etapa está concluída quando você explica, sobre a sua própria gramática, que decisão local o analisador precisará tomar e com que informação ele contará para tomá-la.

Análise sintática descendente

A etapa de maior volume de código. O sistema passa a construir, a partir da sequência de símbolos, uma árvore que representa a estrutura da descrição lida. Essa árvore precisa ser projetada como estrutura própria, distinta da derivação que a gramática induz, contendo o que as etapas seguintes vão consumir e nada além disso. A descrição de exemplo produz a árvore esperada. Uma descrição sintaticamente inválida gera mensagem dirigida a quem a escreveu. E o analisador prossegue depois de um erro, em vez de encerrar no primeiro problema. Com as três acontecendo sobre a mesma descrição de exemplo, a etapa está fechada.

Análise sintática ascendente

Segundo capítulo conceitual, e o único cuja teoria não é implementada por escolha declarada. O sistema segue o caminho descendente por inteiro, e construir uma segunda família completa custaria mais do que renderia.

O que se acrescenta é critério de escolha. Diante da sua própria gramática, o que mudaria se a estratégia fosse a outra? Que conflitos apareceriam, e o que eles revelariam sobre a gramática? A etapa está concluída quando existe um texto curto que sustenta a escolha feita com argumento técnico, e não com a conveniência.

Análise semântica

O sistema passa a manter conhecimento acumulado sobre o texto inteiro, e não apenas sobre a posição corrente. Nomes declarados são registrados e consultados. Referências a nomes inexistentes são recusadas, e as comparações escritas pelo usuário são verificadas quanto à compatibilidade dos tipos envolvidos. A etapa está concluída quando cada condição de invalidez prevista pela sua linguagem produz uma mensagem específica, e quando uma descrição válida atravessa a verificação sem falso alarme. Essa segunda metade, a do falso alarme, é a que mais se esquece de testar.

Ambientes de execução

Passa a existir o mundo em que o resultado vai rodar: o modelo de execução do seu sistema, o formato do que será produzido e a forma como os dados reconhecidos ficam disponíveis durante a execução. É uma etapa de pouco código e muita consequência. O formato decidido aqui é o contrato entre as duas metades do sistema. Fecha quando o formato está escrito por extenso, com um exemplo preenchido à mão para uma descrição mínima. O modelo de execução escolhido também precisa estar justificado, com a alternativa que você descartou.

Geração de código

O fecho. O sistema passa a produzir, a partir da árvore verificada, o objeto executável no formato definido. O motor que carrega esse objeto percorre um texto de entrada real, aplica os reconhecedores e produz saída.

Observe que só aqui a cadeia inteira fica sujeita a uma prova que nenhuma peça isolada sofreu. Até este capítulo, cada componente foi exercitado com entrada que você mesmo preparou para exercitá-lo. Agora um arquivo que ninguém escolheu atravessa o sistema do texto de partida ao resultado final, e qualquer desencontro entre duas etapas aparece.

Fecha quando esse percurso completo funciona e a regra de desempate entre padrões concorrentes está implementada e demonstrada. Falta uma medida numérica comparando duas decisões — quantidade de estados, de instruções emitidas ou de casos processados por unidade de entrada. Qualquer uma serve, desde que seja número, e não adjetivo pendurado numa impressão.

A Organização do Repositório de Trabalho

Um sistema que cresce por acumulação precisa de um lugar onde crescer. A forma desse lugar determina se a peça do capítulo oito reaproveita a peça do capítulo cinco ou se acaba reescrevendo uma versão paralela dela. A organização adotada é simples de propósito e se reparte em três lugares distintos.

flowchart TB
    RAIZ["Repositório de trabalho"] --> RM["README<br/>o que é, como se compila,<br/>como se executa"]
    RAIZ --> DOCS["docs<br/>gramática, decisões,<br/>diário de construção"]
    RAIZ --> SRC["src<br/>o código, uma peça<br/>por responsabilidade"]
    DOCS --> D1["A linguagem<br/>que o sistema aceita"]
    DOCS --> D2["As decisões técnicas<br/>e o que se descartou"]
    SRC --> S1["O que reconhece"]
    SRC --> S2["O que estrutura"]
    SRC --> S3["O que traduz e executa"]

A apresentação do repositório diz, em poucos parágrafos, o que o sistema faz, como se compila e como se executa. Traz um exemplo de uso completo que alguém reproduz sem perguntar nada a ninguém.

É o primeiro texto lido por quem chega de fora e o último a ser escrito por quem constrói, o que explica por que costuma ficar ruim. Escreva-o cedo, e corrija-o a cada capítulo em que o sistema mudar de forma.

A documentação guarda a especificação da linguagem que o sistema aceita, o registro das decisões técnicas com as alternativas descartadas e o diário da construção.

As três coisas envelhecem se não forem atualizadas junto com o código. Uma documentação que descreve um sistema que não existe mais é pior do que a ausência dela, porque induz ao erro em vez de apenas deixar de ajudar.

O código se organiza por responsabilidade, uma peça por assunto, com fronteiras que correspondem às etapas descritas acima.

Separe o que reconhece, o que estrutura e o que traduz. É essa separação que permite substituir a representação da tabela de transição sem tocar no analisador. E trocar o formato do objeto produzido sem reescrever a verificação de tipos.

Falta uma observação sobre a fronteira entre infraestrutura e miolo. Configuração de build, leitura de arquivos, tratamento de argumentos de linha de comando e apoio a testes são necessários, e não são o assunto. O miolo algorítmico é o que se está estudando: a conversão de expressões em máquinas, a determinização, a redução de estados, a análise, a tradução. Manter os dois separados evita que o andaime obscureça a construção. É boa prática de engenharia e, ao mesmo tempo, a condição para que o resultado consiga ser mostrado a alguém.

O que Caracteriza um Bom Resultado

Quatro propriedades que se verificam de fora, e nenhuma delas conta linhas.

Um sistema construído ao longo desta obra pode chegar ao fim de quatro maneiras diferentes. A distinção entre elas não está na quantidade de código.

flowchart LR
    F["Funciona<br/>sobre entrada que<br/>ninguém preparou"] --> R["Resultado defensável"]
    S["Sustenta mudança<br/>uma peça nova entra<br/>sem reescrever o resto"] --> R
    E["Se explica<br/>cada escolha tem<br/>uma razão dizível"] --> R
    R --> U["Alguém de fora<br/>consegue usar"]
    R --> C["Alguém de fora<br/>consegue continuar"]

Funciona sobre entrada que ninguém preparou. É a propriedade mais simples de enunciar e a mais frequentemente ausente. Um sistema que processa bem os três exemplos escritos por quem o construiu, e falha no primeiro arquivo real, não está pronto: está ajustado aos próprios testes. A verificação é direta. Pegue um texto que você não escolheu, submeta-o ao sistema e observe. Só há duas respostas aceitáveis, o resultado correto e uma recusa explicando o que há de errado com a entrada. Qualquer coisa entre as duas é defeito.

Sustenta mudança. Um sistema construído por acumulação é testado toda vez que uma peça nova entra, sem que ninguém planeje isso. Se acrescentar um operador à sua linguagem de padrões obriga a tocar em seis lugares, a estrutura está errada, ainda que tudo funcione. A verificação também é direta. Escolha uma extensão pequena que você não implementou e conte quantos pontos do sistema precisariam mudar. Esse número mede o acoplamento, e é observável sem executar nada.

É um sistema só, e não uma coleção de peças parecidas com um. As etapas precisam estar ligadas de verdade. Os símbolos que o reconhecedor produz são os mesmos que o analisador consome; a árvore que o analisador constrói é a mesma que a verificação anota; a árvore anotada é a que alimenta a tradução. Peças demonstradas em separado, cada uma com entrada preparada à mão para a demonstração dela, imitam um compilador sem serem um. A imitação passa despercebida até alguém pedir para rodar do texto de partida ao objeto final sem parar no meio. Uma execução única, ponta a ponta, custa um comando e revela em segundos o que semanas de demonstrações isoladas escondem.

Se explica. Cada decisão técnica de peso tem uma razão que cabe em duas frases, e essa razão inclui a alternativa descartada. Vale para a representação da tabela de transição, para a forma da árvore, para o formato do objeto produzido e para a ordem em que os padrões concorrentes são desempatados. Quem construiu entendendo responde por que não é de outro jeito. Quem transcreveu de algum lugar descreve o que o código faz e para aí. A diferença é imperceptível no texto do programa e evidente em trinta segundos de conversa.

flowchart TB
    Q1{"A peça roda sobre<br/>uma entrada real?"} -- "não" --> N1["Ainda não está pronta"]
    Q1 -- "sim" --> Q2{"Ela recusa corretamente<br/>o que deve recusar?"}
    Q2 -- "não" --> N2["Falta o caso de erro"]
    Q2 -- "sim" --> Q3{"A peça anterior<br/>continua funcionando?"}
    Q3 -- "não" --> N3["Regressão: corrigir<br/>antes de seguir"]
    Q3 -- "sim" --> Q4{"Você consegue explicar<br/>por que não é de outro jeito?"}
    Q4 -- "não" --> N4["Foi copiada,<br/>não projetada"]
    Q4 -- "sim" --> OK["Etapa concluída"]

Duas escolhas plausíveis não contam como cobertura, e é melhor saber disso agora. A primeira é integrar uma biblioteca pronta que faz justamente o trabalho que o capítulo pedia: um reconhecedor de padrões tomado de fora cumpre a função e fecha o mecanismo que existia para ser aberto. A segunda é pendurar um assunto como ornamento, sem que nada no artefato dependa dele. Um diagrama de autômato desenhado à parte, que o sistema não executa nem consulta, é decoração.

A observação final é a mais difícil de aceitar enquanto se constrói. Qualidade de mensagem de erro é requisito técnico, e não acabamento. Um sistema que reconhece bem a entrada válida e encerra abruptamente diante da inválida está pela metade. E a metade que falta é a que mais se usa: quem escreve padrões passa boa parte do tempo descobrindo por que o padrão escrito não faz o que pretendia. É aí que o resultado deixa de ser exercício e passa a ser algo que outra pessoa consegue usar.

Mostrar o que Foi Construído

Por que a melhor demonstração começa pelo que o sistema recusa.

Construir e demonstrar são competências distintas. A segunda costuma ser tratada como consequência automática da primeira, e não é. Uma demonstração mal conduzida de um sistema excelente convence menos do que uma demonstração bem conduzida de um sistema mediano. A assimetria não é injusta: quem constrói tem a obrigação de tornar visível o que construiu.

flowchart TB
    P1["Mostrar o problema<br/>antes da solução"] --> P2["Executar uma vez,<br/>ponta a ponta, sem cortes"]
    P2 --> P3["Quebrar de propósito<br/>e mostrar a mensagem de erro"]
    P3 --> P4["Abrir uma decisão<br/>e dizer a alternativa descartada"]
    P4 --> P5["Mostrar um número:<br/>estados, instruções, casos"]
    P5 --> P6["Dizer o que ainda<br/>não funciona"]

Comece pelo problema, nunca pela solução. Mostre o texto de entrada e a saída pretendida antes de qualquer explicação sobre o funcionamento. Isso dá a quem assiste um lugar onde encaixar o que vem depois. Em seguida execute uma vez, do início ao fim, sem cortes. A execução completa é a única evidência de que as peças estão ligadas, e uma demonstração feita de fragmentos levanta exatamente a dúvida que deveria dissipar.

Depois quebre o sistema de propósito. Submeta uma descrição inválida e mostre a mensagem produzida. Submeta um padrão que exige mais do que a classe de máquinas reconhece e mostre o limite acontecendo. Demonstrar o que o sistema recusa impressiona mais do que demonstrar o que ele aceita: revela que quem construiu pensou nos casos fora do caminho feliz.

Reserve o centro da demonstração para uma única decisão técnica, apresentada com a alternativa descartada e a razão da escolha. Um número ajuda. Quantos estados a redução eliminou, quantas instruções a mais o resultado teria sem determinada transformação, quantos casos por segundo o motor processa. Uma medida concreta vale mais do que três adjetivos, e é o que separa a apresentação de um sistema da narração do seu código.

Termine dizendo o que ainda não funciona. A tentação de esconder as lacunas é forte, e o efeito é o oposto do pretendido. Quem assiste encontra as lacunas de qualquer forma, e encontrá-las depois de ouvir que tudo funciona desqualifica também o que de fato funcionava. Nomear com precisão o que ficou de fora, e por quê, é o sinal mais confiável de que quem construiu entende o próprio sistema. Na prática, é a diferença entre um resultado apresentado e um resultado defendido.

Vinte Assuntos Possíveis

O que muda de um projeto para outro é o assunto sobre o qual a linguagem fala. A cadeia por baixo dele é sempre a mesma: reconhecer, estruturar, verificar, traduzir, executar. É essa cadeia que o percurso constrói. A lista adiante não oferece vinte trabalhos diferentes, e sim vinte maneiras de encontrar a mesma cadeia por lados distintos. Cada uma endurece um ponto que as outras deixam macio.

Cada entrada diz o que a cena mostra, o que ela endurece e a armadilha que traz junto. Todas trazem uma. Depois vem o campo que responde ao que mais aflige quem escolhe: o que exatamente eu vou ter em mãos no fim? A resposta traz quatro coisas concretas. Um exemplo do que alguém escreve na sua linguagem. O arquivo que o seu compilador grava em disco. O que o segundo programa faz com esse arquivo sobre entrada real, e a cena que se mostra a alguém quando está pronto.

Os trechos de linguagem que aparecem ali são uma forma possível, jamais a obrigatória. A sintaxe concreta, até o último sinal de pontuação, continua sendo decisão de quem constrói. Repare que os exemplos foram escritos curtos de propósito, para caber numa linha e não sugerir gramática nenhuma.

Cada entrada carrega ainda três campos que separam um exercício de uma investigação. Uma pergunta cuja resposta você não sabe antes de medir. A grandeza que responde a ela, comparada contra a solução de referência da própria área. E o que contaria como resultado negativo, que numa investigação é achado e não fracasso — quem não souber disso vai esconder justamente o dado que mais valia.

flowchart TD
    E["Escolha do assunto"] --> R["Reconhecimento<br/>por estados"]
    E --> S["Estrutura que<br/>se aninha"]
    E --> V["Verificacao antes<br/>da execucao"]
    E --> A["Artefato gravado<br/>e depois executado"]

    R --> R1["alfabeto, prioridade<br/>entre padroes, tamanho<br/>da tabela de transicao"]
    S --> S1["profundidade, precedencia,<br/>ambiguidade, recuperacao<br/>de erro"]
    V --> V1["tipos, escopo, ordem<br/>de declaracao, posicao<br/>no fonte"]
    A --> A1["formato do objeto,<br/>pilha e chamadas,<br/>custo do que se emite"]

    R1 --> M["O que a proposta<br/>endurece"]
    S1 --> M
    V1 --> M
    A1 --> M

    M --> P["A pergunta cuja resposta<br/>ninguem sabe de antemao"]
    P --> G["A grandeza medida contra<br/>a referencia da area"]
    G --> N["O resultado que contraria<br/>quem propos"]

Medir contra nada invalida a medida. Qualquer coisa ganha do vazio, e o achado passa a ser do entusiasmo de quem mediu. A referência honesta é a abordagem que a área já usa para o mesmo problema. Ela é mais difícil de vencer, e por isso a única cuja derrota significa alguma coisa.

Uma linguagem que desenha o que leu

O programa não desenha uma figura fixa. Ele lê um texto qualquer e desenha o que encontrou lá dentro. Quem usa escreve duas coisas: os padrões que extraem números do texto e os comandos que transformam esses números em traço. Um cursor que anda, vira, levanta e baixa a caneta. Blocos que se repetem. Alimentado com dois arquivos diferentes, o mesmo programa produz dois desenhos diferentes.

Esta escolha endurece a captura, e nenhuma outra proposta chega perto disso. Reconhecer que uma linha casa com o padrão é fácil, e o autômato determinizado resolve. Dizer de onde saiu cada pedaço é que é difícil. Qual trecho da linha foi o primeiro número, qual foi o segundo: a determinização é justamente o passo que joga fora por onde a máquina passou. A armadilha é resolver a captura com um segundo reconhecedor escrito à parte, por retrocesso. Ficam duas máquinas que discordam sobre a mesma entrada, em algum caso que ninguém testou.

O que fica pronto. Um programa em que se lê quando linha casa /(\d+),(\d+)/ entao ir $1 $2 e, abaixo, repetir 4 { mover lado; virar 90 }. É uma forma possível, e a pontuação é sua. O compilador funde os padrões num autômato que registra onde cada grupo casou. Depois grava o objeto: tabela de transição, marcas de captura, instruções de desenho. O executor carrega esse objeto e um arquivo de dados que ninguém preparou. Uma exportação de planilha, uma tabela copiada de algum lugar. Dele sai o desenho. A cena que fecha o trabalho é o mesmo objeto rodando sobre dois arquivos de dados e desenhando duas figuras. A captura vai conferida à mão numa linha em que os dois números têm tamanhos distintos.

O detalhe merece a descida, porque ele reaparece nas outras dezenove com outra roupa, e quase sempre disfarçado de decisão menor. Um autômato determinizado responde uma pergunta de cada vez: a cadeia pertence à linguagem, sim ou não. O caminho percorrido some, e é essa perda que o torna rápido. Só que o desenho precisa dos números, e os números estão no caminho. Alguma coisa tem de guardar, para cada posição da entrada, que grupo começou ali e que grupo terminou.

Há mais de uma saída, e o percurso ensina as duas metades de cada uma. Marcar as transições com instruções de registro. Guardar o conjunto de posições (todas elas) e resolver a disputa no fim. Voltar ao autômato não determinístico apenas nos trechos em que houve captura. Nenhuma delas sai de graça, e escolher exige medir.

Repare ainda no que a decisão arrasta. Guardar posições muda o formato do objeto gravado, porque a tabela de transição passa a carregar marcas. Muda o segundo programa, que precisa entregar os pedaços capturados aos comandos de traço. E muda a mensagem de erro, porque um grupo que nunca casou tem de ser distinguido de um grupo que casou vazio. O que se ganha em troca é uma linguagem que faz o que a maioria dos programas de desenho não faz.

Pergunta: a partir de quantos grupos de captura o rastreio das posições passa a dominar o tempo de reconhecimento, e existe forma de padrão em que a captura obriga a abandonar o autômato determinizado? Medida: tempo por símbolo e memória do reconhecedor, com e sem captura, contra o mesmo padrão resolvido por uma biblioteca de expressões regulares com grupos. Negativo: a captura pesa pouco em toda a faixa útil, e a arquitetura elaborada que ela motivou não se sustenta.

Descrever quadros de um protocolo binário

Aqui o alfabeto é o byte. A entrada não tem linhas nem espaços onde se apoiar. A linguagem descreve a forma de um quadro: um cabeçalho com certos valores, um campo de tamanho, uma carga que depende dele. O motor produzido varre a sequência e reconhece os quadros bem formados. Note que aqui não há token, linha nem palavra: só bytes em fila.

O que se endurece é a fronteira entre o que um autômato finito reconhece e o que ele não reconhece. Um campo de tamanho que determina quantos bytes vêm depois escapa do regular. Descobrir isso construindo marca bem mais do que ler que é assim. A armadilha é resolver o campo de tamanho com um contador pendurado no reconhecedor: funciona, e a máquina deixou de ser finita sem que ninguém tenha notado.

O que fica pronto. Quem usa escreve a forma de um quadro: cabecalho = 0xAA 0x55, seguido de tipo: 1 byte em {01,02,07} e carga: bytes ate 0x0D. De novo, uma forma possível entre muitas. O compilador transforma isso na tabela de um autômato sobre o alfabeto de 256 símbolos e grava o arquivo objeto correspondente.

O executor pega esse objeto e um arquivo binário capturado de verdade. Varre byte a byte. Imprime o deslocamento onde cada quadro começa, o tipo reconhecido e o tamanho. A demonstração que fecha é essa varredura sobre uma captura real. Os quadros bem formados saem listados, e cada trecho recusado vem com a posição exata da recusa.

Pergunta: que subconjunto do formato escolhido é genuinamente regular, e onde está a primeira construção que exige memória além dos estados? Medida: número de quadros do formato real reconhecidos pela parte regular, contra a cobertura de uma especificação escrita à mão do mesmo formato. Negativo: tudo o que aquele protocolo traz cabe no regular, e o campo que parecia escapar foi mal lido por você.

Uma linguagem de fórmulas de planilha

Poucas construções, todas conhecidas. Referências a células, operadores aritméticos, chamadas de função, parênteses. Repare no que a familiaridade compra: ninguém precisa aprender o domínio para julgar se um resultado saiu certo.

Precedência e associatividade são o que esta escolha endurece. Multiplicação antes de soma. Potência associando à direita. Unário competindo com binário. Cada uma dessas regras precisa estar na estrutura que o analisador constrói, e não num remendo posterior. A armadilha mora na aparência de facilidade, porque uma expressão pode avaliar certo em dez casos, ter a árvore errada e revelar isso só no décimo primeiro.

O que fica pronto. A entrada é uma fórmula digitada como quem digita numa célula, e =(A1+B2)*3^2^0.5 serve de exemplo. Do compilador sai um arquivo de instruções para uma máquina de pilha, na ordem em que ela precisa empilhar e operar. O número fica para depois. O segundo programa lê esse arquivo, recebe os valores das células citadas e imprime o resultado. Compilada uma vez, a mesma fórmula roda cem vezes com valores diferentes sem passar de novo pelo analisador. É isso que dá o que ver numa demonstração. Considere pronto quando a sequência de instruções gravada para uma expressão com potência aninhada puder ser lida na tela e conferida à mão contra a árvore que a precedência exige.

Pergunta: quantos casos de teste são necessários para distinguir uma árvore com precedência correta de outra que apenas acerta o valor nos casos comuns? Medida: casos que separam as duas árvores, contra a suíte de conformidade de uma implementação de planilha estabelecida. Negativo: valor correto e árvore correta coincidem em toda entrada construível, e distingui-los não muda nada observável.

Vários personagens reagindo ao mesmo mundo

Quem usa a linguagem declara personagens e, para cada um, as sequências de acontecimentos a que ele reage. Um inimigo avistado e depois dois danos seguidos levam a recuar. Um obstáculo à frente seguido de chão firme leva a saltar. O que sai consome a gravação de uma partida e produz a sequência de ações que cada personagem executou.

Esta escolha endurece a convivência de vários reconhecedores sobre o mesmo fluxo, e é problema que nenhuma outra proposta encosta. A linguagem de combos também lê acontecimentos na ordem em que chegam. Mas ali existe uma máquina só, e a dificuldade está em decidir sem enxergar o que vem depois. Aqui todas as máquinas leem tudo. Acontece que a dificuldade aparece no instante em que três delas concluem ao mesmo tempo que é hora de agir.

Que ação vale primeiro, o que acontece com as outras duas e por que a resposta é sempre a mesma quando a gravação é a mesma? Nada disso se decide sozinho. A armadilha é deixar a ordem emergir de onde cada personagem foi declarado no arquivo. Funciona, e ninguém percebe. A partida deixa de ser reproduzível no dia em que alguém reordena as declarações.

O que fica pronto. Um arquivo em que se lê heroi { quando vi_inimigo, dano, dano -> recuar(); } ao lado de guarda { quando vi_inimigo -> atacar(); }. Uma forma possível, e a pontuação é sua. O compilador funde os padrões de todos os personagens num objeto único. Ele traz as tabelas de transição, a tabela de ações e a regra de desempate já resolvida.

O executor carrega esse objeto e uma gravação de acontecimentos de uma partida real. Imprime a linha do tempo: em que instante cada personagem agiu, que ação foi essa e qual padrão a provocou. A cena que fecha o trabalho é a mesma gravação submetida duas vezes. As declarações dos personagens vão em ordens diferentes no arquivo, e as linhas do tempo saem idênticas.

Pergunta: quantas vezes, numa partida gravada, mais de um personagem conclui no mesmo instante que deve agir, e a regra de desempate sobrevive quando os padrões são escritos por quem não a conhece? Medida: instantes com mais de uma ação disputando e divergências entre execuções da mesma gravação, contra a ordem de aplicação que um motor de regras de produção estabelecido documenta para o mesmo conflito. Negativo: disputas simultâneas quase não ocorrem em partidas reais, e a regra elaborada resolve algo que o mundo não apresenta.

Um mini-assembler para uma máquina inventada

A linguagem de entrada é textual e simples. O que sai é uma sequência de instruções codificadas que uma máquina de sua autoria executa. Rótulos, saltos, um punhado de operações. Observe que a máquina é sua, e o repertório dela cabe numa página.

Esta escolha endurece a fronteira material entre compilar e executar. O objeto gravado tem de ser lido de volta por um componente que não é o tradutor, possivelmente noutro momento, e o formato precisa estar escrito antes de existir. A armadilha é o rótulo referenciado antes de ser definido, que obriga uma segunda passagem e revela que traduzir linha a linha não basta.

O que fica pronto. Um texto de montagem com linhas como laco: CARGA R1, 10 e SALTA_SE_ZERO fim. Dele sai um arquivo binário: cabeçalho, código e a tabela do que ficou por resolver. Quem executa é um programa separado, escrito por você, que abre esse binário sem nunca ter visto o texto de origem. Ele resolve os endereços dos rótulos e roda as instruções, mostrando o conteúdo dos registradores a cada passo. A separação é o ponto inteiro, e a demonstração a torna visível. Compile numa sessão, feche tudo, execute o binário noutra. Se ele rodar, o formato de objeto que você inventou existe de fato.

Pergunta: que informação precisa sobreviver da primeira à segunda passagem, e qual o menor formato de objeto que ainda permite a um carregador independente resolver os saltos? Medida: tamanho do objeto emitido e número de referências resolvidas tardiamente, contra o formato de um montador estabelecido para máquina de porte comparável. Negativo: uma passagem única dá conta de todos os casos do repertório escolhido, e a segunda existe por hábito.

Uma linguagem cujas palavras quem usa escolhe

A linguagem tem tipos declarados, funções, classes e laços. E não tem vocabulário fixo. As palavras que abrem um laço, encerram um bloco ou somam dois números chegam de um arquivo à parte. Nele, quem adota a linguagem escreve o padrão de cada classe de símbolo e a lista de palavras reservadas. Trocando esse arquivo, o mesmo compilador passa a aceitar programas escritos noutra língua — ou com as duas grafias convivendo, mais onde alguém preferir escrever +.

Esta escolha endurece a colisão entre classes de símbolo, e ela chega com uma pergunta que só se responde com teoria. Se pare é palavra reservada e o padrão dos identificadores aceita qualquer sequência de letras, existe uma cadeia que pertence às duas classes ao mesmo tempo. E quando o vocabulário é escrito de fora, ninguém garante de antemão que isso não vai acontecer.

Descobrir se duas classes se sobrepõem é construir a máquina que reconhece o que ambas aceitam e perguntar se ela reconhece alguma coisa. Note que isso não se responde com exemplos. A armadilha é montar uma bateria deles: passa em todos, e some no primeiro nome de variável que ninguém pensou em testar.

O que fica pronto. Um arquivo de vocabulário em que se lê identificador = [a-zA-ZçÇ_][a-zA-Z0-9çÇ_]* e, abaixo, reservadas = { enquanto, pare, mais }. Uma forma possível, e a notação é sua. O compilador lê esse arquivo antes de qualquer programa e constrói um autômato por classe. Havendo cadeia comum a duas classes, ele recusa o vocabulário e diz qual é a cadeia.

Passando a verificação, grava as tabelas e compila programas escritos com aquelas palavras, emitindo o objeto que a máquina executa. A demonstração são dois vocabulários e um só programa. O primeiro vocabulário cai, com a cadeia culpada na tela. O segundo passa, e o mesmo programa compila e roda depois de trocar as palavras que o escrevem.

Pergunta: manter as palavras reservadas dentro do autômato exige quantos estados a mais do que reconhecer o identificador e consultar uma tabela depois, e isso muda quando o vocabulário cresce de dez para cem palavras? Medida: estados e transições nas duas estratégias, mais as colisões que a máquina de interseção encontra e que uma bateria de cadeias de teste não encontra, contra o tratamento que uma implementação estabelecida de analisador léxico dá às palavras reservadas. Negativo: as cadeias que colidem são todas impronunciáveis na prática, e a verificação prévia previne um defeito que ninguém cometeria.

Um filtro declarativo sobre séries temporais

Leituras chegam ordenadas no tempo, e a linguagem descreve padrões nessa ordem. Três valores acima de um limiar em sequência. Uma queda seguida de recuperação dentro de certa janela. Um silêncio longo demais.

O que se endurece é o casamento mais longo. Dois padrões que reconhecem prefixos comuns disputam a mesma posição da entrada, e o desempate precisa ser decidido, escrito e defendido. A armadilha é deixá-lo emergir da ordem em que os padrões foram declarados: o comportamento resultante nunca foi especificado por ninguém, e muda quando alguém reordena o arquivo.

O que fica pronto. Padrões escritos sobre a ordem do tempo, e não sobre caracteres: alarme = valor > 80 por tres leituras seguidas, ou retomada = queda seguida de subida em ate 20 amostras. Deles sai o arquivo de autômatos que reconhecem essas sequências. O executor recebe esse arquivo e uma série de leituras reais (temperatura, cotação, o que estiver à mão). Ele imprime o instante em que cada padrão casou e qual deles venceu quando dois casaram na mesma posição. O que fecha a construção é mostrar dois padrões concorrendo na mesma leitura e explicar, apontando a regra escrita na especificação, por que o vencedor foi aquele.

Pergunta: entre casamento mais longo e prioridade por ordem de declaração, qual produz menos surpresa em conjuntos de padrões escritos por quem desconhece a regra? Medida: divergências entre a intenção declarada e o reconhecimento efetivo, contra a semântica documentada de uma ferramenta de varredura consagrada. Negativo: as duas regras coincidem em quase toda entrada realista, e tanto faz qual delas você adote.

Uma linguagem para descrever máquinas de estado

A entrada declara estados, eventos e transições. A saída é um objeto que, alimentado com uma sequência de eventos, diz em que estado se termina. Autômatos como assunto e como produto ao mesmo tempo.

A verificação estática é o que esta escolha endurece, e de um jeito raro. Estado inalcançável, evento sem transição declarada e não determinismo acidental são propriedades que a análise semântica aponta antes de qualquer execução. A armadilha é a tentação de aceitar tudo e falhar durante a execução, trocando uma verificação barata por um defeito caro.

O que fica pronto. Uma declaração de máquina, do feitio estado ocioso; ao evento moeda vai para armado; estado armado; ao evento gira vai para ocioso. Antes de gravar coisa alguma, o compilador avisa duas coisas. Que certo estado não é alcançável a partir do inicial, e que certo evento não tem transição declarada em certo estado. Passando na verificação, ele grava a tabela de transições. O simulador carrega a tabela, recebe uma sequência de eventos e diz em que estado se termina, listando o caminho percorrido. Pronto é quando os avisos aparecem para uma máquina escrita com defeito de propósito, e a mesma máquina corrigida roda a sequência inteira sem reclamar.

Pergunta: que fração dos defeitos que aparecem executando máquinas escritas à mão poderia ter sido apontada estaticamente, e qual deles exige análise que não cabe numa passada? Medida: defeitos detectados antes da execução sobre um conjunto de máquinas escritas para o teste, contra o que uma ferramenta de verificação de modelos aponta nas mesmas. Negativo: a maioria dos defeitos só se manifesta com uma sequência concreta de eventos, e a verificação estática alcança pouco.

Um interpretador de expressões de busca com escopo

Termos, operadores booleanos, agrupamentos. E a possibilidade de nomear uma subexpressão para reusá-la adiante, inclusive dentro de outra definição nomeada.

Nomear reusável é o que endurece a cena, porque introduz escopo, sombreamento e a regra de declaração antes do uso. Onde vale um nome definido dentro de um agrupamento? A resposta é sua, precisa ser a mesma em toda parte do sistema, e a tabela de símbolos é onde ela vive. A armadilha é o nome que se refere a si mesmo, que parece elegante e produz uma expansão sem fim.

O que fica pronto. Expressões de busca com nomes reusáveis: def recente = data > 2024-01-01 e, adiante, recente e (titulo:"compilador" ou autor:"aho"). O compilador resolve cada nome na tabela de símbolos. Recusa a definição que se refere a si mesma antes de qualquer execução. Grava a expressão já expandida em forma de instruções.

O buscador lê essas instruções e as aplica sobre uma coleção de documentos, devolvendo os que satisfazem. A cena que fecha o trabalho é a do nome redefinido dentro de um agrupamento. Mostre a consulta, mostre qual das duas definições valeu e diga onde no seu sistema essa escolha está escrita.

Pergunta: entre escopo léxico e escopo dinâmico para as definições nomeadas, qual produz menos consultas mal resolvidas em expressões escritas sem conhecimento da regra? Medida: resoluções divergentes da intenção declarada, contra a semântica de escopo de uma linguagem de consulta estabelecida. Negativo: definições aninhadas são tão raras na prática que os dois escopos nunca chegam a divergir.

Uma linguagem de transformação de documentos estruturados

A entrada é um documento com elementos aninhados. A linguagem descreve o que casar e o que produzir no lugar. Um sistema de reescrita com um front-end de verdade.

O que se endurece é a tipagem, num sentido concreto. Casar um padrão que espera um elemento contra uma posição que só contém texto é erro. Detectá-lo antes de rodar exige que o sistema saiba o tipo de cada posição. A armadilha é o tipo genérico que aceita tudo: com ele, a fase de verificação perde o objeto, porque sem valores incompatíveis não há incompatibilidade a apontar.

O que fica pronto. Regras de reescrita sobre documentos aninhados, do feitio casar secao com titulo -> produzir capitulo { titulo }. O compilador verifica que cada padrão espera um tipo compatível com o que a posição pode conter. A regra que casa um elemento contra uma posição de texto é recusada. Passando, ele grava o programa de transformação. O segundo programa aplica essa transformação a um documento de verdade e escreve o resultado. A demonstração são três arquivos na mesa: o documento de partida, as regras e o documento produzido. Junte a eles a regra malformada que o sistema recusa antes de tocar em qualquer documento.

Pergunta: um sistema de tipos com três categorias apanha quantos dos erros que só apareceriam executando, e quantos falsos alarmes ele produz em transformações legítimas? Medida: erros apontados antes da execução e alarmes falsos, contra o que um processador de transformação consagrado aceita e rejeita. Negativo: os falsos alarmes superam os erros apanhados, e a tipagem atrapalha mais do que protege.

Um reconhecedor de designações e coordenadas celestes

O mesmo objeto do céu atende por vários nomes, e cada catálogo escreve o seu de um jeito. Um prefixo e um número aqui. Outro prefixo e outro número ali. Adiante, uma designação longa que carrega as próprias coordenadas embutidas.

As posições sofrem do mesmo mal. Hora, minuto e segundo numa notação. Grau decimal noutra. Sinais e símbolos variando de fonte para fonte. A linguagem descreve quais dessas formas aceitar, e o que sai reconhece qualquer uma delas sobre um catálogo real.

Muitos padrões parecidos sobre o mesmo alfabeto endurecem a minimização. Formas que compartilham prefixos longos geram um autômato inchado de estados equivalentes. É o que acontece quando dez notações de coordenada começam por um número seguido de separador. Reduzir esse autômato deixa de ser exercício e vira necessidade observável. A armadilha é medir a redução em número de estados e concluir que ela valeu, sem verificar se o tempo de reconhecimento mudou.

O que fica pronto. Uma especificação em que se lê designacao = "NGC" espaco+ digito{1,4} ao lado de designacao = "M" digito{1,3}, mais algumas linhas para as notações de posição. O compilador funde tudo num único autômato, minimiza, e grava a tabela junto com a contagem de estados antes e depois.

O reconhecedor carrega essa tabela e lê um arquivo de texto de um catálogo público. Devolve cada designação e cada coordenada encontrada numa forma só, com a posição em que estava no arquivo. Está pronto quando o mesmo arquivo passa pelas duas versões do autômato e produz exatamente as mesmas designações. O relógio e o tamanho da tabela mostram o que mudou entre elas.

Pergunta: a redução de estados obtida pela minimização se traduz em ganho de tempo proporcional, ou o que se ganha vem sobretudo do que passa a caber em memória próxima? Medida: estados eliminados, memória do autômato e tempo por símbolo, contra o mesmo conjunto de formas reconhecido por uma biblioteca de expressões regulares consagrada. Negativo: a minimização reduz estados sem efeito mensurável no tempo, e minimizar não devolve o esforço investido.

Uma linguagem de combos para um jogo de luta

Quem usa escreve sequências de comando. Uma meia-lua seguida de um botão. Uma carga para trás e depois para a frente. Uma cadeia que só vale se cada entrada chegar dentro de certa janela desde a anterior. O que sai reconhece essas sequências enquanto os comandos chegam, um por vez, e dispara o golpe correspondente.

Esta escolha endurece o reconhecimento em fluxo, com decisão irrevogável. O filtro sobre séries temporais também percorre eventos na ordem em que o tempo os põe. Mas ali o arquivo está inteiro em disco, e dá para reler o começo depois de conhecer o fim. Aqui não existe reler.

Quando o botão de soco chega, ou o golpe fraco sai agora, ou se aposta que os próximos comandos completam o especial. E as duas sequências compartilham o mesmo prefixo. Decidir sem ver o futuro é o problema da análise preditiva, e ele aparece aqui num domínio em que o erro se sente antes de se medir. A armadilha é segurar a entrada esperando o fim da sequência para só então decidir. Funciona nos testes. E transforma o jogo em algo intragável, escondendo o problema de antecipação em vez de resolvê-lo.

O que fica pronto. Um arquivo de definições em que se lê meia_lua = baixo, baixo_frente, frente e, adiante, hadouken = meia_lua + soco em ate 12 quadros. São nomes que se compõem, e é dessa composição que vem o aninhamento. O compilador funde as definições num autômato e grava a tabela junto com a tabela de golpes e as janelas de tempo. O executor carrega o objeto e consome uma gravação de comandos com o instante de cada um, capturada de alguém jogando e não escrita para o teste. Imprime, na ordem, que golpe disparou e em qual comando a decisão foi tomada. A cena que fecha o trabalho é a do prefixo disputado. Mostre a gravação em que o soco solitário e o especial começam igual. Depois explique, apontando a regra escrita na especificação, por que o sistema escolheu o que escolheu.

Pergunta: qual o menor número de comandos de antecipação que resolve todos os conflitos do repertório escrito, e que par de golpes obriga o maior? Medida: comandos de antecipação necessários e atraso entre o último comando e a decisão, contra o que um analisador preditivo com um símbolo de antecipação resolve para a mesma gramática. Negativo: um único comando de antecipação basta para todo repertório que alguém escreve na prática, e a máquina elaborada não devolve o que custou.

Uma linguagem em que o padrão é um valor

Uma linguagem de propósito modesto — nomes, números, texto, condicionais, funções — com uma decisão que muda tudo. O padrão de reconhecimento é um valor de primeira classe. Guarda-se um padrão numa variável. Passa-se um padrão a uma função. Monta-se um padrão juntando pedaços durante a execução, e pergunta-se a ele se certo texto casa.

Esta escolha endurece o lugar onde o construtor de autômatos vive. Um padrão escrito literalmente no programa vira máquina durante a compilação, e ali a construção é fase do compilador, como em qualquer outra proposta. Um padrão montado enquanto o programa roda não tem esse luxo. A conversão de expressão em autômato, a determinização e a redução de estados precisam existir dentro do ambiente de execução, disponíveis a qualquer instante.

Veja bem o que isso significa: é a mesma teoria comparecendo em duas alturas do mesmo sistema. A armadilha é construir duas implementações dela, uma para cada altura, que divergem na primeira correção feita só de um lado.

O que fica pronto. Um programa em que se lê seja p = /[a-z]+[0-9]*/ numa linha e, adiante, seja q = p + "@" + dominio, montando outro padrão com um pedaço lido de um arquivo. O compilador reconhece que o primeiro é literal e grava o autômato dele já pronto no objeto. Do segundo, grava as instruções que mandam construir o autômato na hora.

O executor carrega o objeto, roda o programa sobre um texto de verdade e responde às duas perguntas de casamento. Se você pedir, ele informa quantos autômatos precisou construir durante a execução. Está pronto quando um mesmo programa demonstra os dois caminhos e o resultado do casamento é idêntico, venha o autômato de onde vier.

Pergunta: que fração dos padrões de programas escritos por gente é conhecida já na compilação, e o cache de autômatos construídos durante a execução chega a ser usado mais de uma vez? Medida: autômatos construídos em compilação e em execução, reaproveitamentos do cache e tempo gasto construindo contra tempo gasto casando, contra o comportamento de uma linguagem estabelecida que também trata padrões como valores. Negativo: quase todo padrão é literal, a construção em execução é caso raro, e o maquinário que ela exige do ambiente fica ocioso.

Uma linguagem que só compila se cobrir todos os casos

Uma linguagem de propósito geral, com tipo declarado antes de cada nome, blocos entre chaves, funções e listas. Ela é traduzida para instruções de uma máquina de pilha que as executa depois. O que a distingue está em como o programa pergunta pela forma de um valor. Em vez de uma escada de condicionais, quem escreve enumera os casos possíveis e o que fazer em cada um. E o compilador recusa o programa em que sobrou um caso sem tratamento.

Esta escolha endurece a cobertura, e ela pede um raciocínio que nenhuma outra proposta exige. A verificação estática das máquinas de estado percorre um grafo perguntando aonde se chega. Aqui não há grafo a percorrer. Pergunta-se se o conjunto de casos escritos esgota o conjunto de valores que aquele tipo admite, o que obriga o compilador a raciocinar sobre valores que nunca existiram.

Há ainda a metade gêmea do problema: achar a cláusula que jamais vai casar, porque outra acima já a cobre. A armadilha é deixar passar o programa incompleto e falhar durante a execução, quando o valor não previsto aparece. Troca-se uma recusa barata na compilação por um defeito caro em campo, e a linguagem perde justamente a garantia que ela existia para dar.

O que fica pronto. Um programa em que se lê escolher f { circulo(r) -> area = 3.14 * r * r; retangulo(b, h) -> area = b * h; }. Uma forma possível, e a pontuação é sua. Faltando um caso, o compilador não emite nada e escreve linha 12: o caso 'triangulo' não é tratado. Estando uma cláusula coberta por outra acima dela, avisa que aquela nunca vai casar. Passando, ele grava o arquivo de instruções da máquina de pilha, com os casos já compilados numa árvore de decisão em vez de numa fila de comparações. O executor carrega esse arquivo e roda o programa. A demonstração são dois arquivos lado a lado: o que é recusado com o caso faltante nomeado, e o mesmo arquivo completo compilando e executando.

Pergunta: quantas comparações por valor a árvore de decisão gerada executa, comparada à escada de condicionais que alguém escreveria à mão, e a partir de quantos casos ela ganha? Medida: comparações executadas por valor e instruções emitidas nas duas formas, contra o que um compilador estabelecido com casamento de padrão gera para o mesmo conjunto de casos. Negativo: os conjuntos de casos que se escrevem na prática são pequenos demais para a árvore de decisão vencer a escada ingênua, e construí-la não se justifica.

Uma linguagem de configuração com condicionais

Blocos que valem sob certas condições, aninhados uns nos outros, produzindo ao fim um conjunto de valores. Domínio modesto, problema gramatical clássico.

Ambiguidade é o que se endurece, e ela chega sem convite. Um bloco alternativo pendurado depois de dois condicionais aninhados pertence a qual dos dois? Observe que a gramática ingênua admite as duas leituras. Ficar com uma delas exige mudar a gramática ou impor um desempate declarado. A armadilha é descobrir a ambiguidade tarde, quando arquivos de configuração já foram escritos sob a leitura que o analisador calhou de fazer.

O que fica pronto. Arquivos de configuração com blocos condicionais aninhados: se ambiente = "producao" { porta 443; se replica { timeout 30 } senao { timeout 5 } }. O compilador constrói a árvore, e o interessante é o que ele faz com o senao pendurado. Ou a gramática foi reescrita para não admitir duas leituras, ou existe uma regra de desempate escrita na especificação e implementada.

O resolvedor lê o objeto gravado, recebe os valores do ambiente e imprime o conjunto final de chaves e valores. Está pronto quando a entrada ambígua clássica é submetida e o sistema mostra, além do resultado, qual das duas árvores construiu e por quê.

Pergunta: quantas construções da gramática escolhida admitem mais de uma árvore, e a reescrita que elimina cada ambiguidade preserva a linguagem reconhecida? Medida: construções ambíguas encontradas e entradas que mudam de significado após a reescrita, contra a especificação de um formato de configuração consolidado. Negativo: a ambiguidade é única e local, e desempatá-la por regra sai mais barato que reescrever a gramática.

Um pré-processador de marcação leve

Ênfase, listas, blocos de citação, trechos de código literal. E regiões dentro das quais nada do que está fora vale.

Regiões com regras próprias endurecem o reconhecedor. Dentro de um bloco literal, o que fora seria ênfase é texto comum, e o reconhecimento passa a depender de em que modo se está. Comentários aninhados levam isso adiante, porque contar aberturas excede o que estados finitos guardam. A armadilha é tratar modos como casos especiais soltos, e perder a capacidade de dizer, para qualquer posição, em que modo o reconhecedor está.

O que fica pronto. A entrada é texto de marcação. Asteriscos dão ênfase, exceto dentro de um trecho literal, onde asterisco é asterisco. Quem usa o sistema descreve os modos e o que vale em cada um. O compilador dessa descrição grava um autômato por modo, mais as transições entre eles. O conversor lê esse objeto e um documento real, e escreve a versão marcada. A demonstração mais eloquente é um documento que fala sobre marcação. Dentro do bloco literal aparecem asteriscos, e eles têm de sobreviver intactos à conversão enquanto os de fora viram ênfase.

Pergunta: o conjunto de modos escolhido é fechado, de sorte que toda entrada leve a um modo conhecido, e quantos deles ainda são reconhecíveis por estados sem contador auxiliar? Medida: posições da entrada cujo modo é indeterminado, contra o comportamento de um processador de marcação leve consagrado nas mesmas entradas. Negativo: um único modo adicional cobre todos os casos reais, e a estrutura de modos é sobreprojeto.

Uma linguagem de padrões comparada a si mesma

Duas implementações do mesmo reconhecimento, construídas pelo mesmo projeto. Uma converte o padrão em autômato e o percorre. A outra tenta alternativas e volta atrás quando falha.

A comparação endurece o custo assintótico, e ela é a que mais recompensa quem constrói as duas. Note o que está em jogo. Existem padrões cuja versão com retrocesso leva tempo que cresce sem limite prático, enquanto a versão por estados atravessa a entrada uma vez. A armadilha é a média enganar, porque a implementação com retrocesso costuma ganhar nos casos comuns, e o ponto inteiro está nos casos que não são comuns.

O que fica pronto. Aqui saem dois executores do mesmo compilador. Escreve-se um padrão como (a|aa)*b. O compilador grava um objeto com a tabela do autômato determinizado e outro com a árvore que a busca por retrocesso percorre. Dois programas carregam cada um o seu e respondem à mesma pergunta sobre a mesma entrada.

O que se mostra ao fim é um gráfico. Tamanho da entrada num eixo, tempo no outro, duas curvas. E a entrada exata, pequena e escrita à mão, a partir da qual uma delas dispara e a outra segue reta.

Pergunta: qual a menor entrada em que a diferença entre as duas abordagens deixa de ser de constante e passa a ser de ordem de crescimento, e que forma de padrão a provoca? Medida: tempo em função do tamanho da entrada para famílias de padrões construídas para o teste, contra o comportamento documentado de motores de expressão regular de duas famílias distintas. Negativo: os padrões que provocam a explosão não ocorrem em uso realista, e a abordagem com retrocesso serve melhor na prática.

Um compilador que erra bem

A linguagem pode ser qualquer uma das anteriores. O assunto é o que acontece quando a entrada está errada, que é o estado em que ela passa a maior parte do tempo enquanto alguém a escreve.

Recuperação de erro é o que se endurece. Parar no primeiro defeito é fácil. Seguir depois dele sem inventar uma cascata de defeitos que não existem é o problema real, e ele obriga a decidir onde o analisador volta a confiar na entrada. A armadilha é julgar a qualidade das mensagens por conta própria, sem critério declarado, porque o veredito sempre confirma que as mensagens estão ótimas.

O que fica pronto. O produto visível é o que aparece na tela quando a entrada está errada: linha 7, coluna 12: esperava ')' para fechar o parêntese aberto na linha 5. Depois disso a análise continua e encontra o segundo defeito de verdade, em vez de vinte fantasmas. O compilador segue gravando o objeto quando a entrada é válida. O que muda é que ele passa a ter comportamento definido e testável quando não é. A demonstração é um conjunto de arquivos com um defeito conhecido cada, submetidos em lote. Ao lado vai a tabela do que o sistema relatou contra o que estava lá de fato.

Pergunta: dada uma entrada com um único defeito conhecido, quantos defeitos o analisador relata, e a posição apontada no primeiro coincide com a posição real? Medida: defeitos relatados por defeito real e distância entre posição apontada e posição verdadeira, contra o que um compilador estabelecido relata para defeitos equivalentes. Negativo: a estratégia de recuperação produz mais ruído que a parada no primeiro erro, e parar cedo serve melhor a quem escreve.

Uma linguagem que aceita o mundo como ele é escrito

Identificadores com acento. Texto em alfabetos que não cabem num byte. Símbolos fora do repertório com que os exemplos de livro costumam se contentar.

A codificação da entrada é o que esta escolha endurece, e ela ataca a fundação. Se um caractere ocupa mais de um byte, o que é uma transição do autômato: um byte ou um caractere? As duas respostas funcionam, produzem máquinas diferentes e cobram diferente. A armadilha é decidir isso por omissão, no primeiro laço de leitura, e descobrir a decisão meses depois pela boca de um defeito.

O que fica pronto. Padrões que precisam casar coração, Straße e nomes em alfabetos que não cabem num byte. A decisão que organiza tudo aparece no arquivo gravado: a tabela de transição indexa por byte ou por caractere, e as duas versões existem para serem comparadas.

O reconhecedor lê a tabela e um texto multilíngue de verdade. Imprime o que casou, com a posição contada em caracteres e não em bytes, porque é isso que quem escreveu o padrão espera ver. O trabalho fecha com as duas tabelas medidas lado a lado e um texto que mostra as duas dando a mesma resposta por caminhos que custam diferente.

Pergunta: entre transições por unidade de codificação e transições por caractere, qual produz autômato menor para o mesmo conjunto de padrões, e isso depende do alfabeto do texto? Medida: estados e transições nas duas representações sobre os mesmos padrões, contra o dimensionamento de uma biblioteca de reconhecimento com suporte a texto internacional. Negativo: as duas representações se equivalem para os padrões realistas do domínio escolhido, e dá para decidir por conveniência.

Uma linguagem de busca de motivos musicais

A entrada é uma partitura já em forma digital, e a linguagem descreve trechos a procurar nela. Uma terça ascendente seguida de duas notas de mesma duração. Um desenho rítmico com uma nota livre no meio. Um salto grande em qualquer direção. Quem usa escreve o padrão, e o que sai o encontra no acervo.

Esta escolha endurece a natureza do símbolo, e ataca uma coisa que todas as outras propostas dão de graça. Nas demais, um símbolo é um caractere, e dois símbolos são iguais quando são o mesmo. Aqui um símbolo é um par: altura e duração. O mesmo motivo tocado quatro notas acima continua sendo o mesmo motivo. A igualdade consultada pelo autômato deixa de ser identidade e passa a ser equivalência, com aritmética por trás.

Perceba a armadilha, que é elegante e cara. Converter tudo para intervalos logo na leitura faz a transposição sair de graça. Junto sai também a capacidade de escrever o padrão que fixa uma altura absoluta, e alguém vai querer escrevê-lo.

O que fica pronto. Um padrão escrito como [+4 semínima] [qualquer colcheia]{2} [-2 *], numa notação sua, em que o número é o intervalo e o asterisco é a duração livre. O compilador o converte no autômato que percorre a sequência de notas e grava a tabela, dizendo no arquivo se a comparação é por altura absoluta ou por intervalo. O buscador carrega a tabela e um acervo de partituras digitais de domínio público. Devolve em que peça, em que compasso e em que transposição cada ocorrência apareceu. Está pronto quando um motivo conhecido de uma peça aparece também na variação transposta que a própria peça traz adiante. O sistema informa de quantos semitons foi o deslocamento.

Pergunta: entre um autômato sobre o alfabeto dos intervalos e outro sobre o alfabeto das alturas com equivalência resolvida no casamento, qual reconhece o mesmo conjunto de motivos com menos estados? Medida: estados, transições e tempo por nota consumida nas duas representações, contra a varredura direta que compara o motivo em cada posição da peça, uma vez para cada transposição possível. Negativo: os acervos realistas são pequenos a ponto de a varredura direta bastar, e construir o autômato não devolve o esforço.

Assuntos que Parecem Bons e Falham

Alguns recortes atraem por parecerem ambiciosos e falham por razão estrutural, não por dificuldade. Reconhecê-los antes leva uma tarde. Descobri-los depois de investir semanas leva as semanas.

A linguagem que executa na hora. Ler o texto, montar a árvore, verificar tipos e então percorrer a árvore produzindo o efeito de cada nó.

Cobre bem três das seis frentes e nunca produz código. Sem artefato gravado, não há o que gerar nem onde executar, e as duas frentes que sustentam metade do percurso ficam sem objeto. É o caminho de menor resistência, e por isso o mais frequentado.

A linguagem de comandos de formato fixo. Cada comando numa linha, campos separados, nada dentro de nada. Um reconhecedor de padrões um pouco mais elaborado dá conta da linguagem inteira, e a etapa de estruturação fica sem o que estruturar.

A linguagem sem tipos distintos. Tudo é valor genérico, e usar antes de declarar nunca é detectado. Não sobra propriedade estática a violar, e a verificação vira uma caminhada sem finalidade sobre a árvore.

Os dois últimos são de outra família. Não erram na linguagem escolhida: erram no que o projeto deixa de construir sobre ela.

O reconhecedor tomado pronto (o caso em que a frente parece cumprida). Um gerador produz o reconhecedor, e o autômato subjacente nunca é construído nem examinado. A frente aparece cumprida enquanto o mecanismo que a justifica — estados, transições, determinização — permanece fechado.

As peças demonstradas em separado. Cada etapa funciona com entrada preparada à mão para a demonstração dela, e nenhuma consome a saída real da anterior. O que existe são exercícios que imitam as partes de um compilador.

Um recorte que dependa de dados de pessoas, de acesso a outra instituição ou de qualquer coisa que não seja artefato e execução fica de fora. A medida aqui é sobre entradas, tempos, tamanhos e saídas comparadas. Essa fronteira não se abre por ambição do assunto.

O Teste que Fecha a Escolha

Cinco perguntas decidem, e responder a elas leva uma tarde. Descobrir a resposta construindo leva bem mais.

Existe, em algum ponto, um artefato de código que é saída do tradutor e entrada de outra coisa — ou o texto de partida é executado direto?
A linguagem tem alguma construção que se aninha sem limite fixo, ou todo comando é de formato fixo e reconhecível linha a linha?
Você consegue mostrar o autômato do reconhecimento — estados e transições — e explicar o que cada estado significa?
Existe entrada em que usar um nome antes de declará-lo, ou combinar valores incompatíveis, é apontado antes de qualquer execução?
A pergunta investigativa tem uma referência contra a qual medir, e você consegue enunciar hoje o resultado que a contrariaria?

Quatro respostas boas e uma ruim não reprovam o recorte. Elas indicam onde ele precisa mudar antes de a primeira linha ser escrita. A quinta é a que mais se costuma pular, e a única cuja falta só aparece no fim, quando os números já foram colhidos e não há contra o que compará-los.

Como o Projeto Integrador Funciona na Disciplina

As seções anteriores descrevem o que se constrói e o que caracteriza um bom resultado. Esta descreve outra coisa: como esse trabalho acontece na disciplina — em que grupos, com que acompanhamento, o que se entrega em cada etapa e como o resultado é avaliado. Tudo o que segue é combinado antes que o trabalho comece, e não na devolução da nota.

O Projeto Integrador é desenvolvido em grupos de três a cinco integrantes, o que rende entre oito e treze grupos numa turma do tamanho habitual. A faixa existe para acomodar a composição real da turma, mas as duas pontas dela não são equivalentes e convém saber disso ao formar o grupo. Um trio distribui o trabalho de forma que ninguém consegue ficar de fora, e paga por isso com um arco final pesado, em que a integração ponta a ponta recai sobre poucas mãos. Um grupo de cinco absorve bem esse arco final e cria, em compensação, o espaço onde alguém atravessa o período sem tocar no código — risco que só aparece tarde, porque o artefato é cumulativo e a ausência de um integrante demora a se tornar visível no resultado.

Grupos de quatro ou cinco integrantes, por isso, precisam explicitar desde o início como o trabalho se reparte, e a repartição não pode ser por fases inteiras do sistema: quem for dono exclusivo de uma fase chegará à arguição sem conseguir responder pelas vizinhas. A divisão que funciona é por peça dentro de cada etapa, com rodízio entre os módulos, de modo que todos os integrantes tenham escrito código em pelo menos dois dos três arcos do percurso.

A composição dos grupos é definida no início do percurso e mantida até a entrega final. Trocas de composição no meio do trabalho são possíveis apenas por acordo prévio com o professor, e a razão da restrição é direta: como a arguição final cobra de cada integrante o conhecimento de fases que ele não escreveu, um grupo recomposto tardiamente coloca alguém diante de um artefato cuja história ele não acompanhou.

Dentro do grupo, a dinâmica de trabalho adotada nas sessões de tutoria é a programação em pares, com revezamento explícito de papéis: a cada trecho, um integrante digita e outro revisa, antecipa erros e pensa no passo seguinte, e os papéis giram em intervalos curtos. Grupos de quatro ou cinco se dividem em duplas simultâneas trabalhando em peças distintas, e o integrante que sobra num grupo ímpar entra no rodízio da dupla seguinte em vez de assumir uma frente própria — trabalho individual dentro do grupo é justamente o que esta dinâmica existe para evitar. O revezamento é o que impede que a implementação se concentre em um único estudante, que é o modo mais comum de um grupo produzir um bom artefato e reprovar parte de seus integrantes na arguição.

Ritmo Semanal e Tutoria

flowchart LR
    T["Aulas teóricas<br/>o conceito e a construção<br/>conduzida ao vivo"] --> TU["Aulas de tutoria<br/>o grupo avança<br/>o próprio artefato"]
    TU --> D["Diário de atividades<br/>o que se fez,<br/>quem fez, o que travou"]
    D --> E["Entrega parcial<br/>ao fim do módulo"]
    E --> T

A semana da disciplina comporta seis aulas, quatro delas teóricas e duas 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 são o espaço em que cada grupo faz o próprio artefato avançar, com o professor circulando entre os grupos. Nada é pedido fora do horário de aula, e nenhuma atividade proposta é alheia ao Projeto Integrador.

A intervenção do professor na tutoria é decrescente ao longo do período, e isso é desenho, não variação de disponibilidade. Nos primeiros módulos, o grupo recebe estrutura sugerida, casos de teste prontos e revisão detalhada de decisões de representação. No arco intermediário, o grupo passa a projetar sozinho a gramática e a defender as transformações aplicadas a ela, com o professor atuando por perguntas em vez de por indicação. No arco final, a orientação se concentra em integração e em consequências de decisões tomadas módulos antes — que é exatamente o que a arguição individual vai cobrar.

Cada grupo mantém um diário de atividades, atualizado nas sessões de tutoria. Ele registra o que foi feito, quem fez, que decisão técnica foi tomada com qual alternativa descartada, e o que ficou travado. O diário é a evidência primária de contribuição individual, e é a fonte de que o professor parte para formular as perguntas da arguição. Grupo sem diário atualizado chega à etapa final sem nada que sustente a distribuição do trabalho que ele afirma ter havido.

Entregas Parciais e Entrega Final

flowchart TB
    B1["Bloco dos autômatos<br/>andaime alto:<br/>estrutura sugerida e casos de teste dados"] --> B2["Bloco da gramática<br/>andaime médio:<br/>gramática projetada pelo grupo"]
    B2 --> B3["Bloco da tradução<br/>andaime baixo:<br/>o grupo decide sozinho"]
    B3 --> FIM["Entrega final<br/>sistema completo,<br/>documentação e apresentação"]
    FIM --> ARG["Arguição individual<br/>um estudante por vez"]

Ao final de cada módulo, o grupo entrega o estado corrente do repositório de trabalho — código, documentação e diário — correspondente à etapa descrita na seção do módulo, com os critérios de conclusão ali enunciados. A entrega parcial é a verificação de que a peça daquele módulo existe, funciona e não quebrou o que já funcionava. Um grupo que acumula três módulos de atraso não tem três tarefas pendentes; tem um sistema cujas peças nunca foram integradas.

A entrega final ocorre na semana seguinte à conclusão do último módulo de conteúdo e reúne o sistema completo, a documentação e a apresentação do resultado. A pontualidade das entregas compõe nota própria, e a razão é a mesma que sustenta as entregas parciais: num artefato cumulativo, atraso é acúmulo de risco que se paga na integração final.

Nenhuma data absoluta é fixada aqui. A sequência é relativa ao percurso — entrega parcial ao término de cada módulo, entrega final na semana seguinte ao último módulo de conteúdo —, e as datas correspondentes seguem o calendário acadêmico vigente, comunicado à turma no início do período.

Critérios de Avaliação: a Rubrica

O Projeto Integrador é avaliado pela rubrica abaixo, publicada aqui, com a proposta do trabalho, e não na devolução da nota. Os pesos dos componentes da nota são fixos: as entregas parciais em grupo respondem por quinze por cento e a verificação individual de teoria por cinco por cento dentro da Avaliação Contínua, que se completa com o engajamento no estudo pelo aplicativo, vinte por cento, e a pontualidade nas entregas, dez por cento; na Avaliação Final, o produto completo em grupo responde por vinte por cento e a arguição individual por trinta por cento.

Dimensão	Insuficiente	Em desenvolvimento	Adequado	Exemplar
Domínio conceitual	O código contradiz a teoria correspondente; o grupo não relaciona a peça implementada ao conceito que ela realiza.	A relação entre teoria e implementação é enunciada, mas de forma genérica e sem consequência sobre as escolhas feitas.	Cada peça é apresentada como realização de um resultado teórico específico, com a correspondência explicitada.	O grupo identifica onde a teoria impôs um limite ou um custo à implementação e mostra como lidou com ele.
Resolução do problema	O sistema não processa a entrada de exemplo ponta a ponta.	O caminho feliz funciona; entradas inválidas ou de fronteira produzem falha sem tratamento.	O sistema processa entrada não preparada e recusa entrada inválida com mensagem específica.	O sistema trata casos de fronteira reconhecidos como difíceis e demonstra a própria limitação de forma deliberada.
Qualidade técnica	Peças acopladas a ponto de uma alteração local exigir reescrita ampla; sem verificação automatizada.	Separação parcial de responsabilidades; testes existem mas cobrem apenas o caminho feliz.	Fronteiras claras entre reconhecimento, estruturação e tradução; bateria de testes que detecta regressão.	Uma extensão pequena da linguagem é absorvida com alteração localizada, e isso é demonstrado.
Comunicação e documentação	Sem documentação utilizável; o sistema não pode ser compilado por terceiro a partir do que está escrito.	Documentação presente mas desatualizada em relação ao código.	Documentação que permite a terceiro compilar, executar e entender a linguagem aceita.	Decisões técnicas registradas com as alternativas descartadas e a razão da escolha.
Contribuição individual	Não sabe explicar a própria parte; ausente do diário de atividades.	Descreve o que a própria parte faz, sem justificar as escolhas nela.	Explica as próprias escolhas relacionando-as ao conceito teórico correspondente.	Explica as próprias escolhas e antecipa as consequências delas sobre as fases vizinhas do artefato.

Os pesos internos da rubrica são definidos pelo professor e comunicados junto com ela. A dimensão de contribuição individual é obrigatória em trabalho de grupo e é o instrumento cotidiano contra a carona: ela é aferida pelo diário de atividades, pela observação nas sessões de tutoria e pela avaliação entre pares dentro do grupo, e é o que dá sentido à arguição descrita adiante. Nenhum critério estético compõe a rubrica — apresentação visual, escolha de nomes e organização de diretórios importam apenas na medida em que afetam a compreensão de terceiros, que é o que a dimensão de comunicação afere.

A Arguição Individual

flowchart TB
    A["Arguição individual"] --> PA["Parte A<br/>a própria contribuição"]
    A --> PB["Parte B<br/>uma fase vizinha do<br/>artefato do próprio grupo"]
    PA --> PA1["Percorrer o código escrito"]
    PA --> PA2["Justificar uma decisão:<br/>por que não é de outro jeito"]
    PB --> PB1["Pergunta de consequência:<br/>o que quebra se isto mudar"]
    PB --> PB2["Quem participou responde;<br/>quem foi carregado, não"]

A arguição é individual, oral, um estudante por vez, e recai sobre o sistema que o grupo dele construiu. É o componente de maior peso isolado da nota, e convém saber disso desde o início — não como ameaça, mas porque ela muda o modo racional de trabalhar durante o período: quem se divide de forma a nunca entender as fases vizinhas está otimizando a entrega em grupo e comprometendo trinta por cento da própria nota.

Ela tem duas partes. Na primeira, o estudante percorre o código que escreveu e justifica uma decisão técnica dele — por que a tabela de transição é indexada daquela forma, por que a redução de estados vem antes daquele passo, por que a regra da gramática foi fatorada daquele jeito. O critério é explicar por que o código não é de outro jeito, nomeando a alternativa descartada. Na segunda parte, o professor toma uma fase vizinha do artefato do próprio grupo e faz uma pergunta de consequência: o que quebra se a ordem de desempate entre padrões concorrentes for trocada, o que a verificação semântica deixa de detectar se a tabela de símbolos perder o escopo, quantas instruções a mais o gerador emite sem determinada transformação.

Uma boa defesa é a que distingue com clareza o que o estudante sabe do que não sabe, sustenta com argumento técnico o que afirma e reconhece o limite do próprio conhecimento sem improvisar. Quem participou da construção responde às perguntas da segunda parte mesmo sem ter digitado aquele arquivo, porque acompanhou as decisões; quem foi carregado pelo grupo não tem como reconstruir isso na hora.

Uso de Inteligência Artificial e Integridade Acadêmica

A regra é combinada aqui, por escrito, antes do trabalho começar. Regra que aparece apenas na correção é armadilha, e não é assim que esta disciplina opera.

Onde a inteligência artificial é apoio legítimo: exploração de alternativas de projeto antes de decidir, revisão de código já escrito, esclarecimento de conceito, diagnóstico de erro de compilação, geração de casos de teste adicionais e revisão de texto da documentação. Em todos esses usos o estudante permanece autor da decisão, e é a decisão que a avaliação afere.

Onde a autoria é obrigatoriamente própria: a arguição individual e a verificação individual de teoria, ambas realizadas em aula, sem consulta e sem uso de qualquer assistente. São os dois momentos em que a disciplina verifica domínio pessoal, e neles a mediação de uma ferramenta destruiria justamente o dado que se pretende obter.

O que se espera no meio-termo, que é onde o projeto vive: o grupo pode usar assistentes na construção, desde que registre no diário de atividades onde o uso foi determinante e desde que cada integrante consiga explicar e defender o código que consta como dele. Código que o autor declarado não sabe explicar é tratado como não sendo dele, independentemente de sua origem.

Constitui plágio apresentar como próprio trabalho de terceiro — de outro grupo, de repositório público ou gerado por assistente — sem indicação de origem. Trechos de terceiros legitimamente reaproveitados são identificados na documentação, com a fonte e o que foi alterado. A consequência de um caso confirmado recai sobre quem o praticou e é tratada individualmente, não sobre o grupo inteiro: a arguição existe, entre outras razões, para tornar essa separação possível.

Checklist de Cobertura da Ementa

O recorte que cada grupo escolhe é livre no assunto e amarrado na estrutura. A tabela abaixo é o instrumento de conferência: ela liga cada tópico da ementa ao que precisa existir no projeto para que aquele tópico tenha objeto, e é consultada duas vezes — na aprovação do recorte, antes de o grupo escrever a primeira linha, e na arguição individual, quando a pergunta se dirige exatamente ao que a linha correspondente exige.

Tópico da ementa	O que precisa existir no projeto	Invariante
Análise Léxica	Reconhecedor de tokens fundamentado em autômato — estados e transições — construído ou examinado pelo grupo; classes de token para identificadores, números, palavras-chave e operadores	I1
Análise Sintática	Gramática livre de contexto com ao menos uma construção de aninhamento arbitrário; analisador (descendente recursivo, LL ou LR) que produz árvore sintática	I2
Análise Semântica	Sistema de tipos, regra de declaração antes do uso e escopo, verificados por tabela de símbolos numa passada distinta da execução	I3
Ambientes de Execução	Componente de execução distinto do compilador — máquina virtual, interpretador de bytecode ou processador real —, com noção própria de memória, pilha e fluxo, consumindo o artefato gerado	I4
Geração de Código	Tradução da árvore, tipicamente via representação intermediária, para formato de código-alvo gravado como artefato, e não como efeito observável imediato	I4
Projeto e Implementação de um Compilador	Pipeline único e integrado, fonte até executável, em que a saída de cada fase é a entrada real da próxima	I5

A linha que mais reprova recorte é a de Ambientes de Execução. Um projeto que interpreta a árvore e produz o efeito na hora satisfaz as três primeiras linhas com folga e deixa as duas seguintes sem objeto — e a descoberta costuma acontecer tarde demais para reconstruir duas fases sobre um sistema que nunca separou compilar de executar. A pergunta que fecha esse diagnóstico em segundos é “mostre o código gerado antes da execução”, e ela é feita na aprovação do recorte justamente para não precisar ser feita na arguição.

Na arguição individual, cada integrante responde por ao menos um invariante do projeto do grupo, e a escolha de qual não é anunciada antes. A rubrica de contribuição individual se apoia nisso: explicar como o recorte satisfaz I1 exige ter estado presente quando o autômato foi construído, e nenhuma leitura de véspera substitui essa presença.

Reuso

CC BY-NC-ND 4.0