%%{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 — Resumo
Versão de revisão. Ela recupera o percurso inteiro depressa e não substitui a primeira leitura. As definições aparecem aqui na forma mais curta que ainda é correta. As demonstrações longas ficam na versão completa deste capítulo e no capítulo do livro.
Um arquivo com x = 3 * y guarda nove caracteres, e é só isso que o disco sabe dele. Um programa que conte bytes devolve nove e vai embora satisfeito. Outro toma os mesmos nove caracteres como uma ordem, e aí precisa descobrir se y existe e que tipo ele guarda. Entre uma leitura e a outra há um abismo. Atravessá-lo é o assunto destas páginas.
1.1 O mesmo arquivo, e dois leitores que não combinam
O tradutor sabe que o seu texto está errado; o que você queria escrever, ele não sabe.
Em 1952, num encontro da ACM, Grace Hopper apresentou 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 A-0 não analisava coisa alguma. O nome pegou; a descrição do ofício, não.
O texto que uma pessoa escreve pode ser tratado como dado por outro programa. Foi essa a ideia que sobreviveu. Um programa que conte os caracteres de total = preco * quantidade devolve 26, e outro que conte palavras devolve cinco. Nenhum dos dois precisa saber o que é uma atribuição. 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 dos dois lados? Nenhuma dessas respostas está no arquivo.
Aí está 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 conjunto ninguém escreveu por extenso, e ele é infinito. O arquivo é o dado; a linguagem é a regra que separa os aceitos dos recusados.
E a travessia não é uma passada só. Leia 3x, um caractere por vez. No 3 já houve decisão: começou um número. Aí chega o x, e o caractere seguinte acaba de invalidar a decisão do anterior. Não há como voltar no tempo. Há como voltar na posição da leitura e tentar outra hipótese.
O tradutor recusa 3x. O que exatamente ele acabou de descobrir?
Ele sabe que aquele texto não pertence à linguagem. Não sabe o que você queria escrever. Um tradutor generoso apostaria em 3 * x; outro apostaria em x3, nome que talvez exista no seu programa e guarde outra coisa. A segunda aposta compila, roda e devolve um resultado errado, com a mesma confiança de um resultado certo.
Recusar e dizer onde é a escolha que atravessa a área inteira. Ela obriga a projetar a linguagem antes da primeira linha de código. Toda construção aceita precisa estar prevista. Toda recusada precisa cair fora por uma razão escrita no critério. “Parece um engano” não serve de razão.
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. Pairava a suspeita, então generalizada, 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, e não como acabamento. Backus registrou o clima em The History of FORTRAN I, II, and III, publicado pela ACM SIGPLAN em 1978. 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 quais variáveis voltam a ser usadas adiante e quais laços rodam muitas vezes. 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.
1.2 Vinte rodinhas, duas letras e um milhão de senhas
Um repertório pequeno e fechado, combinado livremente, produz mais textos do que qualquer lista alcança.
Grave só duas letras, a e b, em cada uma das vinte rodinhas de um cadeado de segredo. Ele passa a aceitar 2^{20} senhas, 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 o repertório tinha duas letras. Veja só o tamanho da desproporção.
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\}, a cadeia abba tem comprimento 4, 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. Duas exigências, em compensação, passam despercebidas e cobram depois: que \Sigma seja não vazio, e que o comprimento admita zero. Num sistema real o alfabeto costuma ser derivado, e 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.
Sobre cadeias há poucas operações. O comprimento devolve um número natural. A concatenação emenda w com v e devolve uma cadeia, e não um par nem uma lista de duas. Com w = \texttt{aab} e v = \texttt{ba} sai aabba, e |wv| = |w| + |v| em qualquer caso. A operação é associativa e não é comutativa.
A potência repete a concatenação, de modo que w^3 é aabaabaab. No expoente zero, repetir zero vezes é não repetir, e w^0 é a cadeia sem símbolo algum. Falta a operação que mais aparece em código real: perguntar se uma cadeia é prefixo de outra. É assim que uma máquina reconhece texto sem ter lido a entrada toda.
Essa cadeia de comprimento zero tem nome, \varepsilon, e é a fonte mais produtiva de defeito silencioso deste ponto do percurso. Ela pertence a todo alfabeto e é o elemento neutro da concatenação. O estrago aparece na impressão. 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. Uma linha do formatador resolve o caso, imprimindo o símbolo no lugar da cadeia vazia.
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.
%%{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
Fixado o alfabeto, o conjunto de todas as cadeias sobre ele chama-se \Sigma^*, 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 quatro cadeias; comprimento 3 tem oito. Cada andar tem 2^n elementos, todo andar é finito, e não existe último andar. Como cada andar é finito, \Sigma^* pode ser enfileirado, e toda cadeia sobre \Sigma aparece nessa fila em posição finita.
Guarde a fila. Ela volta na conta mais desconfortável deste capítulo.
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.
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.
A definição cabe em oito palavras e é mais permissiva do que quase todo mundo espera. O conjunto \{a, ab\} são duas cadeias escolhidas a dedo, sem nada em comum além do conjunto, e é linguagem legítima. Nada obriga uma linguagem a ter regra, nem a existir uma frase em português que a descreva, nem a existir programa que decida a pertinência. As duas degeneradas marcam a fronteira: \emptyset recusa toda entrada, e \{\varepsilon\} aceita apenas a entrada sem caracteres.
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.
Confira tudo a olho com L_1 = \{a, ab\} e L_2 = \{b, \varepsilon\}. A união dá \{a, ab, b, \varepsilon\}, e o “ou” da definição é inclusivo. Quem lê depressa o troca por um “e” e transforma a operação em interseção, que aqui é vazia. A concatenação manda formar todos os pares, um de cada conjunto, e emendar cada par numa cadeia. Saem quatro pares e três cadeias distintas, porque ab apareceu 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. Enquanto a linguagem for finita, representá-la em memória é direto, e as duas operações cabem num punhado de linhas. É assim que a Peneira, o sistema de referência destas páginas, guarda linguagens neste ponto do percurso.
01_linguagem.h
// Uma cadeia é uma sequência finita de símbolos. Usamos std::string porque o
// alfabeto da Peneira é de caracteres; a cadeia vazia é a string vazia.
using Cadeia = std::string;
// Conjunto ordenado para que a saída seja determinística — em demonstração, uma
// ordem que muda a cada execução tira do leitor a chance de comparar dois resultados.
using Alfabeto = std::set<char>;
using Linguagem = std::set<Cadeia>;
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;
}
Perceba o acumulador da potência. Ele começa em \{\varepsilon\} e é concatenado com L uma vez por nível, então o nível um devolve o próprio L, porque \varepsilon é neutro. Troque a inicialização por \emptyset e refaça a conta. Não há elemento no primeiro conjunto, logo não existe par nenhum. A função devolve vazio em todo expoente. A concatenação com o conjunto vazio aniquila; a concatenação com o conjunto que contém a cadeia vazia preserva. É a aritmética de sempre, com conjuntos no lugar de números. E L^0 = L também está errado, porque aplica ao conjunto a regra do expoente um.
%%{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 fecho, que leva o nome de Stephen Kleene, reúne todas as potências sem teto, e é aí que a representação explícita morre. Materializá-lo é impossível sempre que L tem alguma cadeia não vazia. A saída é limitar por fora, com um comprimento máximo que a definição não pede. Há uma segunda parada, mais sutil: cada nível precisa descartar as cadeias já vistas. Sem esse descarte o laço roda sem fim, mesmo com o teto aplicado.
Faça a conta pequena, porque ela serve de teste. Com L = \{a, b\} e teto no comprimento três, saem 15 cadeias. São uma de comprimento zero, duas de comprimento 1, quatro de comprimento 2 e oito de comprimento 3. 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.4 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 produz cadeias por aplicação de regras. A segunda reconhece: recebe uma cadeia pronta e responde sim ou não. O lado gerador chama-se gramática; o reconhecedor chama-se máquina e, nos degraus mais baixos, cabe numa tabela de estados.
%%{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
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. O preço são as restrições da classe em que a conversão funciona.
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, com terminais \{a, +, (, )\}, não terminais \{E, T\} e símbolo inicial E.
Quinze símbolos escritos, e o que eles produzem não acaba: a, a+a, (a), ((a)), (a+a)+a, sem teto. O infinito entra por duas portas, e 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. Derivar (a+a) leva seis passos nessa gramática, e a ordem em que as regras foram aplicadas 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.
Leia as folhas da esquerda para a direita e você obtém o texto; leia os nós internos e você obtém a estrutura. O parêntese e o + não estão soltos: 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. Aí a gramática é ambígua, assunto de capítulo próprio adiante.
Escrever gramáticas por extenso cansa. Em junho de 1959, John Backus propôs uma notação compacta para a sintaxe de uma linguagem. Foi no congresso internacional de processamento de informação, em Paris. Peter Naur a adaptou ao editar o Report on the Algorithmic Language ALGOL 60. O relatório saiu nas Communications of the ACM, no volume 3, número 5, de 1960. As abreviações mais comuns são a alternativa e a repetição, e elas não acrescentam poder de expressão nenhum. Encurtam o documento e se desfazem na implementação. Diante de uma gramática abreviada, expanda as abreviações antes de decidir a que classe ela pertence.
Falta o ponto desconfortável. A definição de linguagem não exige regra nem descrição, e uma gramática é um texto finito. Todo subconjunto de \Sigma^* tem alguma descrição? A resposta é não. Toda gramática, toda máquina e todo programa é um texto finito, e textos finitos entram naquela fila de antes, cada um em posição finita.
Já os subconjuntos de um conjunto infinito enumerável não se enfileiram. Georg Cantor demonstrou isso pelo argumento hoje chamado diagonal. Tome uma fila qualquer e construa o conjunto D que decide cada cadeia pela regra oposta à da linguagem correspondente. Ele difere de todas elas. E não está na fila. 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.
A consequência prática é grande e costuma passar batido. Toda linguagem que você projetar cai 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.
1.5 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.
Em 1956, Noam Chomsky publicou nas IRE Transactions on Information Theory o artigo Three Models for the Description of Language. Ele era linguista, e o alvo era a língua natural. A hierarquia que leva o seu nome não foi proposta para orientar o projeto de compiladores. As quatro classes saíram de restrições na forma das regras; a correspondência com máquinas veio depois. A direção costuma ser contada ao contrário, como se alguém tivesse partido 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, e 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, e o tipo 0 é o irrestrito, com a máquina de Turing. O critério que separa um degrau do seguinte é um só: quanta memória a máquina precisa ter, e de que tipo é o acesso a ela. Tamanho do alfabeto, número de regras e velocidade ficam de fora.
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 no fim responde sim ou não. 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 os parênteses balanceados: () está na linguagem, (()) está, e (() não está. Suponha um autômato finito de k estados, fixado antes de qualquer entrada chegar, e alimente-o com uma abertura, duas, três, até k+1. São k+1 leituras para k estados, então duas profundidades i e j terminam no mesmo estado. Complete as duas com i fechamentos: a primeira fica balanceada, a segunda não fica, e as duas recebem a mesma resposta. O obstáculo está na finitude, e não no tamanho — acrescentar estados apenas refaz o argumento com o novo k. E observar que nenhum programa real aninha mais de vinte níveis troca a pergunta formal pela estatística de uso.
O saldo desta seçã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.
O degrau seguinte acrescenta uma pilha, e ela é pobre de propósito: escreve-se no topo, lê-se o topo, remove-se o topo. Não há consulta ao meio nem contagem de itens guardados. É essa pobreza que a faz servir, porque o problema dos parênteses tem a forma de uma pilha. Sobre (()) ela esvazia no fim, e a entrada é aceita. Sobre (() a última remoção não acontece e sobra uma marca. Sobre ()) a máquina tenta remover de uma pilha vazia, e recusa ali mesmo. A memória cresce com a entrada, e é 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. O próprio Dijkstra a expôs em Recursive Programming, publicado na Numerische Mathematik em 1960. A recursão só é barata porque alguém decidiu guardar o retorno numa pilha.
A mesma peça reaparece três vezes ao longo do percurso. Primeiro como memória do autômato do segundo degrau. Depois como cadeia de chamadas de um analisador feito de procedimentos que chamam uns aos outros. Por fim como registro de ativação na memória que executa o programa traduzido.
Três ofícios, um objeto só.
Os dois degraus de cima estas páginas nomeiam e não usam. No tipo 1 as produções podem ter mais de um símbolo à esquerda, 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 sobre as quais a máquina não para nunca.
Nenhuma fase de um tradutor real precisa deles, e essa observação reorganiza o mapa. Declarar antes de usar, casar tipos numa atribuição e conferir o número de argumentos parecem exigir sensibilidade ao contexto. 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.
1.6 Cada fase entrega um artefato, e a seguinte só sabe ler aquilo
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. O que define uma fase é o par formado pelo que ela consome e pelo que devolve. O nome de cada uma é o menos importante.
%%{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. 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. Acompanhe a linha da primeira seção atravessando as seis, supondo que total e preco guardem reais e 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 = t2Repare no que aconteceu entre a terceira linha e a quarta. Nenhum símbolo do texto original mudou, e 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 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 desmontam. Essa metade é a única que pode recusar: símbolo desconhecido, parêntese que não fecha, variável usada sem declaração, tipos incompatíveis. Também é a única que conhece a forma do texto original, e nada disso sobrevive à fronteira. Por isso a mensagem de erro precisa ser emitida ali, 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. A fronteira entre as metades é a árvore verificada, e nada a atravessa em outro formato. A síntese é a única metade que conhece a máquina de destino. É aí que ela encontra o problema que define o ofício. Nenhuma máquina real oferece exatamente as operações que a linguagem oferece. Uma construção que a máquina não realiza diretamente vira uma sequência de operações que ela realiza.
Entre as duas pontas existem artefatos que ninguém encomendou. O fluxo de símbolos responde onde termina cada unidade de significado, e é nessa passagem que espaço em branco e comentário desaparecem. A árvore responde a que construção cada símbolo pertence, com a precedência já resolvida pelo encaixe. A tabela de nomes responde ao que um nome significa, e é a única das três sem forma de sequência nem de árvore.
Suprimir uma delas não faz a pergunta sumir. Sem o fluxo, toda regra da gramática precisa saber pular espaços. Sem a árvore, a verificação de tipos acontece antes de o lado direito ter sido lido inteiro. Sem a tabela, consultar um identificador vira varredura do texto. O custo total passa a crescer com o quadrado do tamanho do programa. Declará-las também cobra, e o preço se paga na sincronia. A posição de um símbolo nasce na análise léxica. Não interessa à sintática, e volta a ser indispensável na mensagem de erro da semântica.
E 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 é de quem constrói a implementação. Numa ponta a tradução acontece antes, uma vez só, e quem executa é o processador físico. Na outra não há tradução. Um programa percorre a estrutura do que você escreveu e executa cada pedaço na hora. Cada operação custa duas coisas: o trabalho dela própria, e o de descobrir qual operação é.
O meio do eixo é o lugar mais povoado. A tradução acontece antes, uma vez, e o alvo é uma representação que uma máquina virtual executa. Em troca, essa máquina precisa existir em toda plataforma onde o programa deva rodar. Note a armadilha de vocabulário: enquanto traduz, o sistema não executa nada do que está escrito no arquivo. O que a máquina não faz, o tradutor faz por ela — e cobra em instruções.
1.7 O item mais consequente de uma especificação é uma recusa
Antes de existir uma linha de código de um tradutor, alguém escreve o que a linguagem aceita. 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. “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.
%%{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
Pense comigo no caso que a Peneira decidiu. 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. Aceitá-la sai da classe das linguagens regulares, porque comparar duas quantidades que crescem sem teto é o que a memória finita não faz. 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 a construção e custa a explicação; compra a garantia de que todo padrão escrito na linguagem tem uma máquina finita correspondente.
Duas cautelas fecham o documento de decisão. A primeira: a gramática de uma linguagem nova sai, na primeira escrita, com recursão à esquerda e com alternativas que começam pelo mesmo símbolo. Há transformações mecânicas que eliminam as duas propriedades. Guarde a forma de partida antes de aplicá-las. Sem o original resta o resultado, e o resultado sozinho parece convenção arbitrária de escrita.
A segunda cautela desfaz uma confusão que erra nos dois sentidos. O texto de uma expressão de padrões tem parênteses que se aninham sem teto. Isso o põe no degrau livre de contexto. Já o conjunto de cadeias que aquela expressão descreve é regular. Uma coisa é ler a descrição; outra é decidir sobre o que ela descreve.
1.8 Ler o fonte deixou de responder à pergunta
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 não usa nada além do que estas páginas montaram. 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 é ofício da análise; emitir código é da síntese. Depois, o mesmo tradutor é modificado para reconhecer o próprio fonte dele e reinserir as duas modificações no binário que produz.
Por fim, as modificações são apagadas do fonte, que volta a estar limpo. E o binário compilado a partir dele continua contaminado, porque quem o compilou foi o binário anterior.
O que sobra é um deslocamento de pergunta. Ler o fonte deixa de responder o que o binário faz e passa a responder apenas o que o autor escreveu. Desmontar o binário também não adianta, porque o desmontador é um programa e alguém o compilou. Trinta e dois anos separam essa palestra do encontro de 1952 em que Hopper propôs tratar como dado o texto que uma pessoa escreve. 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.
A falta que fica é de representação. Tudo o que foi construído aqui guarda linguagens como listas de cadeias. 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á disse onde procurar. É no degrau mais baixo, onde uma tabela finita decide sobre infinitas cadeias em tempo proporcional ao comprimento de cada uma.