flowchart TB
subgraph distancia["Eixo 1 — distância semântica entre fonte e alvo"]
direction LR
M["montador<br/>correspondência quase um para um"] --> T["tradutor entre linguagens<br/>de alto nível"] --> C["compilador para<br/>código de máquina"]
end
subgraph tempo["Eixo 2 — quando a execução acontece"]
direction LR
AN["análise antes,<br/>execução depois"] --> CO["compilação"]
AF["análise e execução<br/>no mesmo momento"] --> IN["interpretação"]
end
distancia --> HIB["sistemas híbridos<br/>compilam para máquina virtual<br/>e interpretam o resultado"]
tempo --> HIB
1 Módulo 1: Panorama da Compilação e Linguagens Formais
Bem-vindo ao primeiro módulo. Aqui eu não vou lhe ensinar a operar nada — vou lhe dar um mapa. Ao fim desta leitura você deve conseguir olhar para qualquer assunto do curso e dizer, antes de estudá-lo, onde ele se encaixa e a que pergunta responde. Parece pouco. Não é: quem sabe situar aprende os detalhes numa fração do tempo de quem os coleciona soltos.
1.1 O problema: três programas defeituosos
Quero começar com três programas quebrados, porque a diferença entre eles contém tudo o que vem depois.
O primeiro esqueceu um ponto e vírgula. Você compila e a resposta vem na hora, específica a ponto de soar mal-educada: linha 42, coluna 17, esperava-se um ponto e vírgula. O segundo está impecavelmente pontuado, mas tenta somar um texto a um número; a reclamação demora um pouco mais, usa outro vocabulário e aponta para a operação inteira, não para um caractere. O terceiro está pontuado e tipado sem nenhuma falha, e entra num laço que nunca termina. O compilador não diz nada, gera o executável, avisa que correu tudo bem — e o problema só aparece quando alguém roda o programa e espera. E espera.
Três defeitos, três destinos. O primeiro é de forma: o texto não obedece às regras de composição da linguagem, e isso se descobre olhando só a sequência de símbolos, sem fazer ideia do que o programa significa. O segundo é de sentido: a forma está certa, mas a combinação de partes válidas produz algo sem significado atribuível, e para pegá-lo o compilador precisa ter construído alguma representação do que cada nome denota. O terceiro não é detectável — e não por preguiça de quem escreveu o compilador: é impossível, com demonstração matemática.
Olha o que acabou de acontecer: para explicar três reações diferentes a três programas quebrados, eu precisei de uma noção de forma, de uma noção de significado e de um teorema de indecidibilidade. Um compilador é um dos poucos lugares em que teoria da computação encosta em engenharia de software com essa proximidade, e é nessa fronteira que você vai passar o semestre.
Antes de seguir, quero ser explícito sobre o que este livro pressupõe, porque é a informação que permite a você decidir se precisa revisar alguma coisa antes de continuar.
Pressuponho fluência em uma linguagem de programação com tipos, ponteiros ou referências e alocação explícita ou automática de memória — o suficiente para ler e escrever funções recursivas sem hesitação. Pressuponho familiaridade com as estruturas de dados que atravessam todo compilador: pilhas, filas, tabelas de dispersão, árvores e a travessia recursiva delas. Pressuponho a noção de grafo, de caminho em um grafo e de percurso em profundidade, que reaparecem sob nomes diferentes na análise de fluxo. E pressuponho o vocabulário elementar de conjuntos e relações — união, interseção, produto cartesiano, relação de equivalência, fecho transitivo —, porque as definições formais deste livro são escritas nesses termos.
O que não pressuponho é experiência anterior com teoria de linguagens formais, com autômatos ou com qualquer ferramenta de geração de analisadores. Tudo o que for necessário desses assuntos é construído aqui, do início, e construído no ponto em que passa a ser necessário. Se você já viu expressões regulares apenas por imitação, copiando padrões que funcionavam em ferramentas de busca, esse é exatamente o ponto de partida que o capítulo seguinte assume — e uma das suas funções é mostrar que havia uma teoria por baixo daquilo.
1.2 O que significa compilar
Um compilador é um programa que lê programas. A entrada não é um dado no sentido usual: é outro programa, um objeto que também tem comportamento — e a saída também. O compilador transforma comportamento em comportamento, preservando o significado no meio do caminho.
Formalizando: dadas a linguagem-fonte L_f e a linguagem-alvo L_a, um tradutor é uma função parcial T que associa a cada programa p \in L_f ou um programa T(p) \in L_a, ou um conjunto não vazio de diagnósticos explicando por que p não é traduzível. A função é parcial de propósito, porque nem todo texto é um programa e o tradutor tem obrigação de dizer isso em vez de produzir lixo; e a falha devolve diagnósticos no plural, porque quem reporta só o primeiro problema é praticamente insuportável. Escrevendo \llbracket p \rrbracket_{L}(x) para o resultado de executar p sobre a entrada x, a condição de correção é esta igualdade:
\llbracket T(p) \rrbracket_{L_a}(x) = \llbracket p \rrbracket_{L_f}(x).
Guarde essa linha. É o contrato que você assume, sem pensar, toda vez que compila — e é o contrato que a otimização coloca sob pressão, porque otimizar é trocar um programa por outro mais rápido mantendo a igualdade. Uma transformação que altera o resultado num único caso de borda não é otimização agressiva; é defeito.
Pare e pense. Se um compilador aceitasse todo texto que recebe e sempre produzisse algum executável, seria melhor ou pior do que um que recusa coisas? Antes de responder, pergunte-se o que ele faria com o programa que esqueceu o ponto e vírgula.
Agora as duas grandes estratégias de executar um programa que a máquina não entende diretamente. Um compilador é um tradutor cujo alvo é executável por alguma máquina, real ou virtual: ele não executa p, produz T(p), que roda depois. Um interpretador recebe p e a entrada x e produz o resultado direto, sem gerar programa intermediário nenhum. A diferença cabe numa palavra: quando.
A análise é paga uma vez e amortizada por todas as execuções futuras, e o programa inteiro é examinado antes de começar, o que revela erros em trechos que nunca seriam alcançados. Em compensação, o código gerado precisa servir para todos os valores possíveis: o compilador não sabe qual ramo será tomado nem que tipo dinâmico um objeto terá.
O custo da análise é pago a cada execução — às vezes a cada iteração de um laço, porque a mesma construção é reexaminada a cada passagem. É a origem estrutural da diferença de desempenho. A contrapartida é informação: rodando, o interpretador sabe o valor de cada variável e o tipo real de cada objeto, e por isso tolera linguagens muito dinâmicas.
Um compilador traduz para instruções de uma máquina virtual, e um interpretador dessa máquina executa o resultado — as duas coisas ao mesmo tempo, porque as definições falam de objetos diferentes. Se o sistema ainda compilar de verdade, em execução, os trechos mais quentes, soma a partida rápida da interpretação ao desempenho da compilação.
E há os parentes. Um montador é um tradutor cuja fonte já corresponde, um para um, às instruções da máquina; formalmente é um compilador, e o nome separado se justifica porque nenhuma dificuldade interessante aparece — não há instrução a escolher nem registrador a alocar, porque quem escreveu o fonte já fez as duas coisas. Um tradutor entre linguagens de alto nível tem como alvo outra linguagem de alto nível, e por isso precisa preservar estrutura, nomes e formatação, enquanto um compilador para código de máquina pode dissolver um laço em desvios condicionais sem culpa.
Não decore essas fronteiras: elas formam um continuum de duas dimensões independentes. Diante de um sistema híbrido, a pergunta produtiva não é “isso é compilador ou interpretador?”, e sim “o que foi decidido antes da execução e o que foi adiado?”.
1.3 O compilador por dentro: as fases
Um compilador completo é grande, e a forma consagrada de domar esse tamanho é dividi-lo em fases — mas o pior resultado possível é você decorar seis nomes. Uma fase se define pelo que recebe, pelo que produz e pela sua responsabilidade de verificação, isto é, o conjunto de erros que só ela tem condições de detectar. Essa terceira componente é a que mais ajuda na prática: em dúvida sobre onde colocar uma checagem, pergunte qual é a primeira fase que dispõe da informação necessária.
flowchart LR
A["texto-fonte<br/>sequência de caracteres"] --> B["análise léxica"]
B --> C["sequência de tokens"]
C --> D["análise sintática"]
D --> E["árvore sintática"]
E --> F["análise semântica"]
F --> G["árvore anotada<br/>e tabela de símbolos"]
G --> H["geração intermediária"]
H --> I["representação intermediária"]
I --> J["otimização"]
J --> I
I --> K["geração de código"]
K --> L["código da máquina-alvo"]
subgraph analise["Análise (frente)"]
B
C
D
E
F
G
end
subgraph sintese["Síntese (retaguarda)"]
H
I
J
K
end
A análise léxica recebe caracteres e produz unidades léxicas. É ela que decide que pattern é uma palavra e não sete letras, que 123.45 é um número e não dois com um ponto no meio, e que espaços e comentários vão para o lixo. Um lexema é a subcadeia reconhecida como unidade indivisível; um token é o par formado pela categoria atribuída a esse lexema e pelos seus atributos, entre os quais está sempre a posição no texto — insisto nesse “sempre”, porque todas as fases seguintes precisarão reportar erros e o único lugar onde a posição existe naturalmente é aqui. A fase existe separadamente porque a estrutura interna dos elementos léxicos cabe num formalismo mais fraco e num mecanismo mais rápido.
A análise sintática recebe tokens e produz uma árvore que exibe a estrutura hierárquica do programa: decide que a multiplicação se agrupa antes da soma, reconhece que um bloco aberto foi fechado, descobre que faltou o ponto e vírgula porque a sequência de tokens não deriva da gramática. A partir dela o programa deixa de ser texto e passa a ser estrutura. A análise semântica devolve a mesma árvore anotada, mais uma tabela de símbolos preenchida — é a fase do meu segundo programa defeituoso. O adjetivo é generoso: ela não verifica que o programa faz o que o programador queria, e sim condições de boa formação dependentes de contexto, do tipo “todo nome usado precisa ter sido declarado”.
Depois da análise vem, em muitos compiladores, uma representação intermediária, independente da linguagem-fonte e da máquina-alvo. À primeira vista é trabalho a mais; o argumento a favor é combinatório. Para suportar m linguagens e n máquinas sem ela, você precisa de m \times n tradutores; com ela no meio, de m + n peças — com dez de cada lado, a diferença entre cem e vinte.
A economia não é só de contagem
O ganho maior é de manutenção. Um defeito na análise de uma linguagem se corrige num lugar só e beneficia todas as máquinas; uma otimização escrita sobre a representação intermediária vale para todas as linguagens de entrada. É por isso que uma linguagem nova nasce já com bom código gerado para dezenas de arquiteturas.
A otimização transforma representação intermediária em representação intermediária, com o mesmo significado e melhor desempenho. O nome é infeliz: nenhum otimizador produz o programa ótimo, porque encontrá-lo é indecidível. Aplicam-se transformações que em média melhoram e que jamais podem alterar o resultado. A geração de código se decompõe em três subproblemas entrelaçados — que instruções realizam cada operação, em que ordem emiti-las e que valores ficam em registradores —, e é a interação entre eles que a mantém difícil.
| Fase | Recebe | Produz | Detecta |
|---|---|---|---|
| Análise léxica | caracteres | tokens | símbolo desconhecido, literal malformado |
| Análise sintática | tokens | árvore sintática | estrutura inválida, delimitador não fechado |
| Análise semântica | árvore sintática | árvore anotada e tabela de símbolos | nome não declarado, tipo incompatível |
| Geração intermediária | árvore anotada | representação intermediária | — |
| Otimização | representação intermediária | representação intermediária | — |
| Geração de código | representação intermediária | código da máquina-alvo | recurso insuficiente na máquina |
As seis fases se agrupam em duas metades separadas pela representação intermediária: a análise vai do texto até uma representação verificada, a síntese vai dela até o executável. A assimetria raramente é dita. A análise é reconhecimento, com teoria madura, algoritmos ótimos e ferramentas que geram código a partir de especificação declarativa; a síntese é otimização combinatória, com subproblemas difíceis no caso geral. Se você sentir, na segunda metade do curso, que o tom muda, é o objeto que mudou.
Duas responsabilidades não pertencem a fase nenhuma e são usadas por todas: a tabela de símbolos, que associa a cada nome declarado o que se sabe sobre ele e precisa refletir os escopos da linguagem, e o tratamento de erros. Vale ainda distinguir fase, unidade lógica definida pelas interfaces, de passagem, unidade física que é uma travessia completa da representação: uma não determina a outra, e o léxico costuma entregar um token por vez sob demanda do sintático, o que dá duas fases numa travessia só.
A recuperação de erro tem risco próprio. Depois de um erro, o compilador está num estado que não corresponde a programa válido nenhum, e o que ele reportar em seguida pode ser consequência do primeiro problema. Erros em cascata escondem o problema verdadeiro no meio do ruído.
1.4 Um recorte histórico, com datas
Tenho impaciência com frases do tipo “no início da computação, programava-se em linguagem de máquina”: são verdadeiras e não ensinam nada, porque não dizem quando nem quem.
flowchart LR
subgraph teoria["Linha da teoria"]
direction LR
TU["1936 · Turing<br/>modelo de computação<br/>e indecidibilidade da parada"] --> CH["1956 · Chomsky<br/>três modelos de descrição"]
CH --> CH2["1959 · Chomsky<br/>propriedades formais das gramáticas"]
CH2 --> RS["1959 · Rabin e Scott<br/>autômatos finitos e decisão"]
end
subgraph engenharia["Linha da engenharia"]
direction LR
HO["início dos anos 1950<br/>Grace Hopper · A-0 no UNIVAC I"] --> FO["1957 · Backus e equipe<br/>FORTRAN no IBM 704"]
FO --> AL["ALGOL 60 · notação de Backus e Naur<br/>sintaxe publicada como gramática"]
AL --> KN["1965 · Knuth<br/>tradução da esquerda para a direita"]
KN --> TH["1968 · Thompson<br/>expressão regular em autômato"]
TH --> BE["anos 1970 · Unix<br/>geradores de analisadores"]
end
CH2 -.-> AL
RS -.-> TH
Dois marcos dizem quase tudo. O compilador de FORTRAN entregue em 1957 para o IBM 704 tinha o objetivo declarado de gerar código competitivo com o que um bom programador escreveria à mão, e boa parte do esforço foi em otimização — que nasceu, portanto, junto com a compilação. E o relatório de ALGOL 60 publicou pela primeira vez a sintaxe de uma linguagem como gramática formal, tornando possível gerar automaticamente partes do compilador. Repare no encontro das duas linhas: a ordem em que este curso apresenta os assuntos é a ordem em que os problemas foram resolvidos.
1.5 O mapa teórico: gramáticas, linguagens e máquinas
A pergunta que organiza este andar de abstração é: dada uma classe de linguagens, que máquina é necessária e suficiente para reconhecê-las?
Os objetos elementares primeiro. Um alfabeto \Sigma é um conjunto finito e não vazio de símbolos; uma cadeia sobre \Sigma é uma sequência finita de símbolos de \Sigma, sendo \varepsilon a de comprimento zero; e \Sigma^* é o conjunto de todas as cadeias sobre \Sigma, sempre infinito enumerável. E então: uma linguagem sobre \Sigma é qualquer subconjunto de \Sigma^*.
A generalidade dessa definição é o que dá poder ao aparato. Uma linguagem de programação é uma linguagem nesse sentido: o alfabeto são os caracteres admissíveis, e a linguagem é o conjunto infinito dos textos que constituem programas corretos. O conjunto dos programas que terminam também é uma linguagem — a diferença entre as duas está na dificuldade de decidir a pertinência, que é o problema central: dada L e dada w, decidir se w \in L. Todo compilador, na sua metade de análise, é um reconhecedor. E como uma linguagem infinita não pode ser descrita listando elementos, precisamos de descrições finitas: gramáticas, que geram as cadeias, e autômatos, que reconhecem a pertinência.
Uma gramática é uma quádrupla G = (V, \Sigma, P, S), com V finito de não terminais, \Sigma finito de terminais disjunto de V, S \in V o símbolo inicial e P um conjunto finito de produções \alpha \to \beta em que \alpha contém pelo menos um não terminal. A linguagem gerada é o conjunto das cadeias de terminais alcançáveis a partir de S por sucessivas substituições de lado esquerdo por lado direito:
L(G) = \{\, w \in \Sigma^* \mid S \Rightarrow^* w \,\}.
A ideia de Chomsky foi restringir progressivamente a forma das produções. Tipo 0 é irrestrita. Tipo 1, sensível ao contexto, exige |\alpha| \le |\beta|, de modo que as formas sentenciais nunca encurtam; o nome vem da forma equivalente em que um não terminal só é reescrito quando cercado por um contexto dado. Tipo 2, livre de contexto, exige que o lado esquerdo seja um único não terminal, e por isso a substituição não depende do que está ao redor. Tipo 3, regular, exige a forma A \to aB ou A \to a. As classes correspondentes satisfazem
\mathcal{L}_3 \subsetneq \mathcal{L}_2 \subsetneq \mathcal{L}_1 \subsetneq \mathcal{L}_0,
e cada inclusão é própria: em cada nível existe linguagem que a classe abaixo não alcança.
Vale ver de perto a separação que mais consequência tem no curso. Tome S \to a\,S\,b \mid \varepsilon: como a única forma de introduzir um a também introduz um b à direita, a linguagem gerada é o conjunto das cadeias a^n b^n. Ela é livre de contexto pela forma e não é regular — nas produções de tipo 3 o não terminal fica numa das pontas, e aqui fica no meio, com terminal de cada lado, que é a assinatura do aninhamento. Compare com A \to a\,A \mid b, que gera a^n b: não há nada a lembrar, e um punhado fixo de estados resolve. A diferença é mínima na aparência e máxima nas consequências, porque a forma das produções determina quanta memória o reconhecimento exige.
Pergunta para levar adiante. Por que uma máquina com número finito de estados não reconhece a^n b^n? A intuição cabe numa frase: reconhecer essa linguagem exige lembrar quantos a foram vistos, e esse número é ilimitado. Guarde a frase — a demonstração formal, mais adiante, é a formalização exata dela, e é ela que obriga todo compilador a ter duas fases de análise em vez de uma.
Do lado dos reconhecedores, cada classe corresponde exatamente a um modelo de máquina.
| Tipo | Gramática | Classe de linguagens | Reconhecedor |
|---|---|---|---|
| 3 | regular | regulares | autômato finito |
| 2 | livre de contexto | livres de contexto | autômato de pilha não determinístico |
| 1 | sensível ao contexto | sensíveis ao contexto | autômato linearmente limitado |
| 0 | irrestrita | recursivamente enumeráveis | máquina de Turing |
Leia essa tabela como uma escala de memória. O autômato finito não tem memória além do estado atual, tomado de um conjunto fixado de antemão. O de pilha acrescenta memória ilimitada com disciplina restrita, porque só se lê e escreve no topo — exatamente o que casa delimitadores aninhados, e por isso a estrutura de blocos e expressões cabe nesse andar. Os dois de cima têm memória de acesso livre, limitada pelo tamanho da entrada ou ilimitada.
Um detalhe da segunda linha costuma passar batido: para autômatos finitos, o não determinismo não aumenta o poder de reconhecimento; para autômatos de pilha isso é falso. Essa diferença é a origem de metade das dificuldades da análise sintática, porque o compilador precisa de um analisador determinístico e portanto não trabalha com todas as linguagens livres de contexto, só com as subclasses que admitem reconhecimento determinístico.
flowchart TB
subgraph T0["Tipo 0 — irrestritas · máquina de Turing"]
subgraph T1["Tipo 1 — sensíveis ao contexto · autômato linearmente limitado"]
subgraph T2["Tipo 2 — livres de contexto · autômato de pilha"]
subgraph T3["Tipo 3 — regulares · autômato finito"]
LEX["análise léxica<br/>categorias de tokens"]
end
SIN["análise sintática<br/>estrutura aninhada"]
end
SEM["condições dependentes de contexto<br/>verificadas por código, não por gramática"]
end
IND["território indecidível<br/>terminação e propriedades do comportamento"]
end
Com o mapa desenhado, digo que trecho vamos percorrer. Os dois andares inferiores, com definição, demonstração e implementação: as regulares fundamentam a análise léxica, em tempo proporcional ao tamanho da entrada; as livres de contexto fundamentam a análise sintática, concretizadas como descida recursiva ou como analisadores dirigidos por tabela. Os dois superiores ficam em nível panorâmico: o sensível ao contexto é teoricamente adequado às condições dependentes de contexto e praticamente inviável para elas, então a prática abandona o formalismo e as verifica por código escrito à mão — um dos poucos pontos em que a engenharia contraria a teoria por escolha, não por ignorância. E fique com esta advertência, porque a hierarquia é um mapa elegante demais: ela classifica por poder de descrição, não por custo de reconhecimento, e não captura ambiguidade, que é propriedade da gramática e, para um compilador, é intolerável.
1.6 O que nenhum compilador pode fazer
Volto ao terceiro programa defeituoso, porque a explicação delimita o território da atividade.
O programa entra num laço que nunca termina e o compilador não avisa. A resposta preguiçosa é que seria difícil; a correta é que é impossível, e a impossibilidade tem demonstração. Turing mostrou, em 1936, que não existe procedimento mecânico que, recebendo a descrição de um programa arbitrário e uma entrada, decida corretamente em todos os casos se a execução termina. O argumento é de autorreferência: supondo que tal procedimento exista, constrói-se com ele um programa que termina exatamente quando o procedimento afirma que ele não termina. A impossibilidade é lógica, não tecnológica. E vai além da terminação: um resultado geral demonstrado nos anos 1950 diz que qualquer propriedade não trivial do comportamento de um programa é indecidível. Sempre que a pergunta é sobre o que o programa faz, e não sobre como está escrito, o terreno é indecidível.
Isso poderia soar como derrota, e não é. Repare no que sobra: perguntas sobre a forma continuam decidíveis, e são todas as que o compilador responde. E há a estratégia intermediária, para chegar perto do indecidível — em vez de “sim” ou “não”, o analisador responde “certamente não” ou “talvez sim”, errando sempre para o mesmo lado.
Critério prático para o resto do curso. Antes de tentar fazer o seu compilador detectar alguma coisa, pergunte se ela é propriedade do texto ou do comportamento. Se for do comportamento, ou você aceita uma aproximação conservadora, ou está tentando resolver um problema que ninguém resolverá.
1.7 A infraestrutura que vem antes da primeira fase
O impulso natural, ao escrever o primeiro compilador da vida, é começar pelo analisador léxico. Vou defender que não: há uma camada que todas as fases usam e que, se não existir desde o primeiro dia, será improvisada ali e replicada mal nas seguintes.
flowchart TB
SRC["arquivo-fonte carregado uma vez<br/>com índice de início de cada linha"] --> POS["posição = deslocamento bruto<br/>convertido em linha e coluna por busca binária"]
POS --> DIAG["coleção de diagnósticos<br/>severidade · posição · mensagem"]
LEX["análise léxica"] --> DIAG
SIN["análise sintática"] --> DIAG
SEM["análise semântica"] --> DIAG
GER["geração de código"] --> DIAG
DIAG --> MAIN["programa principal<br/>consulta se há erros e decide parar ou seguir"]
MAIN --> SAI["saída no formato arquivo, linha, coluna,<br/>severidade e mensagem"]
A primeira peça é o tratamento de posições. Uma posição é o par formado pelo deslocamento bruto e pela sua tradução em linha e coluna, contadas a partir de um, como espera qualquer pessoa que leia uma mensagem de erro. A duplicidade é proposital: as fases trabalham com deslocamentos, que é o que a leitura sequencial produz, e as pessoas com linha e coluna. Alguém tem que converter, e a conversão ingênua, varrendo o texto e contando quebras de linha, custa tempo proporcional ao arquivo a cada erro reportado — quadrático por um motivo evitável. A solução é indexar, uma única vez no carregamento, o deslocamento em que cada linha começa, e converter por busca binária. E uma armadilha do nosso ambiente, onde o fim de linha usa dois caracteres: lido em modo texto, o par pode virar um caractere só, e os deslocamentos deixam de corresponder aos bytes do arquivo. Leia em modo binário.
A segunda peça é a estratégia de reporte. Ou você lança uma exceção que interrompe a fase, ou registra o problema numa coleção e continua — a primeira é a que se obtém sem pensar, a segunda é a que produz compiladores utilizáveis. Um diagnóstico é a tripla formada por severidade, posição e mensagem, e sem posição ele é inútil. Recomendo uma coleção compartilhada por todas as fases, na qual cada uma deposita o que encontrar sem decidir se o processo deve parar; quem decide é o programa principal. A vantagem imediata é reportar vários problemas de uma vez; a maior é que uma fase que não decide sobre a continuação pode ser testada isoladamente.
A terceira peça não é código, é política: ligue o nível mais alto de avisos, desative as extensões não padronizadas e transforme todo aviso em erro. Sem isso, as verificações produzem texto que ninguém lê, e o aviso ignorado no início é o defeito que se manifesta perto do fim, quando o código que o causou já saiu da sua memória. O mesmo vale para a tipagem explícita, que devolve documentação impossível de ficar desatualizada, porque é conferida pelo compilador.
Não deixe o modo estrito para depois. Ligar as verificações rigorosas sobre uma base já escrita produz dezenas de erros de uma vez, e a reação natural diante desse muro é desligá-las de novo. Ligue no primeiro arquivo, quando conformar-se custa uma linha: o custo de manter a política cai rápido, e o de não mantê-la só aparece quando pagá-lo já ficou caro.
Encerro com o conselho mais banal e mais ignorado: escreva o esqueleto pequeno, porque o formato real de cada estrutura só se descobre quando a fase é implementada. Um item, porém, vale a pena mesmo vazio: um relatório das fases, impresso pelo programa principal, listando as etapas e o estado de cada uma. No começo, todas pendentes; a cada módulo, uma linha de “pendente” vira trabalho de verdade.
1.8 O caso conduzido
Curso de compiladores que só apresenta técnicas produz gente que reconhece os algoritmos e não consegue escrever o primeiro arquivo. Por isso tudo aqui gira em torno de um caso conduzido: uma linguagem pequena, com um compilador completo, construída ao longo dos módulos, de modo que cada peça teórica tenha a sua realização concreta.
A escolha de qual linguagem construir não é neutra, e o critério vale mais do que a escolha. Uma linguagem de estudo precisa ser pequena o bastante para caber no tempo disponível e rica o bastante para exigir todas as fases: mais de uma categoria léxica, com ao menos uma descrita por padrões e não por palavras fixas; alguma construção aninhada de profundidade arbitrária, para que a análise sintática não seja trivial; nomes declarados num ponto e usados em outro, para que a tabela de símbolos tenha função; mais de um tipo de valor, com operação restrita a um deles, para que a verificação de tipos tenha o que verificar; e efeito observável, para conferir a execução do código gerado. Falhe em qualquer um desses pontos e uma fase fica sem conteúdo. Guarde a lista: é o contrato que a linguagem do seu grupo também terá de cumprir.
1.8.1 5.1 A linguagem Peneira e o problema que ela resolve
A linguagem que construiremos chama-se Peneira, e o seu domínio é o reconhecimento de padrões em texto. Um programa Peneira declara padrões, escreve regras que reagem ao que for encontrado em um fluxo de entrada e emite resultados rotulados. Se você quiser uma imagem rápida, pense em uma ferramenta de busca por padrões à qual foram acrescentadas condições e ações.
A escolha desse domínio não foi feita por simpatia, e vale expor o raciocínio porque ele ilustra o tipo de decisão que abre ou fecha portas em um projeto de linguagem. Em um livro que trata simultaneamente de teoria de linguagens formais e de construção de compiladores, há um risco específico: os autômatos podem virar um detalhe escondido dentro do analisador léxico, e o compilador levar o crédito inteiro. A teoria vira encanamento, e o leitor sai achando que autômatos servem para reconhecer identificadores e nada mais.
Em um domínio de reconhecimento de padrões isso não acontece, porque o produto da compilação é ele mesmo um motor de autômatos. A teoria aparece duas vezes no mesmo artefato, em dois níveis distintos. Uma vez para reconhecer os símbolos da própria Peneira, na análise léxica, como em qualquer compilador. Outra vez para reconhecer os padrões que o usuário declarou nos seus programas, que é o que o código gerado faz em tempo de execução. E — este é o ponto que amarra o livro — o mesmo módulo de construção de autômatos serve aos dois níveis. O que se escreve para converter uma expressão regular em autômato finito determinístico é usado tanto pelo compilador quanto pelo programa compilado. Essa reutilização é a espinha do projeto, e é o argumento que fecha o percurso: quem chegar ao fim terá construído, uma única vez, uma peça teórica que trabalha nas duas pontas.
1.8.2 5.2 A forma dos programas
Vale olhar para um programa antes de qualquer formalização. Este é o exemplo que acompanha o livro desde o começo:
Repare em quanta decisão de projeto esse texto de sete linhas já contém, mesmo sem gramática escrita.
Os padrões são declarados antes de usados, o que significa que haverá uma tabela de símbolos com uma ordem de declaração a verificar — e portanto que a análise semântica terá conteúdo. A condição é opcional e marcada por uma palavra reservada, o que se traduz em uma produção com parte opcional na gramática e em uma decisão a tomar durante a análise sintática. A extração do valor numérico é explícita, e não uma conversão automática, o que me poupa de inventar regras de coerção de tipo — decisão deliberada de escopo, tomada para que a verificação de tipos exista sem crescer. E a ação é uma emissão com rótulo, que dá o efeito observável sem o qual a fase de execução não teria o que demonstrar.
Nenhuma dessas decisões saiu de análise formal. Todas saíram de escrever o programa pretendido e olhar para ele, que é a ordem correta em projeto de linguagens: primeiro decida como o programa deve parecer, depois descubra a gramática que o descreve. Faço questão de registrar um erro que cometi na primeira versão, porque ele é instrutivo. A condição, no primeiro rascunho, não tinha palavra separadora — era apenas o nome ligado seguido da expressão. Parecia mais limpo e era ambíguo: sem uma marca entre a ligação e a condição, o analisador não sabe onde uma termina e a outra começa sem olhar arbitrariamente para a frente. A palavra separadora custa cinco caracteres a quem escreve o programa e elimina um problema real na análise sintática.
Os dois tipos de valor da linguagem são texto e número, e a operação de extração de valor numérico se aplica a apenas um deles. O aninhamento de profundidade arbitrária vem das expressões de condição, em que uma condição contém outra sem limite. As categorias léxicas são nomes, números, cadeias de texto, literais de padrão e sinais de pontuação, e o literal de padrão é ele próprio descrito por padrões. Confrontando com os critérios da seção anterior, a linguagem atende a todos, e a especificação inteira cabe em duas páginas — que é o outro critério, o de tamanho, e o mais fácil de violar sem perceber. Toda ideia interessante quer crescer: assim que a Peneira ficou de pé, a tentação foi acrescentar funções definidas pelo usuário, variáveis mutáveis e laços. Cada acréscimo parece pequeno e custa capítulos inteiros na análise semântica. Cortei todos.
1.8.3 5.3 A primeira infraestrutura
O compilador da Peneira não começa pelo analisador léxico, pelas razões defendidas na seção anterior. Começa pelas duas peças que todas as fases usam: o arquivo-fonte com posições indexadas e a coleção de diagnósticos.
A primeira carrega o texto na memória e indexa, no carregamento, o deslocamento de início de cada linha, exatamente como argumentei na Definição 4.1. A conversão de deslocamento em linha e coluna passa a ser uma busca binária nesse índice.
01_source.h
#ifndef PENEIRA_01_SOURCE_H
#define PENEIRA_01_SOURCE_H
#include <cstddef>
#include <optional>
#include <string>
#include <vector>
namespace peneira {
// Posição de um caractere no arquivo-fonte. O deslocamento é o índice bruto
// dentro do texto; linha e coluna são contadas a partir de 1, como espera
// qualquer pessoa lendo uma mensagem de erro.
struct Position {
std::size_t offset;
std::size_t line;
std::size_t column;
};
// Guarda o texto de um programa Peneira e o índice de início de cada linha.
// O índice é construído uma única vez, no carregamento: sem ele, converter um
// deslocamento em linha e coluna exigiria varrer o texto do começo a cada erro
// reportado.
class SourceFile {
public:
static SourceFile fromText(std::string name, std::string text);
static std::optional<SourceFile> loadFromDisk(const std::string& path,
std::string& error);
const std::string& name() const noexcept;
const std::string& text() const noexcept;
std::size_t length() const noexcept;
std::size_t lineCount() const noexcept;
// Converte deslocamento em linha e coluna por busca binária no índice.
Position positionAt(std::size_t offset) const;
// Texto de uma linha (contada a partir de 1), sem o terminador.
// Usado para exibir a linha ofensora abaixo da mensagem de erro.
std::string lineText(std::size_t line) const;
private:
SourceFile(std::string name, std::string text);
void indexLines();
std::string name_;
std::string text_;
std::vector<std::size_t> lineStarts_;
};
} // namespace peneira
#endif // PENEIRA_01_SOURCE_H
Duas escolhas de interface merecem comentário. A leitura de disco devolve um valor opcional e uma mensagem de erro por referência, em vez de lançar exceção: falha ao abrir arquivo é situação esperada, não excepcional, e tratá-la pelo mecanismo de exceções mistura duas categorias de problema. E existe uma construção a partir de texto puro, sem disco, que é o que torna a estrutura testável sem depender de arquivos de apoio — uma decisão pequena que se paga na primeira bateria de testes que você escrever.
A segunda peça é a coleção de diagnósticos, que materializa a política defendida na Definição 4.2: as fases registram o que encontram e seguem, e quem decide parar é o programa principal, consultando se há erros.
01_diagnostico.h
#ifndef PENEIRA_01_DIAGNOSTICO_H
#define PENEIRA_01_DIAGNOSTICO_H
#include <cstddef>
#include <cstdint>
#include <iosfwd>
#include <string>
#include <vector>
#include "01_source.h"
namespace peneira {
enum class Severity : std::uint8_t { Error, Warning, Note };
// Um diagnóstico é sempre ancorado numa posição do fonte. Diagnóstico sem
// posição é diagnóstico inútil: o usuário sabe que algo deu errado e não sabe
// onde.
struct Diagnostic {
Severity severity;
Position position;
std::string message;
};
// Coleta os diagnósticos de todas as fases em vez de abortar no primeiro.
// A partir do analisador léxico, cada fase reporta o que encontrar e segue;
// quem decide parar é o programa principal, olhando hasErrors().
class DiagnosticBag {
public:
void report(Severity severity, Position position, std::string message);
void error(Position position, std::string message);
void warning(Position position, std::string message);
bool hasErrors() const noexcept;
std::size_t errorCount() const noexcept;
std::size_t size() const noexcept;
const std::vector<Diagnostic>& all() const noexcept;
// Imprime no formato "arquivo:linha:coluna: severidade: mensagem",
// seguido da linha ofensora e de um cursor sob a coluna.
void printAll(const SourceFile& source, std::ostream& out) const;
private:
std::vector<Diagnostic> items_;
std::size_t errorCount_ = 0;
};
const char* severityLabel(Severity severity) noexcept;
} // namespace peneira
#endif // PENEIRA_01_DIAGNOSTICO_H
Isso parece exagero em um ponto do livro em que não existe fase alguma, e é justamente o que torna possível, muitos capítulos adiante, um analisador sintático que reporta três erros de uma vez em vez de obrigar quem escreve o programa a corrigir e recompilar três vezes. Decisões de infraestrutura têm essa característica desagradável: o custo é imediato e o benefício é remoto, o que faz com que sejam sistematicamente adiadas por quem só olha o próximo passo.
1.8.4 5.4 Compilar e interpretar, sobre a mesma árvore
Encerro o capítulo com um exemplo pequeno e separado do compilador da Peneira, cuja única função é tornar concreta a distinção das Definições 1.3 e 1.4. A ideia é tomar a mesma árvore de expressão e submetê-la aos dois tratamentos: o interpretador percorre a árvore e produz o resultado agora; o compilador percorre a mesma árvore e produz instruções para depois, que uma máquina de pilha executa.
01_traducao.h
#ifndef PENEIRA_01_TRADUCAO_H
#define PENEIRA_01_TRADUCAO_H
#include <cstdint>
#include <memory>
#include <string>
#include <vector>
// Demonstração isolada do Módulo 1: a diferença entre interpretar e compilar,
// sobre a mesma árvore de expressão. Não faz parte do compilador da Peneira —
// é o exemplo mínimo que torna concreta a distinção apresentada na teoria.
// A partir do Módulo 13 o mesmo par de ideias reaparece, aí sim dentro do
// sistema principal.
namespace peneira::demo {
enum class Operador : std::uint8_t { Somar, Subtrair, Multiplicar };
enum class TipoNo : std::uint8_t { Literal, Operacao };
struct No;
using NoPtr = std::unique_ptr<No>;
struct No {
TipoNo tipo;
double valor; // significativo quando tipo == TipoNo::Literal
Operador operador; // significativo quando tipo == TipoNo::Operacao
NoPtr esquerda;
NoPtr direita;
};
NoPtr literal(double valor);
NoPtr operacao(Operador operador, NoPtr esquerda, NoPtr direita);
// Caminho do interpretador: percorre a árvore e produz o resultado agora.
double avaliar(const No& no);
enum class OpCode : std::uint8_t { PushConst, Add, Sub, Mul };
struct Instrucao {
OpCode opcode;
double operando; // significativo apenas para PushConst
};
// Caminho do compilador: percorre a árvore e produz instruções para depois.
std::vector<Instrucao> compilar(const No& no);
// Máquina de pilha que executa o que o compilador emitiu.
double executar(const std::vector<Instrucao>& programa);
std::string desmontar(const std::vector<Instrucao>& programa);
// Monta a expressão usada na demonstração: (2 + 3) * 4 - 5.
NoPtr expressaoDeExemplo();
} // namespace peneira::demo
#endif // PENEIRA_01_TRADUCAO_H
Sobre a expressão (2 + 3) \times 4 - 5, o interpretador devolve 15 diretamente, percorrendo a árvore em profundidade e combinando os resultados dos filhos. O compilador devolve sete instruções — empilhar 2, empilhar 3, somar, empilhar 4, multiplicar, empilhar 5, subtrair — e a máquina de pilha, executando essas sete instruções, também devolve 15. Os dois caminhos chegam ao mesmo número, e é essa igualdade que a Definição 1.2 exige.
O que quero que fique visível é a ordem da emissão. As instruções saem em pós-ordem: primeiro os dois operandos, depois a operação. Essa ordem não é escolha estética, é a única que funciona em uma máquina de pilha, porque no momento em que a instrução de operação executa os dois valores já precisam estar empilhados. É a mesma ordem que reaparecerá na geração de código, aí sim para valer, e quem entender o percurso aqui, com sete instruções, entenderá lá com setenta.
Aproveito para registrar a armadilha que esse exemplo esconde, porque ela apanha quase todo mundo uma vez na vida. Ao implementar a máquina de pilha, o segundo operando sai primeiro do topo, porque foi o último a entrar. Trocar a ordem do desempilhamento não altera nada na soma nem na multiplicação, e produz resultado errado na subtração — um defeito que passa em boa parte dos testes e só é encontrado tarde. A expressão de demonstração termina em uma subtração exatamente por isso, e não por acaso.
1.9 Síntese
Um compilador é um tradutor entre linguagens, sujeito a um contrato de correção que é uma igualdade entre significados, e se distingue de um interpretador não pelo que faz, mas por quando faz. Por dentro, decompõe-se em fases definidas pelas suas interfaces e responsabilidades de verificação, agrupadas em análise e síntese e separadas por uma representação intermediária cuja justificativa é combinatória: de m \times n para m + n peças. Por baixo delas há um mapa de quatro andares em que gramáticas geram e autômatos reconhecem, e a forma das produções determina ao mesmo tempo a classe alcançada e a máquina necessária; a construção de compiladores vive nos dois andares inferiores. E antes de tudo isso há uma camada de infraestrutura cujo custo é imediato e cujo benefício é remoto — razão pela qual é sistematicamente adiada por quem só olha o próximo passo.
Volto, para fechar, aos três programas da abertura. Agora você tem nome para cada um: o primeiro morre na análise sintática, porque a sequência de tokens não deriva da gramática; o segundo morre na análise semântica, porque a condição violada depende de contexto; e o terceiro não morre em lugar nenhum, porque pergunta sobre comportamento, e o andar da hierarquia onde essa pergunta mora é indecidível. Três defeitos, três destinos, e o mapa inteiro do semestre entre eles. Não pule a parte formal dos próximos módulos: é ela que permite escrever um analisador léxico que você sabe estar correto, em vez de um que passa nos testes de que você lembrou.