flowchart LR
F1[Origem 1] --> RI
F2[Origem 2] --> RI
F3[Origem m] --> RI
RI{{Representacao<br/>intermediaria}}
RI --> G1[Destino 1]
RI --> G2[Destino 2]
RI --> G3[Destino n]
1 Módulo 13: Representações Intermediárias e Ambientes de Execução
Bem-vindo ao módulo 13. Aqui o produto principal não é código: é decisão escrita. Você vai escolher em que forma o programa vive entre a análise e a síntese, especificar o que sai do compilador e desenhar como ele se organiza na memória enquanto roda. Nada disso dá erro de compilação quando está errado — por isso leia com atenção redobrada.
1.1 O problema: um desvio para um endereço que ainda não existe
Traduza a condição “a < b e c < d” para instruções de máquina, respeitando a exigência que qualquer linguagem de uso corrente impõe: se o primeiro teste falhar, o segundo nem chega a ser executado. O primeiro pedaço é fácil — compare, e se der falso, desvie. Desvie para onde? Para o ponto logo depois do comando inteiro, que ainda não foi traduzido e cujo endereço, portanto, não existe ainda.
Isso tem nome — preenchimento retroativo — e uma solução bonita, que mostro na terceira seção. Mas repara no que o problema revela antes de ser resolvido. Se você cuspir código de máquina direto durante o percurso da árvore, resolve no mesmo laço dois problemas de naturezas diferentes: a ordem de avaliação com desvios, que é fluxo de controle, e a codificação das instruções, que é formato de arquivo. Cada erro de um parece defeito do outro, e eu mesmo já perdi dias assim. A resposta clássica é interpor uma camada.
Antes de entrar na primeira seção, quero deixar explícito o que este capítulo pressupõe, porque é a informação que permite a você decidir se convém recuperar alguma coisa antes de seguir.
Pressuponho que você tenha em mãos, ao menos conceitualmente, uma árvore sintática abstrata verificada: construída pela análise sintática, anotada pela análise semântica com os tipos de cada subexpressão e com os nomes já resolvidos contra uma tabela de símbolos. É essa árvore que entra na tradução da terceira seção, e o que se assume dela é modesto — que os nomes existem, que os tipos combinam e que as conversões que a linguagem exige estejam explícitas nos nós, e não subentendidas. Se a sua análise semântica ainda deixa alguma dessas três coisas para depois, a tradução deste capítulo vai herdar o problema.
Pressuponho também familiaridade com autômatos finitos determinísticos e com a sua função de transição, porque a quarta seção discute duas representações concorrentes dessa função e a decisão de trocar de uma para a outra na fronteira entre o compilador e o arquivo de saída. Não é preciso lembrar dos algoritmos de determinização e minimização; basta lembrar que a função de transição é um mapa de pares estado-símbolo em estados e que, em alfabetos grandes, ela é quase toda vazia.
E pressuponho o vocabulário elementar de organização de computadores: o que é um endereço, o que distingue uma pilha de uma área de alocação livre, o que significa uma indireção. A quinta seção é o ponto deste livro em que a construção de compiladores encosta nesse assunto de forma mais direta, e a leitura fica bem mais produtiva se esses termos não forem novidade.
O que não pressuponho é qualquer contato anterior com código de três endereços, com preenchimento retroativo, com registros de ativação ou com técnicas de coleta automática de memória. Tudo isso é construído aqui, do início, e no ponto em que passa a ser necessário.
1.2 Por que existe uma camada no meio
Uma representação intermediária é uma linguagem L_i, distinta da fonte L_f e do alvo L_a, tal que o compilador se decompõe em F: L_f \to L_i e G: L_i \to L_a, com C = G \circ F, e tal que L_i é independente das particularidades das duas pontas. A independência é o que dá conteúdo à definição: sem ela, qualquer estrutura interna seria uma representação intermediária, inclusive a árvore sintática abstrata, que é toda moldada pela gramática da origem.
O argumento a favor vira uma conta. Para m origens e n destinos sem camada, cada par exige o seu tradutor: m \times n peças. Com a camada, m frentes e n retaguardas: m + n.
| Origens | Destinos | Tradutores diretos | Peças com a camada |
|---|---|---|---|
| 1 | 1 | 1 | 2 |
| 3 | 3 | 9 | 6 |
| 10 | 10 | 100 | 20 |
Olha a primeira linha, que quase ninguém mostra. Com uma origem e um destino — o caso de praticamente todo compilador que você vai escrever na vida — a tradução direta custa uma peça e a camada custa duas. O argumento combinatório, aplicado ao seu caso, condena a camada; o ponto de virada está em três por três.
Pare e pense. Se o argumento mais citado a favor da camada não vale para o seu projeto, por que quase todo compilador sério tem uma? Tente responder sem repetir a frase do livro.
A resposta é uma segunda justificativa, menos citada e mais útil: a separação de dificuldades. Fluxo de controle e codificação se contaminam quando resolvidos juntos, e a camada permite resolver um antes de o outro existir, porque ela é uma fronteira observável — você imprime, confere à mão e testa a tradução contra uma sequência esperada de instruções, sem uma linha do gerador final. Sem ela, a primeira coisa observável é o arquivo objeto, e conferir arquivo objeto à mão ninguém sustenta.
O teste do apagamento. Antes de meter uma camada de indireção em qualquer projeto, pergunte: se eu apagar esta camada e ligar as duas pontas, o que fica mais difícil? Se a resposta honesta for “nada”, você economizou um mês. E saiba em que nível a sua camada está: é de alto nível quando preserva construções da fonte, como laços e chamadas, e de baixo nível quando elas já viraram cálculo de endereço, leitura, escrita e desvio.
1.3 As formas usuais, comparadas sobre a mesma expressão
Percorro as formas consagradas sob uma regra explícita: comparo todas sobre a mesma expressão, e essa expressão é a mais difícil que a linguagem admite — o que brilha numa soma de dois números pode ser inservível numa condição composta.
É o que você já tem ao fim da análise semântica: a árvore anotada com tipos e nomes resolvidos. É a mais informativa, e a que sustenta o mapeamento entre código gerado e texto-fonte de que um depurador precisa. O defeito é simétrico: a ordem de avaliação está implícita na estrutura — a árvore diz que a soma tem dois operandos, não diz qual é calculado primeiro —, e não há nela lugar para escrever “se este subteste falhar, pule aquele nó”.
A notação pós-fixada de um operando simples é ele mesmo; a de \Theta(E_1, \ldots, E_k) é a concatenação das notações dos operandos, nessa ordem, seguida do operador. Dispensa parênteses e não é ambígua desde que a aridade seja conhecida, e o percurso em pós-ordem da árvore produz exatamente ela — daí ser a linguagem natural das máquinas de pilha. A ordem de avaliação sai de graça, e a pilha faz o papel dos temporários. E ela não exprime desvio: não há onde dizer “salte três símbolos adiante”.
Uma instrução de três endereços tem no máximo um operador e três operandos, tipicamente x := y \;\Theta\; z, com nomes que podem ser variáveis, constantes ou temporários criados pelo compilador. A restrição a um operador é a essência: toda subexpressão composta é quebrada e cada resultado parcial ganha nome. O repertório inclui atribuição binária e unária, cópia, desvio incondicional e condicional, chamada com parâmetros e acesso indexado — e traz o que faltava às outras duas: desvios que carregam um destino.
flowchart TD
A[Arvore verificada] --> B{A forma<br/>exprime desvio?}
B -- nao --> C[Arvore sintatica abstrata<br/>ordem de avaliacao implicita]
B -- nao --> D[Notacao pos-fixada<br/>ordem explicita, sem desvio]
B -- sim --> E[Codigo de tres enderecos<br/>ordem explicita e desvio com destino]
C --> F[Reprovada no curto-circuito]
D --> F
E --> G[Escolhida]
A escolha não foi feita por elegância: a pós-fixada é a mais curta e a mais fácil de executar, e é a errada, porque sem desvio não há curto-circuito e o conectivo avalia sempre os dois lados — o que não é ineficiência, é mudança de semântica.
Falta decidir como guardar. Quádruplas guardam operador, dois operandos e resultado, pagando o preço de criar e comparar nomes de temporários. Triplas eliminam o campo de resultado e usam a posição da instrução como nome do valor produzido — economizam um campo e ficam hostis à reordenação, porque mover uma instrução invalida as referências a posições. Triplas indiretas guardam as triplas numa tabela e, à parte, um vetor de índices com a ordem de execução: reordenar vira permutar o vetor. Recomendo quádruplas: o recurso escasso do seu compilador é a sua atenção.
Em panorama, a forma que domina as infraestruturas modernas. Um código está na forma de atribuição única estática quando cada nome é destino de exatamente uma atribuição no texto do programa; onde dois caminhos de controle se encontram trazendo versões diferentes de um nome, insere-se uma função \phi que seleciona a versão do caminho percorrido. O adjetivo “estática” é a parte mal compreendida: a exigência é sobre o texto, não sobre a execução. A forma foi formalizada em trabalho publicado em 1991 por Ron Cytron, Jeanne Ferrante e colaboradores; sem otimização global sobre fluxo de dados, ela não paga o próprio custo, porque existe para viabilizar essas análises.
1.4 A tradução para código de três endereços
A tradução é um percurso recursivo em que cada nó devolve algo ao pai e, no caminho, emite instruções numa lista que cresce. Um esquema de tradução dirigido pela sintaxe associa a cada tipo de nó as ações a executar e os atributos a devolver, e a frase que torna tudo quase mecânico é esta: o atributo devolvido por um nó de expressão é o nome do temporário que contém o seu valor. Para traduzir uma soma, traduza cada filho e guarde o nome devolvido, crie um temporário, emita a instrução e devolva o nome novo. Sem caso especial e sem tabela de precedência — ela já foi resolvida pela análise sintática e está gravada na forma da árvore.
Uma verificação de graça. O número de temporários criados é igual ao de nós de expressão visitados. Se a sua tradução gerar número diferente do esperado, algum nó está sendo visitado duas vezes ou nenhuma — e as duas coisas são defeitos.
Expressões são o caso fácil porque não têm fluxo de controle; os comandos é que começam o assunto. Um rótulo é um nome associado a uma posição do código, e é pendente enquanto essa posição não é conhecida. Para “se C então S_1 senão S_2”: emite-se C; um desvio condicional que salta para o início de S_2 quando C é falsa; S_1; um desvio incondicional para depois de S_2; e S_2. Dois desvios para a frente, ambos com destino desconhecido na emissão. Para “enquanto C faça S”, marca-se a posição atual, emite-se C, um desvio condicional para depois do laço, o corpo e um desvio incondicional de volta à posição marcada.
Daí a assimetria contraintuitiva que quero gravada: o desvio para trás é o caso fácil, porque aponta para instrução já emitida; o difícil é o desvio para a frente, ainda que laços pareçam mais complicados no texto do programa.
Chego ao problema da abertura. A avaliação de C_1 \wedge C_2 é com curto-circuito quando C_2 só é avaliada se C_1 resultar verdadeira; a de C_1 \vee C_2, quando C_2 só é avaliada se C_1 resultar falsa. Quem calcula sempre os dois lados é ansiosa. Na tradução por valor, cada lado vira expressão comum com um temporário booleano e uma instrução de conjunção combina os dois; é curta e é ansiosa por construção, porque para combinar dois valores é preciso ter calculado os dois. Não é falta de esperteza: é estrutural.
A que funciona é a tradução por fluxo de controle. Nela uma condição não devolve valor: devolve duas listas de desvios pendentes, a dos desvios tomados quando ela resulta verdadeira e a dos tomados quando resulta falsa, nenhuma com destino ainda. Traduzir um conectivo passa a ser combinar as listas dos filhos. Na conjunção, a lista verdadeira de C_1 recebe como destino o início de C_2 — é isso que significa “continue testando”; a verdadeira do conjunto é a de C_2, e a falsa é a união das duas falsas, porque falhar de qualquer lado derruba a conjunção inteira. Na disjunção o esquema é simétrico. E há uma economia: uma comparação isolada emite só o desvio do caso falso, deixando o verdadeiro cair na instrução seguinte — salvo na disjunção, em que o caminho verdadeiro da esquerda precisa pular o lado direito inteiro e nasce um desvio incondicional pendente.
O preenchimento retroativo costura tudo: emitir desvios com o destino vazio, manter listas dos índices dessas instruções e preencher o campo assim que a posição se torna conhecida. São três operações — criar uma lista com um único índice, fundir duas listas, e escrever o mesmo destino em todas as instruções de uma lista.
flowchart TD
A[Emitir desvio<br/>com destino vazio] --> B[criar lista<br/>com um indice]
B --> C{Combinar<br/>com outro operando?}
C -- sim --> D[fundir listas<br/>em uma so]
D --> C
C -- nao --> E{Destino ja<br/>conhecido?}
E -- nao --> F[devolver a lista<br/>ao chamador]
F --> C
E -- sim --> G[preencher<br/>toda a lista de uma vez]
G --> H[verificacao final:<br/>zero desvios pendentes]
Veja o mecanismo num traçado de “se C_1 e C_2 então S_1 senão S_2”:
0: t0 := <avaliação de C1>
1: se_falso t0 desvia para ? <- entra na lista FALSA
2: t1 := <avaliação de C2>
3: se_falso t1 desvia para ? <- entra na lista FALSA
4: <código de S1>
5: desvia para ? <- pendente: pula o senão
6: <código de S2>
7: (fim do comando)Quando a instrução 6 vai ser emitida, a lista falsa — que contém as posições 1 e 3 — é preenchida de uma vez com o valor 6: as duas recebem o mesmo destino, que nenhuma conhecia quando foi gerada. Ao terminar o comando, a posição 7 se conhece e o desvio da posição 5 é preenchido — uma passagem só, sem tabela de rótulos simbólicos.
A verificação que você deve escrever hoje. Aplicado corretamente, o esquema não deixa desvio pendente ao término da tradução de um comando completo. Então conte os desvios pendentes ao final; o número tem de ser zero. O defeito que essa contagem pega é um desvio para lugar nenhum, que não causa erro de compilação: causa comportamento errado semanas depois.
1.5 O programa objeto e a sua especificação
Decidida a representação, é preciso decidir o que sai do compilador — e defendo uma ordem minoritária: escreva a especificação do formato de saída antes do código que a produz. O impulso natural é o oposto, e o resultado parece igual mas não é: a documentação escrita a partir do código registra as decisões acidentais junto com as deliberadas e não distingue umas das outras.
Critério de completude. Uma especificação de formato objeto é completa quando alguém que leia apenas ela consegue escrever um executor compatível: um programa que, dado um objeto no formato descrito e uma entrada, produza a mesma saída que o executor de referência. O teste é literal — entregue a especificação a outra pessoa, dê-lhe um objeto e uma entrada, e peça que descreva a saída. Onde ela precisar perguntar, falta texto, e o que falta não é redação, é decisão.
O que esse teste revela não é a lista de campos, que todo mundo escreve: é o comportamento nos empates e nas bordas, que a implementação escolhe sem perceber que escolhia.
flowchart TD
A[Programa objeto] --> B[Cabecalho:<br/>versao e tamanhos]
A --> C[Area de constantes:<br/>literais referenciados por indice]
A --> D[Tabelas de reconhecimento:<br/>funcao de transicao densa]
A --> E[Codigo das instrucoes:<br/>tamanho fixo, desvio por indice]
A --> F[Modelo de execucao declarado:<br/>laco, desempate, erros]
F --> G[Criterio de completude:<br/>outra pessoa escreve<br/>um executor compativel?]
A primeira decisão de formato é a mais estrutural: que modelo de máquina o objeto pressupõe. Numa máquina de pilha as instruções não nomeiam operandos — a soma desempilha dois valores e empilha o resultado; o conjunto é minúsculo, a codificação é compacta e a geração é quase trivial, porque é o percurso em pós-ordem, mas todo valor intermediário passa pela memória da pilha. Numa máquina de registradores as instruções nomeiam onde os operandos estão e onde o resultado vai; o código é mais rápido e a geração é mais difícil, porque é preciso decidir quais valores merecem registrador. O critério depende da linguagem, não da máquina: a profundidade das expressões, calculável antes de rodar por
d(\text{folha}) = 1, \qquad d(T) = \max\bigl(d(T_e),\; 1 + d(T_d)\bigr).
Na cadeia inclinada à esquerda ((a+b)+c)+d a profundidade dá 2, qualquer que seja o comprimento; na simétrica a+(b+(c+d)) ela cresce e vale 4. Duas expressões equivalentes, custos de pilha bem diferentes, e a diferença está só na forma da árvore — primeira aparição da ordenação da avaliação, que o próximo módulo trata. E como d(T) é conhecida na compilação, o compilador grava no objeto de quanta pilha o programa precisa.
Duas decisões menores têm consequências desproporcionais. Instruções de tamanho fixo desperdiçam espaço e, em troca, fazem a posição de uma instrução ser o seu índice, o que torna o preenchimento retroativo utilizável no objeto. E reunir as constantes numa área única, referenciadas por índice, dá instruções uniformes e um lugar só onde a codificação de texto é resolvida.
Outra decisão passa despercebida: a mesma estrutura pode ter representações diferentes dentro do compilador e dentro do objeto. O caso canônico é a função de transição de um autômato determinístico, que dentro do compilador é construída e minimizada sobre um alfabeto grande e fica quase toda vazia — onde a esparsa vence — e dentro do objeto é apenas consultada, uma vez por símbolo da entrada, onde a matriz densa vence pelo motivo oposto. Defenda a densa com o número medido da fração de posições preenchidas, não com a intuição.
Falta o que mais fica de fora: o modelo de execução — o laço principal, o efeito de cada instrução sobre a pilha e as condições de erro. A regra do casamento mais longo determina que o trecho reconhecido é o mais extenso possível a partir da posição corrente; quando mais de um reconhecedor produz trecho de comprimento máximo igual, é preciso uma regra de desempate escrita, sob pena de dois executores igualmente corretos produzirem saídas diferentes. E as condições de erro devem ser listadas inclusive quando as fases anteriores provaram que não podem ocorrer: o objeto é um arquivo, arquivos podem ser adulterados, e quem confia cegamente numa prova feita em outro programa produz comportamento arbitrário.
1.6 Ambientes de execução
A memória de um programa em execução divide-se convencionalmente em quatro áreas: o código, imutável; a área estática, com os dados de tamanho e posição fixados na compilação; a pilha, que cresce e encolhe conforme os blocos são iniciados e terminados; e o monte, com os dados cujo tempo de vida não segue a estrutura de blocos. Proponho uma leitura mais útil que essa divisão nominal: o corte que interessa é entre o que o compilador sabe e o que só a execução descobre.
flowchart TD
M[Memoria do programa<br/>em execucao] --> S1[O compilador sabe]
M --> S2[So a execucao descobre]
S1 --> C[Codigo:<br/>instrucoes emitidas]
S1 --> E[Area estatica:<br/>constantes e tabelas]
S2 --> P[Pilha:<br/>registros de ativacao]
S2 --> H[Monte:<br/>alocacao dinamica]
P --> N[Profundidade maxima:<br/>calculavel na compilacao]
E a fronteira é menos nítida do que parece: a profundidade máxima da pilha de avaliação é calculável na compilação, embora o conteúdo não seja. O critério não é “esta área cresce ou não”, e sim “que informação sobre ela o compilador consegue provar”. Um cuidado que só aparece medindo: distinga uma área de tamanho zero de uma de tamanho dinâmico, sob pena de a área mais estática de todas parecer crescer em execução.
A área de cada dado decorre do tempo de vida e de o tamanho ser ou não conhecido antecipadamente. Vida do programa inteiro com tamanho conhecido vai para a estática: constantes, tabelas geradas, globais. Vida igual à de um bloco vai para a pilha, porque a disciplina de crescimento da pilha é a de aninhamento dos blocos. O que não segue essa disciplina vai para o monte, a área mais cara — e uma linguagem em que nada sobrevive ao bloco que o criou não precisa de monte. Descrever uma área de alocação dinâmica só porque a divisão canônica tem quatro áreas é preencher formulário.
O registro de ativação de uma execução de procedimento é o bloco contíguo que guarda tudo o que aquela execução precisa: espaço para o valor devolvido, parâmetros efetivos, elo de controle, elo de acesso, estado salvo da máquina, variáveis locais e temporários. Cada execução tem o seu — e é essa frase que dá sentido ao resto, porque se cada procedimento tivesse um bloco fixo único a recursão seria impossível. É a alocação por ativação, empilhada, que a torna viável, e essa é a razão histórica de linguagens antigas sem pilha não admitirem recursão. Ativação não é sinônimo de chamada de procedimento: qualquer construção com ponto de entrada, valores ligados nessa entrada, espaço de trabalho próprio e retorno é uma ativação. Quando elas não se aninham, a pilha degenera num registro único.
Os registros exigem um protocolo. Na chamada, o chamador avalia os parâmetros e os deposita no lugar combinado, salva o que precisa preservar, grava o endereço de retorno e transfere o controle; o chamado completa o seu registro, ajusta o topo da pilha e executa. No retorno, o chamado deposita o valor devolvido, restaura o que salvou e devolve o controle. A divisão exata varia e nenhuma escolha é melhor — o que importa é que seja uma só e documentada, porque duas metades compiladas sob convenções diferentes falham de modo incompreensível. O critério que costuma decidir: o que só o chamador sabe cabe ao chamador, o que só o chamado sabe cabe ao chamado.
Chego ao que mais gente confunde. O elo de controle aponta para o registro da ativação que efetuou a chamada, e a cadeia de controle segue a ordem de execução. O elo de acesso aponta para o registro da ativação do procedimento que contém lexicamente o ativado, e a cadeia de acesso segue a ordem léxica. Uma responde “para onde volto quando terminar”; a outra, “onde estão as variáveis que eu enxergo”. Em muitos casos coincidem, e é essa coincidência que faz tanta gente confundi-las.
flowchart TD
Q0[Quadro 0<br/>principal, nivel 0]
Q1[Quadro 1<br/>externo, nivel 1]
Q2[Quadro 2<br/>interno, nivel 2]
Q3[Quadro 3<br/>externo, nivel 1]
Q3 -- elo de controle --> Q2
Q2 -- elo de controle --> Q1
Q1 -- elo de controle --> Q0
Q3 -. elo de acesso .-> Q0
Q2 -. elo de acesso .-> Q1
Q1 -. elo de acesso .-> Q0
O menor exemplo de divergência precisa de três níveis. Um principal contém um externo, que contém um interno; o principal chama o externo, o externo chama o interno, e o interno chama o externo de novo. No quarto registro — a segunda ativação do externo — o elo de controle aponta para o terceiro, porque foi o interno quem chamou, e o de acesso aponta para o primeiro, porque quem contém o externo no texto é o principal. Dali, uma variável declarada no interno não é visível, embora o registro do interno esteja na pilha logo abaixo: “estar na pilha” e “ser visível” são coisas diferentes, e confundi-las é o erro que a cadeia de acesso existe para impedir.
Um procedimento de nível léxico n_p que acessa variável declarada em nível n_v \le n_p alcança o registro correto seguindo exatamente n_p - n_v elos, porque cada elo reduz o nível em uma unidade. E essa diferença é conhecida na compilação: o acesso a variável não local não custa busca em execução, custa um número fixo de indireções gerado como constante no código — o que parecia exigir procura vira aritmética de endereço, e é isso que torna o escopo estático barato. Registro o erro clássico: ao montar o elo de acesso de uma nova ativação, a tentação é usar o primeiro registro do procedimento envolvente encontrado de baixo para cima; com recursão existem vários, e o correto é o mais recente. A versão errada compila e acessa a variável da ativação errada, silenciosamente. Há ainda o display, das implementações de ALGOL 60: um vetor indexado por nível léxico, com a posição k guardando o apontador para a ativação mais recente de nível k, que reduz o acesso a uma indireção.
Encerro com a gerência de memória. Na gerência explícita o programa pede e devolve, e os dois modos de errar são simétricos: devolver cedo demais, produzindo referência para memória já reaproveitada, e nunca devolver, produzindo consumo sem limite. Vem junto a fragmentação — a externa, quando a memória livre existe mas está partida em pedaços pequenos demais, e a interna, quando o alocador entrega blocos arredondados e a diferença se perde dentro deles. Há um padrão intermediário, o mais simples que funciona: a alocação por região, em que tudo o que foi alocado durante uma fase é devolvido de uma vez ao final dela, sob a condição de nada sobreviver à região.
Quando dados sobrevivem à construção que os criou, entra a coleta automática, toda construída sobre a alcançabilidade: recupera-se o dado quando nenhuma cadeia de referências partindo das raízes chega até ele. A contagem de referências recupera o objeto quando a conta zera, distribui bem o custo e não trata ciclos, que mantêm contagens positivas para sempre. A marcação e varredura, que apareceu já na primeira implementação de LISP, por John McCarthy, no início dos anos 1960, marca o alcançável e varre o resto; trata ciclos e paga com uma pausa proporcional ao tamanho da memória. Os coletores por cópia tornam o custo proporcional ao que sobrevive, ao preço de metade da memória; e os geracionais exploram a observação de que a maior parte dos objetos morre pouco depois de criada. Se o seu projeto não precisa de nenhuma delas, diga por quê: “não há coleta automática porque nada sobrevive à ativação que o criou” é uma frase de engenharia; omitir o assunto não é.
1.7 O caso conduzido
Decisão de projeto só se aprende vendo alguém decidir, inclusive quando o argumento do livro não fecha. Acompanhe a camada intermediária, a especificação do objeto e o mapa de memória no caso conduzido, com os números medidos e as divergências registradas.
1.7.1 6.1 O programa de referência, e por que ele tem condições compostas
O compilador da Peneira que vem sendo construído ao longo deste livro chega a este ponto com a árvore verificada em mãos e nada emitido ainda. O programa que uso como referência do capítulo foi escrito com um propósito único: exercitar a construção mais difícil que a linguagem admite.
Duas ações, uma com conjunção e outra com disjunção. Não é um exemplo de vitrine: é o menor programa que obriga a tradução a lidar com curto-circuito nos dois conectivos, e portanto o menor programa capaz de reprovar a notação pós-fixada.
1.7.2 6.2 A justificativa, com a conta feita para o nosso caso
Comecei pela parte incômoda, que é aplicar o argumento combinatório ao próprio projeto e ver o que acontece. O módulo de representação intermediária calcula a tabela em vez de enunciá-la:
13_ri.h
#ifndef PENEIRA_13_RI_H
#define PENEIRA_13_RI_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
#include "10_ast.h"
namespace peneira {
// Representação intermediária da Peneira: código de três endereços.
//
// Por que existe uma camada aqui, em vez de a árvore verificada ir direto para
// o objeto. O argumento é combinatório e vale escrever com números: para
// suportar $m$ linguagens de origem e $n$ destinos, a tradução direta custa
// $m \times n$ tradutores; com uma representação intermediária no meio, custa
// $m + n$. Cinco por cinco: vinte e cinco contra dez.
//
// Nesta disciplina $m = n = 1$, e o argumento combinatório sozinho NÃO
// justificaria a camada — seria uma indireção paga sem retorno. O que a
// justifica aqui é outra coisa, e é honesto dizer qual: o curto-circuito dos
// conectivos lógicos exige desvios, e desvios exigem rótulos cujo destino só
// se conhece depois. Fazer isso direto sobre a árvore, durante a emissão do
// objeto, mistura duas dificuldades; separá-las é o que torna as duas
// tratáveis. A camada se paga em clareza, não em reaproveitamento.
enum class OpRI : std::uint8_t {
Rotulo, // marca um ponto do código; alvo de desvio
CasamentoDe, // t := o texto casado pela variável de ligação
Valor, // t := valor numérico de um casamento (o `value` da fonte)
Constante, // t := literal
Comparacao, // t := arg1 <op> arg2
DesvioSeFalso, // se arg1 for falso, desvia
Desvio, // desvia incondicionalmente
Emite, // emite (rotulo, arg1)
};
const char* nomeDaOpRI(OpRI op) noexcept;
// Uma instrução de três endereços: um resultado e até dois operandos.
//
// `destino` é o índice da instrução alvo, para os desvios. Ele nasce com
// kDestinoPendente e é preenchido depois — é o campo que a técnica de
// preenchimento retroativo manipula.
inline constexpr std::size_t kDestinoPendente = static_cast<std::size_t>(-1);
struct InstrucaoRI {
OpRI op = OpRI::Rotulo;
std::string resultado; // nome do temporário, ou do rótulo
std::string arg1;
std::string arg2;
std::string operador; // só para Comparacao
std::size_t destino = kDestinoPendente;
};
// O código de uma regra: a condição (com desvios) seguida da emissão.
struct CodigoRI {
std::vector<InstrucaoRI> instrucoes;
std::string padrao; // padrão que dispara a regra
std::string ligacao; // variável de ligação
};
std::string formatarRI(const CodigoRI& c);
// Tradutor de árvore verificada para código de três endereços.
//
// A técnica central é o **preenchimento retroativo**: ao traduzir uma condição,
// o desvio que sai quando ela é falsa precisa apontar para o fim da regra, e o
// fim da regra ainda não foi gerado. Em vez de fazer um segundo percurso para
// descobrir o endereço, a tradução guarda a lista das instruções incompletas e
// as preenche quando o endereço fica conhecido.
//
// É a mesma ideia do módulo 10 em outro disfarce: lá, a decisão sobre qual
// produção usar era adiada até haver informação; aqui, a decisão sobre para
// onde desviar.
class TradutorRI {
public:
// Traduz uma ação verificada (nó Acao) para código de três endereços.
CodigoRI traduzirAcao(const NoAst& acao);
std::size_t temporariosUsados() const noexcept;
private:
// Traduz uma expressão de valor e devolve o nome do temporário que a
// contém.
std::string traduzirValor(const NoAst& expr);
// Traduz uma condição. Devolve as listas de instruções de desvio que ainda
// precisam de destino: as que saem quando a condição é verdadeira e as que
// saem quando é falsa.
struct ListasDeDesvio {
std::vector<std::size_t> verdadeiro;
std::vector<std::size_t> falso;
};
ListasDeDesvio traduzirCondicao(const NoAst& cond);
// Preenche o destino de todas as instruções da lista.
void preencher(const std::vector<std::size_t>& lista, std::size_t destino);
std::size_t emitir(InstrucaoRI instrucao);
std::string novoTemporario();
std::vector<InstrucaoRI> instrucoes_;
std::size_t proximoTemporario_ = 0;
};
// Notação pós-fixada da mesma expressão.
//
// Está aqui porque é a forma intermediária mais simples que existe e serve de
// contraste: ela dispensa temporários e rótulos, porque a ordem de avaliação
// está na própria sequência. O preço é que ela não exprime desvio — e é
// exatamente por isso que ela não serve para o curto-circuito, o que fecha o
// argumento a favor do código de três endereços nesta linguagem.
std::string emPosFixada(const NoAst& expr);
// O argumento combinatório, calculado.
struct CustoDeTraducao {
std::size_t origens = 0;
std::size_t destinos = 0;
std::size_t tradutoresDiretos = 0; // origens * destinos
std::size_t tradutoresComIntermediaria = 0; // origens + destinos
};
CustoDeTraducao custoDeTraducao(std::size_t origens, std::size_t destinos) noexcept;
} // namespace peneira
#endif // PENEIRA_13_RI_H
A saída da demonstração é a tabela que já apareceu na primeira seção, e a nossa linha é a primeira: uma origem, um destino, um tradutor direto contra duas peças com a camada. O argumento clássico, aplicado com honestidade aqui, condena a camada.
A camada existe assim mesmo, e o motivo é o que a segunda justificativa prevê. O curto-circuito exige desvio, o desvio exige um destino que só se conhece adiante, e resolver isso ao mesmo tempo em que se decide a codificação do arquivo de saída torna as duas coisas difíceis. A camada se paga em clareza, não em reaproveitamento — e dizer isso é mais útil do que repetir uma frase que não se aplica.
1.7.3 6.3 As três formas sobre a mesma condição
Comparei as três formas sobre a condição value(n) > 100 and value(n) < 500, e a comparação é a que a seção 2.6 exigia.
A árvore verificada, que é o que já temos, tem a conjunção na raiz e as duas comparações como filhas, cada uma com uma extração de valor à esquerda e um literal à direita:
E
Comparacao ">"
ValorDe "n"
LiteralNumero "100"
Comparacao "<"
ValorDe "n"
LiteralNumero "500"A notação pós-fixada da mesma condição cabe em uma linha:
n valor 100 > n valor 500 < andÉ a mais curta das três, resolve a ordem de avaliação de graça e é a errada, exatamente pela razão geral: não há nela onde escrever um desvio, e sem desvio o and avalia sempre os dois lados.
Sobra o código de três endereços, que é o que o tradutor implementa:
13_ri.cpp
#include "13_ri.h"
#include <sstream>
#include <utility>
namespace peneira {
const char* nomeDaOpRI(OpRI op) noexcept {
switch (op) {
case OpRI::Rotulo: return "rotulo";
case OpRI::CasamentoDe: return "casamento";
case OpRI::Valor: return "valor";
case OpRI::Constante: return "const";
case OpRI::Comparacao: return "cmp";
case OpRI::DesvioSeFalso: return "se_falso";
case OpRI::Desvio: return "desvia";
case OpRI::Emite: return "emite";
}
return "<desconhecida>";
}
std::size_t TradutorRI::emitir(InstrucaoRI instrucao) {
instrucoes_.push_back(std::move(instrucao));
return instrucoes_.size() - 1;
}
std::string TradutorRI::novoTemporario() {
return "t" + std::to_string(proximoTemporario_++);
}
std::size_t TradutorRI::temporariosUsados() const noexcept {
return proximoTemporario_;
}
void TradutorRI::preencher(const std::vector<std::size_t>& lista,
std::size_t destino) {
for (const std::size_t i : lista) {
instrucoes_[i].destino = destino;
}
}
std::string TradutorRI::traduzirValor(const NoAst& expr) {
switch (expr.tipo) {
case TipoAst::LiteralNumero: {
const std::string t = novoTemporario();
InstrucaoRI ins;
ins.op = OpRI::Constante;
ins.resultado = t;
// O lexema, e não o valor reconvertido: preserva a forma escrita
// pelo autor no relatório, e a conversão já foi feita e validada no
// módulo 7.
ins.arg1 = expr.texto;
emitir(std::move(ins));
return t;
}
case TipoAst::LiteralTexto: {
const std::string t = novoTemporario();
InstrucaoRI ins;
ins.op = OpRI::Constante;
ins.resultado = t;
ins.arg1 = "\"" + expr.texto + "\"";
emitir(std::move(ins));
return t;
}
case TipoAst::Referencia: {
const std::string t = novoTemporario();
InstrucaoRI ins;
ins.op = OpRI::CasamentoDe;
ins.resultado = t;
ins.arg1 = expr.texto;
emitir(std::move(ins));
return t;
}
case TipoAst::ValorDe: {
// Duas instruções, e não uma: primeiro o casamento, depois a
// conversão. Separá-las é o que torna a conversão visível na
// representação — e a conversão é justamente o que a fase semântica
// exigiu que fosse explícita no programa fonte.
const std::string casamento = novoTemporario();
InstrucaoRI busca;
busca.op = OpRI::CasamentoDe;
busca.resultado = casamento;
busca.arg1 = expr.texto;
emitir(std::move(busca));
const std::string t = novoTemporario();
InstrucaoRI conversao;
conversao.op = OpRI::Valor;
conversao.resultado = t;
conversao.arg1 = casamento;
emitir(std::move(conversao));
return t;
}
default:
return "<indefinido>";
}
}
TradutorRI::ListasDeDesvio TradutorRI::traduzirCondicao(const NoAst& cond) {
ListasDeDesvio listas;
switch (cond.tipo) {
case TipoAst::Comparacao: {
const std::string esquerda =
cond.filhos.size() > 0 && cond.filhos[0]
? traduzirValor(*cond.filhos[0])
: "<indefinido>";
const std::string direita =
cond.filhos.size() > 1 && cond.filhos[1]
? traduzirValor(*cond.filhos[1])
: "<indefinido>";
const std::string t = novoTemporario();
InstrucaoRI comparacao;
comparacao.op = OpRI::Comparacao;
comparacao.resultado = t;
comparacao.arg1 = esquerda;
comparacao.arg2 = direita;
comparacao.operador = cond.texto;
emitir(std::move(comparacao));
InstrucaoRI desvio;
desvio.op = OpRI::DesvioSeFalso;
desvio.arg1 = t;
const std::size_t indice = emitir(std::move(desvio));
// Quando a comparação é falsa, desvia — destino a preencher.
// Quando é verdadeira, cai para a instrução seguinte, e essa
// "queda" é o caminho verdadeiro. Não emitir desvio para o caso
// verdadeiro é o que mantém o código curto.
listas.falso.push_back(indice);
return listas;
}
case TipoAst::E: {
// Curto-circuito do E: se o lado esquerdo falha, a expressão
// inteira falha e o direito NÃO é avaliado. O caminho verdadeiro do
// esquerdo cai no início do direito; as saídas falsas dos dois se
// juntam.
if (cond.filhos.size() < 2 || !cond.filhos[0] || !cond.filhos[1]) {
return listas;
}
ListasDeDesvio esquerda = traduzirCondicao(*cond.filhos[0]);
// O verdadeiro do esquerdo aponta para onde o direito começa, que é
// a próxima instrução a ser emitida.
preencher(esquerda.verdadeiro, instrucoes_.size());
ListasDeDesvio direita = traduzirCondicao(*cond.filhos[1]);
listas.verdadeiro = std::move(direita.verdadeiro);
listas.falso = std::move(esquerda.falso);
for (const std::size_t i : direita.falso) {
listas.falso.push_back(i);
}
return listas;
}
case TipoAst::Ou: {
// Curto-circuito do OU, simétrico: se o esquerdo é verdadeiro, a
// expressão inteira é verdadeira. O caminho FALSO do esquerdo cai
// no direito.
if (cond.filhos.size() < 2 || !cond.filhos[0] || !cond.filhos[1]) {
return listas;
}
ListasDeDesvio esquerda = traduzirCondicao(*cond.filhos[0]);
// O verdadeiro do esquerdo tem de pular o lado direito inteiro, e
// esse destino ainda não existe. Um desvio incondicional carrega a
// pendência adiante.
InstrucaoRI salto;
salto.op = OpRI::Desvio;
const std::size_t indiceSalto = emitir(std::move(salto));
preencher(esquerda.verdadeiro, indiceSalto);
preencher(esquerda.falso, instrucoes_.size());
ListasDeDesvio direita = traduzirCondicao(*cond.filhos[1]);
listas.verdadeiro.push_back(indiceSalto);
for (const std::size_t i : direita.verdadeiro) {
listas.verdadeiro.push_back(i);
}
listas.falso = std::move(direita.falso);
return listas;
}
default:
return listas;
}
}
CodigoRI TradutorRI::traduzirAcao(const NoAst& acao) {
instrucoes_.clear();
proximoTemporario_ = 0;
CodigoRI codigo;
codigo.padrao = acao.texto;
codigo.ligacao = acao.conteudo;
ListasDeDesvio listas;
const bool temCondicao = !acao.filhos.empty() && acao.filhos[0] != nullptr;
if (temCondicao) {
listas = traduzirCondicao(*acao.filhos[0]);
// O caminho verdadeiro segue para a emissão, que é a próxima
// instrução.
preencher(listas.verdadeiro, instrucoes_.size());
}
// A emissão.
if (!acao.filhos.empty() && acao.filhos.back() &&
acao.filhos.back()->tipo == TipoAst::Emissao) {
const NoAst& emissao = *acao.filhos.back();
std::string valor = "<indefinido>";
if (!emissao.filhos.empty() && emissao.filhos[0]) {
valor = traduzirValor(*emissao.filhos[0]);
}
InstrucaoRI ins;
ins.op = OpRI::Emite;
ins.arg1 = "\"" + emissao.texto + "\"";
ins.arg2 = valor;
emitir(std::move(ins));
}
// Fim da regra. Todo desvio de condição falsa termina aqui, e este é o
// momento em que o endereço finalmente se conhece: é o índice logo após a
// última instrução.
preencher(listas.falso, instrucoes_.size());
codigo.instrucoes = std::move(instrucoes_);
return codigo;
}
std::string formatarRI(const CodigoRI& c) {
std::ostringstream out;
out << " regra: on " << c.padrao << "(" << c.ligacao << ")\n";
for (std::size_t i = 0; i < c.instrucoes.size(); ++i) {
const InstrucaoRI& ins = c.instrucoes[i];
out << " " << i << ": ";
switch (ins.op) {
case OpRI::Constante:
out << ins.resultado << " := " << ins.arg1;
break;
case OpRI::CasamentoDe:
out << ins.resultado << " := casamento " << ins.arg1;
break;
case OpRI::Valor:
out << ins.resultado << " := valor " << ins.arg1;
break;
case OpRI::Comparacao:
out << ins.resultado << " := " << ins.arg1 << " "
<< ins.operador << " " << ins.arg2;
break;
case OpRI::DesvioSeFalso:
out << "se_falso " << ins.arg1 << " desvia para "
<< ins.destino;
break;
case OpRI::Desvio:
out << "desvia para " << ins.destino;
break;
case OpRI::Emite:
out << "emite " << ins.arg1 << ", " << ins.arg2;
break;
case OpRI::Rotulo:
out << "rotulo " << ins.resultado;
break;
}
out << '\n';
}
out << " " << c.instrucoes.size() << ": (fim da regra)\n";
return out.str();
}
std::string emPosFixada(const NoAst& expr) {
switch (expr.tipo) {
case TipoAst::LiteralNumero:
case TipoAst::LiteralTexto:
return expr.texto;
case TipoAst::Referencia:
return expr.texto;
case TipoAst::ValorDe:
return expr.texto + " valor";
case TipoAst::Comparacao: {
const std::string e = expr.filhos.size() > 0 && expr.filhos[0]
? emPosFixada(*expr.filhos[0])
: "";
const std::string d = expr.filhos.size() > 1 && expr.filhos[1]
? emPosFixada(*expr.filhos[1])
: "";
return e + " " + d + " " + expr.texto;
}
case TipoAst::E:
case TipoAst::Ou: {
const std::string e = expr.filhos.size() > 0 && expr.filhos[0]
? emPosFixada(*expr.filhos[0])
: "";
const std::string d = expr.filhos.size() > 1 && expr.filhos[1]
? emPosFixada(*expr.filhos[1])
: "";
return e + " " + d + (expr.tipo == TipoAst::E ? " and" : " or");
}
default:
return "";
}
}
CustoDeTraducao custoDeTraducao(std::size_t origens,
std::size_t destinos) noexcept {
CustoDeTraducao c;
c.origens = origens;
c.destinos = destinos;
c.tradutoresDiretos = origens * destinos;
c.tradutoresComIntermediaria = origens + destinos;
return c;
}
} // namespace peneira
Uma decisão de tradução merece destaque porque não é óbvia e vai contra o instinto de encurtar: a construção value(n) vira duas instruções, e não uma. Primeiro o casamento é buscado, depois convertido em número. Poderia ser uma só, e seria mais curto. Separei porque a conversão explícita foi justamente o que a análise semântica exigiu que aparecesse no programa fonte — foi a razão de recusar conversão implícita. Colapsá-la aqui esconderia, na representação intermediária, a distinção que a fase anterior lutou para tornar visível.
1.7.4 6.4 O traçado do curto-circuito
Vale acompanhar as duas ações traduzidas, porque é nelas que o preenchimento retroativo se torna concreto. A primeira, com conjunção:
regra: on numero(n)
0: t0 := casamento n
1: t1 := valor t0
2: t2 := 100
3: t3 := t1 > t2
4: se_falso t3 desvia para 12
5: t4 := casamento n
6: t5 := valor t4
7: t6 := 500
8: t7 := t5 < t6
9: se_falso t7 desvia para 12
10: t8 := casamento n
11: emite "faixa", t8
12: (fim da regra)As duas saídas falsas — a da instrução 4 e a da instrução 9 — apontam para o mesmo lugar, e nenhuma das duas conhecia esse endereço quando foi gerada. As duas entraram na mesma lista falsa e foram preenchidas de uma vez, no momento em que a tradução da regra terminou e a posição 12 passou a existir. É a fusão de listas da seção 3.4 em ação: a lista falsa da conjunção é a união das listas falsas dos dois lados.
A segunda ação, com disjunção, exibe o caso que exige o desvio incondicional:
regra: on numero(n)
0: t0 := casamento n
1: t1 := valor t0
2: t2 := 0
3: t3 := t1 < t2
4: se_falso t3 desvia para 6
5: desvia para 11
6: t4 := casamento n
7: t5 := valor t4
8: t6 := 1000
9: t7 := t5 > t6
10: se_falso t7 desvia para 13
11: t8 := casamento n
12: emite "extremo", t8
13: (fim da regra)Leia a instrução 5 com atenção, porque ela é o coração do esquema da disjunção. Quando a primeira comparação é verdadeira, o controle cai nela — e ela precisa pular o lado direito inteiro, cujo fim ainda não existia no momento da emissão. Ela nasceu pendente e foi preenchida com 11 quando o código da emissão começou. Já a saída falsa da primeira comparação aponta para 6, que é onde o lado direito começa: falhar à esquerda, numa disjunção, significa “continue testando”.
Cada ação usa nove temporários, e o número não é decorativo: é igual ao número de nós de expressão visitados, o que é a verificação de contagem da seção 3.1. E, ao final das duas traduções, o número de desvios com destino pendente é zero — que é a verificação do Teorema 3.1, escrita como código e não como intenção.
Registro um limite do artefato, porque ele afeta o que este caso consegue demonstrar. A tradução de condicionais está exercitada, já que a condição where é um condicional e é dela que saem os desvios acima. A de laços não está: a Peneira não tem laço algum no nível do usuário, porque a repetição da linguagem é a varredura da entrada feita pelo executor, e isso é parte do modelo de execução, não uma construção que se escreva. Como já argumentei, isso significa que o caso difícil está coberto e o fácil não — todo desvio aqui é para a frente.
1.7.5 6.5 A especificação do objeto, escrita antes do código
Este é o entregável principal do capítulo, e a ordem de trabalho foi a que a seção 4.1 defende: a especificação primeiro. O cabeçalho é a especificação, com os campos trazendo semântica declarada e não apenas nome:
13_objeto.h
#ifndef PENEIRA_13_OBJETO_H
#define PENEIRA_13_OBJETO_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
#include "03_afd.h"
namespace peneira {
// O FORMATO DO PROGRAMA OBJETO DA PENEIRA.
//
// Este cabeçalho é a especificação. O critério de qualidade anunciado para o
// módulo é literal: outra pessoa tem de conseguir escrever um executor
// compatível lendo apenas isto. Por isso os campos vêm com semântica declarada,
// e não apenas com nome.
//
// O objeto tem duas seções, conforme o design do artefato:
//
// 1. A TABELA DE PADRÕES — um autômato finito determinístico por `pattern`,
// serializado como tabela de transição.
// 2. O CÓDIGO DAS REGRAS — para cada ação, uma sequência de instruções de uma
// máquina de pilha.
//
// A escolha de máquina de pilha, e não de registradores, tem motivo: as
// expressões da Peneira são rasas (uma comparação, no máximo alguns conectivos)
// e a máquina de pilha dispensa alocação de registradores por completo. Numa
// linguagem com expressões profundas a conta se inverteria.
// ---------------------------------------------------------------------------
// Conjunto de instruções
// ---------------------------------------------------------------------------
//
// As sete primeiras vêm do design do artefato. As duas de desvio são
// ACRÉSCIMO DELIBERADO, e registro o porquê em vez de silenciá-lo: o design
// lista `AND` e `OR` como instruções, o que implica avaliação ansiosa dos dois
// lados; o curto-circuito exigido na geração de código do módulo seguinte não
// é exprimível sem desvio. Mantive `AND` e `OR` no conjunto — elas continuam
// válidas e são o que um gerador ansiado emitiria — e acrescentei os desvios,
// que são o que o nosso gerador vai usar. Um executor compatível precisa
// implementar as nove.
enum class OpCode : std::uint8_t {
PUSH_CONST = 0, // empilha a constante de índice `argumento`
PUSH_MATCH = 1, // empilha o texto casado pela ligação de índice `argumento`
VALUE = 2, // desempilha texto, empilha o número correspondente
CMP_GT = 3, // desempilha b, a; empilha (a > b)
CMP_LT = 4,
CMP_GE = 5,
CMP_LE = 6,
CMP_EQ = 7,
CMP_NE = 8,
AND = 9, // desempilha b, a; empilha (a e b) — avaliação ansiosa
OR = 10, // desempilha b, a; empilha (a ou b) — avaliação ansiosa
JUMP_IF_FALSE = 11, // desempilha; se falso, desvia para `argumento`
JUMP = 12, // desvia para `argumento`
EMIT = 13, // desempilha valor; emite com o rótulo de índice `argumento`
HALT = 14, // encerra a execução desta regra
};
const char* nomeDoOpCode(OpCode op) noexcept;
// Toda instrução ocupa dois campos: o código e um argumento inteiro. As que não
// usam argumento gravam zero. O tamanho fixo é decisão consciente — dispensa
// decodificação de comprimento variável no executor, ao custo de alguns bytes
// que não importam nesta escala.
struct Instrucao {
OpCode op = OpCode::HALT;
std::uint32_t argumento = 0;
};
// ---------------------------------------------------------------------------
// Seções do objeto
// ---------------------------------------------------------------------------
// Um padrão compilado, serializado como tabela de transição.
//
// `transicoes` é a matriz achatada: a transição do estado `e` pelo símbolo `s`
// está em `transicoes[e * 256 + s]`. O valor kSemTransicao marca ausência, que
// o executor trata como falha de casamento.
//
// A matriz densa é escolha de FORMATO, e diverge da representação esparsa que o
// compilador usa internamente desde o módulo 3. O motivo é que os papéis são
// diferentes: dentro do compilador, o autômato é construído e transformado, e a
// esparsa economiza memória num alfabeto de 256 símbolos; no objeto, ele só é
// consultado, e a densa dá consulta em tempo constante sem busca. Trocar de
// representação na fronteira entre as duas fases é a decisão certa, e é o tipo
// de coisa que só fica evidente quando a especificação é escrita antes do
// código.
inline constexpr std::uint32_t kSemTransicao = 0xFFFFFFFFu;
inline constexpr std::size_t kTamanhoDoAlfabeto = 256;
struct PadraoObjeto {
std::string nome;
std::uint32_t quantidadeDeEstados = 0;
std::uint32_t estadoInicial = 0;
std::vector<std::uint8_t> finais; // 1 por estado
std::vector<std::uint32_t> transicoes; // achatada, 256 por estado
bool casaSomenteNumeros = false; // do verificador de tipos
};
// O código de uma regra.
struct RegraObjeto {
std::uint32_t indiceDoPadrao = 0; // qual padrão dispara esta regra
std::string ligacao; // nome da variável, para diagnóstico
std::vector<Instrucao> codigo;
};
// O programa objeto completo.
struct ProgramaObjeto {
// Constantes agrupadas numa área única, referenciadas por índice. Textos e
// números moram no mesmo vetor, na forma textual: a distinção de tipo já
// foi resolvida na análise semântica, e o executor sabe qual instrução lê o
// quê.
std::vector<std::string> constantes;
std::vector<PadraoObjeto> padroes;
std::vector<RegraObjeto> regras;
// Registra a constante e devolve o índice, reaproveitando se já existir.
std::uint32_t adicionarConstante(const std::string& valor);
};
// Converte o autômato interno para a forma do objeto.
PadraoObjeto serializarPadrao(const Afd& afd, const std::string& nome,
bool casaSomenteNumeros);
// Forma textual do objeto, legível e suficiente para conferência manual.
std::string formatarObjeto(const ProgramaObjeto& p);
// O MODELO DE EXECUÇÃO, em texto, para acompanhar a especificação dos campos.
// Está em código, e não só no material, porque a especificação e o
// implementador precisam ler a mesma coisa.
std::string modeloDeExecucao();
} // namespace peneira
#endif // PENEIRA_13_OBJETO_H
O objeto tem duas seções: uma tabela com um autômato determinístico por pattern, serializado como tabela de transição, e o código das regras para uma máquina de pilha. A escolha da pilha se justifica pela recorrência do Teorema 4.1 aplicada às expressões da Peneira, que são rasas — uma comparação, no máximo alguns conectivos —, de modo que a profundidade nunca passa de um punhado de posições e a alocação de registradores fica dispensada por completo.
Ao escrever o conjunto de instruções encontrei uma divergência entre dois documentos de projeto e prefiro registrá-la a silenciá-la. O desenho original do artefato lista sete instruções, entre elas AND e OR; ter AND e OR como instruções significa avaliação ansiosa, porque para combinar dois valores é preciso ter calculado os dois. E o capítulo seguinte exige curto-circuito, que não é exprimível sem desvio. Resolvi acrescentando duas instruções de desvio ao conjunto e mantendo AND e OR: as sete originais continuam válidas e são o que um gerador ansioso emitiria; os desvios são o que o nosso gerador vai usar. Somam-se a elas as seis comparações, porque o desenho nomeia CMP_GT como representante de uma família e não como instrução isolada: o conjunto fica com quinze códigos de operação, e é essa a conta que um executor compatível precisa implementar. O que não fiz foi mudar o desenho em silêncio nem torcer o conjunto para caber na lista original — divergência entre documentos acontece, e o que não pode acontecer é ela ser resolvida sem ficar escrita.
Escrever a especificação antes fez aparecer duas decisões que eu teria tomado por inércia. A primeira é a troca de representação da função de transição, exatamente o caso geral da seção 4.4: dentro do compilador, ela é um mapa esparso por estado, decisão tomada porque o alfabeto tem 256 símbolos e a maior parte não é usada; no objeto, gravei uma matriz densa. E aqui a medição desmente a intuição confortável — a demonstração imprime a densidade real:
[0] numero: 5 estados, inicial 0, 2 final(is)
celulas: 1280, preenchidas: 52Quatro por cento. A matriz densa desperdiça noventa e seis por cento do espaço que ocupa, e isso não deve ser escondido. A defesa da escolha é feita com o número na mesa: são 5120 bytes por padrão, o laço interno do executor consulta essa tabela uma vez por byte da entrada, e nessa posição a consulta em tempo constante vale mais que os kilobytes. A defesa tem prazo de validade, e é esse número impresso que permitirá notar quando ele vencer.
1.7.6 6.6 O modelo de execução
A especificação dos campos não basta, e o modelo está no código para que a especificação e quem a implementa leiam a mesma coisa:
13_objeto.cpp
#include "13_objeto.h"
#include <sstream>
namespace peneira {
const char* nomeDoOpCode(OpCode op) noexcept {
switch (op) {
case OpCode::PUSH_CONST: return "PUSH_CONST";
case OpCode::PUSH_MATCH: return "PUSH_MATCH";
case OpCode::VALUE: return "VALUE";
case OpCode::CMP_GT: return "CMP_GT";
case OpCode::CMP_LT: return "CMP_LT";
case OpCode::CMP_GE: return "CMP_GE";
case OpCode::CMP_LE: return "CMP_LE";
case OpCode::CMP_EQ: return "CMP_EQ";
case OpCode::CMP_NE: return "CMP_NE";
case OpCode::AND: return "AND";
case OpCode::OR: return "OR";
case OpCode::JUMP_IF_FALSE: return "JUMP_IF_FALSE";
case OpCode::JUMP: return "JUMP";
case OpCode::EMIT: return "EMIT";
case OpCode::HALT: return "HALT";
}
return "<desconhecido>";
}
std::uint32_t ProgramaObjeto::adicionarConstante(const std::string& valor) {
for (std::size_t i = 0; i < constantes.size(); ++i) {
if (constantes[i] == valor) {
return static_cast<std::uint32_t>(i);
}
}
constantes.push_back(valor);
return static_cast<std::uint32_t>(constantes.size() - 1);
}
PadraoObjeto serializarPadrao(const Afd& afd, const std::string& nome,
bool casaSomenteNumeros) {
PadraoObjeto p;
p.nome = nome;
p.quantidadeDeEstados = static_cast<std::uint32_t>(afd.quantidadeDeEstados());
p.estadoInicial = static_cast<std::uint32_t>(afd.inicial());
p.casaSomenteNumeros = casaSomenteNumeros;
p.finais.resize(afd.quantidadeDeEstados(), 0);
p.transicoes.assign(afd.quantidadeDeEstados() * kTamanhoDoAlfabeto,
kSemTransicao);
for (std::size_t e = 0; e < afd.quantidadeDeEstados(); ++e) {
p.finais[e] = afd.ehFinal(e) ? std::uint8_t{1} : std::uint8_t{0};
for (std::size_t s = 0; s < kTamanhoDoAlfabeto; ++s) {
const Estado destino =
afd.transicao(e, static_cast<Simbolo>(s));
if (destino != kSemEstado) {
p.transicoes[e * kTamanhoDoAlfabeto + s] =
static_cast<std::uint32_t>(destino);
}
}
}
return p;
}
std::string formatarObjeto(const ProgramaObjeto& p) {
std::ostringstream out;
out << " area de constantes (" << p.constantes.size() << "):\n";
for (std::size_t i = 0; i < p.constantes.size(); ++i) {
out << " [" << i << "] " << p.constantes[i] << '\n';
}
out << "\n tabela de padroes (" << p.padroes.size() << "):\n";
for (std::size_t i = 0; i < p.padroes.size(); ++i) {
const PadraoObjeto& pd = p.padroes[i];
// Conta as transições preenchidas para mostrar a densidade real da
// matriz — o número que justifica ou condena a escolha de formato.
std::size_t preenchidas = 0;
for (const std::uint32_t t : pd.transicoes) {
if (t != kSemTransicao) {
++preenchidas;
}
}
std::size_t finais = 0;
for (const std::uint8_t f : pd.finais) {
finais += f;
}
out << " [" << i << "] " << pd.nome << ": "
<< pd.quantidadeDeEstados << " estados, inicial "
<< pd.estadoInicial << ", " << finais << " final(is)\n"
<< " celulas: " << pd.transicoes.size() << ", preenchidas: "
<< preenchidas << '\n'
<< " casa somente numeros: "
<< (pd.casaSomenteNumeros ? "sim" : "nao") << '\n';
}
out << "\n codigo das regras (" << p.regras.size() << "):\n";
for (std::size_t i = 0; i < p.regras.size(); ++i) {
const RegraObjeto& r = p.regras[i];
out << " regra [" << i << "] padrao ["
<< r.indiceDoPadrao << "] ligacao '" << r.ligacao << "'\n";
for (std::size_t k = 0; k < r.codigo.size(); ++k) {
const Instrucao& ins = r.codigo[k];
out << " " << k << ": " << nomeDoOpCode(ins.op);
switch (ins.op) {
case OpCode::PUSH_CONST:
case OpCode::EMIT:
out << " " << ins.argumento << " ; "
<< (ins.argumento < p.constantes.size()
? p.constantes[ins.argumento]
: std::string("<fora de faixa>"));
break;
case OpCode::PUSH_MATCH:
case OpCode::JUMP:
case OpCode::JUMP_IF_FALSE:
out << " " << ins.argumento;
break;
default:
break;
}
out << '\n';
}
}
return out.str();
}
std::string modeloDeExecucao() {
// Escrito como contrato para quem for implementar o executor, e não como
// descrição do que o nosso executor faz — ainda não existe executor. A
// diferença importa: um descreve o que se pode assumir, o outro descreve o
// que aconteceu de ser implementado.
return
" ESTADO DA MAQUINA\n"
" - a entrada, lida como sequencia de bytes\n"
" - uma posicao de leitura, que so avanca\n"
" - uma pilha de valores, vazia no inicio de cada regra\n"
" - o ambiente de casamento: o texto casado e o padrao que casou\n\n"
" LACO PRINCIPAL\n"
" Na posicao corrente, o executor tenta TODOS os padroes em\n"
" paralelo, avancando enquanto algum automato ainda tem transicao.\n"
" Registra a ultima posicao em que algum automato esteve em estado\n"
" final, e qual padrao. Ao travar, retrocede ate essa posicao: e a\n"
" regra do CASAMENTO MAIS LONGO, a mesma do analisador lexico.\n"
" Empate entre padroes no mesmo comprimento resolve-se pela ORDEM DE\n"
" DECLARACAO no programa fonte — o primeiro declarado vence.\n"
" Sem casamento nenhum, a posicao avanca um byte e o laco recomeca.\n\n"
" DISPARO DA REGRA\n"
" Com um casamento, o executor liga o texto casado a variavel da\n"
" regra correspondente e executa o codigo daquela regra desde a\n"
" instrucao 0, com a pilha vazia. A execucao termina em HALT ou ao\n"
" passar da ultima instrucao.\n"
" Terminada a regra, a posicao de leitura avanca para o fim do\n"
" casamento e o laco principal recomeca.\n\n"
" SEMANTICA DAS INSTRUCOES\n"
" PUSH_CONST k empilha constantes[k]\n"
" PUSH_MATCH k empilha o texto casado (k identifica a ligacao)\n"
" VALUE desempilha texto, empilha o numero que ele denota\n"
" CMP_* desempilha b, depois a; empilha o resultado de a<op>b\n"
" AND / OR desempilha b, depois a; empilha a combinacao\n"
" JUMP_IF_FALSE k desempilha; se falso, a proxima instrucao e k\n"
" JUMP k a proxima instrucao e k\n"
" EMIT k desempilha o valor e emite o par (constantes[k], valor)\n"
" HALT encerra esta regra\n\n"
" CONDICOES DE ERRO QUE O EXECUTOR PRECISA TRATAR\n"
" - VALUE sobre texto que nao denota numero: nao pode ocorrer, porque\n"
" a analise semantica provou por inclusao de linguagens que o\n"
" padrao so casa numeros. Um executor defensivo aborta com\n"
" diagnostico em vez de produzir valor arbitrario.\n"
" - desvio para fora da faixa de instrucoes: objeto malformado.\n"
" - pilha vazia numa instrucao que desempilha: objeto malformado.\n";
}
} // namespace peneira
Três pontos exigiram decisão explícita, e são justamente os que faltariam numa especificação apressada. O casamento mais longo é a mesma regra do analisador léxico, e reusá-la é o que mantém a linguagem coerente consigo mesma. O empate entre padrões de mesmo comprimento resolve-se pela ordem de declaração no fonte — e essa foi a decisão que o critério de completude revelou: ela estava ausente de tudo o que havia sido escrito até então, e sem ela dois executores corretos produziriam saídas diferentes para o mesmo programa. Não é um detalhe nem uma otimização: é uma escolha que muda a saída. As condições de erro estão listadas, inclusive uma que não pode ocorrer — a extração de valor sobre texto não numérico, impossível porque a análise semântica provou que aquele padrão só casa números —, e mesmo assim o executor deve abortar com diagnóstico, porque o objeto é um arquivo e arquivos podem ser adulterados.
A seção de regras sai vazia nesta demonstração, e de propósito: preenchê-la é geração de código, que é o capítulo seguinte. Este capítulo entrega o formato e a representação intermediária; o próximo traduz uma na outra.
1.7.7 6.7 O mapa de memória e o registro de ativação
O ambiente de execução da Peneira é modesto, e é justamente por isso que ele deixa a lição visível:
13_ambiente.h
#ifndef PENEIRA_13_AMBIENTE_H
#define PENEIRA_13_AMBIENTE_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
namespace peneira {
// AMBIENTES DE EXECUÇÃO.
//
// Duas coisas moram neste arquivo, e é preciso separá-las com clareza porque
// só a primeira é o nosso artefato:
//
// 1. O ambiente de execução DA PENEIRA — a divisão de memória que o programa
// objeto exige e o registro de ativação de uma regra. Isso é o sistema.
//
// 2. Um EXEMPLO MÍNIMO ISOLADO de registro de ativação com procedimentos
// aninhados, cadeia de controle e cadeia de acesso. Isso NÃO faz parte do
// compilador da Peneira, e não faria sentido embutir: a linguagem não tem
// procedimentos definidos pelo usuário, e inventar uns só para exercitar
// o mecanismo distorceria o artefato. Fica aqui como exemplo separado,
// pelo mesmo padrão do exemplo de tradução do módulo 1.
//
// O motivo de não omitir o segundo é que ele é o repertório necessário para ler
// qualquer linguagem real, e a conexão com a organização de memória vista em
// arquitetura de computadores é direta.
// ---------------------------------------------------------------------------
// 1. O ambiente de execução da Peneira
// ---------------------------------------------------------------------------
// As quatro áreas em que a memória de um programa em execução se divide, com o
// que cada uma guarda no caso da Peneira. Tamanho zero significa "cresce em
// execução".
enum class AreaDeMemoria : std::uint8_t {
Codigo, // o código das regras; imutável, tamanho conhecido na compilação
Estatica, // constantes e tabelas de transição; tamanho conhecido também
Pilha, // a pilha de avaliação da regra corrente
Monte, // o texto casado, cujo tamanho só se conhece em execução
};
const char* nomeDaArea(AreaDeMemoria a) noexcept;
struct DescricaoDeArea {
AreaDeMemoria area;
std::string conteudo;
bool tamanhoConhecidoNaCompilacao = false;
std::size_t bytesNesteObjeto = 0; // 0 quando cresce em execução
};
// Descreve o mapa de memória do objeto dado, com os tamanhos reais das áreas
// estáticas. É o que permite dizer, com número, quanto do programa é decidido
// na compilação e quanto sobra para a execução.
struct ProgramaObjeto; // declarado em 13_objeto.h
std::vector<DescricaoDeArea> mapaDeMemoria(const ProgramaObjeto& objeto);
// O registro de ativação de uma regra da Peneira.
//
// A Peneira não tem chamada de procedimento, e mesmo assim tem registro de
// ativação — porque disparar uma regra É uma ativação: há um ponto de entrada,
// um conjunto de valores ligados na entrada, um espaço de trabalho próprio e um
// retorno. O registro é pequeno porque a linguagem é pequena, e mostrar que ele
// existe é o que liga o conceito ao artefato em vez de deixá-lo abstrato.
struct AtivacaoDeRegra {
std::uint32_t regra = 0;
std::size_t posicaoNaEntrada = 0; // onde o casamento começou
std::string textoCasado; // o parâmetro, em essência
std::size_t topoDaPilha = 0; // espaço de trabalho
std::size_t enderecoDeRetorno = 0; // para onde o laço principal volta
};
std::string descreverAtivacao(const AtivacaoDeRegra& a);
// Por que NÃO há cadeia de controle nem de acesso na Peneira: as ativações não
// se aninham. Uma regra dispara, executa e termina antes de a próxima começar,
// então a "pilha" de ativações tem no máximo um elemento. É o que torna o
// registro acima um registro só, e não uma pilha deles.
std::size_t profundidadeMaximaDeAtivacao() noexcept;
// ---------------------------------------------------------------------------
// 2. Exemplo mínimo isolado: aninhamento, cadeia de controle e de acesso
// ---------------------------------------------------------------------------
//
// NÃO faz parte do compilador da Peneira. Existe para exercitar o mecanismo que
// a linguagem não tem, sobre um programa hipotético com procedimentos
// aninhados.
// Um procedimento do exemplo: nome, nível de aninhamento léxico e quem o
// contém.
struct ProcedimentoExemplo {
std::string nome;
std::size_t nivelLexico = 0;
std::size_t contidoEm = 0; // índice do procedimento envolvente
};
// Um quadro na pilha de execução do exemplo.
struct Quadro {
std::size_t procedimento = 0;
// Cadeia de CONTROLE: quem me chamou. Segue a ordem de EXECUÇÃO.
std::size_t eloDeControle = 0;
// Cadeia de ACESSO: o quadro do procedimento que me CONTÉM no texto do
// programa. Segue a ordem LÉXICA. As duas coincidem em muitos casos e
// divergem exatamente quando a recursão ou a chamada cruzada entram —
// e é essa divergência que justifica manter as duas.
std::size_t eloDeAcesso = 0;
bool temElo = false;
};
// Os procedimentos do exemplo: um programa principal contendo `externo`, que
// contém `interno`.
const std::vector<ProcedimentoExemplo>& procedimentosDoExemplo();
// Simula a sequência de chamadas dada (por índice de procedimento) e devolve a
// pilha de quadros resultante, com as duas cadeias montadas.
std::vector<Quadro> simularChamadas(const std::vector<std::size_t>& chamadas);
std::string desenharPilha(const std::vector<Quadro>& pilha);
// Resolve o acesso a uma variável declarada no nível léxico dado, a partir do
// topo da pilha, seguindo a cadeia de ACESSO. Devolve o índice do quadro que a
// contém, ou o tamanho da pilha se não achar.
//
// É este percurso que torna a cadeia de acesso necessária: seguir a de controle
// aqui daria a variável do chamador, que pode não ser o mesmo procedimento que
// envolve este no texto.
std::size_t resolverAcesso(const std::vector<Quadro>& pilha,
std::size_t nivelLexicoAlvo);
} // namespace peneira
#endif // PENEIRA_13_AMBIENTE_H
A divisão útil não é a nominal, e sim a que separa o que o compilador sabe do que só a execução descobre:
area | tamanho conhecido na compilacao | bytes
---------+--------------------------------+-------
codigo | sim | 0
estatica | sim | 5137
pilha | nao | cresce
monte | nao | cresceA área de código aparece com zero bytes porque o gerador ainda não emitiu nada, e essa linha custou uma correção: na primeira versão, tamanho zero e tamanho dinâmico apareciam iguais, e a área mais estática de todas parecia crescer em execução. É exatamente a armadilha apontada na seção 5.1, e ela só apareceu rodando.
A Peneira não tem chamada de procedimento e mesmo assim tem registro de ativação, porque disparar uma regra é uma ativação: há entrada, valores ligados nela, espaço de trabalho próprio e retorno.
registro de ativacao da regra 0:
posicao na entrada ... 42
texto casado ......... "250" (3 bytes)
topo da pilha ........ 0
endereco de retorno .. 45O texto casado é, em essência, o parâmetro; o endereço de retorno é para onde o laço principal volta. E há um resultado que decide o resto: a profundidade máxima da pilha de ativações é um, porque uma regra termina antes de a próxima começar. As ativações não se aninham, e é por isso que a Peneira não precisa de cadeia de controle nem de cadeia de acesso — o caso degenerado previsto no fim da seção 5.3.
1.7.8 6.8 O mecanismo que a linguagem dispensa
A ementa deste capítulo pede as duas cadeias e a Peneira não as exercita. Havia duas saídas ruins e uma terceira.
A primeira saída ruim seria omitir o assunto, alegando que o artefato não usa. É o repertório necessário para ler qualquer linguagem real, e a conexão com organização de computadores é direta demais para ser desperdiçada. A segunda seria inventar procedimentos na Peneira só para exercitar o mecanismo, o que distorceria o artefato: a linguagem não precisa deles, e acrescentá-los produziria uma característica que nenhuma outra parte do sistema usa. A terceira, que foi a adotada, é manter um exemplo mínimo isolado, claramente separado do compilador — o mesmo padrão do exemplo de interpretação contra compilação do primeiro capítulo:
13_ambiente.cpp
#include "13_ambiente.h"
#include <sstream>
#include "13_objeto.h"
namespace peneira {
const char* nomeDaArea(AreaDeMemoria a) noexcept {
switch (a) {
case AreaDeMemoria::Codigo: return "codigo";
case AreaDeMemoria::Estatica: return "estatica";
case AreaDeMemoria::Pilha: return "pilha";
case AreaDeMemoria::Monte: return "monte";
}
return "<desconhecida>";
}
std::vector<DescricaoDeArea> mapaDeMemoria(const ProgramaObjeto& objeto) {
std::vector<DescricaoDeArea> areas;
std::size_t bytesDeCodigo = 0;
for (const RegraObjeto& r : objeto.regras) {
bytesDeCodigo += r.codigo.size() * sizeof(Instrucao);
}
std::size_t bytesEstaticos = 0;
for (const PadraoObjeto& p : objeto.padroes) {
bytesEstaticos += p.transicoes.size() * sizeof(std::uint32_t);
bytesEstaticos += p.finais.size() * sizeof(std::uint8_t);
}
for (const std::string& c : objeto.constantes) {
bytesEstaticos += c.size();
}
areas.push_back(DescricaoDeArea{
AreaDeMemoria::Codigo,
"o codigo das regras; imutavel e nunca realocado", true,
bytesDeCodigo});
areas.push_back(DescricaoDeArea{
AreaDeMemoria::Estatica,
"tabelas de transicao dos padroes e area de constantes", true,
bytesEstaticos});
areas.push_back(DescricaoDeArea{
AreaDeMemoria::Pilha,
"pilha de avaliacao da regra corrente; profundidade limitada pela "
"expressao mais aninhada, conhecida na compilacao",
false, 0});
areas.push_back(DescricaoDeArea{
AreaDeMemoria::Monte,
"o texto casado, cujo comprimento so se conhece ao casar", false, 0});
return areas;
}
std::string descreverAtivacao(const AtivacaoDeRegra& a) {
std::ostringstream out;
out << " registro de ativacao da regra " << a.regra << ":\n"
<< " posicao na entrada ... " << a.posicaoNaEntrada << '\n'
<< " texto casado ......... \"" << a.textoCasado << "\" ("
<< a.textoCasado.size() << " bytes)\n"
<< " topo da pilha ........ " << a.topoDaPilha << '\n'
<< " endereco de retorno .. " << a.enderecoDeRetorno << '\n';
return out.str();
}
std::size_t profundidadeMaximaDeAtivacao() noexcept { return 1; }
// ---------------------------------------------------------------------------
// Exemplo mínimo isolado
// ---------------------------------------------------------------------------
const std::vector<ProcedimentoExemplo>& procedimentosDoExemplo() {
// principal contem externo, que contem interno. Tres niveis, que e o
// minimo para a cadeia de acesso divergir da de controle.
static const std::vector<ProcedimentoExemplo> procs = {
ProcedimentoExemplo{"principal", 0, 0},
ProcedimentoExemplo{"externo", 1, 0},
ProcedimentoExemplo{"interno", 2, 1},
};
return procs;
}
std::vector<Quadro> simularChamadas(const std::vector<std::size_t>& chamadas) {
const std::vector<ProcedimentoExemplo>& procs = procedimentosDoExemplo();
std::vector<Quadro> pilha;
for (const std::size_t proc : chamadas) {
if (proc >= procs.size()) {
continue;
}
Quadro q;
q.procedimento = proc;
if (!pilha.empty()) {
q.temElo = true;
// Cadeia de CONTROLE: sempre o quadro imediatamente abaixo, isto é,
// quem chamou. Não depende de onde o procedimento foi escrito.
q.eloDeControle = pilha.size() - 1;
// Cadeia de ACESSO: o quadro mais recente cujo procedimento é o que
// CONTÉM este no texto. Procura de cima para baixo — o mais
// recente é o correto, e é isso que faz a recursão funcionar.
const std::size_t envolvente = procs[proc].contidoEm;
q.eloDeAcesso = pilha.size() - 1;
for (std::size_t i = pilha.size(); i > 0; --i) {
if (pilha[i - 1].procedimento == envolvente) {
q.eloDeAcesso = i - 1;
break;
}
}
}
pilha.push_back(q);
}
return pilha;
}
std::string desenharPilha(const std::vector<Quadro>& pilha) {
const std::vector<ProcedimentoExemplo>& procs = procedimentosDoExemplo();
std::ostringstream out;
out << " quadro | procedimento | nivel | controle | acesso\n";
out << " -------+--------------+-------+----------+-------\n";
for (std::size_t i = 0; i < pilha.size(); ++i) {
const Quadro& q = pilha[i];
const ProcedimentoExemplo& p = procs[q.procedimento];
out << " " << i << " | " << p.nome;
for (std::size_t k = p.nome.size(); k < 12; ++k) {
out << ' ';
}
out << " | " << p.nivelLexico << " | ";
if (q.temElo) {
out << q.eloDeControle << " | " << q.eloDeAcesso;
} else {
out << "- | -";
}
out << '\n';
}
return out.str();
}
std::size_t resolverAcesso(const std::vector<Quadro>& pilha,
std::size_t nivelLexicoAlvo) {
if (pilha.empty()) {
return 0;
}
const std::vector<ProcedimentoExemplo>& procs = procedimentosDoExemplo();
std::size_t atual = pilha.size() - 1;
// Sobe pela cadeia de ACESSO até chegar ao nível léxico procurado. O número
// de saltos é a diferença de níveis, conhecida na compilação — é por isso
// que este percurso não custa busca em tempo de execução num compilador de
// verdade.
while (procs[pilha[atual].procedimento].nivelLexico > nivelLexicoAlvo) {
if (!pilha[atual].temElo) {
return pilha.size();
}
const std::size_t proximo = pilha[atual].eloDeAcesso;
if (proximo == atual) {
return pilha.size();
}
atual = proximo;
}
if (procs[pilha[atual].procedimento].nivelLexico == nivelLexicoAlvo) {
return atual;
}
return pilha.size();
}
} // namespace peneira
O exemplo tem três procedimentos aninhados — principal contém externo, que contém interno — porque três níveis são o mínimo para as duas cadeias divergirem, e a divergência é o assunto inteiro. Simulando a sequência em que principal chama externo, que chama interno, que chama externo de novo:
quadro | procedimento | nivel | controle | acesso
-------+--------------+-------+----------+-------
0 | principal | 0 | - | -
1 | externo | 1 | 0 | 0
2 | interno | 2 | 1 | 1
3 | externo | 1 | 2 | 0O quadro 3 é onde tudo se decide. A cadeia de controle aponta para o quadro 2, porque foi interno quem chamou — ela segue a ordem de execução. A cadeia de acesso aponta para o quadro 0, porque é principal que contém externo no texto do programa. As duas divergem, e é essa divergência que obriga a manter as duas.
A resolução de acesso a partir do topo confirma o Teorema 5.1:
variavel de nivel lexico 0 -> quadro 0 (principal)
variavel de nivel lexico 1 -> quadro 3 (externo)
variavel de nivel lexico 2 -> nao visivel daquiO nível 2 não é visível do quadro 3, e está certo: interno está fisicamente na pilha, mas não envolve externo no texto, então as suas variáveis não são acessíveis dali. Confundir “está na pilha” com “é visível” é o erro que a cadeia de acesso existe para impedir.
Sobre gerência de memória, o objeto da Peneira aloca explicitamente e libera por escopo: o texto casado vive enquanto a regra executa e some ao terminar, que é o padrão de região, o mais simples que existe. A coleta automática não foi implementada e não caberia — coletar exige rastrear referências que sobrevivem à ativação, e nesta linguagem nada sobrevive. É a frase de engenharia que a seção 5.7 pedia, com o motivo escrito ao lado.
1.8 Síntese
A camada intermediária existe por duas razões: a combinatória só é decisiva a partir de três origens e três destinos, e o que a sustenta em compiladores de origem única é a separação de dificuldades. Entre as formas, a árvore deixa a ordem implícita, a pós-fixada não exprime desvio, e o código de três endereços é o que se usa — e a comparação que decide precisa ser feita sobre a construção mais difícil da linguagem. A tradução é um esquema dirigido pela sintaxe em que cada nó de expressão devolve o nome do temporário que contém o seu valor, enquanto as condições devolvem duas listas de desvios pendentes; o preenchimento retroativo fecha o mecanismo com três operações — criar, fundir, preencher — e uma verificação: ao final, zero desvios pendentes. Do lado do produto, a especificação vem antes do código, e o que o critério de completude revela são comportamentos não decididos. Do lado da execução, o corte útil da memória separa o que o compilador prova do que só a execução descobre; cada ativação tem o seu registro, e duas cadeias atravessam a pilha respondendo a perguntas diferentes.
Volto ao desvio da abertura, aquele que apontava para um endereço inexistente. Agora ele tem nome, tem lista, tem três operações e tem uma verificação que pega o defeito no dia em que ele nasce. O próximo módulo pega a representação que construímos aqui e o formato que especificamos aqui e escreve a peça que liga um ao outro — o gerador de código. E prepare-se para um reencontro: os autômatos do começo do curso reaparecem, como tabelas de transição, dentro do arquivo que o compilador gera.
Um conselho final: o produto principal deste módulo é um documento, e documentos não dão erro de compilação. Dá para escrever uma especificação bonita e incompleta que passa despercebida por semanas, até alguém tentar usá-la. Aplique o critério de completude literalmente, e antes de escrever o código que o documento descreve.