flowchart LR
T["um mesmo arquivo<br/>de texto"] --> H["para quem escreveu:<br/>instruções a executar"]
T --> C["para o tradutor:<br/>dado a analisar"]
C --> V["não confia<br/>em nada"]
V --> D["desmonta<br/>em pedaços"]
D --> P["produz um artefato<br/>que executa"]
H -.->|"a pessoa completa,<br/>corrige e adivinha"| X["imprecisão<br/>tolerada"]
C -.->|"a máquina<br/>não adivinha"| Y["critério que responde<br/>sim ou não sempre"]
1 Linguagens formais e a arquitetura de um compilador
O vocabulário com que se descreve um conjunto infinito de textos, e o mapa do sistema que decide sobre cada um deles.
Em 1952, num encontro da ACM, Grace Hopper apresentou um trabalho de título modesto: The Education of a Computer. O programa descrito ali chamava-se A-0 e rodava num UNIVAC I. Ele lia uma lista de chamadas escrita à mão. Procurava cada rotina numa fita magnética. Montava o programa final juntando os pedaços na ordem pedida. Hopper batizou aquilo de compilador, no sentido de quem compila uma antologia: reúne o que já existe e publica num volume só.
O nome pegou. A descrição do ofício, não. O A-0 colava trechos prontos e não analisava coisa alguma, e nenhum compilador de hoje trabalha sem antes desmontar o texto que recebeu. O que sobreviveu daquele encontro foi a ideia por baixo do nome: o texto que uma pessoa escreve pode ser tratado como dado por outro programa. A frase parece inofensiva. Deixa de parecer no instante em que alguém pergunta o que ela exige.
Ela exige uma decisão sobre cada sequência de caracteres que possa ser digitada. Essa sequência pertence ao conjunto das admitidas? O conjunto quase sempre é infinito, e nenhuma estrutura de dados guarda um conjunto infinito. Mesmo assim o programa responde depressa, milhares de vezes por segundo, sem jamais ter visto a lista inteira. Como?
O vocabulário que responde tem três degraus e cabe em meia página. Símbolo, cadeia, linguagem. Sobre eles se apoiam a gramática, a hierarquia que casa classes de linguagem com classes de máquina, e a anatomia do sistema que traduz.
O que passa a estar ao seu alcance. Escrever a definição formal de um alfabeto e de uma linguagem. Operar união, concatenação, potência e fecho sem cair nas duas armadilhas que derrubam quase todo mundo. Ler uma gramática e derivar dela uma cadeia. Situar uma linguagem no degrau certo da hierarquia, perguntando de que memória a máquina precisaria. Percorrer as fases de um tradutor dizendo o que cada uma consome e o que entrega. E escrever a primeira especificação da linguagem que você mesmo vai tratar.
1.1 O mesmo arquivo, e dois leitores que não combinam
Enquanto traduz, o compilador não roda uma linha do seu programa.
Abra um fonte qualquer e leia x = = 3. Você entende o engano em meio segundo, corrige de cabeça e segue adiante. Provavelmente nem registra que houve engano. O tradutor não tem essa boa vontade. Ele percorre a mesma linha atrás de uma sequência que case com alguma regra escrita. Não acha nenhuma, e para. Nada mudou no arquivo — mudou o leitor.
Repare no que isso faz com a palavra enquanto no meio do arquivo. Para quem escreveu, ela é uma ordem: repita isto até aquilo. Para o tradutor, são oito letras que casam com uma entrada de tabela. A ordem mora no significado que alguém atribuiu à palavra, e o tradutor não tem acesso a significado nenhum. Ele tem a tabela, e é só isso que ele tem.
E é ótimo que ele não adivinhe. Suponha que adivinhasse. Você escreveu 3 x e esqueceu o asterisco entre os dois. Um tradutor generoso apostaria em 3 * x. Outro apostaria que você quis dizer x3, um nome de variável que por acaso existe no seu programa e guarda o total de itens processados. A segunda aposta compila, roda e devolve um número. Errado, e em silêncio: x3 guarda outra coisa, e tudo o que vem depois se apoia nele.
Adivinhar sai barato na hora do palpite. A conta chega quando dois tradutores adivinham de modos diferentes: o mesmo arquivo passa a significar duas coisas, conforme a ferramenta instalada na máquina. Recusar o palpite é o que torna a tradução reprodutível. E reprodutibilidade é a única propriedade que faz alguém confiar num compilador que não escreveu.
Pare um instante nisto. Quando o compilador recusa 3 x, o que exatamente ele acabou de descobrir? Escreva a resposta antes de ler o parágrafo seguinte — a diferença entre as duas respostas possíveis organiza metade do que vem depois.
Ele sabe que aquele texto não pertence à linguagem. Ele não sabe o que você queria escrever. São afirmações de força bem diferente, e a segunda ele nunca faz. A mensagem de erro mais honesta que um compilador consegue dar nomeia a posição e diz o que era esperado ali, sem propor conserto. O compilador é o leitor mais literal que você vai encontrar na vida, e isso é uma virtude.
Existe ainda uma terceira leitura do mesmo arquivo, e ela confunde quem começa. Escreva num arquivo de texto a frase “se o sensor passar de setenta por cento, dispare”. Um colega lê e implementa. O tradutor lê e não faz nada. Descrever comportamento em português não basta, e a diferença nada tem a ver com clareza de intenção: falta o conjunto de textos admitidos contra o qual a frase pudesse ser comparada.
Entre a primeira letra lida e o resultado que roda há uma sequência de perguntas. Cada uma só pode ser feita depois de a anterior ter sido respondida. Onde termina cada unidade com significado próprio dentro daquela fila de caracteres? Como essas unidades se encaixam umas nas outras? O que se encaixou faz sentido segundo as regras da linguagem? A ordem se impõe sozinha, porque perguntar se uma soma é válida exige saber que ali há uma soma.
Por que separar em passos, se um programa suficientemente esperto poderia decidir tudo de uma vez? Imagine um sistema que decidisse o significado de cada caractere no momento em que o lê. Ele encontra o 3 de 3x e precisa escolher entre início de um número e início de um nome que será recusado adiante. Escolhe o número, avança para o x, e a escolha não fecha. Volta então ao 3 e recomeça pela outra interpretação, que era a segunda hipótese em aberto.
Voltar atrás uma vez sai barato. O problema é que cada símbolo do arquivo pode disparar um retrocesso, e retrocessos se aninham: voltar ao 3 pode obrigar a voltar ao caractere anterior.
O tempo de leitura deixa de ser proporcional ao tamanho do arquivo e passa a crescer bem mais depressa, com um fator que ninguém prevê olhando o fonte. Separar em passos elimina o retrocesso, porque cada passo trabalha sobre um objeto já fechado.
A arquitetura em passagens sucessivas não nasceu de gosto por elegância. Em 1957, a equipe de John Backus, na IBM, entregou o compilador de FORTRAN sob uma suspeita então generalizada: a de que código produzido por máquina seria lento demais para ser levado a sério. Programadores da época escreviam em linguagem de montagem e tinham motivo para desconfiar. Quem paga o tempo de máquina não compra conveniência de quem digita. Essa desconfiança organizou o projeto inteiro. A otimização entrou como condição de aceitação, desde o primeiro dia, e a separação do trabalho em passagens sucessivas apareceu como resposta a uma exigência de desempenho. Backus publicou o relato em 1978, no The History of FORTRAN I, II, and III, pela ACM SIGPLAN. Um tradutor só é aceito quando o código que ele escreve aguenta comparação com o que a pessoa escreveria à mão.
Duas heranças daquele projeto atravessam tudo o que vem adiante. A primeira é a forma: um sistema de tradução se organiza em etapas que se comunicam por artefatos, em vez de num bloco único. A segunda é de método, e vale mais. Julgamento de otimização se faz com número, e uma implementação que se anuncia rápida sem apresentar a medida está pedindo crédito. Crédito é exatamente o que aquela equipe não teve.
1.1.1 O que a área supõe que você já saiba
Nada sobre compiladores é pressuposto aqui. Este é o primeiro capítulo, e o que ele pede vem de fora do assunto — três coisas, nomeadas agora para que você possa reforçar a que estiver frouxa antes de seguir.
A primeira é programar numa linguagem com tipos declarados, e compilar e executar o resultado a partir de um comando. Você vai escrever bastante código ao longo destas páginas, e ele é de sistema: nada de biblioteca que resolva o problema por você, porque o problema é a biblioteca. A segunda é estrutura de dados. Conjunto, árvore, pilha e tabela de dispersão aparecem no primeiro terço do percurso e não param mais de aparecer, e você vai precisar decidir entre elas por conta própria. A terceira é recursão. Escrever uma função que chama a si mesma, enxergar quando ela termina e reconhecer a pilha de chamadas por trás dela são hábitos que este livro usa desde o quarto capítulo, sem reapresentá-los.
O sistema que acompanha o percurso chama-se Peneira. É uma linguagem pequena em que se declaram padrões sobre texto e se escrevem regras que reagem ao casamento desses padrões. O compilador dela produz um motor de autômatos, e não código de máquina. Ela existe para ser estudada, e não copiada: o sistema que você constrói é seu, sobre o domínio que escolher, e a Peneira serve de referência de acabamento.
A escolha desse artefato tem uma razão que se colhe ao longo de todo o percurso. Os padrões escritos por quem usa a linguagem são compilados para autômatos finitos. Os símbolos da própria Peneira são reconhecidos por autômatos finitos, construídos pelo mesmo maquinário. A teoria comparece duas vezes, em alturas diferentes do mesmo sistema, e é essa dupla aparição que impede os autômatos de virarem preâmbulo esquecível de uma caixa fechada.
1.2 Três degraus que cabem em meia página
Símbolo é aquilo que se decidiu não decompor.
A definição de símbolo incomoda por parecer circular, e é a única honesta. Nada num objeto o torna indivisível por natureza. O que fixa o degrau é a escolha de quem descreve. Uma letra é símbolo quando o alfabeto é o dos caracteres; uma palavra inteira é símbolo quando o alfabeto é o das unidades já classificadas.
flowchart TB
A["símbolo<br/>aquilo que se decidiu<br/>não decompor"] --> B["cadeia<br/>sequência finita<br/>de símbolos"]
B --> C["linguagem<br/>conjunto de cadeias<br/>admitidas"]
A -.->|"muda de altura"| A2["uma letra, quando o alfabeto<br/>é o dos caracteres"]
A -.->|"muda de altura"| A3["uma palavra inteira, quando o alfabeto<br/>é o dos símbolos classificados"]
C --> D["finito: o alfabeto<br/>e a descrição"]
C --> E["infinito: o conjunto<br/>que ela descreve"]
Essa mudança de altura acontece dentro do mesmo sistema, entre uma fase e a seguinte, e ela responde por metade da confusão deste ponto do percurso. A fase que separa pedaços tem como símbolo o caractere. A fase seguinte recebe a saída dela e passa a ter como símbolo a unidade classificada inteira. Duas fases vizinhas usam a mesma palavra para coisas de tamanhos diferentes, e ninguém avisa a troca.
Um alfabeto é a lista fechada do que pode aparecer. A exigência de ser finita paga uma conta bem concreta: com ela se monta uma tabela de uma linha por símbolo, consultável em tempo previsível. Alfabeto infinito inviabiliza a máquina, e a razão é rasteira. A tabela nunca termina de ser montada. Não há como consultar o que não terminou de existir.
NotaAlfabeto e cadeia, no enunciado formal
Um alfabeto \Sigma é um conjunto finito e não vazio, cujos elementos são chamados símbolos. Uma cadeia sobre \Sigma é uma sequência finita a_1 a_2 \ldots a_n com a_i \in \Sigma para todo i, e n \geq 0. O número n é o comprimento da cadeia, escrito |w|.
Tome o menor exemplo interessante, \Sigma = \{a, b\}. As cadeias aab e b estão sobre esse alfabeto, e a cadeia de comprimento zero também está. A cadeia abc fica de fora, e o motivo é único: c não pertence a \Sigma. Pertencer ao alfabeto é a única condição que a definição impõe a cada posição da cadeia. Note também o que a definição não exige. Ela não pede que a cadeia signifique alguma coisa, nem que seja legível, nem que apareça em algum lugar. Ela tampouco limita o comprimento por cima: cada cadeia é finita, e não existe um teto comum a todas elas. As duas coisas são diferentes, e vão se separar de novo quando o assunto for conjunto infinito.
Complemento: e se o alfabeto fosse vazio?
A exigência de ser não vazio é a que mais parece arbitrária, então desfaça-a e veja no que dá. Sobre um alfabeto sem símbolo algum existe exatamente uma cadeia, a de comprimento zero, que não precisa de símbolo nenhum para existir. Logo o universo de cadeias é o conjunto que contém apenas a cadeia vazia. Há duas linguagens possíveis ali. A vazia, e a que contém essa única cadeia. Um alfabeto sem símbolos não recusa toda entrada, portanto. Ele admite uma, e só uma.
No outro extremo, o Unicode passa de cem mil símbolos e inclui as letras desta página, hieróglifos egípcios e emojis. Continua sendo um alfabeto, porque continua sendo uma lista fechada — grande, mas fechada. Grande e finito são coisas distintas, e é a segunda que a definição cobra. Na prática o alfabeto costuma vir de fora (de uma norma, de um formato de arquivo), e às vezes vem da própria coleção de cadeias que se está descrevendo.
O que essas poucas linhas revelam do conceito é a direção da dependência. A definição apresenta o alfabeto primeiro e a linguagem depois, como se um viesse antes do outro no tempo. No código a seta se inverte sem prejuízo nenhum: as cadeias existem, e o alfabeto sai delas por varredura. As duas leituras convivem porque a definição fixa uma relação, e relação não tem ordem de construção.
Sobre cadeias há poucas operações, e todas produzem cadeias. O comprimento |w| conta as posições, de modo que |aab| = 3 e a cadeia vazia tem comprimento zero. A concatenação escreve a segunda cadeia logo depois da primeira: aa com b produz aab, e a operação não comuta, porque b com aa produz baa. Comprimentos somam-se sempre, e vale |xy| = |x| + |y|.
A cadeia vazia é o elemento neutro dessa operação. Concatená-la de qualquer lado devolve a cadeia original, porque escrever nada antes ou depois de algo não muda esse algo. Daí sai a potência de uma cadeia, que é a concatenação dela consigo mesma um número dado de vezes, com w^0 = \varepsilon pelo mesmo motivo pelo qual o produto vazio de números vale um. Fecham o repertório duas perguntas de comparação: x é prefixo de w quando w começa por x, e é sufixo quando w termina por x.
Agora o objeto que dá mais trabalho, e ele é perfeitamente definido e completamente invisível. Imprima o conjunto de três elementos \{\varepsilon, a, aa\} sem tratamento nenhum e a saída sai assim: { , a, aa }.
Quem lê conta dois elementos e uma vírgula sobrando, conclui que o programa tem um defeito de formatação, e não desconfia de que o defeito está na leitura dele.
O elemento não sumiu. Ele foi impresso, com o número exato de caracteres que tem.
01_linguagem.cpp
Cadeia formatar(const Linguagem& linguagem) {
Cadeia texto = "{ ";
bool primeiro = true;
for (const Cadeia& cadeia : linguagem) {
if (!primeiro) {
texto += ", ";
}
// A cadeia vazia é invisível quando impressa como está, e o leitor
// conclui que o conjunto tem um elemento a menos do que tem.
texto += cadeia.empty() ? Cadeia{"\xce\xb5"} : cadeia;
primeiro = false;
}
texto += " }";
return texto;
}Uma linha de tratamento para um problema de aparência cosmética, e ela não é cosmética. Enquanto não existe bateria de testes, a verificação disponível é comparar duas saídas a olho e contar elementos. Um formatador que apaga um elemento faz a contagem errar sem avisar, e a contagem errada é justamente a que se usa para julgar se a operação anterior está correta. O defeito de exibição contamina o diagnóstico de tudo o que vem antes dele.
O saldo desta seção
O conjunto que não tem elemento algum e o conjunto cujo único elemento é a cadeia vazia são objetos diferentes. Um tem cardinalidade zero; o outro tem cardinalidade um. Trocar um pelo outro é o erro cujas consequências se medem daqui a uma seção, e ele reaparece na construção de autômatos, na determinização e na verificação de significado. Cada retorno sai mais caro que o anterior.
Fixado um alfabeto, o conjunto de todas as cadeias sobre ele tem nome e notação: \Sigma^*. Ele é infinito sempre que \Sigma tem ao menos um símbolo, porque as cadeias não têm teto de comprimento. A notação \Sigma^n recorta desse infinito as cadeias de comprimento exatamente n, e esse recorte é sempre finito. Escreva \Sigma^3 para \Sigma = \{a, b\} sem pular nenhuma: aaa, aab, aba, abb, baa, bab, bba, bbb.
São oito, que é 2^3, e a conta é a de qualquer escolha independente posição a posição. Para comprimento 10 são 1024 cadeias, e para comprimento 20, sobre o mesmo alfabeto de dois símbolos, são 2^{20} = 1.048.576. Esse último número explica por que uma senha curta cai. Um PIN de quatro dígitos tem 10.000 combinações. Vinte escolhas entre dois símbolos rendem cem vezes mais, com um alfabeto cinco vezes menor. O comprimento rende mais que a variedade, e a aritmética disso está inteira em |\Sigma|^n.
1.3 Uma linguagem é um conjunto, e conjuntos se combinam
Uma linguagem não precisa ter regra, padrão nem descrição. Ela pode ser um punhado de cadeias escolhidas a esmo, o resultado de um sorteio, ou um conjunto que ninguém jamais conseguirá escrever. Basta que todos os seus elementos sejam cadeias sobre o mesmo alfabeto. Toda a dificuldade que vem adiante nasce dessa generosidade.
Isso soa como falta de rigor e é o contrário. Quanto menos a definição exige, mais objetos ela alcança, e mais valem os teoremas que a usam. A conta chega depois. Alcançar tudo significa alcançar coisas com que nenhuma máquina lida. Antes da notação, o que o objeto faz: uma linguagem responde a uma pergunta de pertinência, e nada mais.
NotaO enunciado formal de linguagem
Uma linguagem L sobre um alfabeto \Sigma é um subconjunto de \Sigma^*, isto é, L \subseteq \Sigma^*. Nenhuma outra exigência é feita: L pode ser vazia, finita ou infinita, e não precisa ter regra, padrão ou descrição finita.
Dada uma cadeia qualquer, ela está dentro ou fora? Tudo o que se pede é que essa resposta exista para toda cadeia do universo. Ninguém exige que ela seja fácil de obter, nem que alguém saiba obtê-la. O menor exemplo concreto tem dois elementos: sobre \Sigma = \{a, b\}, o conjunto \{a, ab\} é uma linguagem, o conjunto vazio também é, e \{\varepsilon\} é uma terceira, distinta das outras duas.
Enquanto a linguagem for finita, representá-la é trivial. Basta um conjunto de cadeias na memória, que é o que a definição literalmente diz. Escrever o que a definição diz costuma ser o começo certo, e é o que o sistema de referência faz neste ponto do percurso.
01_linguagem.h
// Uma cadeia é uma sequência finita de símbolos. Usamos std::string porque o
// alfabeto da Peneira é de caracteres; a cadeia vazia é a string vazia.
using Cadeia = std::string;
// Conjunto ordenado para que a saída seja determinística — em demonstração, uma
// ordem que muda a cada execução tira do leitor a chance de comparar dois resultados.
using Alfabeto = std::set<char>;
using Linguagem = std::set<Cadeia>;Três linhas, e uma delas carrega uma decisão que a definição não tomava. O conjunto escolhido ali é ordenado, e a razão é de demonstração: uma ordem que muda a cada execução tira de quem lê a chance de comparar duas saídas lado a lado. É escolha daquele projeto, tomada por reprodutibilidade. Conjunto, em matemática, não tem ordem nenhuma, e uma tabela de dispersão seria igualmente correta e mais rápida.
Essa separação volta em cada capítulo com valores diferentes. De um lado, o que o conceito exige. Do outro, o que um projeto específico decidiu, com o motivo escrito ao lado. Confundir as duas coisas é o caminho mais curto para decorar como lei o que era preferência de quem implementou.
NotaAs quatro operações, em notação
Sejam L_1 e L_2 linguagens sobre \Sigma. A união é L_1 \cup L_2 = \{w : w \in L_1 \text{ ou } w \in L_2\}. A concatenação é L_1 L_2 = \{xy : x \in L_1 \text{ e } y \in L_2\}. A potência é L^0 = \{\varepsilon\} e L^{n+1} = L^n L. O fecho de Kleene é L^* = \bigcup_{n \geq 0} L^n.
flowchart LR
U["união<br/>isto ou aquilo"] --> F["conjunto finito<br/>continua finito"]
C["concatenação<br/>isto seguido daquilo"] --> F
C --> P["potência<br/>exatamente n vezes"]
P --> F
P --> K["fecho<br/>união de todas<br/>as potências"]
K --> I["conjunto infinito<br/>não cabe em memória"]
I --> S["a saída: guardar o critério,<br/>não as cadeias"]
Comece pela união, que é a mais simples e a mais confundida das quatro. Ela traz as cadeias que estão em alguma das duas linguagens, e o conectivo da definição é ou. Quem lê depressa e escreve “as cadeias que estão nas duas” acabou de descrever a interseção, que é outra operação e produz outro conjunto. União é escolha, e é generosa. A concatenação toma uma cadeia de cada lado e as cola nessa ordem. Sobre L_1 = \{a, ab\} e L_2 = \{b\}, o resultado é \{ab, abb\}. A definição fala de pares, e mesmo assim o resultado é um conjunto de cadeias: as duas metades se fundem numa só, e a fronteira entre elas desaparece. Quem devolve o par em vez da cadeia colada implementou outra operação, com o nome certo e o efeito errado.
01_linguagem.cpp
Linguagem uniao(const Linguagem& esquerda, const Linguagem& direita) {
Linguagem resultado = esquerda;
resultado.insert(direita.begin(), direita.end());
return resultado;
}
Linguagem concatenacao(const Linguagem& esquerda, const Linguagem& direita) {
Linguagem resultado;
for (const Cadeia& prefixo : esquerda) {
for (const Cadeia& sufixo : direita) {
resultado.insert(prefixo + sufixo);
}
}
return resultado;
}O código expõe a diferença de escala melhor que a notação. A união é uma inserção em bloco e percorre cada linguagem uma vez. A concatenação é um laço dentro de outro laço, e o resultado tem tamanho proporcional ao produto dos dois. Duas linguagens de mil cadeias cada se unem em duas mil linhas; concatenadas, pedem um milhão.
E aqui mora um detalhe que contraria o que a aritmética sugere à primeira vista. Concatenar uma linguagem de 40 cadeias com outra de 25 produz no máximo mil cadeias, e quase sempre menos. Dois pares distintos podem gerar a mesma cadeia — ab com c e a com bc produzem abc —, e num conjunto ela conta uma vez só. Mil é teto, e é teto justamente porque o resultado é conjunto.
A potência repete a concatenação: L^2 é L concatenada consigo mesma, L^3 é isso mais uma vez, e assim por diante. O caso que interessa é o de baixo, e ele diz que L^0 vale \{\varepsilon\}.
A escolha parece convenção arbitrária até você executá-la errado. Escreva L^0 = \emptyset, com o argumento razoável de que zero cópias de coisa nenhuma dá coisa nenhuma, e depois concatene: o conjunto vazio não tem com o que colar, então ele aniquila tudo o que multiplica.
01_linguagem.cpp
Linguagem potencia(const Linguagem& linguagem, const std::size_t expoente) {
// A potência zero contém a cadeia vazia. Devolver a linguagem vazia aqui
// quebraria o fecho de Kleene inteiro, porque a concatenação com o conjunto
// vazio aniquila o resultado em vez de preservá-lo.
Linguagem resultado{Cadeia{}};
for (std::size_t i = 0; i < expoente; ++i) {
resultado = concatenacao(resultado, linguagem);
}
return resultado;
}Repare na primeira linha do corpo, que é onde a definição vira código. O acumulador nasce contendo a cadeia vazia, e o laço concatena a partir dali. Trocar aquela inicialização pelo conjunto vazio compila, roda e devolve conjunto vazio para toda entrada — inclusive para uma linguagem de duas cadeias que se confere a olho em cinco segundos.
Siga o sintoma até o fim, porque ele ensina mais que o conserto. Você chama o fecho sobre \{a, b\} e recebe um conjunto vazio. A função do fecho parece a culpada, e ela está somando corretamente uma sequência de conjuntos vazios. A linha que falha nunca é a linha errada: o defeito mora três funções acima, numa inicialização de uma palavra.
O fecho de Kleene, esse, reúne todas as potências de uma linguagem, da zero em diante. O nome vem de Stephen Kleene. É a operação que produz infinito a partir de finito: se L contém uma cadeia não vazia, L^* é infinito, sem exceção. Uma linguagem de duas cadeias de um símbolo cada já gera um conjunto que não termina, o que põe um problema imediato para quem queira materializá-lo.
01_linguagem.cpp
Linguagem fechoDeKleene(const Linguagem& linguagem, const std::size_t comprimentoMaximo) {
Linguagem resultado{Cadeia{}};
Linguagem nivelAtual{Cadeia{}};
// Cresce por níveis em vez de calcular potência por potência: cada nível é o
// anterior concatenado uma vez com a linguagem, e paramos quando nenhuma
// cadeia nova cabe no comprimento máximo. Sem essa parada por comprimento o
// laço não termina, porque o fecho é infinito por definição.
while (!nivelAtual.empty()) {
Linguagem proximoNivel;
for (const Cadeia& cadeia : concatenacao(nivelAtual, linguagem)) {
if (cadeia.size() <= comprimentoMaximo) {
proximoNivel.insert(cadeia);
}
}
// A cadeia vazia reaparece a cada nível se a linguagem a contiver; o
// conjunto absorve a repetição, mas o nível precisa perder as já vistas,
// senão o laço nunca esvazia.
Linguagem novidades;
for (const Cadeia& cadeia : proximoNivel) {
if (resultado.find(cadeia) == resultado.end()) {
novidades.insert(cadeia);
}
}
resultado.insert(novidades.begin(), novidades.end());
nivelAtual = novidades;
}
return resultado;
}O parâmetro de comprimento máximo é o que a teoria não pediu e a memória exigiu. É bom que ele incomode. Ele não está na definição, não tem valor certo e muda a resposta: perguntada sobre uma cadeia longa, essa função responde “não está” quando a verdade é “está, e ficou fora do recorte que eu materializei”. Uma implementação que não distingue as duas respostas ensina a quem lê a saída o oposto do verdadeiro.
Repare também na parte do laço que filtra as cadeias já vistas. Sem ela o nível nunca esvazia, porque a cadeia vazia reaparece a cada volta e o conjunto absorve a repetição em silêncio. O programa não erraria o resultado; ele simplesmente não terminaria. É o tipo de defeito que passa em toda revisão feita a olho, e que só aparece quando alguém desiste de esperar a saída.
O que fica desta seção é uma dívida.
O conjunto explícito é curto de escrever, correto e inútil na primeira linguagem interessante. A saída é guardar o critério em vez das cadeias, e o critério cabe em três linhas onde a lista não cabe em disco nenhum.
1.4 Ninguém guarda um conjunto infinito
Duas famílias de descrição finita, e a prova de que juntas elas não alcançam quase nada.
Se a linguagem é infinita e a memória não é, como se guarda uma linguagem? A pergunta parece de engenharia e é de matemática. A resposta prática é conhecida — guarda-se uma descrição finita em vez das cadeias — e ela abre imediatamente uma segunda pergunta, que é a interessante: toda linguagem tem uma descrição finita?
Antes de responder, veja a ideia funcionando. Tome a linguagem dos identificadores válidos de qualquer linguagem de programação: começam por letra, seguem com letras ou dígitos, sem teto de comprimento. Ela é infinita, e a lista dela não termina de ser escrita. A descrição dela cabe em três linhas e decide qualquer cadeia que alguém apresente, inclusive uma que ninguém jamais escreveu.
flowchart LR
G["descrição que GERA<br/>gramática"] -->|"fácil de escrever<br/>por gente"| H["pessoa"]
R["descrição que RECONHECE<br/>autômato"] -->|"é o que a máquina<br/>consegue executar"| M["máquina"]
G ==>|"conversão mecânica,<br/>por algoritmo"| R
T["todas as linguagens<br/>não enumerável"] --> Z["descrições finitas<br/>enumerável"]
Z --> W["o que sobra é o que<br/>se pode projetar e implementar"]
Há duas maneiras de descrever um conjunto de cadeias em espaço finito, e elas se distinguem pelo verbo. Uma gera: dá regras que produzem cadeias, e a linguagem é tudo o que se consegue produzir. A outra reconhece: descreve uma máquina que lê uma cadeia e responde sim ou não, e a linguagem é tudo o que recebe sim. A repartição de trabalho entre as duas segue de quem as lê. Regras que geram são confortáveis para pessoas, porque descrevem a forma da coisa como alguém a explicaria em voz alta. Máquinas que reconhecem são o que um processador executa, porque consistem em olhar um símbolo, mudar de estado e seguir. Ninguém desenha estados à mão por prazer, e nenhum processador executa regra de produção diretamente.
Essa assimetria é permanente, e escolher um lado só não a resolve. Um projeto que tivesse apenas a gramática precisaria interpretá-la a cada cadeia examinada. Um projeto que tivesse apenas a máquina obrigaria alguém a redesenhar estados toda vez que a linguagem mudasse de uma vírgula. A ponte entre as duas famílias é mecânica: existe algoritmo que converte descrição que gera em descrição que reconhece, dentro de cada degrau da hierarquia.
Você escreve na forma conveniente, a máquina executa na forma eficiente, e o programa que faz a travessia é o compilador. Isso é quase a definição do ofício. Fica então a pergunta de como se escreve, com precisão, uma descrição que gera — e é aí que entra a gramática.
NotaA gramática, em notação
Uma gramática é uma quádrupla G = (V, \Sigma, P, S) em que V é um conjunto finito de não terminais, \Sigma é um alfabeto de terminais com V \cap \Sigma = \emptyset, P é um conjunto finito de produções da forma \alpha \to \beta com \alpha, \beta \in (V \cup \Sigma)^* e \alpha contendo ao menos um não terminal, e S \in V é o símbolo inicial.
A gramática mantém dois vocabulários separados: os símbolos que aparecem na cadeia final e os nomes auxiliares que existem só durante a construção. E mantém uma lista de regras que trocam pedaço por pedaço. Começa-se pelo símbolo inicial e aplicam-se regras até não restar nome auxiliar nenhum. Falta dizer o que significa aplicar uma regra, e a definição seguinte faz isso em duas linhas.
NotaDerivar, em notação
Escreve-se \gamma \alpha \delta \Rightarrow \gamma \beta \delta quando \alpha \to \beta é uma produção de G, e \Rightarrow^* para o fecho reflexivo e transitivo de \Rightarrow. A linguagem gerada por G é L(G) = \{ w \in \Sigma^* : S \Rightarrow^* w \}.
flowchart TB
S["símbolo inicial"] -->|"aplica uma regra"| D["cadeia com terminais<br/>e não terminais"]
D -->|"aplica outra regra"| D2["cadeia só<br/>com terminais"]
D2 --> L["a cadeia pertence<br/>à linguagem gerada"]
D2 --> A1["árvore A<br/>a multiplicação mais fundo"]
D2 --> A2["árvore B<br/>a soma mais fundo"]
A1 --> R1["um resultado"]
A2 --> R2["outro resultado"]
R1 --> AMB["mesma cadeia,<br/>dois significados:<br/>a gramática é ambígua"]
R2 --> AMB
O menor exemplo que produz um conjunto infinito tem duas regras: S \to aSb e S \to \varepsilon. Derive aaabbb passo a passo, escrevendo cada linha. Do símbolo inicial vem aSb; aplicando a primeira regra outra vez vem aaSbb; e outra vez, aaaSbbb; a segunda regra apaga o S e sobra a cadeia pedida. Quatro aplicações (três da primeira regra, uma da segunda), seis símbolos, e nenhum limite superior para quantas vezes o passo se repete.
O infinito sai de um lugar exato. A primeira regra tem S dos dois lados da seta. Uma produção em que o não terminal reaparece à direita pode ser aplicada de novo sobre o próprio resultado, e é essa recursão que produz cadeias arbitrariamente longas a partir de duas linhas de texto. Retire a recursão e a gramática passa a gerar um conjunto finito, sempre.
Repare no que a definição não exige. Ela não pede que cada cadeia gerada tenha uma única derivação. Uma mesma cadeia pode ser produzida por dois caminhos, com estruturas diferentes, e quando a estrutura carrega significado, dois caminhos significam dois resultados. Uma gramática de expressões aritméticas mal escrita deriva 2 + 3 * 4 de dois modos. Um põe a multiplicação mais fundo. O outro põe a soma. Os números que saem no fim são 14 e 20.
Gramática com essa propriedade chama-se ambígua, e desfazer ambiguidade é trabalho que reaparece com força no arco da análise sintática. Por ora basta reconhecer o sintoma: duas árvores para a mesma cadeia, e nada na definição proibindo isso.
Falta a notação, e ela tem data. Em 1959, John Backus propôs uma forma de descrever a sintaxe da linguagem que viria a ser o ALGOL 60; Peter Naur, ao editar o relatório oficial, adaptou-a e a usou por extenso. Ela sobreviveu a tudo o que a cercava e continua sendo o modo padrão de escrever gramática de linguagem de programação, em manual, em norma e em artigo.
O que ela acrescenta é abreviação, e nada além disso. A barra vertical junta numa linha só duas produções com o mesmo lado esquerdo. O colchete marca o que é opcional, e o par de chaves marca o que se repete zero ou mais vezes. Escrever A \to [\,b\,] é escrever duas produções, A \to b e A \to \varepsilon; escrever A \to \{\,b\,\} é introduzir um não terminal auxiliar recursivo, do mesmo formato daquele que gerava aaabbb.
O documento encurta; a linguagem gerada permanece exatamente a mesma. Quem confunde encurtar com ampliar acaba atribuindo à notação garantias que pertencem à classe. Guarde a distinção assim: o que decide o alcance de uma gramática é a forma das produções permitidas, e açúcar de escrita não muda forma de produção nenhuma.
Volte agora à pergunta que abriu a seção. A resposta é não, e o “não” é bem mais forte do que parece — quase nenhuma linguagem tem descrição finita. O argumento não exige aparato e cabe em três movimentos. Primeiro, conte as descrições: uma descrição finita é um texto finito sobre um alfabeto finito, seja ela gramática, máquina ou programa. Enfileire todas as de comprimento 1, depois as de comprimento 2, depois as de comprimento 3.
Cada bloco é finito, os blocos vêm em ordem, e toda descrição aparece em algum ponto da fila. O conjunto das descrições é, portanto, enumerável: uma fila em que cada gramática e cada programa que alguém venha a escrever tem posição marcada. Segundo, conte as linguagens. Uma linguagem é um subconjunto de \Sigma^*, e o argumento diagonal de Cantor mostra que os subconjuntos de um conjunto infinito enumerável não se enfileiram.
Dada qualquer fila proposta, constrói-se um subconjunto que difere do primeiro item no primeiro elemento, do segundo no segundo, e assim por diante. Ele fica de fora da fila inteira. Terceiro, compare: de um lado uma coleção que se enfileira, do outro uma que não se enfileira. Para quase toda linguagem sobre um alfabeto qualquer não existe gramática, não existe máquina e não existe programa que a descreva.
O saldo desta seção
A palavra “existe” ali é literal, e é a parte que costuma passar batida. A descrição não está por descobrir, esperando alguém mais esperto: ela não existe, e isso é demonstrado, não conjecturado. Resultado de impossibilidade é diferente, em espécie, de dificuldade em aberto. Daí o recorte que organiza a área inteira — não se estudam as linguagens, estudam-se as que têm descrição finita, que é a fatia que se pode projetar, implementar e verificar.
1.5 A pergunta certa é de que memória a máquina precisa
Quatro classes, quatro máquinas, e um critério só para separá-las.
Em 1956, Noam Chomsky publicou nas IRE Transactions on Information Theory o artigo Three Models for the Description of Language. Ele era linguista, o alvo declarado era a linguagem humana, e computadores não entravam na conversa. A computação herdou o resultado depois, sem que o autor tivesse escrito uma linha pensando em compilador algum.
O caminho que ele percorreu importa, porque o senso comum o inverte. Chomsky partiu das regras e foi restringindo a forma delas. Primeiro sem restrição alguma; depois exigindo que o lado direito nunca encurte; depois exigindo que o lado esquerdo tenha um único não terminal; por fim, apertando a forma do lado direito até quase nada caber nela. Quatro níveis de restrição, quatro classes de linguagem, e a correspondência com máquinas veio depois, de outra direção.
flowchart TB
subgraph T0["irrestrita — máquina de Turing<br/>fita ilimitada"]
subgraph T1["sensível ao contexto — autômato<br/>linearmente limitado"]
subgraph T2["livre de contexto — autômato<br/>de pilha"]
subgraph T3["regular — autômato finito<br/>só o estado atual"]
R["identificadores,<br/>números,<br/>palavras-chave"]
end
C["aninhamento,<br/>parênteses<br/>balanceados"]
end
S["concordância entre<br/>três listas paralelas"]
end
U["tudo o que um<br/>programa pode decidir"]
end
As quatro classes se encaixam, e o desenho mostra isso melhor que a lista. Toda linguagem regular é livre de contexto; toda livre de contexto é sensível ao contexto; e assim por diante até o topo. Uma linguagem sobe de degrau quando o degrau de baixo comprovadamente não a alcança, e “comprovadamente” é palavra pesada aqui: cada separação dessas é um teorema com demonstração própria.
01_pipeline.cpp
std::vector<NivelDeChomsky> hierarquiaDeChomsky() {
return {
{3, "regular", "automato finito",
"os patterns do usuario e os simbolos da propria linguagem"},
{2, "livre de contexto", "automato de pilha",
"a gramatica da Peneira e o analisador descendente"},
{1, "sensivel ao contexto", "automato linearmente limitado",
"fora do artefato: nenhuma fase precisa deste poder"},
{0, "irrestrita", "maquina de Turing",
"fora do artefato: e o poder do compilador, nao o da linguagem compilada"},
};
}Escrever a hierarquia como dado que o programa imprime, em vez de comentário no alto de um arquivo, tem uma vantagem que vale além deste caso. Comentário não executa, não se compara com nada e envelhece em silêncio. Uma tabela impressa é conferida junto com o resto da saída. Note a última coluna: ela diz onde cada degrau comparece no sistema, e dois dos quatro comparecem com “fora”.
Antes de descer aos degraus, uma advertência que derruba os três palpites mais comuns. O que separa um degrau do seguinte não é o tamanho do alfabeto, nem o número de regras da gramática, nem a velocidade de coisa alguma. Uma gramática de degrau baixo pode ter centenas de regras. O critério é quanta memória a máquina precisa ter, e de que tipo é o acesso a ela.
1.5.1 A máquina que conta nos dedos, com um número fixo de dedos
O degrau mais baixo tem a máquina mais pobre que se pode imaginar. Ela lê um símbolo por vez. Avança sempre para a frente. Toda a memória dela cabe num único dado: em qual de um número fixo de estados ela está agora. Não há contador, não há bloco de anotações, não há como voltar. É uma máquina que conta nos dedos. E os dedos foram contados antes de ela ligar. Quem só sabe em que estado está não sabe quantas vezes já entrou nele.
Essa frase vira argumento em três linhas. Pegue lápis e papel. Fixe uma máquina com k estados, escolhidos antes de ela rodar. Alimente-a com uma abertura de parêntese, depois com duas, depois com três, e assim por diante. As profundidades de abertura são infinitas; os estados são k. Apresentadas k+1 profundidades diferentes, duas delas terminam no mesmo estado. Não há estado sobrando para acomodar todas.
flowchart TB
E["uma máquina com k estados<br/>escolhidos antes de rodar"]
E --> P1["leu ( <br/>parou no estado q1"]
E --> P2["leu (( <br/>parou no estado q2"]
E --> P3["leu ((( <br/>parou no estado q3"]
E --> PN["leu ( repetido n vezes<br/>e n não tem teto"]
P1 --> C{"profundidades infinitas,<br/>estados em quantidade fixa"}
P2 --> C
P3 --> C
PN --> C
C -->|"duas delas, i e j,<br/>param no mesmo estado"| M["dali em diante a máquina<br/>não distingue i de j"]
M --> A["o fechamento certo para i<br/>é aceito também para j"]
A --> F["e a cadeia de j<br/>está desbalanceada"]
Chame de i e j essas duas profundidades. Dali em diante a máquina não as distingue mais: ela está no mesmo lugar nos dois casos, e o que vier a seguir será tratado de modo idêntico. Apresente agora i fechamentos. Para a entrada que abriu i vezes, a resposta certa é aceitar; para a que abriu j vezes, a resposta certa é recusar, porque sobram parênteses abertos. A máquina responde a mesma coisa às duas.
O caso extremo é engraçado e verdadeiro: existe entrada com mil aberturas e um único fechamento que essa máquina aceita, chegando ao fim perfeitamente confiante.
E acrescentar estados não resolve, por mais tentadora que a saída pareça. O argumento se refaz para qualquer k finito, e uma máquina de 101 estados reconhece outra linguagem — a dos parênteses balanceados até profundidade 100, que é regular. O obstáculo é a finitude do conjunto de estados, e nada tem a ver com o tamanho dele.
O saldo desta seção
Memória finita reconhece o que se decide sem contar. Identificadores, números, palavras reservadas e operadores cabem nesse degrau, porque decidir sobre eles nunca exige lembrar uma quantidade sem teto. Aninhamento não cabe, e a razão é sempre a mesma: a contagem de aberturas pendentes não tem limite superior. Diante de qualquer linguagem nova, faça a si mesmo a pergunta nesta forma — o que essa máquina precisaria lembrar para decidir?
1.5.2 A pilha, e uma data em Amsterdã
O degrau seguinte acrescenta uma peça, e a peça é modesta a ponto de parecer insuficiente. É uma pilha: lê-se e escreve-se apenas no topo. Não se consulta o meio, não se conta quantos itens há sem desempilhar tudo, não se troca a ordem. Uma estrutura de dados com menos operações do que qualquer curso introdutório costuma apresentar, e é exatamente essa pobreza que a torna útil. Em troca do que recusa, a pilha lembra uma quantidade sem teto, na ordem inversa em que os itens chegaram. Essa é precisamente a ordem em que fechamentos casam com aberturas: o último parêntese aberto é o primeiro a fechar. A estrutura não foi projetada para aninhamento. Ela simplesmente tem a forma do problema, o que é a sorte mais bem aproveitada da área.
A entrada dela na engenharia tem data e lugar. Em agosto de 1960, no Mathematisch Centrum de Amsterdã, Edsger W. Dijkstra e Jaap A. Zonneveld concluíram o primeiro compilador de ALGOL 60. A implementação de procedimentos recursivos por pilha de registros de ativação vem dessa linhagem, e Dijkstra a expôs em Recursive Programming, publicado na Numerische Mathematik em 1960. O problema na mesa era concreto: com o mesmo procedimento ativo várias vezes ao mesmo tempo, ninguém sabia dizer qual endereço de retorno era o certo. Guardar cada retorno numa pilha resolveu. A recursão só é barata porque alguém decidiu guardar o retorno numa pilha.
A mesma peça reaparece em três alturas ao longo desta obra, e reconhecê-las como o mesmo objeto é metade do ganho. Aqui ela é a memória do autômato do segundo degrau. Adiante ela é a cadeia de chamadas de um analisador escrito por procedimentos recursivos. No fim, ela é o registro de ativação na memória da máquina que executa o programa traduzido. Três ofícios, um objeto.
Acima da pilha há mais dois degraus, e nenhum deles aparece na construção de um compilador comum. O terceiro é o das linguagens sensíveis ao contexto. A máquina dele tem fita de trabalho proporcional à entrada. O exemplo típico é a concordância entre três listas paralelas de mesmo comprimento. Uma pilha não sustenta isso: ela casa dois lados, e ali são três. Verificações desse tipo existem em linguagens reais, e nenhum compilador as resolve com gramática: elas caem na fase que verifica significado, escrita como código comum.
O quarto degrau é o das linguagens irrestritas, reconhecidas por máquina de Turing, e aqui mora a distinção que mais confunde neste ponto. A máquina de Turing é o poder do compilador, e não o da linguagem compilada. O programa que traduz é um programa comum, com memória e laços. A gramática que ele reconhece fica dois ou três degraus abaixo. E fica ali por escolha. Se eu tivesse de defender uma única decisão de projeto desta parte do percurso, seria manter a sintaxe da sua linguagem no segundo degrau, mesmo quando subir parecer resolver um problema.
1.6 Cada fase entrega um artefato, e a seguinte só sabe ler aquilo
Um tradutor é uma sequência de fases, e cada fase é um programa com entrada e saída bem definidas. Nada de misterioso acontece entre elas. O formato do dado que atravessa cada fronteira tem nome, estrutura e, se alguém quiser, arquivo em disco. Ler a arquitetura como sequência de artefatos, e não de rótulos, é o que torna cada fase testável isoladamente.
flowchart TD
T["texto escrito<br/>por quem usa"] --> S["análise<br/>de símbolos"]
S -->|"sequência de símbolos<br/>classificados"| E["análise<br/>de estrutura"]
E -->|"árvore de<br/>decomposição"| G["análise<br/>de significado"]
G -->|"árvore verificada<br/>+ tabela de nomes"| M["emissão"]
M -->|"objeto"| X["execução"]
X --> R["saída sobre a<br/>entrada do domínio"]
subgraph ANALISE["metade que analisa"]
S
E
G
end
subgraph SINTESE["metade que sintetiza"]
M
end
Vou usar como exemplo uma linguagem inventada e mínima, que chamarei de Régua. Nela, alguém escreve uma condição sobre valores medidos e uma ação a tomar quando a condição vale. Régua não existe fora destas páginas e não precisa existir: o que ela serve para mostrar é o percurso, e para isso qualquer linguagem pequena serve.
A primeira fase recebe o texto e devolve uma sequência de unidades classificadas. Onde havia medida > 70, passa a haver quatro itens: um nome, um operador de comparação, um número e o fim da linha. Espaços somem, comentários somem, e cada item carrega a posição em que estava no texto. Sem essa posição, nenhuma mensagem de erro adiante consegue dizer onde o problema mora. A segunda fase recebe essa sequência e devolve uma estrutura em árvore. A comparação vira um nó com dois filhos; a condição inteira vira filha de um nó que também guarda a ação. A ordem em que os itens apareciam no texto deixa de importar, porque a estrutura passa a dizer o que se relaciona com o quê. É aqui que a precedência entre operadores para de ser regra escrita e vira forma de objeto.
A terceira fase recebe a árvore e devolve a mesma árvore, agora verificada, mais uma tabela com o que cada nome significa. Ela é a primeira que pode reclamar de algo sintaticamente perfeito. Comparar uma medida com um texto é gramaticalmente impecável e semanticamente sem sentido, e nenhuma das duas fases anteriores tinha como perceber isso, porque nenhuma delas sabia o que é uma medida. A quarta recebe a árvore verificada e devolve um objeto executável (num formato que ela mesma escolhe); a quinta roda esse objeto sobre dados reais.
01_pipeline.cpp
std::vector<Fase> pipelineDaPeneira() {
return {
{"analise lexica", "texto do programa .pen", "sequencia de simbolos com posicao",
Metade::Analise},
{"analise sintatica", "sequencia de simbolos", "arvore da estrutura do programa",
Metade::Analise},
{"analise semantica", "arvore da estrutura", "arvore verificada e tabela de simbolos",
Metade::Analise},
{"geracao de codigo", "arvore verificada", "objeto: vetor de AFDs + bytecode das regras",
Metade::Sintese},
{"execucao na maquina virtual", "objeto + texto de entrada", "saida do emit",
Metade::Sintese},
};
}O que a tabela revela do conceito são as duas colunas do meio. Cada linha declara o que consome e o que produz, e a conferência fica trivial: o produzido por uma linha tem de ser exatamente o consumido pela seguinte. Onde houver salto — uma fase que consome algo que ninguém produziu —, falta uma linha na arquitetura, e a lacuna vira uma peça esquecida muitos capítulos adiante.
As três primeiras fases têm algo em comum que justifica tratá-las como um bloco: todas desmontam. Recebem uma representação e produzem outra mais estruturada, mais explícita e mais distante do texto original. Nenhuma delas produz coisa parecida com um programa executável, e nenhuma precisa saber que máquina vai rodar o resultado. Troque a máquina de destino e as três continuam idênticas, letra por letra. O artefato de fronteira entre as duas metades tem nome, e nomeá-lo agora resolve uma pergunta que costuma ficar vaga até tarde. É a árvore verificada, acompanhada da tabela de nomes. A análise entrega isso, a síntese consome isso, e nada atravessa a fronteira em outro formato. Uma fase da síntese que precisasse voltar a olhar o texto original seria sintoma de que a análise não terminou o serviço.
Sintetizar é o movimento inverso: a partir de uma estrutura explícita, produzir algo executável. E aqui aparece um problema que a metade anterior nunca enfrenta, porque só a síntese conhece a máquina de destino.
Nenhuma máquina real oferece exatamente as operações que a linguagem oferece. A linguagem tem operações que a máquina não tem; a máquina tem restrições que a linguagem ignora. O que a máquina não faz, o tradutor faz por ela — e cobra em instruções.
Uma operação ausente do repertório da máquina não some do programa: ela vira uma sequência de operações que existem, mais longa e mais lenta do que a operação única teria sido. Essa distância é o que torna possível falar em qualidade de tradução. Dois tradutores corretos para a mesma linguagem e a mesma máquina produzem saídas diferentes, e comparar as duas exige uma medida: quantas instruções, quantos acessos à memória, quanto tempo.
Entre a primeira e a última fase existem artefatos que nenhuma das duas pontas pediu. Quem escreve o programa quer escrever texto; quem usa o resultado quer o resultado. A sequência de unidades classificadas, a árvore, a tabela de nomes e o objeto emitido não são nem o texto nem o resultado, e mesmo assim os quatro existem em qualquer sistema de tradução que se sustente.
01_pipeline.cpp
std::vector<FormaIntermediaria> formasIntermediariasDaPeneira() {
return {
{"sequencia de simbolos", "analise lexica", "analise sintatica",
"sem ela o parser voltaria a olhar caractere, e espaco e comentario reapareceriam"},
{"arvore da estrutura", "analise sintatica", "analise semantica",
"sem ela o verificador teria de redescobrir a estrutura a cada checagem"},
{"tabela de simbolos", "analise semantica", "geracao de codigo",
"guarda o que o nome significa longe do ponto do texto em que ele aparece"},
{"arvore verificada", "analise semantica", "geracao de codigo",
"e o artefato de fronteira: a analise entrega, a sintese consome"},
{"objeto: AFDs + bytecode", "geracao de codigo", "maquina virtual",
"separa compilar de executar: compila-se uma vez, executa-se sobre muitas entradas"},
};
}A última coluna do trecho é a que carrega o conceito: cada forma vem acompanhada da razão pela qual não se elimina. Uma arquitetura declarada sem essa coluna descreve o que existe e não defende nada, e a primeira pessoa que tentar simplificar o sistema removerá a peça errada. Vale a pena ler a tabela uma linha por vez, perguntando o que aconteceria se aquela linha sumisse.
Pular uma forma intermediária não faz o trabalho dela desaparecer; faz o trabalho migrar. Considere a expressão a + b * c e a pergunta “essa multiplicação já foi calculada em algum lugar acima?”. Sobre o texto, responder exige achar todas as ocorrências de b * c, descontar as que estão dentro de comentário e conferir se b ou c mudaram entre uma e outra. Agora decomponha em passos elementares: t1 = b * c e depois t2 = a + t1.
A mesma pergunta vira uma busca nas linhas anteriores por uma atribuição com o mesmo lado direito. O que separa as duas versões é a quantidade de casos que cada uma obriga a tratar. A forma decomposta tem uma operação por linha, dois operandos por operação e nenhum aninhamento. É pobre por decisão, e a pobreza é o que torna o raciocínio sobre ela mecânico.
Declarar uma forma intermediária exige três coisas, e nenhuma delas é o código que a produz. Vem antes de tudo a definição do formato: o que aquele artefato contém e o que ele garante a quem o consumir. Depois, a conversão de entrada e a de saída, escritas e testadas separadamente. Por último, e é o que mais se esquece, a decisão sobre o que não entra ali. A sequência de unidades é útil porque jogou fora espaço e comentário. A árvore é útil porque jogou fora os parênteses.
flowchart LR
F["texto escrito<br/>por quem usa"] --> A["metade que analisa<br/>(igual nas três)"]
A --> V["árvore verificada"]
V --> P1["emite objeto<br/>de máquina"] --> E1["o objeto executa"]
V --> P2["ninguém emite nada"] --> E2["uma máquina percorre<br/>a árvore a cada uso"]
V --> P3["emite objeto<br/>de formato próprio"] --> E3["uma máquina virtual<br/>executa o objeto"]
Uma linguagem é compilada ou interpretada? A pergunta é comum e está mal formulada, e desfazê-la resolve boa parte da confusão em torno do assunto. Compilar e interpretar são propriedades de implementações. A mesma linguagem admite as três estratégias, e várias linguagens conhecidas têm implementações de mais de um tipo circulando ao mesmo tempo.
A metade que analisa é idêntica nas três, e essa é a primeira coisa a fixar. O que varia é o que se faz depois da árvore verificada. Na compilação, a tradução acontece antes da execução, uma única vez. Ela produz um objeto que roda sem o tradutor por perto. Perceba onde o custo cai: quem publica arca com o tempo de traduzir. Quem usa não precisa nem ter o compilador instalado. Na interpretação não há tradução nenhuma: a estrutura é percorrida a cada execução, e as decisões que a compilação tomaria uma vez são retomadas toda vez.
01_pipeline.cpp
std::vector<EstrategiaDeExecucao> estrategiasDeExecucao() {
return {
{"compilacao", "antes da execucao, uma vez", "o codigo de maquina gerado",
"C traduzido para codigo nativo", false},
{"interpretacao", "nao ha traducao: a estrutura e percorrida a cada execucao",
"o interpretador, sobre a arvore ou o texto", "shell POSIX, comando a comando", false},
{"hibrida", "antes da execucao, para uma representacao intermediaria",
"uma maquina virtual, sobre o bytecode", "Java compilado para bytecode da JVM", true},
};
}A terceira estratégia parte a diferença ao meio: traduz-se antes da execução, mas o alvo é um formato próprio, executado por um programa que se comporta como se fosse uma máquina. O objeto é traduzido uma vez, executado muitas, e roda onde quer que aquele programa rode. Leia a tabela pela coluna dos exemplos e a pergunta mal formulada se desfaz sozinha: nenhuma das três linhas nomeia uma linguagem, todas nomeiam implementações.
Há ainda uma consequência da interpretação que raramente entra na comparação e decide muitos projetos. O programa continua disponível como texto na máquina de quem o executa. Isso é o que permite corrigir um sistema em produção abrindo um arquivo, e é também o que impede distribuir um programa sem distribuir junto tudo o que ele diz. As duas coisas são a mesma propriedade vista de dois lados.
1.7 O documento que se escreve antes da primeira linha de código
Que perguntas se respondem antes de existir uma linha de código?
A primeira coisa que se escreve de uma linguagem é um documento curto, sem uma linha de código dentro. Ele responde a quatro perguntas: sobre que domínio a linguagem fala, que classe de construções ela aceita, que forma tem o texto que alguém escreve nela, e o que o sistema produz ao processá-lo. Nenhuma das quatro respostas é programa, e todas as quatro decidem o que o programa poderá ser.
flowchart TB
E["a primeira especificação"] --> D1["sobre que domínio<br/>a linguagem fala"]
E --> D2["que classe de construções<br/>ela aceita"]
E --> D3["que forma tem o texto<br/>que alguém escreve"]
E --> D4["o que o sistema produz<br/>ao processá-lo"]
D1 --> R1["recusa os<br/>demais domínios"]
D2 --> R2["recusa o que não cabe<br/>na classe escolhida"]
D4 --> R4["recusa os<br/>demais formatos"]
R2 --> C["e decide em que degrau<br/>o sistema opera"]
Por que escrever primeiro, se o texto não roda? Porque cada uma daquelas respostas restringe todas as fases seguintes. Uma ambiguidade deixada ali só se manifesta quando já existe código apoiado sobre a decisão que faltou. Consertá-la enquanto ela é um parágrafo leva dez minutos; consertá-la quando ela virou quatro fases significa reescrever as quatro. Veja o peso da segunda pergunta. Escolher a classe de construções aceitas é escolher em que degrau da hierarquia o seu sistema opera e, portanto, que tipo de máquina você vai precisar construir. Uma classe que caiba no primeiro degrau se resolve com memória finita. Uma que exija aninhamento sem teto obriga a subir para a pilha, e a subida ocupa vários capítulos.
Note o formato que quase ninguém adota na primeira vez: cada decisão vem acompanhada da alternativa que foi descartada, com a razão técnica ao lado. Registrar o que não se escolheu tem cara de burocracia e é o que torna a decisão revisitável meses depois. Quem a encontrar adiante, sem o registro, não distingue uma escolha de um esquecimento. E há uma pergunta de controle para cada linha do documento: se uma decisão não restringe nada, ela era descrição fantasiada de decisão, e sai sem perda.
Especificar é sobretudo recusar. Ao dizer que um nome válido começa por letra, você acabou de dizer que 3x não vale — e que o sistema, ao encontrar 3x, não deve tentar entender o que a pessoa queria. A recusa parece pequena e sustenta tudo o que veio antes. Volte por um instante ao tradutor generoso, o que adivinhava. A generosidade dele só é possível numa linguagem cuja especificação não recuse nada. E uma linguagem que não recusa nada não tem conjunto de textos admitidos.
Sem esse conjunto, caem juntas quatro coisas: a gramática, a máquina reconhecedora, a mensagem de erro com posição e a própria noção de programa inválido.
Uma fronteira que ninguém escreveu não existe.
Repare também que a recusa se escreve uma vez e é cobrada em todas as fases. A que separa unidades recusa o caractere fora do alfabeto. A que descobre a estrutura recusa a sequência que nenhuma produção deriva. E a que verifica o significado recusa a comparação entre tipos incompatíveis.
A gramática que sai dessa primeira escrita quase nunca serve para o analisador. Ela costuma ter recursão à esquerda, alternativas com prefixo comum e produções que dizem duas coisas ao mesmo tempo. Cada um desses traços tem algoritmo de correção conhecido, aplicado depois, e a tentação é corrigir tudo na hora e guardar só a forma final.
Não corrija: registre a gramática como ela saiu, feia, e preserve esse texto.
A comparação entre a forma de partida e a forma corrigida é a explicação mais eficiente que existe sobre por que cada transformação é necessária. Quem só vê a forma final aprende a receita e não aprende o problema. Guardar a versão anterior de uma decisão ocupa um arquivo de texto e devolve, meses depois, a única coisa que ninguém reconstrói de memória: por que o caminho foi aquele. A forma final é sempre recuperável a partir das regras; a forma de partida, uma vez apagada, não volta.
Falta uma última cena, e ela desloca a pergunta que se pode fazer sobre qualquer programa.
Em agosto de 1984, ao receber o Prêmio Turing, Ken Thompson descreveu nas Communications of the ACM um experimento que quase ninguém esperava ouvir numa cerimônia de premiação. Ele mostrou como um compilador pode ser modificado para inserir uma porta dos fundos em todo programa que compila, e como essa modificação pode ser feita desaparecer do código-fonte do próprio compilador.
flowchart LR
F["fonte do tradutor<br/>com a modificação"] --> B1["binário<br/>modificado"]
B1 -->|"compila o próprio<br/>fonte do tradutor"| B2["binário novo,<br/>ainda modificado"]
F2["fonte limpo<br/>modificação removida"] --> B2
B2 --> P["todo programa compilado<br/>sai sabotado"]
B2 -->|"e a próxima geração<br/>também"| B2
P --> L["a leitura do fonte<br/>não revela nada"]
O argumento tem três passos e todos cabem num parágrafo. Modifique o fonte do compilador para que ele reconheça um programa específico e insira código extra ao traduzi-lo. Acrescente uma segunda modificação, que reconhece o fonte do próprio compilador e reinsere as duas ao traduzi-lo. Compile o compilador modificado, guarde o binário resultante e apague as modificações do fonte. O que sobra é um código-fonte limpo, auditável, sem nada a encontrar em leitura nenhuma.
Compilado pelo binário guardado, esse fonte limpo produz um compilador que continua sabotando e que continua sabendo se reproduzir na geração seguinte. A saída óbvia seria ler o binário em vez do fonte, e ela não fecha: ler um binário exige um desmontador, o desmontador é um programa, e aquele programa também foi compilado por alguém. Empurrar a verificação um nível para baixo apenas move a pergunta.
Deixa de fazer sentido, portanto, perguntar apenas “o que este programa faz?”. A resposta depende de outra pergunta: quem traduziu este programa, e o que aquele tradutor sabia? A cadeia de confiança não termina no código que você lê — ela termina, quando termina, em alguém. No fim das contas, confiar num programa é confiar em quem o traduziu. Em 1952, ao chamar de compilador um programa que colava rotinas de uma fita, Grace Hopper propunha que texto escrito por pessoas fosse tratado como dado por máquinas. Trinta e dois anos depois, a consequência que ninguém podia antever naquele encontro foi enunciada num discurso de premiação.
Fica daqui um critério de decisão que serve além destas páginas. Diante de qualquer pergunta sobre o que um sistema de reconhecimento consegue fazer, não olhe o tamanho do texto, o número de regras nem a aparência da entrada. Pergunte de que memória a máquina precisaria para decidir, e de que tipo é o acesso a ela. As duas respostas situam qualquer problema no degrau certo, e o degrau decide o resto — inclusive quanto do sistema você vai precisar escrever à mão.
1.8 O sistema, neste ponto do percurso
Tudo o que foi definido até aqui tem uma contrapartida que roda, e ela cabe num executável só. O sistema de referência chama-se Peneira: uma linguagem pequena em que se declaram padrões sobre texto e se escrevem regras que reagem ao casamento desses padrões, e cujo compilador produz um motor de autômatos. Ela existe para ser estudada, não copiada — o sistema que você constrói é seu, sobre o domínio que escolher, e a Peneira serve de referência de acabamento.
A escolha desse artefato tem uma razão que se colhe ao longo de todo o percurso. Os padrões escritos por quem usa a linguagem são compilados para autômatos finitos; os símbolos da própria Peneira são reconhecidos por autômatos finitos construídos pelo mesmo maquinário. A teoria comparece duas vezes, em alturas diferentes do mesmo sistema. Essa dupla aparição é o que impede que os autômatos virem preâmbulo esquecível de uma caixa fechada.
1.8.1 O que o programa faz quando executa
O executável deste ponto do percurso imprime três demonstrações, na ordem em que os conceitos se apoiam.
A primeira percorre as operações sobre cadeias, sobre duas cadeias curtas e conferíveis a olho: comprimento, concatenação, reverso, potência, prefixo e sufixo. Ela termina imprimindo \Sigma^3 para o alfabeto de dois símbolos — as oito cadeias, uma por uma, seguidas da contagem. É a frase “uma linguagem é um subconjunto das cadeias possíveis” com o subconjunto e o universo lado a lado na tela.
A segunda faz o mesmo com duas linguagens finitas de duas cadeias cada. União, concatenação, potência zero, potência dois e o fecho truncado em comprimento 3, que sai com 15 elementos. A última linha é a que mais ensina: perguntada sobre abab, a demonstração responde que a cadeia está fora do recorte, e não fora da linguagem. Sem essa distinção impressa, quem lê a saída conclui o oposto do verdadeiro.
A terceira imprime a anatomia do sistema — as fases, a hierarquia de Chomsky, as formas intermediárias e as três estratégias de execução — como tabelas que o programa constrói, e não como comentário no alto de um arquivo. Nenhuma dessas fases existe ainda. A tabela é a promessa registrada em formato executável, e cada capítulo seguinte substitui uma linha dela por implementação real.
DicaA conta que fecha à mão
Antes de rodar qualquer coisa, confira: o fecho de uma linguagem com duas cadeias de um símbolo, truncado em comprimento 3, tem 15 elementos — uma cadeia vazia, duas de comprimento 1, quatro de comprimento 2 e oito de comprimento 3. Outro número aponta erro na potência zero ou na condição de parada, e em nenhum outro lugar.
1.8.2 O código do marco, por inteiro
O sistema tem dois pares de arquivos neste ponto. O primeiro traz o vocabulário formal — símbolo, cadeia, linguagem e as operações de cada degrau. Os recortes que apareceram ao longo do capítulo saíram daqui, e vê-los no arquivo inteiro mostra o que a extração escondeu: a ordem em que as funções se apoiam umas nas outras.
01_linguagem.h
// 01_linguagem.h — Alfabeto, cadeia e linguagem como conjunto de cadeias.
//
// Este é o vocabulário formal sobre o qual todo o resto da Peneira é construído,
// e ele vem em três degraus: o símbolo, a cadeia e a linguagem. Representamos
// linguagem como conjunto porque é exatamente o que a definição diz: uma
// linguagem sobre um alfabeto é um subconjunto de todas as cadeias possíveis
// sobre ele. Trabalhar com o conjunto explícito só é viável para linguagens
// finitas — e é por isso que os capítulos seguintes trocam esta representação pelo
// autômato, que descreve conjuntos infinitos em espaço finito.
#ifndef PENEIRA_01_LINGUAGEM_H
#define PENEIRA_01_LINGUAGEM_H
#include <cstddef>
#include <set>
#include <string>
namespace peneira {
// recorte:inicio linguagem-como-conjunto
// Uma cadeia é uma sequência finita de símbolos. Usamos std::string porque o
// alfabeto da Peneira é de caracteres; a cadeia vazia é a string vazia.
using Cadeia = std::string;
// Conjunto ordenado para que a saída seja determinística — em demonstração, uma
// ordem que muda a cada execução tira do leitor a chance de comparar dois resultados.
using Alfabeto = std::set<char>;
using Linguagem = std::set<Cadeia>;
// recorte:fim linguagem-como-conjunto
// --- Degrau 1: operações sobre cadeias -------------------------------------
// Estas quatro são as operações da definição, e nenhuma delas devolve conjunto:
// cadeia entra, cadeia (ou resposta de sim/não) sai. Separá-las das operações
// sobre linguagens é o que impede a confusão mais comum deste ponto — tratar a
// concatenação de duas cadeias e a de duas linguagens como a mesma coisa, quando
// a primeira produz um resultado e a segunda produz o produto cartesiano dos dois
// conjuntos.
// O comprimento de uma cadeia é a quantidade de símbolos nela; o da cadeia vazia
// é zero, e ela é o elemento neutro da concatenação.
std::size_t comprimento(const Cadeia& cadeia);
// Concatenação de cadeias: os símbolos da primeira seguidos dos da segunda.
Cadeia concatenarCadeias(const Cadeia& esquerda, const Cadeia& direita);
// Reverso: os mesmos símbolos na ordem inversa. Aparece cedo porque é o
// contraexemplo mais barato contra a ideia de que operar sobre texto é sempre
// percorrer da esquerda para a direita.
Cadeia reverso(const Cadeia& cadeia);
// Potência de uma cadeia: ela repetida `expoente` vezes. A potência zero é a
// cadeia vazia — mesma convenção da potência de linguagem, e pela mesma razão.
Cadeia potenciaDaCadeia(const Cadeia& cadeia, std::size_t expoente);
bool ePrefixo(const Cadeia& candidata, const Cadeia& cadeia);
bool eSufixo(const Cadeia& candidata, const Cadeia& cadeia);
// --- Degrau 2: o universo em que a linguagem vive ---------------------------
// Todas as cadeias de comprimento exato sobre um alfabeto — o Σ^n da definição.
// É a operação que torna visível o que "linguagem é subconjunto" significa: o
// conjunto devolvido aqui tem |Σ|^n elementos, e a linguagem é alguma parte dele.
Linguagem cadeiasDeComprimento(const Alfabeto& alfabeto, std::size_t tamanho);
// --- Degrau 3: operações sobre linguagens -----------------------------------
// O alfabeto de uma linguagem é o conjunto dos símbolos que ocorrem nas suas cadeias.
Alfabeto alfabetoDe(const Linguagem& linguagem);
// União: pertence ao resultado a cadeia que pertence a pelo menos uma das duas.
Linguagem uniao(const Linguagem& esquerda, const Linguagem& direita);
// Concatenação: toda cadeia de `esquerda` seguida de toda cadeia de `direita`.
// O tamanho do resultado é o produto dos tamanhos, e essa multiplicação é a razão
// pela qual a representação por conjunto não escala.
Linguagem concatenacao(const Linguagem& esquerda, const Linguagem& direita);
// Potência: a linguagem concatenada com ela mesma `expoente` vezes.
// Por definição, a potência zero é a linguagem que contém apenas a cadeia vazia —
// e não a linguagem vazia. Confundir as duas é o erro mais comum deste capítulo.
Linguagem potencia(const Linguagem& linguagem, std::size_t expoente);
// Fecho de Kleene: a união de todas as potências, da zero em diante.
// O fecho é infinito sempre que a linguagem tem alguma cadeia não vazia, então
// aqui ele é truncado por comprimento máximo. O truncamento é da implementação,
// não da definição: é o preço de materializar o conjunto.
Linguagem fechoDeKleene(const Linguagem& linguagem, std::size_t comprimentoMaximo);
bool contem(const Linguagem& linguagem, const Cadeia& cadeia);
// Formatação em notação de conjunto, com a cadeia vazia grafada como ε.
Cadeia formatar(const Linguagem& linguagem);
Cadeia formatar(const Alfabeto& alfabeto);
} // namespace peneira
#endif // PENEIRA_01_LINGUAGEM_H
01_linguagem.cpp
#include "01_linguagem.h"
namespace peneira {
// recorte:inicio operacoes-sobre-cadeias
std::size_t comprimento(const Cadeia& cadeia) {
return cadeia.size();
}
Cadeia concatenarCadeias(const Cadeia& esquerda, const Cadeia& direita) {
return esquerda + direita;
}
Cadeia reverso(const Cadeia& cadeia) {
return Cadeia(cadeia.rbegin(), cadeia.rend());
}
Cadeia potenciaDaCadeia(const Cadeia& cadeia, const std::size_t expoente) {
// A potência zero é a cadeia vazia, e não uma cadeia de um símbolo qualquer:
// repetir zero vezes é não repetir. Mesma convenção da potência de linguagem,
// e é ela que faz a cadeia vazia ser o elemento neutro da concatenação.
Cadeia resultado;
for (std::size_t i = 0; i < expoente; ++i) {
resultado += cadeia;
}
return resultado;
}
// recorte:fim operacoes-sobre-cadeias
bool ePrefixo(const Cadeia& candidata, const Cadeia& cadeia) {
return candidata.size() <= cadeia.size() &&
cadeia.compare(0, candidata.size(), candidata) == 0;
}
bool eSufixo(const Cadeia& candidata, const Cadeia& cadeia) {
return candidata.size() <= cadeia.size() &&
cadeia.compare(cadeia.size() - candidata.size(), candidata.size(), candidata) == 0;
}
// recorte:inicio universo-das-cadeias
Linguagem cadeiasDeComprimento(const Alfabeto& alfabeto, const std::size_t tamanho) {
// Começa do conjunto que contém só a cadeia vazia e estende um símbolo por
// vez. O resultado tem |alfabeto| elevado a `tamanho` elementos — a contagem
// que torna concreta a frase "uma linguagem é um subconjunto de Σ*": este é
// um andar do universo, e a linguagem é alguma parte dele.
Linguagem resultado{Cadeia{}};
for (std::size_t i = 0; i < tamanho; ++i) {
Linguagem proximoAndar;
for (const Cadeia& prefixo : resultado) {
for (const char simbolo : alfabeto) {
proximoAndar.insert(prefixo + simbolo);
}
}
resultado = proximoAndar;
}
return resultado;
}
// recorte:fim universo-das-cadeias
// recorte:inicio alfabeto-de-uma-linguagem
Alfabeto alfabetoDe(const Linguagem& linguagem) {
Alfabeto alfabeto;
for (const Cadeia& cadeia : linguagem) {
for (const char simbolo : cadeia) {
alfabeto.insert(simbolo);
}
}
return alfabeto;
}
// recorte:fim alfabeto-de-uma-linguagem
// recorte:inicio uniao-e-concatenacao
Linguagem uniao(const Linguagem& esquerda, const Linguagem& direita) {
Linguagem resultado = esquerda;
resultado.insert(direita.begin(), direita.end());
return resultado;
}
Linguagem concatenacao(const Linguagem& esquerda, const Linguagem& direita) {
Linguagem resultado;
for (const Cadeia& prefixo : esquerda) {
for (const Cadeia& sufixo : direita) {
resultado.insert(prefixo + sufixo);
}
}
return resultado;
}
// recorte:fim uniao-e-concatenacao
// recorte:inicio potencia-zero-e-cadeia-vazia
Linguagem potencia(const Linguagem& linguagem, const std::size_t expoente) {
// A potência zero contém a cadeia vazia. Devolver a linguagem vazia aqui
// quebraria o fecho de Kleene inteiro, porque a concatenação com o conjunto
// vazio aniquila o resultado em vez de preservá-lo.
Linguagem resultado{Cadeia{}};
for (std::size_t i = 0; i < expoente; ++i) {
resultado = concatenacao(resultado, linguagem);
}
return resultado;
}
// recorte:fim potencia-zero-e-cadeia-vazia
// recorte:inicio fecho-que-precisa-parar
Linguagem fechoDeKleene(const Linguagem& linguagem, const std::size_t comprimentoMaximo) {
Linguagem resultado{Cadeia{}};
Linguagem nivelAtual{Cadeia{}};
// Cresce por níveis em vez de calcular potência por potência: cada nível é o
// anterior concatenado uma vez com a linguagem, e paramos quando nenhuma
// cadeia nova cabe no comprimento máximo. Sem essa parada por comprimento o
// laço não termina, porque o fecho é infinito por definição.
while (!nivelAtual.empty()) {
Linguagem proximoNivel;
for (const Cadeia& cadeia : concatenacao(nivelAtual, linguagem)) {
if (cadeia.size() <= comprimentoMaximo) {
proximoNivel.insert(cadeia);
}
}
// A cadeia vazia reaparece a cada nível se a linguagem a contiver; o
// conjunto absorve a repetição, mas o nível precisa perder as já vistas,
// senão o laço nunca esvazia.
Linguagem novidades;
for (const Cadeia& cadeia : proximoNivel) {
if (resultado.find(cadeia) == resultado.end()) {
novidades.insert(cadeia);
}
}
resultado.insert(novidades.begin(), novidades.end());
nivelAtual = novidades;
}
return resultado;
}
// recorte:fim fecho-que-precisa-parar
bool contem(const Linguagem& linguagem, const Cadeia& cadeia) {
return linguagem.find(cadeia) != linguagem.end();
}
// recorte:inicio cadeia-vazia-impressa
Cadeia formatar(const Linguagem& linguagem) {
Cadeia texto = "{ ";
bool primeiro = true;
for (const Cadeia& cadeia : linguagem) {
if (!primeiro) {
texto += ", ";
}
// A cadeia vazia é invisível quando impressa como está, e o leitor
// conclui que o conjunto tem um elemento a menos do que tem.
texto += cadeia.empty() ? Cadeia{"\xce\xb5"} : cadeia;
primeiro = false;
}
texto += " }";
return texto;
}
// recorte:fim cadeia-vazia-impressa
Cadeia formatar(const Alfabeto& alfabeto) {
Cadeia texto = "{ ";
bool primeiro = true;
for (const char simbolo : alfabeto) {
if (!primeiro) {
texto += ", ";
}
texto += simbolo;
primeiro = false;
}
texto += " }";
return texto;
}
} // namespace peneira
O segundo par declara a arquitetura como dado. Comentário não roda, não se verifica e envelhece em silêncio; uma tabela impressa é comparada e corrigida junto com o código. A linha marcada na tabela de estratégias é a híbrida, e é ela que explica por que existe uma máquina virtual num percurso que se anuncia como de compiladores.
01_pipeline.h
// 01_pipeline.h — A anatomia do sistema: as fases, o que cada uma consome e produz.
//
// Nenhuma fase existe ainda como código; o que existe aqui é a declaração da
// cadeia inteira, como dado. Declará-la agora tem uma função concreta: cada
// capítulo seguinte substitui uma linha desta tabela por implementação real, e a
// tabela continua sendo a resposta às três perguntas que valem para qualquer
// etapa — o que entra, o que sai, e por que esta vem depois daquela.
#ifndef PENEIRA_01_PIPELINE_H
#define PENEIRA_01_PIPELINE_H
#include <string>
#include <vector>
namespace peneira {
// A divisão clássica: a metade que decompõe o texto de entrada e a metade que
// constrói o resultado. O artefato de fronteira entre as duas é a árvore
// verificada — é ela que a análise entrega e a síntese consome.
enum class Metade { Analise, Sintese };
struct Fase {
std::string nome;
std::string consome;
std::string produz;
Metade metade;
};
// A cadeia da Peneira, na ordem em que será construída ao longo do percurso.
std::vector<Fase> pipelineDaPeneira();
// Um nível da hierarquia de Chomsky e a máquina que lhe corresponde, com o ponto
// do artefato em que aquele nível comparece. As duas primeiras linhas são as que
// a Peneira realiza; as duas últimas existem para situar o que fica de fora.
struct NivelDeChomsky {
int tipo;
std::string gramatica;
std::string maquina;
std::string ondeApareceNaPeneira;
};
std::vector<NivelDeChomsky> hierarquiaDeChomsky();
// Uma forma intermediária é um artefato que nenhuma das duas pontas pede: não é o
// texto que o usuário escreveu nem o resultado que ele espera. Existe porque
// separa duas fases que, coladas, ficariam presas uma à outra. Declará-las aqui
// evita a leitura ingênua da cadeia como "texto entra, resultado sai".
struct FormaIntermediaria {
std::string nome;
std::string faseQueProduz;
std::string faseQueConsome;
std::string porQueNaoSeElimina;
};
std::vector<FormaIntermediaria> formasIntermediariasDaPeneira();
// Onde cada estratégia coloca a fronteira entre traduzir e executar. A distinção
// não é entre linguagens, e sim entre implementações: a mesma linguagem admite as
// três. A Peneira é híbrida, e a linha marcada é a dela.
struct EstrategiaDeExecucao {
std::string nome;
std::string quandoATraducaoAcontece;
std::string oQueDeFatoExecuta;
std::string exemploConhecido;
bool eAEstrategiaDaPeneira;
};
std::vector<EstrategiaDeExecucao> estrategiasDeExecucao();
std::string formatarPipeline(const std::vector<Fase>& fases);
std::string formatarHierarquia(const std::vector<NivelDeChomsky>& niveis);
std::string formatarFormasIntermediarias(const std::vector<FormaIntermediaria>& formas);
std::string formatarEstrategias(const std::vector<EstrategiaDeExecucao>& estrategias);
} // namespace peneira
#endif // PENEIRA_01_PIPELINE_H
01_pipeline.cpp
#include "01_pipeline.h"
#include <cstddef>
namespace peneira {
// recorte:inicio pipeline-do-tradutor
std::vector<Fase> pipelineDaPeneira() {
return {
{"analise lexica", "texto do programa .pen", "sequencia de simbolos com posicao",
Metade::Analise},
{"analise sintatica", "sequencia de simbolos", "arvore da estrutura do programa",
Metade::Analise},
{"analise semantica", "arvore da estrutura", "arvore verificada e tabela de simbolos",
Metade::Analise},
{"geracao de codigo", "arvore verificada", "objeto: vetor de AFDs + bytecode das regras",
Metade::Sintese},
{"execucao na maquina virtual", "objeto + texto de entrada", "saida do emit",
Metade::Sintese},
};
}
// recorte:fim pipeline-do-tradutor
// recorte:inicio hierarquia-de-chomsky
std::vector<NivelDeChomsky> hierarquiaDeChomsky() {
return {
{3, "regular", "automato finito",
"os patterns do usuario e os simbolos da propria linguagem"},
{2, "livre de contexto", "automato de pilha",
"a gramatica da Peneira e o analisador descendente"},
{1, "sensivel ao contexto", "automato linearmente limitado",
"fora do artefato: nenhuma fase precisa deste poder"},
{0, "irrestrita", "maquina de Turing",
"fora do artefato: e o poder do compilador, nao o da linguagem compilada"},
};
}
// recorte:fim hierarquia-de-chomsky
// recorte:inicio formas-intermediarias
std::vector<FormaIntermediaria> formasIntermediariasDaPeneira() {
return {
{"sequencia de simbolos", "analise lexica", "analise sintatica",
"sem ela o parser voltaria a olhar caractere, e espaco e comentario reapareceriam"},
{"arvore da estrutura", "analise sintatica", "analise semantica",
"sem ela o verificador teria de redescobrir a estrutura a cada checagem"},
{"tabela de simbolos", "analise semantica", "geracao de codigo",
"guarda o que o nome significa longe do ponto do texto em que ele aparece"},
{"arvore verificada", "analise semantica", "geracao de codigo",
"e o artefato de fronteira: a analise entrega, a sintese consome"},
{"objeto: AFDs + bytecode", "geracao de codigo", "maquina virtual",
"separa compilar de executar: compila-se uma vez, executa-se sobre muitas entradas"},
};
}
// recorte:fim formas-intermediarias
// recorte:inicio estrategias-de-execucao
std::vector<EstrategiaDeExecucao> estrategiasDeExecucao() {
return {
{"compilacao", "antes da execucao, uma vez", "o codigo de maquina gerado",
"C traduzido para codigo nativo", false},
{"interpretacao", "nao ha traducao: a estrutura e percorrida a cada execucao",
"o interpretador, sobre a arvore ou o texto", "shell POSIX, comando a comando", false},
{"hibrida", "antes da execucao, para uma representacao intermediaria",
"uma maquina virtual, sobre o bytecode", "Java compilado para bytecode da JVM", true},
};
}
// recorte:fim estrategias-de-execucao
namespace {
// Alinha a coluna para que a tabela impressa fique legível na projeção. Sem isso
// o leitor precisa contar vírgulas para saber qual campo é qual.
std::string preencher(const std::string& texto, const std::size_t largura) {
std::string resultado = texto;
while (resultado.size() < largura) {
resultado += ' ';
}
return resultado;
}
std::string nomeDaMetade(const Metade metade) {
return metade == Metade::Analise ? "analise" : "sintese";
}
} // namespace
std::string formatarPipeline(const std::vector<Fase>& fases) {
std::string texto;
texto += preencher("FASE", 30) + preencher("CONSOME", 28) + preencher("PRODUZ", 44) + "METADE\n";
for (const Fase& fase : fases) {
texto += preencher(fase.nome, 30);
texto += preencher(fase.consome, 28);
texto += preencher(fase.produz, 44);
texto += nomeDaMetade(fase.metade);
texto += '\n';
}
return texto;
}
std::string formatarHierarquia(const std::vector<NivelDeChomsky>& niveis) {
std::string texto;
texto += preencher("TIPO", 6) + preencher("GRAMATICA", 22) + preencher("MAQUINA", 32) +
"ONDE APARECE\n";
for (const NivelDeChomsky& nivel : niveis) {
texto += preencher(std::to_string(nivel.tipo), 6);
texto += preencher(nivel.gramatica, 22);
texto += preencher(nivel.maquina, 32);
texto += nivel.ondeApareceNaPeneira;
texto += '\n';
}
return texto;
}
std::string formatarFormasIntermediarias(const std::vector<FormaIntermediaria>& formas) {
std::string texto;
texto += preencher("FORMA", 26) + preencher("PRODUZIDA POR", 22) + preencher("CONSUMIDA POR", 24) +
"POR QUE NAO SE ELIMINA\n";
for (const FormaIntermediaria& forma : formas) {
texto += preencher(forma.nome, 26);
texto += preencher(forma.faseQueProduz, 22);
texto += preencher(forma.faseQueConsome, 24);
texto += forma.porQueNaoSeElimina;
texto += '\n';
}
return texto;
}
std::string formatarEstrategias(const std::vector<EstrategiaDeExecucao>& estrategias) {
std::string texto;
texto += preencher("ESTRATEGIA", 16) + preencher("QUANDO TRADUZ", 60) +
preencher("QUEM EXECUTA", 44) + "EXEMPLO\n";
for (const EstrategiaDeExecucao& estrategia : estrategias) {
// A marca na coluna do nome poupa uma legenda: quem le a tabela ve, sem
// procurar no texto, qual das tres linhas descreve o artefato desta obra.
texto += preencher(estrategia.eAEstrategiaDaPeneira ? "> " + estrategia.nome : " " + estrategia.nome, 16);
texto += preencher(estrategia.quandoATraducaoAcontece, 60);
texto += preencher(estrategia.oQueDeFatoExecuta, 44);
texto += estrategia.exemploConhecido;
texto += '\n';
}
return texto;
}
} // namespace peneira
O ponto de entrada deste marco é próprio dele e não será reescrito por nenhum capítulo adiante. O arquivo de build lista apenas os fontes existentes até aqui, declara o padrão da linguagem uma vez e aplica as flags de rigor conforme o compilador disponível. Reconstruir do zero e rodar a demonstração é um comando só.
marcos/01/CMakeLists.txt
# Modelo do arquivo de build de um marco da Peneira.
#
# ESCRITO UMA VEZ, para a linguagem. Quem o preenche por marco e
# tools/gerar_marcos.exe (specs/marcos-executaveis.md). Os arquivos gerados a
# partir dele — marcos/NN/CMakeLists.txt — NAO se editam a mao: a edicao some na
# proxima geracao, e a lista de fontes deixa de corresponder ao marco.
#
# CUIDADO AO EDITAR ESTE MODELO: a substituicao dos marcadores alcanca o arquivo
# INTEIRO, comentario incluido. Citar um marcador aqui em cima, para explicar o
# que ele faz, injeta a lista de fontes dentro do comentario e quebra o parser —
# aconteceu na primeira versao deste arquivo.
cmake_minimum_required(VERSION 3.10.0)
project(peneira01 VERSION 0.1.0 LANGUAGES CXX)
# O padrao e declarado uma vez, aqui, e nao repetido por compilador.
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)
# Os fontes deste marco: os modulos 01 a 01, e mais nada. A lista e derivada,
# nunca escrita — e o que impede o capitulo 01 de exibir uma peca que so vai
# existir adiante.
add_executable(peneira01
../../01_linguagem.cpp
../../01_pipeline.cpp
../../demos/01_demo.cpp
)
# Aviso e erro. Incomoda no primeiro dia e economiza semanas depois — num programa
# que manipula indices de tabela o tempo inteiro, um aviso de conversao implicita
# ignorado e um defeito adiado, nao um defeito evitado.
if(MSVC)
target_compile_options(peneira01 PRIVATE /W4 /WX /permissive- /utf-8 /EHsc)
else()
target_compile_options(peneira01 PRIVATE -Wall -Wextra -Wpedantic -Werror)
endif()
include(CTest)
enable_testing()
# A demonstracao deste marco roda como teste, e o diretorio de trabalho e a raiz
# da variante: os arcos que leem descricoes de `exemplos/` dependem disso, e sem
# ele reprovariam por nao achar o arquivo — falha por motivo que nada tem a ver
# com o que a demonstracao mede.
add_test(NAME demo_01 COMMAND peneira01)
set_tests_properties(demo_01 PROPERTIES
WORKING_DIRECTORY "${CMAKE_CURRENT_SOURCE_DIR}/../..")
Três decisões dentro do arquivo de build merecem justificativa. Desligar as extensões do compilador, porque com elas ligadas o código deixa de ser portável sem que ninguém perceba — continua compilando na máquina de quem o escreveu. Aplicar dois conjuntos de flags de aviso conforme o compilador, porque código que passa limpo em apenas um dos três previstos não cumpre a exigência de tipagem estrita, e descobrir isso na máquina de outra pessoa é a pior hora possível. E registrar a demonstração como teste, para que uma regressão futura acuse no capítulo em que ela entrou, e não três capítulos depois.
1.8.3 A primeira especificação, escrita à mão
O recorte da linguagem foi registrado como documento de decisão, com a alternativa descartada ao lado de cada escolha. O item mais consequente dele é uma recusa: a Peneira não aceita retrovisores. Retrovisor sai da classe das linguagens regulares, e um padrão que o usasse não poderia ser compilado para autômato finito — o que derrubaria a demonstração central de todo o percurso.
docs/01_recorte.md
# O recorte da Peneira — decisões fixadas no primeiro módulo
Registro das três decisões que a Tarefa 1 pede, na forma em que ficarão travadas para todo o
percurso. Cada uma vem acompanhada da alternativa descartada, porque é a comparação que torna a
decisão compreensível quando ela precisar ser revisitada.
## Que classe de padrões o sistema aceita
**Decisão:** expressões regulares com concatenação, alternância (`|`), fecho (`*`), fecho positivo
(`+`), opcional (`?`), classe de caracteres (`[...]`), coringa (`.`) e agrupamento por parênteses.
**Núcleo mínimo:** concatenação, alternância e fecho. Os outros três são conveniência de escrita e
serão **reduzidos ao núcleo** antes de qualquer processamento — `a+` vira `aa*`, `a?` vira `(a|ε)`,
e uma classe `[abc]` vira `(a|b|c)`. A redução acontece uma única vez, logo depois da leitura, e
tudo o que vem depois trabalha só com três operadores.
**Descartado:** grupos de captura e retrovisores (*backreferences*). Não é economia de esforço — é
teoria: retrovisor sai da classe das linguagens regulares, e um sistema que o aceitasse não poderia
ser compilado para autômato finito. A decisão de recusá-lo é o que mantém o artefato coerente com o
que a obra demonstra.
## Que forma tem a descrição escrita pelo usuário
**Decisão:** um programa é uma sequência de declarações `pattern` seguida de um bloco `rule`. Cada
`pattern` associa um nome a uma expressão regular; cada ação dentro de `rule` reage ao casamento de
um `pattern` nomeado, opcionalmente condicionada por um `where`, e produz saída por `emit`.
A gramática completa está em `docs/01_gramatica.txt`, e o exemplo canônico em
`exemplos/exemplo01.pen`.
**Descartado:** sintaxe sem nomes, em que a expressão apareceria direto na ação. Nomear o padrão
custa uma declaração a mais e paga em três lugares: a tabela de símbolos passa a ter o que registrar,
a verificação semântica passa a ter o que checar (`on x` com `x` inexistente), e a mesma expressão
pode ser reusada em mais de uma ação sem ser recompilada.
## O que o sistema produz
**Decisão:** o objeto gerado tem duas partes — um vetor de autômatos finitos determinísticos, um por
`pattern`, na forma de tabelas de transição; e, para cada `rule`, um bytecode de máquina de pilha que
avalia o `where` e executa o `emit`. Uma máquina virtual própria varre a entrada, aplica os autômatos
com desempate por casamento mais longo e executa o bytecode.
**Descartado:** interpretar a árvore diretamente, sem emitir objeto. Seria mais curto e apagaria a
etapa que a obra existe para demonstrar: é na emissão que o autômato deixa de ser estrutura interna
do reconhecedor e vira **o próprio código-alvo**, que é o que faz a teoria de autômatos aparecer
duas vezes no artefato.
## Conferência do recorte, item a item
A segunda metade da tarefa é confrontar as três decisões acima com as propriedades que o percurso
inteiro vai cobrar. Registramos a conferência aqui, e não na cabeça de quem decidiu, porque a
propriedade que falta só se manifesta no módulo que dependia dela — e aí o conserto alcança tudo o
que já foi construído em cima.
| Propriedade cobrada | Onde o recorte a satisfaz | Módulo que a cobra |
| --- | --- | --- |
| O usuário escreve padrões | `pattern nome = /regex/;` é declaração de primeira classe da linguagem | expressões regulares |
| Os símbolos da própria linguagem saem do mesmo motor | o reconhecedor da Peneira é construído sobre o mesmo módulo de AFD que compila os `pattern` | análise léxica |
| A gramática tem aninhamento arbitrariamente profundo | `expr` desce a `primary`, que volta a `"(" expr ")"` — recursão sem teto de profundidade | gramáticas livres de contexto |
| Há tipos e verificação antes da execução | `where` compara número com número e texto com texto; `on x` exige `x` declarado antes | análise semântica |
| Existe objeto produzido, consumido por outro componente | o vetor de AFDs mais o bytecode são gravados e lidos por uma máquina virtual que não é o compilador | geração de código e execução |
| O domínio pede algo que a máquina finita não atende | um `pattern` de parênteses balanceados é escrevível e nenhum AFD o reconhece | lema do bombeamento |
A última linha é a que costuma faltar num recorte feito às pressas, e é a mais consequente. Sem um
pedido do domínio que o autômato finito não atenda, a subida do reconhecimento regular para o
reconhecimento com pilha vira mudança de assunto em vez de resposta a um limite provado — e o
argumento de impossibilidade, quando chegar, será sobre um exemplo de fora, não sobre a linguagem
que se está construindo.
A gramática foi registrada na forma de partida, com recursão à esquerda e sem fatoração. Preservá-la assim é decisão, e não descuido: no capítulo sobre gramáticas livres de contexto, a forma anterior aparece ao lado da final, e essa comparação é a explicação mais eficiente que existe sobre por que a transformação é necessária.
docs/01_gramatica.txt
A gramatica da Peneira, escrita por extenso no primeiro modulo.
Esta e a forma de partida: ainda tem recursao a esquerda e ainda nao esta fatorada.
O modulo de gramaticas livres de contexto retoma este arquivo e registra cada
transformacao com a forma anterior ao lado da forma final.
--- Gramatica hospedeira (a linguagem que o usuario escreve) ---
program := decl* ;
decl := patternDecl | ruleBlock ;
patternDecl := "pattern" ID "=" REGEX ";" ;
ruleBlock := "rule" "{" action* "}" ;
action := "on" ID "(" ID ")" ( "where" expr )? "=>" "emit" "(" STRING "," expr ")" ";" ;
expr := andExpr ( "or" andExpr )* ;
andExpr := cmpExpr ( "and" cmpExpr )* ;
cmpExpr := primary ( ("<"|">"|"=="|"!="|">="|"<=") primary )? ;
primary := ID | NUMBER | STRING | "value" "(" ID ")" | "(" expr ")" ;
--- Mini-linguagem regular (o alvo dos automatos) ---
regex := alt ;
alt := concat ( "|" concat )* ;
concat := repeat+ ;
repeat := atom ( "*" | "+" | "?" )? ;
atom := CHAR | "." | "[" classe "]" | "(" alt ")" ;
--- Onde cada nivel da hierarquia de Chomsky comparece ---
A gramatica hospedeira e livre de contexto (tipo 2): as producoes aninhadas de
expr/andExpr/cmpExpr/primary exigem memoria de pilha, e nenhum automato finito as
reconhece. A mini-linguagem regular tambem e descrita por uma gramatica livre de
contexto — porque a NOTACAO de expressao regular tem parenteses aninhados —, mas a
LINGUAGEM que cada expressao denota e regular (tipo 3). Confundir as duas coisas e
o erro mais frequente deste ponto do percurso: o que e regular e o conjunto de
cadeias descrito pela expressao, nao o texto da expressao.
Por fim, o exemplo escrito à mão, com dois padrões e uma regra sobre cada um. Um dos padrões exercita concatenação, classe de caracteres e fecho positivo. O outro acrescenta o opcional, o agrupamento e o aninhamento de um sobre o outro — que é justamente o caso em que a redução ao núcleo mínimo deixa de ser óbvia. A regra condicionada obriga a tabela de nomes, a verificação de tipo e o objeto emitido a existirem.
exemplos/exemplo01.pen
// exemplo01.pen — o primeiro programa valido da Peneira, escrito a mao.
//
// Este arquivo nao e lido por nenhum programa ainda: o reconhecedor de simbolos
// so existe a partir do capitulo de analise lexica. Ele e a especificacao pelo
// exemplo — o alvo contra o qual cada fase construida adiante sera verificada.
//
// Resultado esperado sobre a entrada de teste (exemplos/entrada01.txt):
// contato ana.silva@exemplo.com
// grande 1500
// A linha "contato" sai porque o texto casa o pattern email; a linha "grande"
// sai porque casa numero E satisfaz a condicao value(n) > 100.
// Dois numeros da entrada casam o pattern e NAO produzem saida: 42 falha por
// magnitude e -240.75 falha por sinal — o sinal entra no casamento, entao o
// valor comparado e negativo. Sao esses dois casos negativos que provam que o
// where esta sendo avaliado, e nao apenas o casamento.
pattern email = /[a-z0-9._]+@[a-z]+\.[a-z]+/;
pattern numero = /-?[0-9]+(\.[0-9]+)?/;
rule {
on email(e) => emit("contato", e);
on numero(n) where value(n) > 100 => emit("grande", n);
}
O resultado esperado é a outra metade do exemplo. Sobre a entrada de teste, o sistema deve emitir duas linhas. Os casos mais valiosos são os dois números que casam o padrão e não produzem saída: um falha por magnitude, e o outro falha por sinal, já que o sinal entra no casamento e o valor comparado é negativo. Um sistema que emitisse quatro linhas estaria casando os padrões corretamente e ignorando a condição — falha que os casos positivos sozinhos jamais revelariam.
1.8.4 A descrição finita que ainda falta escrever
O sistema deste ponto do percurso guarda linguagens como listas de cadeias, e essa representação morre no capítulo seguinte. Ela morre por onde este capítulo já apontou: o fecho de Kleene é infinito, e a lista precisou de um teto de comprimento que a definição não pede.
O que entra no lugar é a notação que quem usa a Peneira escreve entre barras, na declaração de um pattern. Uma linha dessas descreve um conjunto infinito de textos em vinte caracteres, e é dela que sai, por conversão mecânica, o autômato que decide sobre cada entrada. Duas coisas mudam de uma vez. A linguagem deixa de ser materializada e passa a ser decidida sob demanda. E o objeto que o compilador produz deixa de ser uma tabela de resultados e passa a ser uma máquina.
Antes de virar a página, faça uma coisa com o seu próprio recorte. Escreva à mão, em português mesmo, o padrão mais longo que a sua linguagem vai precisar aceitar. Conte quantos caracteres ele teria se você o escrevesse numa notação compacta, e quantas cadeias distintas ele descreve. O segundo número não fecha — é infinito, ou grande demais para contar —, e é justamente por não fechar que a notação existe.
O que segue é o que cabe a você construir com o vocabulário desta primeira etapa. Nada aqui pede uma linha de código, e é por isso mesmo que costuma ser subestimado.
Tarefa 1: Fixar o recorte da linguagem
Decida sobre que domínio os padrões da sua linguagem vão falar, que classe de padrões o seu sistema aceitará, que forma terá a descrição escrita por quem o usa e o que ele produzirá ao processá-la. É um texto curto e consequente: tudo o que vem nos capítulos seguintes responde a ele, e cada ambiguidade deixada aqui reaparece adiante como retrabalho, quando já existe código apoiado sobre a decisão que faltou.
Confira o recorte, item a item, contra as propriedades que o capítulo do projeto enumera — o usuário escrevendo padrões, os símbolos da própria linguagem saindo do mesmo motor, o aninhamento na gramática, os tipos e o escopo, o objeto produzido e o pedido do domínio que a máquina finita não atende. A conferência custa dez minutos aqui; a propriedade que faltar só se manifesta no capítulo que dependia dela, e aí o conserto alcança tudo o que já foi construído em cima.
A tentação natural é começar largo e restringir depois. O caminho barato é o inverso: comece pelo menor recorte que ainda seja interessante de processar e amplie quando a peça correspondente estiver funcionando. Um recorte generoso escrito no primeiro capítulo não acelera nada — apenas transfere para o meio do percurso a decisão de abandoná-lo. Note que essa economia vale para o tamanho do recorte, não para as propriedades acima: cortar operadores é barato e reversível; descobrir tarde que o domínio escolhido não sustenta uma delas, não.
Tarefa 2: Escrever à mão um exemplo válido
Escreva, sem apoio de nenhum programa, um exemplo de descrição válida no recorte que acabou de fixar, e registre ao lado dele o que se espera que o sistema faça ao recebê-lo. Este par — entrada e resultado pretendido — é o primeiro caso de verificação do percurso, e continuará sendo usado muito depois de existirem centenas de outros: é ele que o analisador de símbolos precisará reconhecer por inteiro, que a gramática precisará derivar e que o sistema completo precisará processar do começo ao fim.
Tarefa 3: Criar o repositório de trabalho
Monte o repositório com as três partes que sustentam um sistema construído por acumulação: a apresentação, que diz o que o sistema faz e como se compila e executa; a documentação, que guarda a especificação da linguagem, o registro das decisões técnicas e o diário da construção; e o código, organizado por responsabilidade. Deixe o comando único que reconstrói tudo e roda os casos existentes funcionando desde já, ainda que haja pouquíssimo a compilar — ele é a única defesa contra a regressão silenciosa numa peça considerada pronta, e instalá-lo depois custa mais do que parece.
Esta etapa se conclui sem uma linha de código escrita, e é essa a razão pela qual costuma ser subestimada. O que ela produz são decisões: o recorte, o exemplo e o lugar onde o sistema vai crescer.