%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
A["total = preco * quantidade<br/>26 caracteres num arquivo"]
B["leitor que conta<br/>26 caracteres, 5 palavras, 3 letras a"]
C["leitor que traduz<br/>preco existe? guarda número?<br/>a multiplicação está definida?"]
D["resposta sem sair do arquivo"]
E["resposta que depende de um modelo<br/>construído a partir do próprio texto"]
A --> B
A --> C
B --> D
C --> E
1 Linguagens formais e a arquitetura de um compilador
Um mesmo arquivo, dois programas: o primeiro conta os bytes, o segundo obedece a eles.
Este é o capítulo em que o vocabulário aparece antes das máquinas. Nada aqui exige código escrito; tudo aqui é cobrado nos próximos onze. Leia com papel ao lado: metade das contas deste texto se confere à mão em dois minutos.
Em 1952, num encontro da ACM, Grace Hopper apresentou um trabalho de título modesto: The Education of a Computer. O objeto descrito ali era o A-0. Rodava num UNIVAC I e montava outro programa a partir de rotinas gravadas em fita. Hopper usou a palavra compilador na acepção de quem compila uma antologia — junta pedaços prontos e costura um volume. O nome pegou. A descrição do ofício, não.
O A-0 não analisava nada. Colava trechos já escritos, na ordem pedida. Entregava a costura pronta para rodar. Nenhum passo perguntava se a entrada fazia sentido, conferia tipo ou recusava coisa alguma. Um tradutor de hoje passa quase todo o tempo fazendo exatamente essas três coisas, e a colagem virou o último de vários passos.
O que sobreviveu foi a ideia por baixo do nome, e ela é mais estranha do que o nome deixa ver. O texto que uma pessoa escreve pode ser tratado como dado por outro programa. Um arquivo com x = 3 * y é uma sequência de nove caracteres tão dócil quanto uma lista de compras. Dá para contá-los, ordená-los, comprimi-los. E dá, em vez disso, para tomar os mesmos nove caracteres como uma ordem e obedecê-los. Entre uma coisa e a outra existe um abismo. Atravessá-lo exige duas construções: um vocabulário que descreva conjuntos infinitos de textos sem escrever nenhum deles, e uma arquitetura que reparta o caminho em pedaços verificáveis.
1.1 O arquivo não sabe que é um programa
Você já escreveu um programa que lê outro programa? Provavelmente já, e provavelmente contando linhas.
Pergunte o que há dentro de um arquivo de texto e você ouve: texto. Pergunte o que há dentro de um arquivo de código-fonte e a resposta muda de natureza, embora o arquivo seja do mesmo tipo. O disco — que é quem guarda os dois, byte a byte — não sabe de nada. Quem decide o que eles são é o programa que os abre. Tome uma linha escrita em qualquer linguagem que use atribuição:
Um programa que conte caracteres devolve 26. Um que conte palavras separadas por espaço devolve cinco. Um que procure a letra a acha três ocorrências, nas posições 4, 9 e 22. Nenhum deles precisa saber o que é uma atribuição, nem se preco foi declarado em algum lugar. Para eles a linha é uma sequência de símbolos, e a única estrutura que importa é a ordem.
Agora troque o leitor. Um tradutor abre a mesma linha e pergunta outra coisa. Existe uma variável chamada preco? Ela guarda um número ou um texto? A multiplicação está definida entre os tipos das duas coisas à direita? Nenhuma dessas perguntas se responde olhando os 26 caracteres. Todas dependem de um modelo do que a sequência significa, e esse modelo tem de ser construído a partir da própria sequência — porque não há mais nada no arquivo.
É aqui que mora a assimetria que organiza o assunto inteiro. Contar caracteres é operação sobre a cadeia. Decidir se a linha é um programa válido é operação sobre a linguagem a que ela pertenceria. Esse objeto não está no arquivo, ninguém o escreveu por extenso, e ele é infinito. O arquivo é o dado; a linguagem é a regra que separa os aceitos dos recusados. Um tradutor é uma máquina que carrega essa regra por dentro.
A travessia parece que devia ser direta — leia da esquerda para a direita e no fim você entendeu. Experimente com dois caracteres. Leia 3x, um símbolo por vez. No 3, uma decisão já foi tomada: começou um número, porque dígitos iniciam números em praticamente toda linguagem. Aí chega o x. Números não têm letra no meio, identificadores não começam com dígito, e a decisão do caractere anterior acabou de ser invalidada pelo seguinte. Não há como voltar no tempo. Há como voltar na posição da leitura, desfazer o que foi montado e tentar outra hipótese.
É por isso que ler um programa nunca é uma passada só.
Pergunta para levar adiante. Se o tradutor conseguisse adivinhar o que você quis dizer, isso seria uma vantagem? Guarde a sua resposta e compare com o parágrafo seguinte — ele mostra o estrago da gentileza.
Acontece que a gentileza produz um estrago silencioso. Suponha um tradutor que, diante de 3x, resolvesse consertar em silêncio. Ele tem duas emendas plausíveis: você inverteu dois caracteres e queria x3, ou esqueceu o asterisco de 3 * x. As duas produzem programas válidos. As duas produzem programas diferentes. Se ele escolher a primeira e você quisesse a segunda, o programa passa a ler uma variável chamada x3. Ela talvez exista, e talvez guarde algo importante de outra parte do código. Nada quebra. Nada avisa.
O resultado sai errado toda vez, com a mesma confiança de um resultado certo.
Repare no que o tradutor sabe e no que não sabe. Ele sabe que 3x não pertence à linguagem. Não sabe o que você queria escrever. Daí a escolha que atravessa a área inteira: ele recusa e diz onde. Preto no branco. Isso obriga a projetar a linguagem por inteiro antes da primeira linha de código. Toda construção aceita precisa estar prevista, e toda recusada precisa cair fora por uma razão escrita no critério. “Parece um engano” não serve de razão, já que a máquina não tem como saber o que parece.
Em 1957, a equipe de John Backus entregou na IBM o compilador de FORTRAN, num clima que o próprio Backus registrou em The History of FORTRAN I, II, and III, publicado pela ACM SIGPLAN em 1978. A suspeita então generalizada era de que código gerado por máquina sairia lento demais para ser levado a sério. Otimizar entrou como condição de aceitação do projeto inteiro. Um tradutor só é aceito quando o código que ele escreve aguenta comparação com o que a pessoa escreveria à mão.
A frase parece exigência de qualidade e é exigência de estrutura. Escolher bem entre duas formas de traduzir um trecho exige saber coisas que só aparecem depois de ler o programa inteiro. Quais variáveis voltam a ser usadas adiante. Quais laços rodam muitas vezes. Quais valores nunca mudam. Uma leitura única decidiria sem nada disso. A tradução se parte em passagens sucessivas. É isso que permite adiar cada decisão até haver informação para tomá-la.
Cinco anos separam a apresentação de Hopper da entrega de Backus. A distância entre as duas soluções é a distância entre colar pedaços prontos e analisar um texto. Qual delas merece o rótulo de primeiro compilador da história fica aqui sem resposta: depende da definição de compilador que se adote, e as duas atribuições são disputadas. De 1957 fica também um método. Julgamento sobre otimização se faz com número, e quem se anuncia rápido sem apresentar a medida está pedindo crédito.
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 estas páginas usam 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 Vinte rodinhas, duas letras e um milhão de senhas
Grave só duas letras, a e b, em cada uma das vinte rodinhas de um cadeado de segredo. O número de senhas que ele passa a aceitar é 2^{20}, ou seja, 1.048.576. Cem vezes mais combinações do que o cartão de banco com senha de quatro dígitos que você carrega no bolso — e você trabalhou com um repertório de duas letras.
Duas letras. Um milhão de senhas. Veja só o tamanho da desproporção.
A desproporção é o motor do assunto. Um conjunto pequeno e fechado de símbolos, combinado livremente, produz mais textos do que qualquer lista alcança. É para descrever essas quantidades sem enumerá-las que serve o vocabulário a seguir.
1.2.1 O repertório fechado, e as duas exigências que passam batido
A primeira decisão de qualquer projeto de linguagem é qual é o repertório de símbolos permitidos, e ela tem duas propriedades que parecem burocráticas e não são. O repertório é finito. Uma máquina precisa olhar um símbolo e dizer se ele está dentro ou fora. E é decidido antes de a primeira cadeia existir, porque toda operação seguinte o pressupõe fixado.
NotaDefinição — Alfabeto e cadeia
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|.
Sobre \Sigma = \{a, b\}, abba é cadeia de comprimento 4, a tem comprimento 1, e abc não é cadeia nenhuma — o c nunca entrou no repertório. Repare no que a definição não exige: os símbolos não precisam ser letras, nem legíveis, nem ter relação entre si. Um alfabeto de quatro símbolos pode ser o conjunto das quatro leituras que um sensor produz por ciclo. A teoria olha para quantos existem e para o fato de o conjunto ser fechado, nunca para o que cada um significa.
Duas exigências passam despercebidas: que \Sigma seja não vazio, e que o comprimento admita zero — o que garante a existência de uma cadeia sem símbolo nenhum. A segunda volta com força. E num sistema real o alfabeto costuma ser derivado, não declarado: dada uma coleção de cadeias, o alfabeto que basta para escrevê-las é a união dos símbolos que aparecem nelas.
01_linguagem.cpp
DicaNo código
Nove linhas, dois laços encaixados, e o resultado é um conjunto — o alfabeto, sem repetição e sem ordem de importância. Duas cadeias que usem as mesmas letras em ordens diferentes produzem o mesmo alfabeto.
Sobre cadeias há poucas operações, e o percurso usa duas. Medir o comprimento devolve um número natural. Emendar w com v, o que se escreve wv e se chama concatenação, devolve uma cadeia — não um par, não uma lista de duas, e sim uma terceira cadeia. Com w = \texttt{aab} e v = \texttt{ba} sai aabba, de comprimento 5, e |wv| = |w| + |v| em qualquer caso. A operação é associativa e não é comutativa: aabba e baaab são distintas.
01_linguagem.cpp
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;
}
DicaNo código
Quatro funções, e só a potência precisa de um laço. O acumulador dela nasce vazio, o que fixa w^0 = \varepsilon — a definição admitia qualquer convenção, e o código teve de escolher uma.
A potência de uma cadeia é a concatenação dela consigo mesma, repetida: w^3 é aabaabaab, de comprimento 9. O caso interessante é o expoente zero — repetir zero vezes é não repetir, então w^0 é a cadeia sem símbolo algum. Guarde a convenção. Um andar acima, sobre conjuntos, a mesma escolha decide se um algoritmo devolve resultado ou lixo. Falta a operação que mais aparece em código real: perguntar se uma cadeia é prefixo de outra. aa é prefixo de aab e não é sufixo dela. A pergunta parece pequena porque a resposta é fácil de calcular; é grande porque é a forma de uma máquina reconhecer texto sem ter lido a entrada toda.
1.2.2 A cadeia que existe e some na impressão
A definição admite n = 0, e essa permissão cria um objeto: a cadeia de comprimento zero, escrita \varepsilon. Ela pertence a todo alfabeto, porque não usa símbolo nenhum de nenhum deles, e é o elemento neutro da concatenação — \varepsilon w = w \varepsilon = w. Também é a fonte mais produtiva de defeito silencioso deste ponto do percurso. O problema aparece na hora de imprimir. Uma cadeia vazia sai como nada, e nada, dentro de um conjunto, desaparece. Mande imprimir a linguagem \{\varepsilon, a, aa\} sem tratamento e o que chega à tela é { , a, aa }. Quem lê conta dois elementos onde havia três, com toda a confiança do mundo.
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;
}
DicaNo código
O formatador resolve o caso numa linha: onde a cadeia é vazia, imprime-se o símbolo \varepsilon em lugar dela. É uma correção de cinco palavras que só se escreve depois de alguém ter contado errado uma vez.
A confusão irmã é mais séria e não se resolve com formatador nenhum. Existe o conjunto vazio, \emptyset, sem elemento algum, e existe o conjunto \{\varepsilon\}, com exatamente um elemento. Ponha as cardinalidades lado a lado: |\emptyset| = 0 e |\{\varepsilon\}| = 1. Um conjunto sem nada dentro, e um conjunto com uma coisa invisível dentro.
Fixado o alfabeto, o conjunto de todas as cadeias sobre ele tem nome próprio: \Sigma^*. É o universo em que toda linguagem sobre \Sigma vai morar, e é infinito assim que \Sigma tem ao menos um símbolo. Enumere por comprimento e a estrutura aparece sozinha: comprimento zero tem só \varepsilon; comprimento 1 tem a e b; comprimento 2 tem aa, ab, ba, bb; comprimento 3 tem oito. Cada andar tem 2^n elementos, os andares são finitos, e há infinitos andares.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
S["todas as cadeias sobre a, b"]
N0["comprimento 0<br/>a cadeia vazia<br/>1 cadeia"]
N1["comprimento 1<br/>a, b<br/>2 cadeias"]
N2["comprimento 2<br/>aa, ab, ba, bb<br/>4 cadeias"]
N3["comprimento 3<br/>8 cadeias"]
NN["e assim por diante,<br/>2 elevado a n por andar,<br/>sem último andar"]
S --> N0 --> N1 --> N2 --> N3 --> NN
01_linguagem.cpp
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;
}
DicaNo código
Um andar de cada vez, partindo do conjunto que contém só a cadeia vazia: é assim que o código sobe. Com o universo impresso na tela, a palavra subconjunto deixa de ser formalidade de enunciado.
A enumeração por andares tem uma leitura que não é óbvia. Como cada andar é finito, \Sigma^* pode ser enfileirado: primeiro \varepsilon, depois as de comprimento 1 em ordem alfabética, depois as de comprimento 2. Toda cadeia sobre \Sigma aparece nessa fila, em posição finita. Guarde a fila; ela volta.
1.3 Nenhuma lista alcança o que quatro regras alcançam
Uma linguagem é um conjunto — e a maior parte dos conjuntos não cabe em disco nenhum, por mais barato que ele fique.
1.3.1 A linguagem é o conjunto, e o conjunto não cabe em memória
Uma linguagem sobre \Sigma é um subconjunto de \Sigma^*. A definição cabe em oito palavras e é mais permissiva do que quase todo mundo espera na primeira leitura.
NotaDefinição — 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.
O menor exemplo — L = \{a, ab\} sobre \Sigma = \{a, b\} — são duas cadeias escolhidas a dedo, sem nada em comum além do conjunto. É uma linguagem legítima. A segunda frase da definição carrega a permissividade toda e soa como formalidade jurídica até alguém tentar usá-la. Nada obriga uma linguagem a ter regra, nem a existir uma frase em português que a descreva, nem a existir um programa que decida se uma cadeia pertence a ela. Duas linguagens degeneradas mostram a fronteira: \emptyset não contém cadeia nenhuma e recusa toda entrada; \{\varepsilon\} contém exatamente uma cadeia, a vazia, e aceita apenas a entrada sem caracteres. São objetos distintos, com cardinalidades distintas.
Sendo conjuntos, as linguagens herdam as operações de conjunto. Herdam também uma operação que só faz sentido porque os elementos são cadeias, e é ela que constrói linguagens grandes a partir de pequenas.
NotaDefinição — Operações sobre linguagens
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.
Tome L_1 = \{a, ab\} e L_2 = \{b, \varepsilon\}, pequenos de propósito, e confira tudo a olho. A união dá \{a, ab, b, \varepsilon\}, e o ou da definição é inclusivo. Quem lê depressa troca esse ou por um e, e aí a operação vira interseção — que neste caso é vazia. A concatenação manda formar todos os pares, um de cada conjunto, e emendar cada par numa cadeia: a \cdot b = \texttt{ab}, a \cdot \varepsilon = \texttt{a}, ab \cdot b = \texttt{abb}, ab \cdot \varepsilon = \texttt{ab}. Quatro pares, três cadeias distintas — ab saiu duas vezes, por caminhos diferentes, e num conjunto conta uma.
|L_1 L_2| \leq |L_1| \cdot |L_2|
A desigualdade vale sempre, com igualdade só quando não há colisão. Representar uma linguagem finita em memória é direto, e as duas operações cabem num punhado de linhas.
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>;
DicaNo código
Três apelidos de tipo, e o que eles decidem é o comportamento da saída. A ordem determinística é escolha de demonstração, não de desempenho — ordem que muda a cada execução tira de quem lê a chance de comparar dois resultados lado a lado.
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;
}
DicaNo código
Duas funções, e a estrutura escolhida faz metade do trabalho: como o resultado é um conjunto, a colisão se resolve sozinha na inserção. O resultado da concatenação é uma coisa só — cada elemento é uma cadeia única, com a costura invisível. Ninguém guarda o par que a originou, e recuperar x e y a partir de xy costuma ser impossível.
A restrição está numa palavra do parágrafo anterior: finita. Toda linguagem que um compilador processa é infinita, porque há infinitos programas válidos em qualquer linguagem usável. O conjunto explícito funciona, é curto de escrever, e para de servir na primeira linguagem que alguém queira compilar.
1.3.2 Multiplicar por zero, com conjuntos no lugar de números
A potência de uma linguagem repete a concatenação: L^2 = LL, L^3 = LLL, e por aí adiante. Com L_1 = \{a, ab\}, a potência dois dá \{aa, aab, aba, abab\} — quatro cadeias, sem colisão desta vez. Vamos por partes, porque o caso zero é onde o assunto morde. A definição fixa L^0 = \{\varepsilon\}, e a escolha parece arbitrária até você tentar a alternativa.
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;
}
DicaNo código
A linha que cria o acumulador é a definição inteira. Nascendo com a cadeia vazia dentro, ela preserva o que multiplica; nascendo com o conjunto sem elemento algum, aniquila. Um caractere de diferença, e a função passa a devolver vazio para toda entrada.
Veja o acumulador. Ele começa em \{\varepsilon\} e é concatenado com L uma vez por nível. No nível um, como \varepsilon é neutro, o resultado é o próprio L_1. No nível dois sai o conjunto de quatro cadeias de antes. Agora troque a inicialização por \emptyset e refaça a conta. A definição manda formar todos os pares com um elemento de cada conjunto — e o primeiro conjunto não tem elemento algum, então não existe par nenhum. O acumulador nunca sai do vazio, e a função devolve conjunto vazio para toda entrada, em todo expoente.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
A["acumulador no nível 0"]
B1["inicia com a cadeia vazia<br/>elemento neutro: preserva"]
B2["inicia com o conjunto vazio<br/>nenhum par possível: aniquila"]
C1["nível 1 devolve L"]
C2["nível 1 devolve vazio"]
D1["nível 2 devolve L concatenado com L"]
D2["nível 2 devolve vazio<br/>e todos os níveis seguintes também"]
E["teto de comprimento imposto por fora<br/>fora do recorte não é fora da linguagem"]
A --> B1 --> C1 --> D1 --> E
A --> B2 --> C2 --> D2
O efeito tem nome preciso. A concatenação com o conjunto vazio aniquila o resultado; a concatenação com o conjunto que contém a cadeia vazia o preserva. Um conjunto sem elementos multiplica por zero. Um conjunto com um elemento neutro multiplica por um. É a aritmética de sempre, com conjuntos no lugar de números. E é por isso que L^0 = L também está errado. Essa igualdade aplica ao conjunto a regra do expoente um, lendo a potência como operação sobre o rótulo, e não sobre o conteúdo.
O fecho — que leva o nome de Stephen Kleene — reúne todas as potências, sem teto. Com L_1 = \{a, ab\} ele contém \varepsilon, a, ab, aa, aab, aba, abab, e continua para sempre. Para sempre é o problema. Materializá-lo como conjunto é impossível sempre que L tem alguma cadeia não vazia. O número de elementos cresce sem parar. A única saída é limitar por fora.
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;
}
DicaNo código
Materializar o conjunto tem um custo, e ele está no parâmetro de comprimento máximo — que não faz parte da definição, e é bom que incomode. Há uma segunda parada escondida no código, mais sutil. Cada nível precisa descartar as cadeias já vistas. Senão o conjunto de trabalho nunca esvazia, e o laço roda sem fim mesmo com o teto aplicado.
Faça a conta num caso pequeno, porque ela serve de teste. Com L = \{a, b\} e teto 3, o fecho truncado tem uma cadeia de comprimento zero, duas de comprimento 1, quatro de comprimento 2 e oito de comprimento 3: quinze ao todo. Outro número denuncia erro na potência zero ou na condição de parada, e em nenhum outro lugar.
A armadilha de leitura, e ela custa a conclusão inteira
Perguntado se abab está no fecho truncado em comprimento 3, o programa responde que não. A resposta correta é que abab está fora do recorte, e não fora da linguagem: ela pertence ao fecho, tem comprimento 4, e o teto a excluiu. Quem lê a saída sem essa distinção conclui o oposto do verdadeiro.
1.3.3 Quatro regras, quinze símbolos, um conjunto sem fim
Toda linguagem que um compilador processa é infinita, e todo arquivo em que alguém a descreve é finito. Como se escreve, num espaço fixo, uma coisa que não acaba? Há duas maneiras, e elas atacam por lados opostos. A primeira gera: parte de um símbolo inicial e vai produzindo cadeias por aplicação de regras. A segunda reconhece: recebe uma cadeia pronta e responde sim ou não.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
L["uma linguagem<br/>conjunto infinito de cadeias"]
G["descrição que GERA<br/>parte de um símbolo inicial<br/>e produz cadeias sem parar"]
R["descrição que RECONHECE<br/>recebe uma cadeia pronta<br/>e responde sim ou não"]
GG["gramática"]
RR["máquina de estados"]
T["texto finito, escrito à mão"]
M["tabela finita, executada rápido"]
L --> G
L --> R
G --> GG --> T
R --> RR --> M
GG -.->|"conversão mecânica<br/>dentro da mesma classe"| RR
O lado gerador se chama gramática. O lado reconhecedor se chama máquina e, nos degraus mais baixos, cabe numa tabela de estados. A seta pontilhada carrega a parte mais valiosa do desenho: dentro de uma mesma classe existe conversão mecânica de um lado para o outro.
Escrever a descrição geradora é confortável, porque ela se parece com a intenção de quem projeta; executar o reconhecedor é rápido, porque ele decide olhando um símbolo por vez. Ter as duas sem escrever nenhuma delas duas vezes é o negócio que a teoria oferece, e o preço são as restrições da classe em que a conversão funciona. Repare que a tabela finita e o conjunto infinito que ela reconhece têm tamanhos incomparáveis. Nada na máquina contém a lista das cadeias aceitas, e é essa ausência que a faz caber na memória.
NotaDefinição — Gramática
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.
Tome a menor gramática que ainda diz algo interessante: terminais \Sigma = \{a, +, (, )\}, não terminais V = \{E, T\}, símbolo inicial E, e quatro produções.
Quatro regras, quinze símbolos escritos, e o que elas produzem não acaba: a, a+a, (a), a+a+a, ((a)), (a+a)+a, sem teto. O infinito entra por duas portas. As duas são recursões. A primeira regra tem E dos dois lados, o que alonga a soma indefinidamente; a terceira faz T voltar a E dentro de parênteses, o que encaixa níveis indefinidamente. Sem nenhuma das duas, o conjunto gerado caberia numa lista.
NotaDefinição — Derivação e linguagem gerada
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 \}.
Produzir uma cadeia é aplicar regras até não sobrar não terminal nenhum. Derive (a+a) com a regra usada anotada ao lado:
Seis passos, e no fim não sobra não terminal — a derivação terminou, e (a+a) pertence à linguagem gerada. Aplicar a primeira regra mais uma vez em qualquer ponto produziria outra cadeia, mais longa e igualmente legítima. A derivação registra a ordem em que as regras foram aplicadas, e essa ordem não interessa a ninguém adiante. O que interessa é a estrutura de encaixe, e ela se guarda numa árvore.
NotaDefinição — Árvore de derivação
Seja G = (V, \Sigma, P, S) uma gramática. Uma árvore é um conjunto finito de nós em que cada nó tem uma sequência ordenada de filhos e em que todo nó, exceto um — a raiz —, é filho de exatamente um outro nó; nó sem filhos chama-se folha, e a subárvore de um nó é esse nó com todos os seus descendentes. Uma árvore de derivação de G é uma árvore cuja raiz é rotulada com S, cujos nós internos são rotulados com elementos de V e cujas folhas são rotuladas com elementos de \Sigma ou com \varepsilon, e em que, para todo nó interno rotulado A cujos filhos são rotulados X_1, \ldots, X_n nessa ordem, A \to X_1 \cdots X_n é uma produção de P. A cadeia formada pelas folhas, lidas da esquerda para a direita, é a cadeia derivada pela árvore.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
R["E<br/>raiz, símbolo inicial"]
T1["T"]
AB["#40;"]
E2["E"]
FE["#41;"]
E3["E"]
MAIS["+"]
T3["T"]
T2["T"]
A1["a"]
A2["a"]
R --> T1
T1 --> AB
T1 --> E2
T1 --> FE
E2 --> E3
E2 --> MAIS
E2 --> T3
E3 --> T2
T2 --> A1
T3 --> A2
Leia as folhas da esquerda para a direita e você obtém ( a + a ). Leia os nós internos e você obtém a estrutura. O parêntese e o + não estão soltos no texto: estão pendurados em nós que dizem a que construção cada um pertence. A definição não exige que a árvore seja única — uma cadeia pode ter duas árvores distintas na mesma gramática, e aí a gramática é ambígua, assunto de capítulo próprio adiante.
Escrever gramáticas por extenso cansa. Em junho de 1959, no congresso internacional de processamento de informação, em Paris, John Backus propôs uma notação compacta para a sintaxe de uma linguagem. Peter Naur a adaptou ao editar o Report on the Algorithmic Language ALGOL 60, publicado nas Communications of the ACM no volume 3, número 5, de 1960. As duas abreviações mais comuns são a alternativa e a repetição:
Repare no segundo par. A forma da esquerda produz zero ou mais itens por recursão; a da direita diz a mesma coisa com um asterisco. Elas geram exatamente o mesmo conjunto de cadeias, e a expansão que desfaz a segunda na primeira é mecânica. Daí a consequência que costuma surpreender: a notação abreviada não acrescenta poder de expressão nenhum — encurta o documento e se desfaz na implementação. Diante de uma gramática abreviada, expanda mentalmente as abreviações antes de decidir a que classe ela pertence. A classe sai da forma das regras, e o açúcar de escrita não a move.
1.3.4 As linguagens que texto nenhum descreve
Chegamos ao ponto desconfortável. Pense comigo antes de ler a resposta. A definição de linguagem não exige regra nem descrição. Uma gramática é um texto finito. Todo subconjunto de \Sigma^* tem alguma gramática, alguma máquina, algum programa que o descreva? A resposta é não, e a distância entre o sim e o não é maior do que qualquer intuição sugere.
O argumento se monta em duas colunas. Na primeira, as descrições finitas. Toda gramática, toda máquina, todo programa é um texto finito sobre algum alfabeto fixo. E textos finitos podem ser enfileirados, na mesma fila de antes: primeiro por comprimento, depois em ordem alfabética. Cada descrição possível ocupa uma posição finita nessa fila. Na segunda coluna, as linguagens. Cada uma é um subconjunto de \Sigma^*, e Georg Cantor demonstrou, por um argumento que hoje se chama diagonal, que os subconjuntos de um conjunto infinito enumerável não se enfileiram.
Faça o teste. Suponha que alguém apresente uma fila com todos eles: L_1, L_2, L_3, \ldots. Construa um conjunto novo, D, decidindo cada cadeia da fila do universo pela regra oposta. A primeira cadeia entra em D se, e só se, ela não estiver em L_1. A segunda entra se, e só se, não estiver em L_2. E assim por diante, sem fim. O conjunto D é uma linguagem legítima. Ele difere de cada L_n da fila exatamente na n-ésima cadeia.
Ele não está na fila. E a fila que se prometeu completa não era completa.
Ponha as duas colunas lado a lado e a conclusão sai sozinha. As descrições formam uma fila; as linguagens não formam. Como cada descrição descreve no máximo uma linguagem, sobram linguagens sem descrição — e não sobram poucas.
A leitura que inverte o resultado
O ponto não é que ninguém ainda descobriu descrição para essas linguagens. A descrição não existe, e isso está demonstrado. Trocar demonstração por ignorância provisória é o que faria alguém passar meses procurando uma gramática que não pode ser encontrada, porque nada há para encontrar.
O resultado incomoda menos do que devia, e a razão é que ele parece não ter consequência prática. Tem uma, e é grande: toda linguagem que você projetar vai estar dentro da fatia descritível, porque você a projeta escrevendo a descrição. O que se decide daqui em diante é em que degrau da fatia ela cai. E cada degrau cobra um preço diferente em memória de máquina.
1.4 A pergunta certa é de que memória a máquina precisa
Um artigo de linguística de 1956 virou o mapa que todo projetista de linguagem usa. Ele não foi escrito para isso.
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 era a língua natural, e a hierarquia que leva o seu nome não foi proposta para orientar o projeto de compiladores. A computação herdou o resultado por uma coincidência afortunada. As restrições que ele impôs à forma das regras produziram classes que correspondem, uma a uma, a modelos de máquina. A direção costuma ser contada ao contrário — ninguém partiu das máquinas para derivar as gramáticas.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
subgraph Z0["tipo 0 — irrestrita · máquina de Turing · pode não parar"]
subgraph Z1["tipo 1 — sensível ao contexto · fita do tamanho da entrada"]
subgraph Z2["tipo 2 — livre de contexto · autômato de pilha · memória cresce com a entrada"]
Z3["tipo 3 — regular<br/>autômato finito<br/>nenhuma memória além do estado"]
end
end
end
A hierarquia é um encaixe, não uma lista de opções paralelas. O tipo 3, o mais restrito, chama-se regular, e a máquina é o autômato finito. O tipo 2 é o livre de contexto, com o autômato de pilha. O tipo 1 é o sensível ao contexto, com o autômato linearmente limitado. O tipo 0 é o irrestrito, com a máquina de Turing.
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"},
};
}
DicaNo código
Dos quatro degraus, dois são realizados pelo sistema que acompanha estas páginas e dois estão ali para situar o que fica de fora — é a última coluna que diz qual é qual. A quarta linha traz a distinção que mais confunde aqui: a máquina de Turing é o poder do tradutor, e não o poder da linguagem traduzida.
E qual é o critério que separa um degrau do seguinte? Não é o tamanho do alfabeto, nem o número de regras, nem a velocidade. O critério é quanta memória a máquina precisa ter, e de que tipo é o acesso a ela.
1.4.1 A máquina que conta nos dedos, com um número fixo de dedos
No degrau mais baixo, a máquina tem uma quantidade fixa de estados e nenhuma outra memória. Lê um símbolo, muda de estado conforme uma tabela, e segue. No fim da entrada, olha em que estado parou e responde sim ou não. É 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. A frase soa como limitação técnica menor, e é a fronteira inteira da classe. Tome a linguagem dos parênteses balanceados: () está nela, (()) está, (()()) está, e (() não está. Um autômato finito dá conta dela? Suponha que sim, e chame de k o número de estados dessa máquina, fixado antes de qualquer entrada chegar. Adivinhe o que acontece se você a alimentar com k+1 entradas: uma abertura, duas, três, até k+1. São k+1 leituras para k estados disponíveis, então duas terminam no mesmo estado. Chame essas profundidades de i e j, com i menor que j.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
K["máquina com k estados<br/>fixados antes de ligar"]
E["k + 1 entradas:<br/>1 abertura, 2 aberturas, ... , k+1 aberturas"]
C["duas delas param no mesmo estado<br/>profundidades i e j, com i menor que j"]
S["complete as duas com i fechamentos"]
R["mesma resposta para as duas<br/>uma delas está errada"]
K --> E --> C --> S --> R
A partir daí a máquina não distingue mais as duas situações, porque o estado é tudo o que ela guarda. Complete as duas entradas com i fechamentos. A primeira fica balanceada; a segunda, com j aberturas e i fechamentos, não fica. As duas partem do mesmo estado com o mesmo sufixo, terminam no mesmo estado, e recebem a mesma resposta. Uma delas está errada, qualquer que seja.
O obstáculo está na finitude, e não no tamanho. Acrescentar estados não resolve, porque o argumento se refaz com o novo k. Uma máquina de 101 estados reconhece corretamente a linguagem dos aninhamentos até profundidade 100. Essa é regular, e não é a que se pediu. Uma tentação vizinha merece o mesmo tratamento. Alguém sempre observa que nenhum programa real aninha mais de vinte níveis, e portanto a máquina de vinte e um estados serviria. Isso troca a pergunta formal pela estatística de uso, e a definição de linguagem não fala de frequência.
O saldo desta subseção
Memória finita reconhece o que se decide sem contar. Onde a resposta depende de comparar duas quantidades que crescem sem teto — aberturas contra fechamentos, níveis de encaixe, um bloco contra outro —, o degrau regular acaba. O próximo começa ali.
1.4.2 A pilha, e uma data em Amsterdã
O degrau seguinte acrescenta uma peça, e a peça é pobre de propósito. É uma pilha: escreve-se no topo, lê-se o topo, remove-se o topo. Não há consulta ao meio, não há contagem de itens guardados, não há como olhar o fundo sem desmontar o que está por cima. De tão limitada, quase nenhuma biblioteca a ofereceria sozinha. E é essa pobreza que faz dela a peça certa. O problema dos parênteses tem a forma de uma pilha: cada abertura empilha uma marca, cada fechamento remove a do topo, e a resposta no fim é uma pergunta só.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
P0["vazia"]
P1["uma marca"]
P2["duas marcas"]
P3["uma marca"]
P4["vazia"]
OK["aceita: pilha vazia no fim"]
F1["#40;#40;#41; sobra marca: recusa"]
F2["#40;#41;#41; remoção em pilha vazia: recusa"]
P0 -->|"lê ("| P1
P1 -->|"lê ("| P2
P2 -->|"lê )"| P3
P3 -->|"lê )"| P4
P4 --> OK
P2 -.-> F1
P0 -.-> F2
Percorra os quadros e repare no que sobra em cada modo de recusa. Sobre (()) a pilha esvazia no fim, e a entrada é aceita. Sobre (() a última remoção não acontece, sobra uma marca, e a entrada é recusada. Sobre ()) a máquina tenta remover de uma pilha vazia, e recusa ali mesmo. A memória cresce com a entrada. É esse crescimento sem teto que a máquina finita não tinha.
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 o próprio Dijkstra a expôs em Recursive Programming, publicado na Numerische Mathematik em 1960. A pilha — hoje exemplo de primeira aula — entrou na engenharia de compiladores resolvendo um problema concreto de quem escrevia um tradutor de verdade. A recursão só é barata porque alguém decidiu guardar o retorno numa pilha.
A mesma peça aparece três vezes ao longo destas páginas, em alturas diferentes do mesmo sistema. Primeiro como a memória do autômato do segundo degrau, que é o que acabamos de ver. Depois como a cadeia de chamadas de um analisador feito de procedimentos que chamam uns aos outros. Por fim como o registro de ativação na memória da máquina que executa o programa traduzido. Três ofícios, um objeto só.
Acima do livre de contexto ficam duas classes que estas páginas nomeiam e não usam. No tipo 1, as produções podem ter mais de um símbolo do lado esquerdo, e a máquina dispõe de memória proporcional ao tamanho da entrada. Ela alcança linguagens que a pilha não alcança, e a conta aparece no tempo de decidir. No tipo 0 a moeda deixa de ser tempo e passa a ser existência de resposta. Há cadeias para as quais a máquina não para nunca, e não há como saber de antemão quais. Um analisador que pudesse não terminar sobre uma entrada válida é um analisador que ninguém instala.
Nenhuma fase de um tradutor real precisa desses dois degraus, e a observação reorganiza o mapa inteiro. Três verificações parecem exigir sensibilidade ao contexto: declarar antes de usar, casar o tipo dos dois lados de uma atribuição, conferir o número de argumentos de uma chamada. Todas são feitas fora da gramática, por uma fase que percorre a árvore com uma tabela de nomes ao lado. Sobe-se um degrau na estrutura de dados em vez de subir na hierarquia. A troca compensa: a tabela custa tempo constante por consulta, e o degrau custa tudo.
1.5 Seis fases, e nada atravessa a fronteira em outro formato
Todo tradutor faz as mesmas seis coisas, na mesma ordem, mesmo quando o manual dele não as chama assim.
Um tradutor é uma sequência de funções pequenas, cada uma recebendo o que a anterior devolveu, pela razão que Backus já apresentou: decidir cedo é decidir com pouca informação. A divisão canônica conta seis fases, e o nome de cada uma é o menos importante. O que define uma fase é o par formado pelo que ela consome e pelo que devolve.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
T["texto do programa"]
L["análise léxica"]
S["análise sintática"]
M["análise semântica"]
I["geração de código intermediário"]
O["otimização"]
F["geração de código final"]
R["código da máquina de destino"]
AN["metade que desmonta:<br/>a única que recusa"]
SI["metade que monta:<br/>a única que conhece a máquina"]
T --> L
L -->|"fluxo de símbolos"| S
S -->|"árvore da estrutura"| M
M -->|"árvore verificada<br/>+ tabela de nomes"| I
I -->|"representação intermediária"| O
O -->|"representação melhor<br/>por um critério declarado"| F
F --> R
AN -.- L
SI -.- I
A análise léxica recebe o texto e devolve um fluxo de símbolos, cada um com a posição em que foi encontrado. A análise sintática devolve a árvore da estrutura, e a análise semântica devolve a árvore verificada, com a tabela de nomes ao lado. A geração de código intermediário devolve uma representação que não fala de máquina nenhuma. A otimização devolve outra, melhor por um critério declarado. E a geração de código final devolve o código da máquina de destino.
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},
};
}
DicaNo código
Uma entrada por fase, com o que ela consome, o que devolve e a que metade pertence: a cadeia de fases virou dado em vez de comentário. A diferença entre as duas formas só aparece meses depois — comentário não roda, não se confere e envelhece calado.
E o que sobra do seu texto em cada etapa? Acompanhe a linha da primeira seção atravessando as seis, supondo que total e preco guardem números reais e que quantidade guarde um inteiro:
fonte total = preco * quantidade
léxica ID(total) IGUAL ID(preco) VEZES ID(quantidade)
sintática atribui( total , multiplica( preco , quantidade ) )
semântica atribui( total:real , multiplica( preco:real , paraReal(quantidade:int) ) )
intermediária t1 = paraReal quantidade
t2 = preco * t1
total = t2
final as instruções da máquina de destino que executam essas três linhasRepare no que aconteceu entre a terceira linha e a quarta. Nenhum símbolo do texto original mudou, e mesmo assim a árvore ganhou um nó que ninguém escreveu. É a conversão do inteiro para real, inserida porque a multiplicação exigia os dois lados no mesmo tipo. É a primeira vez, no percurso de um programa, em que o tradutor acrescenta ao seu texto uma coisa que você não digitou. Não será a última.
As três primeiras fases formam a análise, e o nome descreve o que elas fazem: desmontam. Essa metade tem uma propriedade que a segunda não tem — é a única que pode recusar. Todo erro reportado ao programador nasce aqui: símbolo desconhecido, parêntese que não fecha, variável usada sem declaração, tipos incompatíveis. Ela também é a única que conhece a forma do texto original — sabe em que linha o * apareceu, sabe que havia um espaço ali —, e nada disso sobrevive à fronteira. Por isso uma mensagem de erro precisa ser emitida durante a análise, com a posição ainda em mãos. Guarde uma assimetria útil: como a análise depende só da linguagem-fonte, trocar a máquina de destino deixa as três primeiras fases idênticas.
As três últimas formam a síntese, e invertem o movimento: recebem a árvore verificada e vão montando algo que uma máquina consiga executar. A fronteira entre as metades é exatamente esse objeto, e nada a atravessa em outro formato. A síntese é a única metade que conhece a máquina de destino, e é aí que encontra o problema que define o ofício. Nenhuma máquina real oferece exatamente as operações que a linguagem oferece. A linguagem tem construções que descrevem intenções. A máquina tem um repertório fixo, decidido por quem projetou o processador sem consultar quem projetou a linguagem. O que a máquina não faz, o tradutor faz por ela — e cobra em instruções.
Essa distância não some; ela é paga, e quem paga é a última fase. Uma construção que a máquina não realiza diretamente vira uma sequência de operações que ela realiza. É essa distância, também, que torna possível falar em qualidade de tradução. Se a máquina executasse a linguagem diretamente, não haveria escolha a fazer nem nada a comparar. Como não executa, existem muitas sequências com o mesmo efeito e custos diferentes. O valor dessa conta fica para o fim do percurso, quando houver máquina de destino declarada e instruções para contar.
1.5.1 Três artefatos que ninguém encomendou
Entre o texto que entra e o resultado que sai existem artefatos que nenhuma das duas pontas pediu. Quem escreve o programa não pede uma lista de símbolos; quem executa o resultado não pede uma árvore. As duas existem por conveniência de quem constrói o tradutor, e essa origem é o que torna fácil descartá-las por engano.
A primeira forma é o fluxo de símbolos, e responde a uma pergunta que o texto bruto não responde: onde termina cada unidade de significado. No texto, total são seis caracteres soltos; no fluxo, é um símbolo só, com tipo e posição, e espaço em branco e comentário desaparecem nessa passagem. A segunda é a árvore da estrutura, que responde a que construção cada símbolo pertence. No fluxo, * é um símbolo entre outros. Na árvore, é um nó com dois filhos, e a precedência já está resolvida pelo encaixe. A terceira é a tabela de nomes, que responde ao que um nome significa e é a única das três sem forma de sequência nem de árvore.
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"},
};
}
DicaNo código
A última coluna é a que muda a leitura da tabela: ao lado de cada forma está escrita a razão de ela não se eliminar. Sem essa coluna a tabela seria um inventário; com ela, é um argumento.
Suprimir uma forma não faz a pergunta correspondente desaparecer. Ela passa a ser respondida em outro lugar, e o outro lugar quase sempre é pior. Sem o fluxo de símbolos, toda regra da gramática precisa saber pular espaços e atravessar comentários. A lógica que estava num lugar só se espalha por dezenas de cópias, e cada uma envelhece sozinha. Sem a árvore, a verificação de tipos acontece durante a leitura, quando o lado direito da operação ainda não foi lido inteiro. Sem a tabela de nomes, consultar um identificador vira varredura do texto, e o custo total passa a crescer com o quadrado do tamanho do programa. Num arquivo de duzentas linhas ninguém percebe; num de duzentas mil, é a diferença entre compilar e esperar.
Declarar uma forma intermediária também cobra, e a cobrança recai sobre quem mantém o código. O primeiro custo é o de definição: a forma precisa ser descrita com precisão suficiente para que produtor e consumidor não divirjam. O segundo é o de conversão, e a posição de um símbolo é o caso clássico. Ela nasce na análise léxica, não interessa à sintática, e volta a ser indispensável na mensagem de erro da semântica. Se alguma forma do meio não a carregar, a mensagem sai sem endereço.
O terceiro é o de sincronia. Uma construção acrescentada ao fluxo e esquecida na árvore produz um tradutor que aceita o texto e não sabe o que fazer com ele. A mensagem de erro, quando vem, aponta para um lugar sem defeito nenhum.
1.5.2 Onde alguém põe a fronteira entre traduzir e rodar
Chamar uma linguagem de compilada ou de interpretada é hábito antigo e imprecisão. A mesma linguagem admite as três estratégias, e escolher entre elas é decisão de quem constrói a implementação — nada disso está na especificação da linguagem. Existem interpretadores de C, e compiladores de linguagens que quase todo mundo chama de interpretadas.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart LR
A["traduzir antes, uma vez<br/>executa: o processador físico<br/>o texto pode ser apagado"]
B["traduzir antes para uma forma intermediária<br/>executa: uma máquina virtual<br/>a máquina virtual precisa existir onde se roda"]
C["não traduzir<br/>executa: o interpretador, percorrendo a estrutura<br/>o texto fica presente o tempo todo"]
A --- B --- C
Numa ponta, a tradução acontece antes, uma vez só. O texto vira código da máquina de destino. Pode ser apagado, que o programa continua rodando. Quem executa é o processador físico, sem intermediário. Isso exige do tradutor o conhecimento mais específico: o repertório exato da máquina, o tamanho dos registradores, a convenção de chamada. Na outra ponta, tradução não há. Um programa percorre a estrutura do que você escreveu e executa cada pedaço na hora, toda vez. Isso obriga o texto a estar presente durante a execução inteira.
Cada operação custa duas coisas: o trabalho dela própria, e o de o interpretador descobrir qual operação é.
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},
};
}
DicaNo código
A estratégia híbrida ocupa o meio do eixo, e o trecho a marca explicitamente como o lugar mais povoado. A tradução acontece antes, uma vez, e o alvo é uma representação intermediária que uma máquina virtual executa. Como o repertório dessa máquina é projetado junto com a linguagem, a tradução fica mais simples e o despacho mais barato do que interpretar a estrutura original. Em troca, a máquina virtual precisa existir em toda plataforma onde o programa deva rodar.
Note uma armadilha de vocabulário antes de seguir. Enquanto traduz, o sistema não executa nada do que está escrito no arquivo. Um laço escrito no fonte não gira durante a compilação. Ele vira instruções que vão girar depois, quando alguém rodar o resultado. Tratar traduzir e executar como o mesmo verbo apaga a distinção que separa um erro de compilação de um erro em tempo de execução.
A decisão não é neutra para quem programa, e cobra em três lugares. Traduzir antes faz erros de tipo, de nome e de estrutura aparecerem sobre o programa inteiro — inclusive nas partes que aquela execução não visitaria. Interpretar faz o mesmo erro aparecer quando o fluxo chega à linha que o contém. E uma linha num ramo raro passa meses sem ser visitada. Um programa compilado — desde que o processador seja aquele — roda sozinho. Um interpretado ou híbrido roda onde o executor exista, e não roda onde ele falte. E executores que trabalham durante a execução usam informação que o tradutor não tinha, como o ramo tomado quase sempre. O que não se defende é escolher por hábito de comunidade, que é como a escolha costuma ser feita.
1.6 O item mais consequente de uma especificação é uma recusa
Antes de existir uma linha de código de um tradutor, alguém sentou e escreveu o que a linguagem aceita. Aconteceu com FORTRAN em 1957, aconteceu com ALGOL 60 no relatório que Naur editou, e acontece com toda linguagem pequena que alguém constrói para resolver um problema específico. A primeira especificação responde a três perguntas, e nenhuma é sobre implementação. Sobre que domínio a linguagem fala. Que forma tem o texto que alguém escreve nela. E o que o sistema produz ao processar esse texto.
As três parecem óbvias enquanto ninguém as escreve. Escritas, viram restrições, e aí se descobre que a resposta que se tinha na cabeça era vaga. “A linguagem aceita expressões” é ruído. “A linguagem aceita concatenação, alternativa e repetição, e recusa tudo o mais” é especificação, porque pode ser conferida contra um texto qualquer. E uma regra prática rende mais do que a lista de perguntas: registre, ao lado de cada decisão, a alternativa que você descartou e por quê. Meses depois, a resposta a “por que a linguagem não aceita isto?” está escrita com a razão técnica junto, e não depende da memória de quem decidiu naquele dia.
Considere agora uma linguagem de padrões sobre texto. Existe uma construção, presente em quase toda ferramenta de busca, que permite a um padrão referir-se a um trecho que ele próprio já casou. Ela exige, por exemplo, que a segunda metade da cadeia repita a primeira. É útil, é familiar, e quem escreve padrões a pede na primeira semana.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
P["construção pedida:<br/>o padrão repete um trecho que ele já casou"]
Q["exige comparar duas quantidades<br/>que crescem sem teto"]
R["sai da classe das linguagens regulares"]
S["nenhuma máquina finita corresponde ao padrão"]
T["o produto que se pretendia entregar<br/>era exatamente essa máquina"]
U["decisão: recusar, e escrever a razão"]
P --> Q --> R --> S --> T --> U
Aceitá-la sai da classe das linguagens regulares. Uma linguagem que exija a repetição exata de um trecho de comprimento arbitrário pede o que a memória finita não faz: comparar duas quantidades que crescem sem teto. Um sistema que a aceitasse não poderia compilar os padrões para autômato finito — e o autômato finito era o produto que se pretendia entregar. A recusa custa uma construção que os usuários pedem. Custa também a explicação de por que ela não existe. Compra a garantia de que todo padrão escrito na linguagem tem uma máquina finita correspondente, com tempo de decisão proporcional ao comprimento da entrada. E só se toma antes de haver código, porque voltar atrás depois significa reescrever tudo o que se apoiou nela.
Há um segundo item que se decide agora e parece descuido. A gramática de uma linguagem nova, na primeira escrita, sai numa forma que os capítulos adiante chamarão de imprópria. Tem recursão à esquerda, como o E → E + T de antes. E tem alternativas que começam pelo mesmo símbolo. As duas propriedades quebram o método de análise mais simples que existe, e há transformações mecânicas que as eliminam.
A tentação natural é aplicá-las já. Pois não faça isso. Escreva a gramática na forma em que ela sai e guarde esse arquivo: quando as transformações chegarem, a forma anterior ao lado da final explica por que elas são necessárias. Sem o original, resta o resultado, e o resultado sozinho parece convenção arbitrária de escrita.
Há ainda uma confusão que se instala exatamente aqui, e ela erra nos dois sentidos possíveis. Uma notação de padrões e a linguagem que um padrão denota são objetos de classes diferentes. O texto de uma expressão de padrões tem parênteses que se aninham sem teto, o que o põe no degrau livre de contexto: ler esse texto exige uma pilha. Já o conjunto de cadeias que aquela expressão descreve é regular, e uma máquina finita o reconhece. Uma coisa é ler a descrição; outra é decidir sobre o que ela descreve.
1.7 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 marco da Peneira neste ponto não implementa fase nenhuma do compilador — implementa o vocabulário formal, imprime a arquitetura como tabela e para exatamente onde o conjunto explícito para de servir.
1.7.1 O que o programa faz quando executa
O executável 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. Nenhuma dessas fases existe ainda. Cada capítulo seguinte substitui uma linha por implementação real, e a tabela impressa no primeiro dia e no último dia tem o mesmo formato.
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.7.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. 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.7.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. O arquivo separa em dois blocos a gramática que quem usa a linguagem escreve e a mini-linguagem de padrões, e a separação existe justamente por causa da confusão que o corpo do capítulo nomeou — a notação de padrões tem parênteses aninhados e é livre de contexto, enquanto o conjunto de cadeias que cada padrão denota é regular.
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: contato ana.silva@exemplo.com e grande 1500. Os casos mais valiosos são os dois números que casam o padrão e não produzem saída. O valor 42 falha por magnitude, que é o caso negativo previsível; o valor -240.75 falha por sinal, porque o sinal entra no casamento e o número comparado é negativo. São esses dois casos negativos que provam que a condição está sendo avaliada, e não apenas o casamento. Um sistema que emitisse quatro linhas passaria em dois terços da bateria, proporção que num relatório de progresso passa por sucesso.
exemplos/entrada01.txt
Fica declarado, para o marco seguinte, o que este não entrega: nenhuma dessas descrições é lida por programa algum ainda. O .pen é especificação pelo exemplo, e o primeiro código que vai olhar para dentro dele só aparece no capítulo de análise léxica. Até lá, ele serve de alvo — e de teste que já existe antes do que ele testa.
1.8 Ler o fonte deixou de responder à pergunta
Uma palestra de 1984 desloca a pergunta que você acha que está fazendo ao ler o fonte de um programa.
Em agosto de 1984, as Communications of the ACM publicaram o texto da palestra que Ken Thompson havia proferido ao receber o Prêmio Turing. O argumento tem três passos, e nenhum deles depende de nada mais sofisticado do que aquilo que estas páginas já montaram. A premissa é a primeira coisa que este capítulo afirmou: um tradutor recebe o texto de um programa como dado.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
P1["passo 1<br/>o tradutor reconhece o texto de um programa<br/>e insere código que ninguém escreveu"]
P2["passo 2<br/>o tradutor reconhece o próprio fonte dele<br/>e reinsere as duas modificações ao compilar-se"]
P3["passo 3<br/>as modificações são apagadas do fonte<br/>e sobrevivem no binário produzido"]
C["a pergunta muda de lugar:<br/>quem traduziu este programa,<br/>e o que aquele tradutor sabia?"]
P1 --> P2 --> P3 --> C
No primeiro passo, alguém modifica um tradutor para que ele reconheça o texto de um programa específico e, ao traduzi-lo, insira código que ninguém escreveu. Não há dificuldade técnica nisso. Reconhecer texto é o ofício da análise, e emitir código é o da síntese. As duas metades já estão prontas. No segundo passo, o mesmo tradutor é modificado para reconhecer o próprio fonte dele — e ao compilar a si mesmo, reinsere as duas modificações no binário que produz. Um tradutor é um programa como qualquer outro, e um programa é texto.
No terceiro passo, as modificações são apagadas do fonte, que volta a estar limpo. E o binário compilado a partir dele continua inserindo as duas coisas, porque quem o compilou foi o binário anterior, que já as carregava. Compile o fonte limpo com o binário contaminado e você obtém outro binário contaminado, indefinidamente.
O que sobra é um deslocamento de pergunta. Ler o fonte de um programa deixa de responder o que o binário faz, e passa a responder apenas o que o autor escreveu. A pergunta que importa vira outra: quem traduziu este programa, e o que aquele tradutor sabia? Também não adianta desmontar o binário, porque o desmontador é um programa, e alguém o compilou.
Volte agora ao encontro de 1952. Hopper propôs que o texto que uma pessoa escreve pode ser dado de outro programa, e o A-0 fez com aquilo a coisa mais modesta possível: colou pedaços prontos. Trinta e dois anos separam aquela apresentação desta palestra. Tudo o que veio no meio — as seis fases, os quatro degraus, a confiança que não se transfere — é a mesma frase levada mais a sério.
Cinco coisas passam a estar ao seu alcance. Escrever a definição formal de alfabeto e de cadeia, e decidir se um texto é cadeia sobre um alfabeto dado. Operar com linguagens como conjuntos, incluindo a razão de a potência zero conter a cadeia vazia. Escrever uma gramática de poucas regras que gere um conjunto infinito, derivar uma cadeia dela e desenhar a árvore. Situar uma linguagem na hierarquia pela memória que a máquina precisaria ter. E percorrer as seis fases dizendo, em cada uma, o que entra e o que sai.
A falta que fica é de representação. Tudo o que foi construído aqui guarda linguagens como listas de cadeias, e essa escolha morreu na conta do fecho de Kleene. Para materializá-lo foi preciso um teto de comprimento que a definição não pede — e o teto mente sobre o objeto. O que entra no lugar precisa de três coisas ao mesmo tempo. Descrever o conjunto sem enumerá-lo. Caber em espaço fixo. E decidir a pertinência de uma cadeia qualquer sem construir o conjunto todo.
A hierarquia já respondeu onde procurar: no degrau mais baixo, onde uma tabela finita decide sobre infinitas cadeias em tempo proporcional ao comprimento de cada uma.
1.8.1 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.
As três primeiras decisões do seu próprio projeto já cabem no que você tem em mãos, e nenhuma delas exige uma linha de código escrita.
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 bem 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.