flowchart LR
T["um mesmo arquivo<br/>de texto"] --> H["para quem escreveu:<br/>instruções a executar"]
T --> C["para o tradutor:<br/>dado a analisar"]
C --> V["não confia<br/>em nada"]
V --> D["desmonta<br/>em pedaços"]
D --> P["produz um artefato<br/>que executa"]
H -.->|"a pessoa completa,<br/>corrige e adivinha"| X["imprecisão<br/>tolerada"]
C -.->|"a máquina<br/>não adivinha"| Y["critério que responde<br/>sim ou não sempre"]
1 Linguagens formais e a arquitetura de um compilador — Resumo
Versão de revisão. Ela recupera o percurso inteiro depressa e não substitui a primeira leitura: as definições vêm na forma mais curta que ainda é correta, e as demonstrações longas ficam na versão completa deste capítulo e no capítulo do livro.
Abra um fonte qualquer e leia x = = 3. Você entende o engano em meio segundo e segue adiante. O tradutor percorre a mesma linha, não acha regra que case, e para. Nada mudou no arquivo. Mudou o leitor. Um lê instrução, o outro lê dado, e as duas leituras não combinam.
1.1 O mesmo arquivo, e dois leitores que não combinam
O tradutor não sabe o que você queria escrever, e é bom que não saiba.
Em 1952, num encontro da ACM, Grace Hopper apresentou um trabalho de título modesto: The Education of a Computer. O programa descrito ali chamava-se A-0 e rodava num UNIVAC I. Ele lia uma lista de chamadas escrita à mão. Procurava cada rotina numa fita magnética e montava o programa final na ordem pedida. Hopper batizou aquilo de compilador, no sentido de quem compila uma antologia. O nome pegou; a descrição do ofício, não.
O que sobreviveu daquele encontro foi a ideia por baixo do nome. O texto que uma pessoa escreve pode ser tratado como dado por outro programa. A frase parece inofensiva até alguém perguntar o que ela exige. Ela exige uma decisão sobre cada sequência de caracteres que se possa digitar, e o conjunto das admitidas quase sempre é infinito.
Repare no que isso faz com a palavra enquanto no meio do arquivo. Para quem escreveu, é uma ordem. Para o tradutor, são oito letras que casam com uma entrada de tabela. A ordem mora no significado, e ele não tem acesso a significado nenhum.
Quando o compilador recusa 3 x, 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 por acaso existe no seu programa e guarda outra coisa. A segunda aposta compila, roda e devolve um número errado, em silêncio.
Adivinhar sai barato na hora do palpite. A conta chega quando dois tradutores adivinham de modos diferentes. O mesmo arquivo passa a significar duas coisas, conforme a máquina. Recusar o palpite é o que torna a tradução reprodutível, e reprodutibilidade é a única propriedade que faz alguém confiar num compilador que não escreveu.
Separar o trabalho em fases tem a mesma raiz prática. Um sistema que decidisse tudo de uma vez encontraria o 3 de 3x, escolheria uma interpretação, avançaria para o x e voltaria atrás. Cada símbolo poderia disparar um retrocesso, e retrocessos se aninham. Em 1957, a equipe de John Backus entregou o compilador de FORTRAN na IBM sob a suspeita, então generalizada, de que código produzido por máquina seria lento demais para ser levado a sério. A otimização foi condição de aceitação, não acabamento, e Backus relatou o episódio em 1978. Um tradutor só é aceito quando o código que ele escreve aguenta comparação com o que a pessoa escreveria à mão.
1.2 Três degraus que cabem em meia página
Símbolo é aquilo que se decidiu não decompor.
A definição de símbolo incomoda por parecer circular, e é a única honesta. Nada num objeto o torna indivisível por natureza; o que fixa o degrau é a escolha de quem descreve. Uma letra é símbolo quando o alfabeto é o dos caracteres. Uma palavra classificada inteira é símbolo quando o alfabeto é o das unidades já separadas. A altura muda entre uma fase e a seguinte, dentro do mesmo sistema, e ninguém avisa a troca.
NotaAlfabeto e cadeia, no enunciado formal
Um alfabeto \Sigma é um conjunto finito e não vazio, cujos elementos são chamados símbolos. Uma cadeia sobre \Sigma é uma sequência finita a_1 a_2 \ldots a_n com a_i \in \Sigma para todo i, e n \geq 0. O número n é o comprimento da cadeia, escrito |w|.
Tome \Sigma = \{a, b\}. As cadeias aab e b estão sobre esse alfabeto, e a de comprimento zero também está. A cadeia abc fica de fora por um motivo único: c não pertence a \Sigma. A exigência de finitude paga uma conta concreta, porque a tabela de uma linha por símbolo precisa terminar de ser montada. O Unicode passa de cem mil símbolos — letras, hieróglifos egípcios, emojis — e continua sendo alfabeto, já que grande e infinito são coisas distintas.
Sobre cadeias há poucas operações, e todas devolvem cadeias. O comprimento conta posições, de modo que |aab| = 3. A concatenação cola a segunda logo depois da primeira, e não comuta. aa com b dá aab; b com aa dá baa. A cadeia vazia é o elemento neutro dessa colagem, e daí sai w^0 = \varepsilon pelo mesmo motivo pelo qual o produto vazio de números vale um.
O objeto que dá mais trabalho é perfeitamente definido e completamente invisível. Imprima \{\varepsilon, a, aa\} sem tratamento e a saída sai { , a, aa }. Quem lê conta dois elementos, conclui que há defeito de formatação e não desconfia de que o defeito está na leitura. O elemento não sumiu: foi impresso com o número exato de caracteres que tem. Enquanto a verificação disponível for contar elementos a olho, um formatador que apaga um deles contamina o diagnóstico de tudo o que veio antes.
Fixado o alfabeto, \Sigma^* reúne todas as cadeias sobre ele e é infinito sempre que houver ao menos um símbolo. O recorte \Sigma^n é sempre finito. Escreva \Sigma^3 sobre dois símbolos sem pular nenhuma: aaa, aab, aba, abb, baa, bab, bba, bbb. São oito, e a conta é |\Sigma|^n. Para comprimento 20 sobre o mesmo alfabeto são 2^{20} = 1.048.576 cadeias, cem vezes as dez mil combinações de um PIN de quatro dígitos. O comprimento rende mais que a variedade.
1.3 Uma linguagem é um conjunto, e conjuntos se combinam
NotaO enunciado formal de linguagem
Uma linguagem L sobre um alfabeto \Sigma é um subconjunto de \Sigma^*, isto é, L \subseteq \Sigma^*. Nenhuma outra exigência é feita: L pode ser vazia, finita ou infinita, e não precisa ter regra, padrão ou descrição finita.
Uma linguagem responde a uma pergunta de pertinência, e nada mais. Dada uma cadeia qualquer, ela está dentro ou fora? Ninguém exige que a resposta seja fácil de obter, nem que alguém saiba obtê-la. Sobre \Sigma = \{a, b\}, o conjunto \{a, ab\} é uma linguagem, o conjunto vazio é outra, e \{\varepsilon\} é uma terceira, distinta das duas anteriores.
Enquanto a linguagem for finita, representá-la é escrever o que a definição diz. É o que a Peneira, o sistema de referência deste percurso, faz neste ponto.
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;
}
Duas decisões moram ali, e só uma vem do conceito. Conjunto, em matemática, não tem ordem alguma; o conjunto ordenado do cabeçalho foi escolhido por reprodutibilidade, para que duas saídas se comparem lado a lado, e uma tabela de dispersão seria igualmente correta. Já a primeira linha do corpo da potência é a definição virando código: o acumulador nasce contendo a cadeia vazia.
flowchart LR
U["união<br/>isto ou aquilo"] --> F["conjunto finito<br/>continua finito"]
C["concatenação<br/>isto seguido daquilo"] --> F
C --> P["potência<br/>exatamente n vezes"]
P --> F
P --> K["fecho<br/>união de todas<br/>as potências"]
K --> I["conjunto infinito<br/>não cabe em memória"]
I --> S["a saída: guardar o critério,<br/>não as cadeias"]
A união traz as cadeias que estão em alguma das duas linguagens. O conectivo da definição é ou. Quem escreve depressa “as cadeias que estão nas duas” acabou de descrever a interseção. A concatenação toma uma cadeia de cada lado e as cola nessa ordem, fundindo as duas metades numa só. Duas linguagens de mil cadeias se unem em duas mil linhas e, concatenadas, pedem um milhão. Concatenar 40 cadeias com 25 produz no máximo mil, porque pares distintos podem gerar a mesma cadeia e num conjunto ela conta uma vez.
Trocar L^0 = \{\varepsilon\} por L^0 = \emptyset compila e roda. O conjunto vazio não tem com o que colar, então aniquila tudo o que multiplica, e o fecho devolve vazio para qualquer entrada. Siga o sintoma: você chama o fecho sobre \{a, b\}, recebe vazio, e a função do fecho está somando corretamente uma sequência de conjuntos vazios. O defeito mora três funções acima, numa inicialização de uma palavra.
O fecho de Kleene reúne todas as potências, da zero em diante, e produz infinito a partir de finito. Materializá-lo exige um teto de comprimento que a definição não pede, e o teto muda a resposta. Perguntada sobre uma cadeia longa, a implementação precisa dizer que ela ficou fora do recorte, e não fora da linguagem.
1.4 Ninguém guarda um conjunto infinito
Duas famílias de descrição finita — e, juntas, elas não alcançam quase nada.
Se a linguagem é infinita e a memória não é, guarda-se uma descrição em vez das cadeias. A dos identificadores válidos cabe em três linhas e decide qualquer cadeia apresentada, inclusive uma que ninguém jamais escreveu. Há duas famílias de descrição, separadas pelo verbo. Uma gera, dando regras que produzem cadeias. A outra reconhece, descrevendo uma máquina que lê e responde sim ou não.
A assimetria entre elas é permanente. Regras que geram são confortáveis para pessoas; máquinas que reconhecem são o que um processador executa. A ponte é mecânica, e existe algoritmo que converte uma na outra dentro de cada degrau. Você escreve na forma conveniente, a máquina executa na forma eficiente, e o programa que faz a travessia é o compilador.
NotaA gramática e a derivação, em notação
Uma gramática é uma quádrupla G = (V, \Sigma, P, S) em que V é um conjunto finito de não terminais, \Sigma é um alfabeto de terminais com V \cap \Sigma = \emptyset, P é um conjunto finito de produções da forma \alpha \to \beta com \alpha, \beta \in (V \cup \Sigma)^* e \alpha contendo ao menos um não terminal, e S \in V é o símbolo inicial.
Escreve-se \gamma \alpha \delta \Rightarrow \gamma \beta \delta quando \alpha \to \beta é uma produção de G, e \Rightarrow^* para o fecho reflexivo e transitivo de \Rightarrow. A linguagem gerada por G é L(G) = \{ w \in \Sigma^* : S \Rightarrow^* w \}.
flowchart TB
S["símbolo inicial"] -->|"aplica uma regra"| D["cadeia com terminais<br/>e não terminais"]
D -->|"aplica outra regra"| D2["cadeia só<br/>com terminais"]
D2 --> L["a cadeia pertence<br/>à linguagem gerada"]
D2 --> A1["árvore A<br/>a multiplicação mais fundo"]
D2 --> A2["árvore B<br/>a soma mais fundo"]
A1 --> R1["um resultado"]
A2 --> R2["outro resultado"]
R1 --> AMB["mesma cadeia,<br/>dois significados:<br/>a gramática é ambígua"]
R2 --> AMB
O menor exemplo que produz conjunto infinito tem duas regras: S \to aSb e S \to \varepsilon. Derive aaabbb escrevendo cada linha. De S vem aSb, depois aaSbb, depois aaaSbbb, e a segunda regra apaga o S. Perceba de onde sai o infinito. A primeira regra tem S dos dois lados da seta, e essa recursão pode ser aplicada sobre o próprio resultado. Retire-a e a gramática passa a gerar um conjunto finito, sempre.
A definição não pede que cada cadeia tenha uma única derivação. Uma gramática de expressões mal escrita deriva 2 + 3 * 4 de dois modos, um com a multiplicação mais fundo e outro com a soma, e os números que saem são 14 e 20. Gramática assim chama-se ambígua, e desfazer ambiguidade é trabalho do arco da análise sintática. Por ora basta reconhecer o sintoma: duas árvores para a mesma cadeia.
Falta a notação, e ela tem data. Em 1959, John Backus propôs uma forma de descrever a sintaxe do que viria a ser o ALGOL 60, e Peter Naur a adaptou ao editar o relatório oficial. Ela abrevia, e nada além disso. A barra vertical junta duas produções de mesmo lado esquerdo, o colchete marca o opcional e as chaves marcam a repetição. Escrever A \to [\,b\,] é escrever A \to b e A \to \varepsilon. O documento encurta; a linguagem gerada permanece idêntica.
Toda linguagem tem descrição finita? Não, e o “não” é mais forte do que parece. As descrições são textos finitos sobre alfabeto finito — gramática, máquina ou programa —, e enfileiram-se por comprimento, formando coleção enumerável. As linguagens são os subconjuntos de \Sigma^*, e o argumento diagonal de Cantor mostra que esses não se enfileiram. Para quase toda linguagem não existe gramática, máquina nem programa que a descreva. A descrição não está por descobrir: ela não existe, e isso é demonstrado.
1.5 A pergunta certa é de que memória a máquina precisa
Quatro classes, quatro máquinas, e um critério só para separá-las.
Em 1956, Noam Chomsky publicou nas IRE Transactions on Information Theory o artigo Three Models for the Description of Language. Ele era linguista, o alvo declarado era a linguagem humana, e computadores não entravam na conversa. O caminho que ele percorreu importa, porque o senso comum o inverte: Chomsky partiu das regras e foi restringindo a forma delas, e a correspondência com máquinas veio depois. As quatro classes se encaixam umas nas outras, e cada separação entre duas delas é um teorema com demonstração própria.
O que separa um degrau do seguinte não é o tamanho do alfabeto, nem o número de regras, nem a velocidade de coisa alguma. Uma gramática de degrau baixo pode ter centenas de regras. O critério é quanta memória a máquina precisa ter, e de que tipo é o acesso a ela. No degrau mais baixo está a máquina mais pobre que se pode imaginar. Ela lê um símbolo por vez e avança sempre para a frente. Toda a memória dela cabe em saber em qual de um número fixo de estados ela está. Quem só sabe em que estado está não sabe quantas vezes já entrou nele.
flowchart TB
E["uma máquina com k estados<br/>escolhidos antes de rodar"]
E --> P1["leu ( <br/>parou no estado q1"]
E --> P2["leu (( <br/>parou no estado q2"]
E --> P3["leu ((( <br/>parou no estado q3"]
E --> PN["leu ( repetido n vezes<br/>e n não tem teto"]
P1 --> C{"profundidades infinitas,<br/>estados em quantidade fixa"}
P2 --> C
P3 --> C
PN --> C
C -->|"duas delas, i e j,<br/>param no mesmo estado"| M["dali em diante a máquina<br/>não distingue i de j"]
M --> A["o fechamento certo para i<br/>é aceito também para j"]
A --> F["e a cadeia de j<br/>está desbalanceada"]
Essa frase vira argumento em três linhas. Fixe uma máquina de k estados e alimente-a com uma abertura de parêntese, depois duas, depois três. As profundidades são infinitas e os estados são k, então duas delas, chame-as i e j, terminam no mesmo lugar. Dali em diante a máquina não as distingue mais. Apresente i fechamentos: para uma das entradas a resposta certa é aceitar, para a outra é recusar, e ela responde a mesma coisa às duas. Existe entrada com mil aberturas e um único fechamento que essa máquina aceita, chegando ao fim perfeitamente confiante.
Acrescentar estados não resolve, por mais tentadora que a saída pareça. O argumento se refaz para qualquer k finito, e uma máquina de 101 estados reconhece outra linguagem, a dos balanceados até profundidade 100. O obstáculo é a finitude, e não o tamanho.
O degrau seguinte acrescenta uma pilha, e a peça é modesta a ponto de parecer insuficiente: lê-se e escreve-se apenas no topo, sem consultar o meio e sem contar sem desempilhar. Em troca, ela lembra uma quantidade sem teto, na ordem inversa em que os itens chegaram, que é a ordem em que fechamentos casam com aberturas. Em agosto de 1960, no Mathematisch Centrum de Amsterdã, Edsger W. Dijkstra e Jaap A. Zonneveld concluíram o primeiro compilador de ALGOL 60, e a implementação de recursão por pilha de registros de ativação vem dessa linhagem, exposta por Dijkstra em Recursive Programming, de 1960. A mesma peça reaparece em três alturas ao longo do percurso: memória do autômato, cadeia de chamadas do analisador, registro de ativação.
Diante de uma linguagem nova, o que essa máquina precisaria lembrar para decidir?
Acima da pilha há mais dois degraus, e nenhum deles aparece na construção de um compilador comum. A máquina de Turing é o poder do compilador, não o da linguagem compilada: o programa que traduz tem memória e laços, e a gramática que ele reconhece fica dois ou três degraus abaixo, por escolha.
1.6 Cada fase entrega um artefato, e a seguinte só sabe ler aquilo
flowchart TD
T["texto escrito<br/>por quem usa"] --> S["análise<br/>de símbolos"]
S -->|"sequência de símbolos<br/>classificados"| E["análise<br/>de estrutura"]
E -->|"árvore de<br/>decomposição"| G["análise<br/>de significado"]
G -->|"árvore verificada<br/>+ tabela de nomes"| M["emissão"]
M -->|"objeto"| X["execução"]
X --> R["saída sobre a<br/>entrada do domínio"]
subgraph ANALISE["metade que analisa"]
S
E
G
end
subgraph SINTESE["metade que sintetiza"]
M
end
Tome uma linguagem mínima, que chamo de Régua, em que se escreve uma condição sobre valores medidos e a ação a tomar quando ela vale. A primeira fase recebe o texto e devolve unidades classificadas: onde havia medida > 70 passa a haver um nome, um operador, um número e o fim da linha, cada item carregando a posição que ocupava no texto. Sem essa posição, nenhuma mensagem de erro adiante diz onde o problema mora. A segunda devolve uma árvore. Repare que é aqui que a precedência deixa de ser regra escrita e vira forma de objeto.
A terceira fase devolve a mesma árvore verificada, mais a tabela do que cada nome significa. Ela é a primeira que pode reclamar de algo sintaticamente perfeito. Comparar uma medida com um texto é impecável de gramática e sem sentido de significado. As três desmontam, e nenhuma precisa saber que máquina roda o resultado. O artefato de fronteira entre as duas metades é essa árvore verificada acompanhada da tabela de nomes, e nada atravessa em outro formato.
Note o que a metade seguinte enfrenta sozinha. Nenhuma máquina real oferece exatamente as operações que a linguagem oferece, e uma operação ausente não some do programa: vira uma sequência de operações que existem, mais longa e mais lenta. Essa distância é o que torna possível falar em qualidade de tradução, e comparar dois tradutores corretos exige medida — quantas instruções, quantos acessos à memória.
Entre as pontas existem artefatos que ninguém pediu, e pular um deles não faz o trabalho sumir: faz o trabalho migrar. Sobre o texto, perguntar se b * c já foi calculado exige achar todas as ocorrências e conferir se b ou c mudaram. Decomponha em t1 = b * c e t2 = a + t1, e a pergunta vira uma busca por atribuição com o mesmo lado direito. A forma é pobre por decisão, e a pobreza é o que torna o raciocínio mecânico.
Uma linguagem é compilada ou interpretada? A pergunta está mal formulada, porque as duas são propriedades de implementações, e a metade que analisa é idêntica nas três estratégias. Compilar traduz antes, uma vez só. O objeto entregue roda sem o tradutor por perto. Interpretar percorre a estrutura a cada execução, retomando toda vez decisões que a compilação tomaria uma só. A híbrida traduz antes para um formato próprio, executado por um programa que se comporta como máquina, e é ela que explica a máquina virtual no fim deste percurso. O que a máquina não faz, o tradutor faz por ela — e cobra em instruções.
1.7 O documento que se escreve antes da primeira linha de código
Especificar é sobretudo recusar.
A primeira coisa que se escreve de uma linguagem é um documento curto, sem uma linha de código dentro. Ele responde a quatro perguntas: sobre que domínio a linguagem fala, que classe de construções aceita, que forma tem o texto que alguém escreve nela, e o que o sistema produz ao processá-lo. Por que escrever primeiro, se o texto não roda? Porque cada resposta restringe todas as fases seguintes, e consertar uma ambiguidade enquanto ela é parágrafo leva dez minutos. Depois de quatro fases apoiadas nela, significa reescrever as quatro.
A segunda pergunta pesa mais que as outras. Escolher a classe de construções aceitas é escolher em que degrau da hierarquia o sistema opera e, portanto, que máquina será preciso construir. É o que a Peneira registra na própria especificação ao recusar retrovisores: um padrão com retrovisor sai da classe regular e não se compila para autômato finito. Ao dizer que um nome válido começa por letra, você acabou de dizer que 3x não vale e que o sistema não deve adivinhar o que a pessoa queria. Sem conjunto de textos admitidos caem juntas a gramática, a máquina reconhecedora, a mensagem de erro com posição e a própria noção de programa inválido.
A gramática que sai dessa primeira escrita quase nunca serve ao analisador, e a tentação é corrigi-la na hora. Não corrija: registre-a como saiu, feia, com recursão à esquerda e alternativas de prefixo comum. A comparação entre a forma de partida e a corrigida é a explicação mais eficiente sobre por que cada transformação é necessária. A forma final é sempre recuperável a partir das regras; a de partida, uma vez apagada, não volta.
flowchart LR
F["fonte do tradutor<br/>com a modificação"] --> B1["binário<br/>modificado"]
B1 -->|"compila o próprio<br/>fonte do tradutor"| B2["binário novo,<br/>ainda modificado"]
F2["fonte limpo<br/>modificação removida"] --> B2
B2 --> P["todo programa compilado<br/>sai sabotado"]
B2 -->|"e a próxima geração<br/>também"| B2
P --> L["a leitura do fonte<br/>não revela nada"]
Falta uma cena, e ela desloca a pergunta. Em agosto de 1984, ao receber o Prêmio Turing, Ken Thompson descreveu nas Communications of the ACM um experimento que ninguém esperava ouvir numa premiação. Um compilador pode ser modificado para inserir uma porta dos fundos em todo programa que traduz. E essa modificação pode desaparecer do fonte do próprio compilador. Compile o compilador modificado, guarde o binário e apague as modificações do fonte. O que sobra é um fonte limpo e auditável, enquanto o binário guardado continua sabotando e sabendo se reproduzir. Ler o binário não fecha a brecha, porque o desmontador também é um programa que alguém compilou.
Deixa de fazer sentido perguntar apenas o que um programa faz. A resposta depende de quem o traduziu e do que aquele tradutor sabia, que é a consequência que Grace Hopper não podia antever em 1952, enunciada 32 anos depois num discurso de premiação. Fica daqui o critério que o seu grupo leva para a especificação da linguagem própria. Diante de qualquer pergunta sobre o que um reconhecedor consegue fazer, não olhe o tamanho do texto nem a aparência da entrada. Pergunte de que memória a máquina precisaria, e de que tipo é o acesso a ela.