flowchart TD
A["Cadeia de tokens"] --> B{"Existe derivação a partir<br/>do símbolo inicial da gramática?"}
B -- não --> C["Defeito de forma<br/>erro sintático"]
B -- sim --> D["Árvore sintática"]
D --> E{"As condições dependentes de<br/>contexto estão satisfeitas?"}
E -- não --> F["Defeito de sentido<br/>erro semântico"]
E -- sim --> G["Árvore anotada com tipos<br/>e tabela de símbolos preenchida"]
G --> H["Perguntas sobre o comportamento<br/>do programa: indecidíveis"]
1 Módulo 12: Análise Semântica
Bem-vindo ao módulo em que o compilador aprende a discordar. Até aqui ele sabia dizer se um programa está bem escrito; a partir daqui, se o programa faz sentido. No fim desta leitura você deve conseguir olhar para uma verificação qualquer e decidir, antes de escrever uma linha, se ela cabe na gramática, se cabe nesta fase, ou se não cabe em lugar nenhum.
1.1 O problema: zero erros, e o programa é um absurdo
Imagina a cena, porque ela se repete todo semestre. Você termina o analisador sintático, joga nele um programa de teste e ele responde: zero erros. A árvore sai bonita, cada nó no lugar certo. E o programa, lido por um humano com dois minutos de atenção, é um disparate — usa um nome que ninguém declarou, aplica uma operação numérica a algo que nunca vai ser número, compara duas coisas que não são comparáveis.
A primeira reação de quase todo mundo é achar que o analisador sintático está com defeito. Não está: ele fez o que lhe cabia. O que aconteceu é que o programa atravessou a fronteira mais nítida do curso — entre forma e sentido — e do outro lado dela existe uma fase inteira do compilador que ainda não foi escrita.
Repara que a gente já esbarrou nisso. No primeiro módulo eu falei de três programas defeituosos, e o segundo, aquele impecavelmente pontuado que somava um texto a um número, ficou pendente; eu disse que a reclamação demoraria mais e apontaria para a operação inteira em vez de para um caractere. Chegou a hora de explicar por quê.
Antes de seguir, deixo explícito o que este capítulo pressupõe, porque é a informação que permite a você decidir se convém revisar algo antes de continuar.
Pressuponho a árvore sintática abstrata construída no capítulo de análise descendente: a estrutura de nós com posição de origem que o analisador sintático entrega, e a travessia recursiva dela. Pressuponho a coleção de diagnósticos apresentada no primeiro capítulo, com a política de registrar e prosseguir em vez de interromper. E pressuponho, de forma decisiva para a última parte da seção 5, as operações booleanas sobre autômatos finitos — complemento, interseção, diferença e teste de vacuidade — construídas no capítulo sobre os limites e as propriedades de fechamento das linguagens regulares, além do resultado de que o autômato mínimo de uma linguagem regular é único.
O que não pressuponho é qualquer contato anterior com gramáticas de atributos, com sistemas de tipos apresentados por regras de inferência ou com tabelas de símbolos. Os três assuntos são construídos aqui, do início, e no ponto em que passam a ser necessários.
1.2 O que a gramática não captura
Uma cadeia de tokens é sintaticamente correta quando existe derivação dela a partir do símbolo inicial da gramática, e essa pergunta a fase anterior decide por completo. Já a correção semântica estática exige condições de boa formação dependentes de contexto, cuja verificação obriga a relacionar pontos do programa que a árvore não conecta.
São três famílias. A de declaração: todo nome usado precisa ter sido declarado, nenhum pode ser declarado duas vezes no mesmo escopo, e a declaração precisa estar visível do ponto de uso. A de tipos: cada operação exige operandos de certos tipos. E a de fluxo estático: não se lê um valor antes de atribuí-lo. Olha o traço comum, porque ele decide a arquitetura da fase: todas relacionam dois pontos distantes, e nenhuma dessas relações é local. É por isso que a árvore, que exprime bem aninhamento, não as exprime.
Agora o argumento formal, porque a versão intuitiva — “a gramática não lembra os nomes” — é vaga demais. Sobre o alfabeto \{a,b,c\}, considere L_{du} = \{\, wcw \mid w \in \{a,b\}^+ \,\}: à esquerda do c está o nome na declaração, à direita o mesmo nome no uso, e o c é tudo o que existe entre um e outro. Essa linguagem não é livre de contexto, pelo lema do bombeamento: em z = a^p b^p c\, a^p b^p, o trecho bombeável tem comprimento no máximo p e não alcança ao mesmo tempo uma posição da metade esquerda e a correspondente da direita, de modo que bombear faz as metades deixarem de coincidir.
Pare e pense. Se a segunda metade fosse o reverso da primeira, a linguagem seria livre de contexto e a gramática sairia em duas produções. Por que o reverso cabe na pilha e a cópia não? Porque a pilha reconhece correspondências aninhadas, e declaração e uso é correspondência paralela: o primeiro nome declarado não é o último a ser usado.
A consequência, sem meias palavras: não existe gramática livre de contexto que descreva os programas corretos de uma linguagem realista com declarações. A que você escreveu no módulo anterior aceita todos os corretos e mais uma infinidade de incorretos; esta fase recorta o subconjunto que interessa.
E o andar de cima da hierarquia, o das gramáticas sensíveis ao contexto? Em teoria resolve, na prática ninguém mora nele, por três razões somadas. Legibilidade: simular “propague a lista de nomes declarados até aqui” custa dezenas de produções de contabilidade, e a gramática deixa de documentar a linguagem. Custo: o problema de pertinência é decidível, mas o algoritmo geral é exponencial. E a decisiva: a gramática não produziria o que o compilador precisa — ela responderia sim ou não, quando o que se quer é a árvore anotada com tipos, a tabela preenchida e diagnósticos que nomeiem o identificador ofensor.
Falta o teto. Esta fase decide propriedades do texto, não do comportamento. Entre as duas fica a faixa das aproximações conservadoras, que respondem “certamente não” ou “talvez sim”, errando sempre para o mesmo lado: a verificação de atribuição antes do uso considera todos os caminhos, inclusive os que jamais serão tomados, e ocasionalmente recusa um programa correto para jamais aceitar um que leia lixo.
1.3 A tabela de símbolos
A estrutura que sustenta a fase associa a cada nome declarado os atributos conhecidos sobre a entidade que ele denota, de modo que a consulta, feita a partir de um ponto do programa, devolva a declaração visível naquele ponto. Essa última cláusula é o que a torna interessante: sem escopos, uma tabela de símbolos é um dicionário.
flowchart LR
N["nome"] --> C1["chave de toda consulta"]
E["espécie"] --> C2["recusa do nome usado<br/>na categoria errada"]
T["tipo"] --> C3["verificação de tipos"]
P["posição da declaração"] --> C4["mensagem de redeclaração<br/>que aponta a primeira"]
U["marcador de uso"] --> C5["aviso de declaração<br/>que ninguém referencia"]
A["índice do autômato compilado"] --> C6["geração de código"]
Eu prefiro apresentá-la pelo consumidor de cada campo, e a regra que aplico economiza muito retrabalho: nenhum campo entra por completude; cada campo entra porque alguma verificação precisa dele. O nome é a chave. A espécie distingue categorias que compartilham o espaço de nomes — sem ela, um programa que usa um nome de tipo como se fosse valor passa batido, porque a consulta encontra a entrada e o verificador não percebe que encontrou a coisa errada. A posição da declaração existe por motivo de diagnóstico: dizer “já declarado” sem dizer onde estava a primeira obriga quem lê a sair procurando. E o marcador de uso só pode ser consultado depois que a árvore inteira foi percorrida.
Vem daí uma lição que vale muito além de compiladores: a estrutura de dados sai do padrão de operações previsto, não da estrutura conceitual do problema. Conceitualmente a tabela é uma árvore, porque escopos aninham, e quem deixa o conceito escolher obtém algo elegante e lento. O padrão real é outro: a consulta por nome domina, uma vez por ocorrência de identificador, contra um punhado de inserções.
| Estrutura | Consulta | Inserção | Preserva ordem | Quando usar |
|---|---|---|---|---|
| Tabela de dispersão | O(1) médio | O(1) médio | não | caso geral |
| Árvore balanceada | O(\log n) | O(\log n) | sim | quando a listagem ordenada importa |
| Lista linear | O(n) | O(1) | por inserção | escopos comprovadamente pequenos |
A interface mínima tem quatro operações: a inserção, que registra uma declaração no escopo corrente e reporta se o nome já existia ali; a consulta visível, que procura do escopo mais interno para o mais externo; a consulta local, restrita ao escopo corrente; e o par de entrada e saída de escopo. As duas consultas parecem redundantes e não são: a visível responde “o que este nome significa aqui?”; a local responde “este nome já foi declarado neste escopo?”. Quem implementa só a visível e a usa para as duas coisas obtém um compilador que recusa programas válidos.
1.4 Escopos, visibilidade e as duas estratégias
O escopo de uma declaração é a região do texto em que ela é a que dá significado ao nome. Declarado o nome em mais de um bloco que contém o ponto de uso, vale a declaração do bloco mais interno, e diz-se que a interna sombreia as externas. Isso é o escopo estático, ou léxico, disciplina que ALGOL 60 consagrou: a região é determinada pela posição no texto e portanto conhecida em tempo de compilação. A alternativa histórica, o escopo dinâmico das primeiras implementações de Lisp, praticamente desapareceu porque empurra a resolução de nomes para o tempo de execução.
E repito o alerta anterior, fonte constante de defeito: redeclaração e sombreamento são situações distintas. Declarar duas vezes o mesmo nome no mesmo escopo é erro em quase toda linguagem; declarar num escopo interno um nome que existe no externo é legítimo, e às vezes só é péssimo estilo — daí muitos compiladores emitirem aviso, não erro.
flowchart TB
subgraph EMP["Uma tabela por escopo, empilhadas"]
direction TB
T2["escopo interno (topo)"] --> T1["escopo intermediário"]
T1 --> T0["escopo global (base)"]
Q1["consulta visível: desce do topo<br/>para a base e para no primeiro acerto"]
end
subgraph ENC["Tabela única com encadeamento por nome"]
direction TB
H["tabela de dispersão do nome"] --> S["pilha de declarações ativas<br/>daquele nome, da mais externa<br/>no fundo para a mais interna no topo"]
S --> Q2["consulta visível: leia o topo"]
D["trilha de desfazimento por nível"] --> S
end
Entrar empilha uma tabela vazia; sair desempilha e descarta. A consulta visível caminha do topo para a base e para no primeiro acerto — e repara que, assim, a regra do bloco mais interno não precisa de código algum: ela é a ordem do percurso. Em troca, a consulta custa tempo proporcional à profundidade no pior caso: um nome global consultado do fundo de dez blocos exige dez sondagens falhadas antes do acerto.
Mantém-se uma tabela de dispersão, do nome para a pilha de declarações ativas daquele nome, da mais externa no fundo para a mais interna no topo. A consulta visível vira uma sondagem seguida da leitura do topo: custo constante, independente da profundidade. A inserção empilha registrando o nível, o que permite à consulta local decidir entre redeclaração e sombreamento. O custo mudou de lugar: sair de escopo exige desempilhar cada nome declarado ali, e saber quais são sem varrer a tabela inteira exige uma trilha de desfazimento por nível — o preço da estratégia e a sua principal fonte de defeito.
Sendo d a profundidade de aninhamento no ponto da consulta e m o número de declarações do escopo que se fecha: a empilhada consulta em O(d) no pior caso e sai em O(1); a encadeada consulta em O(1) médio e sai em O(m). As duas declaram e entram em escopo em tempo constante.
Afirmar um compromisso não é medi-lo. A comparação diz onde cada custo está, não qual estratégia serve à sua linguagem. Com dois níveis de escopo, a diferença é de uma sondagem por consulta — nada, diante do risco de uma trilha de desfazimento incorreta. Com blocos profundamente aninhados, a conclusão se inverte. Instrumente as duas com um contador de sondagens e meça.
E há o caso que quebra o modelo de pilha: classes cujos métodos referenciam campos declarados adiante exigem o escopo preenchido por inteiro antes de qualquer método ser verificado — questão de quantos percursos a fase faz, não de estratégia de tabela.
1.5 Tradução dirigida por sintaxe
Chegamos ao arcabouço conceitual da fase. Temos uma árvore e queremos associar informação aos seus nós: parte flui de baixo para cima, como o tipo de uma soma; parte flui de cima para baixo, como o escopo visível num bloco. E há informação cujo cálculo mistura as duas direções — é aí que fica interessante.
A formalização é de Donald Knuth, num trabalho de 1968 sobre a semântica de linguagens livres de contexto, e chama-se gramática de atributos. A contribuição não foi pendurar informação nos nós, que já se fazia; foi dar à especificação uma forma declarativa, em que se escrevem as equações e não a ordem, e mostrar que a ordem pode ser derivada delas. Cada símbolo recebe atributos sintetizados — cujo valor vem dos filhos, e a informação sobe — e herdados — cujo valor vem do pai e dos irmãos, e a informação desce. A disciplina que vale ler devagar é esta: uma produção só define os sintetizados do seu lado esquerdo e os herdados dos seus filhos, nunca o contrário. É o que faz cada ocorrência de atributo na árvore ser definida por exatamente uma regra.
Dois exemplos ficam conosco. O tipo de uma expressão é sintetizado: nasce nas folhas e sobe, e sozinho pediria pós-ordem. O escopo visível num ponto é herdado: nasce onde o bloco foi aberto e desce até cada folha, e sozinho pediria pré-ordem.
flowchart TD
ACAO["nó da ação"] -- "escopo, herdado" --> COMP["nó da comparação"]
COMP -- "escopo, herdado" --> VAL["nó de extração de valor"]
COMP -- "escopo, herdado" --> LIT["literal numérico"]
VAL -- "tipo, sintetizado" --> COMP
LIT -- "tipo, sintetizado" --> COMP
COMP -- "tipo, sintetizado" --> ACAO
Agora o ponto que faz a teoria valer a pena. Num nó que consulta um identificador, o tipo é sintetizado, porque sobe para o operador acima; só que calculá-lo depende do atributo herdado de escopo do mesmo nó, porque descobrir o tipo do identificador exige saber a que declaração ele se refere.
A consequência mais importante desta seção. Quando há atributos das duas direções, a ordem de avaliação não é pós-ordem nem pré-ordem: os herdados exigem o pai antes dos filhos, os sintetizados exigem os filhos antes do pai, e nenhum percurso de direção fixa satisfaz as duas exigências. A ordem correta é uma ordem topológica do grafo de dependências entre ocorrências de atributo.
Formalizando: uma ocorrência de atributo é um par formado por um nó e um atributo do símbolo que o rotula, e o grafo de dependências tem essas ocorrências como vértices, com uma aresta de uma para outra quando a regra que define a segunda usa a primeira. Existe atribuição consistente de valores se e somente se esse grafo é acíclico, e então qualquer ordem topológica serve. Eu uso o algoritmo de Kahn, e não pela eficiência: os vértices que sobram sem ser emitidos são os que participam de ciclos.
Um ciclo, aliás, não é erro do programa que está sendo compilado: é erro da especificação da tradução, e o programa de entrada só teve o azar de produzir a árvore em que a inconsistência se materializa. Knuth mostrou que decidir a não circularidade é possível sem examinar árvore alguma, mas um resultado de Jazayeri, Ogden e Rounds, de 1975, estabelece que o problema é intrinsecamente exponencial. Daí as ferramentas restringirem a classe a duas subclasses em que a não circularidade sai de graça pela forma das regras.
Uma gramática é S-atribuída quando todos os atributos são sintetizados: toda aresta vai de filho para pai, a pós-ordem é ordem topológica, e a avaliação cabe numa análise ascendente, no momento de cada redução. É L-atribuída quando cada herdado de um filho depende apenas de herdados do pai e de atributos dos irmãos à esquerda — daí a letra —, e então a avaliação cabe num único percurso em profundidade da esquerda para a direita, e portanto durante uma análise descendente, sem que a árvore precise ser construída. Toda S-atribuída é L-atribuída, e a inclusão é própria. Isso não é taxonomia: saber que a sua especificação é L-atribuída é saber que você tem a opção de traduzir durante a análise — opção que a maioria dos compiladores modernos não exerce, porque as fases seguintes precisam da árvore de qualquer jeito.
Falta a forma prática em que isso aparece no código. Um esquema de tradução é uma gramática livre de contexto com ações semânticas intercaladas aos símbolos do lado direito, na posição em que devem executar: é a gramática de atributos com o quando já escolhido. A regra de posicionamento cai dos resultados anteriores — ação que calcula herdado de um símbolo vai antes dele, ação que calcula sintetizado do lado esquerdo vai no fim. Se a gramática for L-atribuída, o esquema funciona durante a análise; se não for, alguma ação precisará de um valor que ainda não existe, e não há posicionamento que salve.
1.6 Verificação de tipos
Esta é a aplicação mais visível do arcabouço anterior, e onde a maior parte do código de uma fase semântica real acaba morando. Um sistema de tipos atribui a cada expressão bem formada um tipo, ou a declara maltipada, por meio de julgamentos \Gamma \vdash e : \tau, lidos como “no ambiente \Gamma, a expressão e tem tipo \tau”. Repara em quem é \Gamma: é a tabela de símbolos, na sua forma matemática. Toda decisão de tipo é relativa às declarações visíveis — e é por isso que o atributo de escopo tinha de ser herdado.
As regras vão com as premissas acima da barra e a conclusão abaixo. A consulta de um nome devolve o que a tabela registra:
\frac{\Gamma(x) = \tau}{\Gamma \vdash x : \tau}
uma operação aritmética binária, sem conversões implícitas, exige os dois lados numéricos:
\frac{\Gamma \vdash e_1 : \text{num} \qquad \Gamma \vdash e_2 : \text{num}}{\Gamma \vdash e_1 + e_2 : \text{num}}
e uma comparação produz booleano a partir de dois operandos de tipo idêntico:
\frac{\Gamma \vdash e_1 : \tau \qquad \Gamma \vdash e_2 : \tau}{\Gamma \vdash e_1 = e_2 : \text{bool}}
Escreva as regras assim antes de implementá-las: a notação força a explicitar o que cada operação exige e o que produz, e uma regra que você não consegue escrever é uma decisão de projeto que ainda não tomou. A implementação segue-as quase literalmente, numa função recursiva com um caso por forma de expressão.
Com construtores de tipo — registros, vetores, ponteiros, funções —, a pergunta “estes dois tipos são o mesmo?” deixa de ter resposta óbvia. Sob equivalência estrutural, dois tipos são iguais quando são o mesmo tipo básico ou o mesmo construtor aplicado a tipos equivalentes; sob equivalência por nome, quando vieram da mesma declaração, tenham a estrutura que tiverem. A consequência é grande: sob a segunda, você declara um tipo para metros e outro para segundos, ambos numéricos, e obtém do compilador a recusa de somá-los — sob a primeira, os dois são o mesmo tipo. As linguagens reais misturam as duas noções, e o relatório original de Pascal não deixou claro qual valia, o que produziu programas que compilavam num compilador e não em outro. Tome essa decisão explicitamente, sob pena de ela ser tomada por omissão pelo seu código.
Uma coerção é a conversão de tipo que o compilador insere sem que apareça no texto do programa. A favor dela: exigir conversão explícita em toda operação mista polui o programa com ruído, e ruído também reduz legibilidade. Contra: ela transforma um erro em silêncio, porque diante de tipos diferentes ou o autor sabia o que fazia, ou se enganou — e a coerção escolhe automaticamente a primeira leitura. O caso doloroso é a comparação entre valor com sinal e sem sinal em linguagens que promovem ambos a sem sinal: o negativo vira um positivo enorme e a comparação dá o resultado oposto ao pretendido, sem mensagem alguma. A política numa frase: coerção que perde informação deve ser explícita; coerção que preserva informação pode ser implícita.
O truque de melhor retorno da fase inteira. Reserve um tipo de erro distinguido, atribuído a toda expressão cujo tipo o verificador não determinou por causa de um defeito já reportado, com a propriedade de absorção: toda operação com um operando desse tipo produz esse tipo e não gera diagnóstico novo. Sem isso, uma expressão maltipada no fundo da árvore gera um diagnóstico ali e mais um em cada operador acima, e o defeito verdadeiro fica soterrado nas consequências. A absorção precisa valer em todas as regras — é comum implementá-la na aritmética, esquecê-la na atribuição e obter um relatório quase limpo com duas mensagens espúrias sobreviventes.
Encerro com o caso que dá identidade a esta fase, reutilizando a teoria dos primeiros módulos. Às vezes o tipo é uma propriedade derivável do que já foi escrito, e as duas saídas óbvias são ruins: exigir anotação transfere ao autor uma verificação que o compilador poderia fazer; adivinhar por heurística erra nos dois sentidos, silenciosamente. A terceira é decidir. Se os valores de um tipo formam a linguagem L_\tau e a entidade produz valores que formam L_e, a pergunta “esta entidade tem tipo \tau?” é a inclusão L_e \subseteq L_\tau, que equivale a L_e \setminus L_\tau = \emptyset — decidível para linguagens regulares, porque a classe é fechada sob complemento e interseção e o teste de vacuidade é uma busca de alcançabilidade.
flowchart LR
P["padrão declarado<br/>pelo programa"] --> AP["autômato do padrão"]
N["mesma especificação léxica<br/>usada pelo analisador léxico"] --> AN["autômato do número"]
AN --> CO["complemento sobre<br/>o alfabeto declarado"]
AP --> IN["interseção"]
CO --> IN
IN --> V{"a linguagem resultante<br/>é vazia?"}
V -- sim --> T1["a ligação tem tipo número<br/>extração de valor permitida"]
V -- não --> T2["a ligação tem tipo texto<br/>extração de valor recusada"]
Dois cuidados, porque ambos produzem erro silencioso. O alfabeto precisa ser declarado, porque o complemento só existe em relação a um alfabeto fixado. E o caso degenerado da linguagem vazia, subconjunto de qualquer linguagem, classificaria uma entidade que não produz valor algum como tendo qualquer tipo — correto e inútil. Mas o que quero que fique é o hábito: antes de acrescentar uma anotação à sua linguagem, pergunte se a informação que ela carrega já não está determinada pelo que o programa diz.
1.7 A organização da fase em percursos
Sobra a decisão operacional: quantas travessias da árvore, e o que cada uma faz. A resposta ingênua é uma só, e funciona num caso restrito — linguagens que exigem declaração antes do uso. Não é acidente que várias linguagens antigas imponham essa restrição: ela existe para permitir compiladores de uma passagem, e Pascal é o exemplo canônico. Quando a linguagem permite referenciar um nome declarado depois, um percurso não basta e nenhuma esperteza local resolve: a informação não existe no momento da consulta.
flowchart TD
A["árvore entregue pelo analisador sintático"] --> P1["Primeiro percurso<br/>coletar declarações, compilar<br/>autômatos e inferir tipos"]
P1 --> P2["Segundo percurso<br/>verificar usos, condições<br/>e emissões"]
P2 --> F["Varredura final da tabela completa<br/>avisos de declaração sem uso"]
F --> S["árvore anotada e tabela preenchida<br/>para as fases de síntese"]
P1 -.-> D["coleção de diagnósticos"]
P2 -.-> D
F -.-> D
A ordem entre os percursos raramente é escolha: é ditada pelo grafo de dependências entre as informações, como a ordem de avaliação dos atributos — o mesmo princípio em outra escala.
A pergunta que resolve a decomposição. Quando não souber quantos percursos fazer, não decida pela arquitetura. Liste as verificações e, para cada uma, pergunte: que informação preciso já ter coletado para poder fazer isto? Agrupe as que dependem do mesmo conjunto e ordene os grupos pela dependência. O número de grupos é o número de percursos, e sai da análise em vez de ser arbitrado.
Há ainda uma categoria que não é percurso: a verificação que depende de informação acumulada ao longo de todos eles. O aviso de declaração sem uso é o exemplo — a qualquer momento ainda pode aparecer um uso adiante, então ele sai depois, varrendo a tabela completa.
Cada fase tem uma classe de defeito característica, e a desta é o escopo desbalanceado. O percurso entra num escopo ao processar a construção que o abre e deve sair ao terminar; se houver um retorno antecipado no meio, a saída pode ser pulada e a construção seguinte é processada com o escopo anterior ainda aberto. O sintoma é perverso: o compilador passa a aceitar programas que referenciam nomes locais de uma construção dentro de outra, sem erro nenhum. A defesa é barata: entrada e saída na mesma função, sem caminho de retorno entre elas, e a invariante de que a profundidade da tabela seja a mesma antes e depois de cada construção que abre escopo.
Termino com o assunto que separa um compilador que se usa com prazer de um que se tolera. A partir desta fase o compilador conhece o identificador, a posição exata, a posição da declaração conflitante e os tipos dos dois lados; uma mensagem que se limita a “tipo incompatível” descarta tudo isso. O padrão que recomendo tem três componentes: identificação, porque mensagem sem nome obriga quem lê a contar colunas; posição, no formato de arquivo, linha e coluna que os editores sabem interpretar; e explicação da natureza do problema, não só que os tipos diferem, mas quais são e por que a operação exige que coincidam. E vale a política que atravessa todas as fases: não pare no primeiro erro — o tipo de erro absorvente é o que torna isso viável sem ruído.
1.8 O caso conduzido
Toda a teoria acima tem realização concreta no compilador que este curso constrói. As três peças a procurar são a tabela de símbolos com as duas estratégias lado a lado e instrumentadas, o verificador de tipos escrito como tradução direta das regras de inferência, e a construção explícita do grafo de atributos que expõe o mecanismo que a recursão esconde.
1.8.1 7.1 O programa que atravessa o front-end sem uma queixa
O compilador da Peneira ficou com o front-end completo no capítulo anterior, e desde então ele aceita qualquer programa bem formado. Este capítulo é onde ele passa a recusar programas bem formados que não fazem sentido.
O programa que motiva a fase inteira declara dois padrões, um para endereços eletrônicos e outro para números, e escreve quatro ações. A primeira reage a um padrão chamado telefone, que não foi declarado em lugar nenhum. A segunda aplica a operação de extração de valor numérico a uma variável ligada ao padrão de endereço eletrônico, que não casa números. A terceira compara diretamente um casamento com um literal numérico, sem a conversão explícita. A quarta declara uma variável de ligação e não a usa.
O analisador sintático não reclama de nada disso, e reportar isso como zero erros é a demonstração mais convincente que conheço da Definição 1.2. As quatro falhas são exatamente as três famílias de condição dependente de contexto que eu listei: declaração ausente, tipo incompatível em dois sabores distintos, e declaração inútil.
Vale localizar cada uma delas no Teorema 1.1. A primeira ação é literalmente a instância wcw do teorema: o nome telefone usado é a segunda cópia de um nome que deveria ter aparecido como primeira cópia numa declaração acima, e a gramática não tem como exigir que as duas cadeias coincidam. As demais são consequências dessa mesma impossibilidade num nível a mais: verificar tipos exige primeiro resolver o nome, que é a verificação que a gramática já não alcança.
1.8.2 7.2 A tabela de símbolos, com as duas estratégias implementadas
Começo pela estrutura, e aplico a regra da seção 2.1 — nenhum campo entra por completude.
12_simbolos.h
#ifndef PENEIRA_12_SIMBOLOS_H
#define PENEIRA_12_SIMBOLOS_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <unordered_map>
#include <vector>
#include "01_source.h"
#include "12_tipos.h"
namespace peneira {
// O que a tabela guarda. A escolha dos campos não é neutra: cada um existe
// porque alguma verificação precisa dele.
//
// nome — a chave da consulta
// especie — distingue o que foi declarado por `pattern` do que foi ligado
// por `on p(x)`; sem isso, `on numero(numero)` passaria batido
// tipo — o que a verificação de tipos consome
// posicao — para a mensagem "declarado aqui" da redeclaração
// usado — para o aviso de declaração sem uso, que só pode ser emitido
// depois que a árvore inteira foi percorrida
enum class Especie : std::uint8_t { Padrao, Ligacao };
const char* nomeDaEspecie(Especie e) noexcept;
struct SimboloSemantico {
std::string nome;
Especie especie = Especie::Padrao;
Tipo tipo = Tipo::Texto;
Position posicao{0, 0, 0};
bool usado = false;
// Só para Especie::Padrao: o índice do autômato compilado na lista de
// padrões. O módulo 14 vai emitir esse vetor; guardar o índice aqui é o
// que liga o nome ao autômato sem que a tabela conheça a classe Afd.
std::size_t indicePadrao = 0;
};
// ---------------------------------------------------------------------------
// Estratégia A: uma tabela por escopo, empilhadas.
// ---------------------------------------------------------------------------
//
// Entrar num escopo empilha uma tabela vazia; sair desempilha e destrói. A
// consulta caminha a pilha do topo para a base e para no primeiro acerto — é
// a regra de visibilidade escrita como percurso.
//
// Compromisso: entrada e saída de escopo custam O(1) e não tocam nos símbolos
// existentes, mas a consulta custa O(profundidade) no pior caso, porque um
// nome global visto do fundo de dez escopos aninhados exige dez consultas
// falhadas antes do acerto.
class TabelaEmpilhada {
public:
TabelaEmpilhada();
void entrarEscopo();
void sairEscopo();
std::size_t profundidade() const noexcept;
// Insere no escopo atual. Devolve false se o nome já existe **neste**
// escopo — sombrear um nome de escopo externo é legítimo e não é erro.
bool declarar(const SimboloSemantico& s);
// Consulta obedecendo à visibilidade: do escopo atual para fora.
const SimboloSemantico* consultar(const std::string& nome) const;
SimboloSemantico* consultarMutavel(const std::string& nome);
// Consulta restrita ao escopo atual, que é o que a checagem de
// redeclaração precisa.
const SimboloSemantico* consultarLocal(const std::string& nome) const;
// Instrumentação: quantas tabelas foram examinadas nas consultas. É o
// número que torna o compromisso mensurável em vez de afirmado.
std::size_t sondagens() const noexcept;
void zerarSondagens() noexcept;
std::vector<const SimboloSemantico*> todosDoEscopoAtual() const;
private:
std::vector<std::unordered_map<std::string, SimboloSemantico>> escopos_;
mutable std::size_t sondagens_ = 0;
};
// ---------------------------------------------------------------------------
// Estratégia B: tabela única, com pilha de declarações por nome.
// ---------------------------------------------------------------------------
//
// Um só mapa, do nome para a pilha de declarações ativas daquele nome. A
// declaração mais recente fica no topo, e é ela que a consulta devolve — a
// visibilidade vira o topo da pilha em vez de um percurso.
//
// Compromisso invertido em relação à estratégia A: a consulta é O(1) sempre,
// independente da profundidade, mas sair de um escopo custa O(declarações
// daquele escopo), porque cada nome declarado nele precisa ser desempilhado.
// Por isso a classe mantém a trilha de desfazimento — sem ela, sair de escopo
// exigiria varrer o mapa inteiro.
class TabelaEncadeada {
public:
TabelaEncadeada();
void entrarEscopo();
void sairEscopo();
std::size_t profundidade() const noexcept;
bool declarar(const SimboloSemantico& s);
const SimboloSemantico* consultar(const std::string& nome) const;
SimboloSemantico* consultarMutavel(const std::string& nome);
const SimboloSemantico* consultarLocal(const std::string& nome) const;
std::size_t sondagens() const noexcept;
void zerarSondagens() noexcept;
private:
struct Entrada {
SimboloSemantico simbolo;
std::size_t nivel = 0;
};
std::unordered_map<std::string, std::vector<Entrada>> pilhasPorNome_;
// Trilha de desfazimento: os nomes declarados em cada nível, na ordem.
std::vector<std::vector<std::string>> trilha_;
std::size_t nivel_ = 0;
mutable std::size_t sondagens_ = 0;
};
// A Peneira usa a estratégia A. A razão é a profundidade: a linguagem tem
// exatamente dois níveis de escopo — o global, com os `pattern`, e o da ação,
// com a variável de ligação —, e com profundidade dois a vantagem de consulta
// da estratégia B não se paga. A estratégia B está implementada assim mesmo,
// e é exercitada pela demonstração comparativa: a decisão só é defensável se
// medida, e as duas precisam existir para haver medida.
using TabelaDeSimbolos = TabelaEmpilhada;
} // namespace peneira
#endif // PENEIRA_12_SIMBOLOS_H
O nome é a chave. A espécie distingue o que foi declarado como padrão do que foi ligado por uma ação, e sem ela um programa que usasse um nome de padrão onde se espera uma variável de ligação passaria batido. O tipo é o que a verificação da seção 5 consome. A posição existe para a mensagem de redeclaração poder dizer onde estava a primeira. O marcador de uso só pode ser lido depois que a árvore inteira foi percorrida, exatamente como a seção 6.1 antecipou. E o índice do autômato compilado é o campo que liga o nome à sua realização em autômato sem que a tabela precise conhecer a classe de autômato — dependência que o gerador de código, dois capítulos adiante, vai consumir.
A linguagem tem dois níveis de escopo: os padrões são globais, e cada ação abre um escopo com a sua variável de ligação, visível apenas ali. São dois níveis, e é a existência do segundo que justifica a tabela ter escopos em vez de ser um mapa único.
Implementei as duas estratégias da seção 3, e faço questão de explicar por quê. O compromisso entre elas é o conteúdo do tópico, e afirmar um compromisso sem medi-lo é exatamente o que a advertência da seção 3.4 desaconselha. Com as duas implementadas e instrumentadas com um contador de sondagens, a comparação deixa de ser retórica.
12_simbolos.cpp
#include "12_simbolos.h"
namespace peneira {
const char* nomeDaEspecie(Especie e) noexcept {
switch (e) {
case Especie::Padrao: return "padrao";
case Especie::Ligacao: return "ligacao";
}
return "<desconhecida>";
}
// ---------------------------------------------------------------------------
// TabelaEmpilhada
// ---------------------------------------------------------------------------
TabelaEmpilhada::TabelaEmpilhada() {
// O escopo global já nasce aberto. Sem isso, todo usuário da classe teria
// de lembrar de abrir um, e esquecer produziria acesso a pilha vazia.
escopos_.emplace_back();
}
void TabelaEmpilhada::entrarEscopo() { escopos_.emplace_back(); }
void TabelaEmpilhada::sairEscopo() {
// O escopo global nunca sai. Proteger aqui é mais barato que descobrir o
// desbalanceamento como acesso inválido três fases adiante.
if (escopos_.size() > 1) {
escopos_.pop_back();
}
}
std::size_t TabelaEmpilhada::profundidade() const noexcept {
return escopos_.size();
}
bool TabelaEmpilhada::declarar(const SimboloSemantico& s) {
auto& atual = escopos_.back();
if (atual.find(s.nome) != atual.end()) {
return false;
}
atual.emplace(s.nome, s);
return true;
}
const SimboloSemantico* TabelaEmpilhada::consultar(const std::string& nome) const {
// Do topo para a base: a primeira ocorrência encontrada é a visível, e é
// exatamente isso que faz o sombreamento funcionar sem código extra.
for (std::size_t i = escopos_.size(); i > 0; --i) {
++sondagens_;
const auto& escopo = escopos_[i - 1];
const auto it = escopo.find(nome);
if (it != escopo.end()) {
return &it->second;
}
}
return nullptr;
}
SimboloSemantico* TabelaEmpilhada::consultarMutavel(const std::string& nome) {
for (std::size_t i = escopos_.size(); i > 0; --i) {
++sondagens_;
auto& escopo = escopos_[i - 1];
const auto it = escopo.find(nome);
if (it != escopo.end()) {
return &it->second;
}
}
return nullptr;
}
const SimboloSemantico* TabelaEmpilhada::consultarLocal(const std::string& nome) const {
const auto& atual = escopos_.back();
const auto it = atual.find(nome);
return it == atual.end() ? nullptr : &it->second;
}
std::size_t TabelaEmpilhada::sondagens() const noexcept { return sondagens_; }
void TabelaEmpilhada::zerarSondagens() noexcept { sondagens_ = 0; }
std::vector<const SimboloSemantico*> TabelaEmpilhada::todosDoEscopoAtual() const {
std::vector<const SimboloSemantico*> saida;
for (const auto& par : escopos_.back()) {
saida.push_back(&par.second);
}
return saida;
}
// ---------------------------------------------------------------------------
// TabelaEncadeada
// ---------------------------------------------------------------------------
TabelaEncadeada::TabelaEncadeada() { trilha_.emplace_back(); }
void TabelaEncadeada::entrarEscopo() {
++nivel_;
trilha_.emplace_back();
}
void TabelaEncadeada::sairEscopo() {
if (nivel_ == 0) {
return;
}
// Aqui está o custo desta estratégia, e ele é visível: cada nome declarado
// no nível que termina precisa ser desempilhado individualmente. Sem a
// trilha, a alternativa seria varrer o mapa inteiro procurando entradas
// deste nível — trocaria um custo proporcional às declarações do escopo
// por outro proporcional ao programa todo.
for (const std::string& nome : trilha_.back()) {
const auto it = pilhasPorNome_.find(nome);
if (it != pilhasPorNome_.end() && !it->second.empty()) {
it->second.pop_back();
if (it->second.empty()) {
pilhasPorNome_.erase(it);
}
}
}
trilha_.pop_back();
--nivel_;
}
std::size_t TabelaEncadeada::profundidade() const noexcept {
return nivel_ + 1;
}
bool TabelaEncadeada::declarar(const SimboloSemantico& s) {
// A consulta vem antes da inserção de propósito: `operator[]` criaria uma
// pilha vazia para o nome mesmo quando a declaração vai ser recusada, e
// essa entrada fantasma faria `consultar` devolver nulo por um caminho
// diferente do "nome inexistente" — mesma resposta, motivo diferente, e a
// diferença apareceria mais tarde como um erro difícil de localizar.
const auto existente = pilhasPorNome_.find(s.nome);
if (existente != pilhasPorNome_.end() && !existente->second.empty() &&
existente->second.back().nivel == nivel_) {
return false;
}
pilhasPorNome_[s.nome].push_back(Entrada{s, nivel_});
trilha_.back().push_back(s.nome);
return true;
}
const SimboloSemantico* TabelaEncadeada::consultar(const std::string& nome) const {
++sondagens_;
const auto it = pilhasPorNome_.find(nome);
if (it == pilhasPorNome_.end() || it->second.empty()) {
return nullptr;
}
return &it->second.back().simbolo;
}
SimboloSemantico* TabelaEncadeada::consultarMutavel(const std::string& nome) {
++sondagens_;
const auto it = pilhasPorNome_.find(nome);
if (it == pilhasPorNome_.end() || it->second.empty()) {
return nullptr;
}
return &it->second.back().simbolo;
}
const SimboloSemantico* TabelaEncadeada::consultarLocal(const std::string& nome) const {
const auto it = pilhasPorNome_.find(nome);
if (it == pilhasPorNome_.end() || it->second.empty()) {
return nullptr;
}
if (it->second.back().nivel != nivel_) {
return nullptr;
}
return &it->second.back().simbolo;
}
std::size_t TabelaEncadeada::sondagens() const noexcept { return sondagens_; }
void TabelaEncadeada::zerarSondagens() noexcept { sondagens_ = 0; }
} // namespace peneira
Medindo consultas ao nome mais externo em profundidades crescentes, o resultado reproduz a previsão da tabela de custos: a estratégia empilhada cresce linearmente com a profundidade, e a encadeada permanece constante. Para dez consultas, ela sobe de vinte sondagens em profundidade um para noventa em profundidade oito, enquanto a encadeada faz dez em qualquer profundidade.
E fica visível também que, para esta linguagem, a escolha é a empilhada. A Peneira vive na primeira linha dessa tabela: profundidade dois, no máximo. Ali a diferença é de uma sondagem por consulta, e a estratégia mais simples de destruir corretamente vence — sair de escopo é desempilhar, sem trilha de desfazimento para manter em dia. A conclusão se inverteria numa linguagem com blocos profundamente aninhados, que é precisamente o motivo pelo qual a medição importa mais que a preferência.
1.8.3 7.3 O sistema de tipos, e o tipo decidido por autômato
São três tipos e nenhum construtor de tipo: número, texto e o tipo de erro da Definição 5.5.
12_tipos.h
#ifndef PENEIRA_12_TIPOS_H
#define PENEIRA_12_TIPOS_H
#include <cstdint>
#include <string>
#include "03_afd.h"
namespace peneira {
// O sistema de tipos da Peneira.
//
// São três tipos e nenhuma construção composta — nem registro, nem função,
// nem vetor. Isso torna a **equivalência estrutural** e a **equivalência por
// nome** indistinguíveis aqui: sem construtores de tipo não há duas árvores
// de tipo diferentes com a mesma forma, então as duas noções colapsam.
// Registro isso porque a distinção é central em linguagens maiores e não tem
// como ser exercitada nesta: numa linguagem com registros, `struct {int x;}`
// e `struct {int y;}` são estruturalmente diferentes e `Ponto` e `Par`
// declarados iguais são estruturalmente iguais e nominalmente diferentes.
enum class Tipo : std::uint8_t {
Numero,
Texto,
// Tipo de erro. Existe para que uma expressão malformada não produza uma
// cascata de mensagens: quem recebe Erro como operando cala a boca, porque
// o erro de verdade já foi reportado embaixo. É a técnica que evita o
// relatório de trinta linhas para um defeito só.
Erro,
};
const char* nomeDoTipo(Tipo t) noexcept;
// Compatibilidade dos operandos de uma comparação.
//
// A regra é a mais restritiva possível: os dois lados têm de ter o **mesmo**
// tipo. Não há conversão implícita nenhuma nesta linguagem, e a decisão é
// deliberada — em `where value(n) > "100"` a intenção do autor é ambígua, e
// converter em silêncio escolheria uma das leituras sem avisar. A conversão
// existe, mas é explícita e tem nome: `value`.
//
// Devolve Erro quando os tipos não casam, e propaga Erro sem reclamar.
bool comparacaoValida(Tipo esquerda, Tipo direita) noexcept;
// Os operadores de ordem (`>`, `<`, `>=`, `<=`) só fazem sentido sobre número;
// os de igualdade (`==`, `!=`) valem para os dois tipos. Comparar textos por
// ordem seria definível (ordem lexicográfica), e não defini: a linguagem não
// tem caso de uso, e um operador que existe sem uso é superfície de erro.
bool operadorDeOrdem(const std::string& operador) noexcept;
// Inferência do tipo de um casamento de padrão.
//
// Aqui está a decisão de projeto que dá identidade a esta fase, e ela reusa o
// que o módulo 6 construiu. A pergunta "o que este `pattern` casa é sempre um
// número?" é a pergunta de **inclusão de linguagens**:
//
// L(padrao) subconjunto de L(NUMERO) <=> L(padrao) \ L(NUMERO) = vazio
//
// e a diferença de dois autômatos finitos, seguida do teste de vacuidade, é
// exatamente o par de operações do módulo 6. Nenhuma heurística sobre o texto
// da expressão regular, nenhuma anotação do programador: o tipo é **decidido**,
// e é decidido pela mesma maquinaria de autômatos que o resto do compilador já
// usa para outra coisa.
//
// O caso degenerado importa: um padrão cuja linguagem é vazia é subconjunto de
// qualquer coisa, inclusive dos números. Tratar isso como Numero seria
// tecnicamente correto e praticamente inútil, então a função devolve Texto e
// quem chama reporta o padrão vazio como problema à parte.
Tipo inferirTipoDoCasamento(const Afd& padrao);
// O autômato mínimo da categoria NUMERO, construído a partir da mesma
// especificação léxica do módulo 2 e memorizado na primeira chamada. É o lado
// direito da inclusão acima.
const Afd& afdDeNumero();
} // namespace peneira
#endif // PENEIRA_12_TIPOS_H
Registro no próprio cabeçalho o que esta linguagem não consegue exercitar, em vez de fingir que o assunto foi coberto: sem construtores de tipo, a equivalência estrutural e a equivalência por nome da seção 5.2 colapsam uma na outra, porque não há duas árvores de tipo distintas com a mesma forma nem duas declarações distintas com a mesma estrutura. A distinção é real e central em linguagens maiores; aqui ela não tem como aparecer.
A ausência de conversão implícita é deliberada, e segue a política da seção 5.3. Comparar diretamente um casamento com um número é ambíguo quanto à intenção do autor, e converter em silêncio escolheria uma das leituras sem avisar. A conversão existe nesta linguagem e tem nome: a operação de extração de valor. Tornar a conversão visível no programa é o que autoriza o compilador a recusar o resto.
Chego agora ao ponto que dá identidade a esta fase, e ele é a instância concreta do Teorema 5.1. A operação de extração de valor só faz sentido sobre uma ligação cujo padrão case sempre um número. Como o compilador sabe disso?
Considerei as duas saídas óbvias e descartei ambas, pelos motivos da seção 5.5. Pedir uma anotação ao autor do programa transfere a ele uma verificação que o compilador tem informação para fazer. Inspecionar o texto da expressão regular procurando dígitos é heurística, e heurística erra nos dois sentidos.
A saída correta estava pronta desde o capítulo sobre propriedades de fechamento. A pergunta
L(\text{padrão}) \subseteq L(\text{NÚMERO})
equivale a
L(\text{padrão}) \setminus L(\text{NÚMERO}) = \emptyset,
e a diferença de dois autômatos finitos, seguida do teste de vacuidade, são exatamente as duas operações já construídas. O tipo do casamento é decidido, não estimado:
12_tipos.cpp
#include "12_tipos.h"
#include <string>
#include <vector>
#include "02_lexico.h"
#include "04_notacao.h"
#include "04_thompson.h"
#include "05_determinizacao.h"
#include "05_minimizacao.h"
#include "06_fechamento.h"
namespace peneira {
const char* nomeDoTipo(Tipo t) noexcept {
switch (t) {
case Tipo::Numero: return "numero";
case Tipo::Texto: return "texto";
case Tipo::Erro: return "<erro>";
}
return "<desconhecido>";
}
bool comparacaoValida(Tipo esquerda, Tipo direita) noexcept {
// Erro é absorvente e silencioso: o defeito já foi reportado no operando.
if (esquerda == Tipo::Erro || direita == Tipo::Erro) {
return true;
}
return esquerda == direita;
}
bool operadorDeOrdem(const std::string& operador) noexcept {
return operador == ">" || operador == "<" || operador == ">=" ||
operador == "<=";
}
const Afd& afdDeNumero() {
// Construído uma vez, na primeira chamada, e reusado. O caminho é o mesmo
// pipeline dos módulos 4 e 5 — notação, Thompson, subconjuntos, Moore —
// aplicado à notação que já está na especificação léxica do módulo 2. Não
// há uma segunda definição de "o que é um número" neste compilador, e é
// essa unicidade que impede o verificador de tipos e o analisador léxico
// de divergirem.
static const Afd numero = [] {
std::string notacao;
for (const CategoriaLexica& c : especificacaoLexica()) {
if (c.nome == "NUMERO") {
notacao = c.notacao;
break;
}
}
const ResultadoNotacao r = analisarNotacao(notacao);
const Afn afn = thompson(*r.expressao, "NUMERO");
return minimizar(determinizar(afn, "NUMERO"), "NUMERO");
}();
return numero;
}
Tipo inferirTipoDoCasamento(const Afd& padrao) {
const Afd& numero = afdDeNumero();
// O alfabeto tem de ser explícito e comum aos dois autômatos. Esta é a
// armadilha que o módulo 6 documentou: a diferença é definida com o
// complemento embutido, e o complemento só está certo em relação a um
// alfabeto declarado. Inferir o alfabeto dos símbolos usados faria a
// resposta sair certa para os símbolos que aparecem e errada, em silêncio,
// para os demais.
const std::vector<Simbolo> alfabeto = alfabetoComum(padrao, numero);
// L(padrao) \ L(numero) vazio <=> todo casamento do padrão é um número.
const Afd sobra = diferencaAfd(padrao, numero, alfabeto, "sobra");
if (!linguagemVazia(sobra)) {
return Tipo::Texto;
}
// Padrão de linguagem vazia é subconjunto de tudo, e classificá-lo como
// número seria verdadeiro e inútil. Devolvemos Texto; o padrão vazio é
// reportado à parte, como o defeito que ele é.
if (linguagemVazia(padrao)) {
return Tipo::Texto;
}
return Tipo::Numero;
}
} // namespace peneira
Sobre o programa de exemplo, o padrão numérico tem diferença vazia e é classificado como numérico; o de endereço eletrônico não, e é texto. Nenhuma anotação de tipo foi escrita em lugar algum, e a partir daí a extração de valor é permitida sobre a ligação de um e recusada sobre a do outro.
Duas armadilhas ficaram documentadas no código, e são as duas que a seção 5.5 anunciou. A primeira é o alfabeto explícito, porque a diferença tem o complemento embutido e o complemento só está certo em relação a um alfabeto declarado. A segunda é o padrão de linguagem vazia, subconjunto de tudo, que seria classificado como numérico com correção técnica e inutilidade prática — ele é reportado à parte, como o defeito que é.
Registro também o que não fiz. O autômato de referência do número é construído a partir da mesma especificação léxica usada pelo analisador léxico, pelo mesmo caminho de construção, determinização e minimização. Não existe uma segunda definição de “o que é um número” neste compilador, e é essa unicidade que impede o verificador de tipos e o analisador léxico de divergirem.
1.8.4 7.4 Os dois percursos, e a dependência que fixa a ordem
12_sema.h
#ifndef PENEIRA_12_SEMA_H
#define PENEIRA_12_SEMA_H
#include <cstddef>
#include <string>
#include <vector>
#include "01_diagnostico.h"
#include "03_afd.h"
#include "10_ast.h"
#include "12_simbolos.h"
#include "12_tipos.h"
namespace peneira {
// Análise semântica da Peneira.
//
// Organizada em DOIS percursos sobre a árvore, e a quantidade não é escolha
// estética. O primeiro coleta as declarações de `pattern`; o segundo verifica
// as ações. Um percurso só não bastaria, e a razão é concreta: a linguagem
// permite que um bloco `rule` apareça antes do `pattern` que ele referencia,
// e um verificador de passagem única acusaria "padrao nao declarado" para um
// padrão declarado três linhas abaixo. Ou se aceita a ordem obrigatória de
// declaração, ou se faz dois percursos. Escolhemos dois.
//
// O primeiro percurso também é onde os autômatos dos padrões são construídos,
// porque o tipo da variável de ligação depende do autômato — e o segundo
// percurso precisa do tipo pronto. Essa dependência é o que fixa a ordem entre
// os dois: não é preferência, é o grafo de dependências mandando.
struct PadraoCompilado {
std::string nome;
std::string notacao;
Afd automato;
Tipo tipoDoCasamento = Tipo::Texto;
};
struct ResultadoSemantico {
// Os padrões na ordem de declaração. O módulo 14 emite este vetor.
std::vector<PadraoCompilado> padroes;
std::size_t errosSemanticos = 0;
std::size_t avisos = 0;
// Instrumentação dos percursos, para a demonstração.
std::size_t nosVisitadosPercurso1 = 0;
std::size_t nosVisitadosPercurso2 = 0;
std::size_t consultasNaTabela = 0;
};
class AnalisadorSemantico {
public:
AnalisadorSemantico(const SourceFile& fonte, DiagnosticBag& diagnosticos);
// Verifica a árvore inteira. Não para no primeiro erro: cada verificação
// reporta e segue, porque um relatório com os cinco problemas do programa
// vale cinco execuções de um que para no primeiro.
ResultadoSemantico verificar(const NoAst& raiz);
private:
// Percurso 1: coleta declarações de padrão, compila os autômatos e infere
// o tipo do casamento de cada um.
void coletarDeclaracoes(const NoAst& no);
// Percurso 2: verifica as ações, as condições e as emissões.
void verificarUsos(const NoAst& no);
void verificarAcao(const NoAst& acao);
// Avalia o tipo de uma expressão, reportando o que estiver errado no
// caminho. Devolve Tipo::Erro quando não conseguiu decidir — e o valor de
// erro é absorvente, o que impede a cascata de mensagens.
Tipo tipoDe(const NoAst& expr);
void erro(const NoAst& no, const std::string& mensagem);
void aviso(const NoAst& no, const std::string& mensagem);
const SourceFile& fonte_;
DiagnosticBag& diagnosticos_;
TabelaDeSimbolos tabela_;
ResultadoSemantico resultado_;
};
// Atalho para as demonstrações e para o programa principal.
ResultadoSemantico verificarArquivo(const SourceFile& arquivo,
const NoAst& raiz,
DiagnosticBag& diagnosticos);
} // namespace peneira
#endif // PENEIRA_12_SEMA_H
A decisão da seção 6.1, aplicada aqui, dá dois percursos, e por duas dependências concretas.
A primeira é que a linguagem permite que o bloco de regras apareça antes dos padrões que ele referencia. Um verificador de passagem única acusaria padrão não declarado para um padrão declarado três linhas abaixo. Ou se exige ordem de declaração — restrição real imposta a quem escreve, para conveniência do compilador —, ou se fazem dois percursos.
A segunda é mais forte e não tem alternativa. O tipo da variável de ligação depende do autômato do padrão, que é construído no primeiro percurso; o segundo percurso precisa desse tipo pronto. A ordem entre os dois não é preferência: é o grafo de dependências mandando, exatamente como no caso dos atributos.
Então o primeiro percurso coleta declarações, compila autômatos e infere tipos; o segundo verifica ações, condições e emissões. E há o terceiro grupo, que não é percurso: os avisos de declaração sem uso, emitidos depois dos dois, com a tabela inteira montada — a categoria que a seção 6.1 isolou.
Sobre a qualidade do relato, seguindo os três componentes da seção 6.3: toda mensagem nomeia o identificador envolvido, aponta a posição e explica a natureza do problema, e nenhuma interrompe a verificação das demais. A do uso indevido da extração de valor foi a que mais trabalhei, porque a mensagem óbvia — “tipo incompatível” — não ajuda ninguém; a que ficou explica que o padrão ligado àquela variável casa também cadeias que não são números, que é a informação de que o autor precisa para corrigir.
Sobre o defeito característico da seção 6.2, a defesa está no desenho: a entrada e a saída de escopo de uma ação estão no mesmo bloco de função, sem retorno antecipado entre elas, e a invariante conferida é que a profundidade da tabela seja a mesma antes e depois de verificar cada ação.
1.8.5 7.5 O grafo de atributos, com o mecanismo à vista
O verificador da subseção anterior avalia atributos o tempo todo, e avalia de um jeito que esconde o mecanismo: a recursão da linguagem hospedeira resolve a ordem sozinha, e quem lê o código vê chamadas de função, não um grafo de dependências. Escrevi um módulo à parte para expor o que aquele esconde.
12_atributos.h
#ifndef PENEIRA_12_ATRIBUTOS_H
#define PENEIRA_12_ATRIBUTOS_H
#include <cstddef>
#include <cstdint>
#include <string>
#include <vector>
#include "10_ast.h"
namespace peneira {
// Tradução dirigida por sintaxe, tornada observável.
//
// O verificador de `12_sema` avalia atributos o tempo todo, mas avalia de um
// jeito que esconde o mecanismo: a recursão da linguagem hospedeira resolve a
// ordem sozinha, e quem lê o código vê chamadas de função, não um grafo de
// dependências. Este arquivo existe para expor o que aquele esconde —
// construir explicitamente os atributos, as dependências entre eles e a ordem
// de avaliação que delas decorre.
//
// Não é código morto nem exercício paralelo: é o mesmo cálculo do verificador,
// feito com a maquinaria visível, e a demonstração confronta os dois
// resultados. Se divergirem, um dos dois está errado.
enum class Fluxo : std::uint8_t {
// Sintetizado: o valor sobe. Calculado a partir dos atributos dos filhos.
Sintetizado,
// Herdado: o valor desce. Calculado a partir do pai ou dos irmãos.
Herdado,
};
const char* nomeDoFluxo(Fluxo f) noexcept;
// Uma ocorrência de atributo: um atributo nomeado, preso a um nó da árvore.
// O identificador do nó é o índice na numeração em pré-ordem, que é estável e
// dispensa guardar ponteiros num grafo que sobrevive à travessia.
struct Atributo {
std::size_t no = 0;
std::string nome;
Fluxo fluxo = Fluxo::Sintetizado;
std::string valor;
// Índices, no vetor de atributos, daqueles de que este depende. É a aresta
// do grafo de dependências, e é o que determina a ordem de avaliação.
std::vector<std::size_t> depende;
};
// O grafo de dependências de atributos de uma árvore.
struct GrafoDeAtributos {
std::vector<Atributo> atributos;
// Rótulo de cada nó, para a impressão.
std::vector<std::string> rotulosDeNo;
};
// Constrói o grafo para a árvore dada, com dois atributos por nó de expressão:
//
// `escopo` — HERDADO. Desce da ação para os operandos e carrega o nome da
// variável de ligação visível ali. É herdado porque a informação
// nasce acima do ponto onde é usada: a expressão `value(n) > 100`
// não tem, em si, como saber o que é `n`.
// `tipo` — SINTETIZADO. Sobe dos operandos para o operador. É sintetizado
// porque o tipo de uma comparação é função dos tipos dos lados,
// e de mais nada.
//
// Ter os dois na mesma árvore é o ponto: um desce, o outro sobe, e a ordem de
// avaliação tem de respeitar as duas direções ao mesmo tempo. É por isso que a
// ordem não é "pós-ordem" nem "pré-ordem", e sim a ordem topológica do grafo.
GrafoDeAtributos construirGrafo(const NoAst& raiz);
// Ordem topológica das ocorrências de atributo. Devolve os índices na ordem em
// que podem ser avaliados; vazio se houver ciclo.
//
// A existência da ordem é o que torna a gramática de atributos **bem
// definida**. Uma gramática cujo grafo tem ciclo não é avaliável em ordem
// nenhuma, e o ciclo é um defeito da especificação, não do programa de
// entrada. Detectá-lo aqui, e não com um estouro de pilha em tempo de
// execução, é o motivo de o grafo existir.
std::vector<std::size_t> ordemDeAvaliacao(const GrafoDeAtributos& g);
// Verifica se a gramática de atributos usada cabe na classe S-atribuída
// (somente sintetizados) ou na L-atribuída (sintetizados mais herdados que só
// dependem do pai e dos irmãos à esquerda). A classificação decide se a
// tradução pode ser feita durante a análise sintática, em um percurso só, ou
// se exige a árvore construída antes.
struct ClasseDaGramatica {
bool sAtribuida = false;
bool lAtribuida = false;
std::string justificativa;
};
ClasseDaGramatica classificar(const GrafoDeAtributos& g);
std::string formatarGrafo(const GrafoDeAtributos& g);
} // namespace peneira
#endif // PENEIRA_12_ATRIBUTOS_H
São dois atributos por nó de expressão, um de cada fluxo, e a escolha deles é o que faz a demonstração valer. O atributo de escopo é herdado: desce da ação para os operandos, carregando a variável de ligação visível ali. O atributo de tipo é sintetizado: sobe dos operandos para o operador. O nó de extração de valor é onde os dois se encontram, e é o mais instrutivo da árvore — o tipo que ele sintetiza depende do escopo que ele herdou, porque saber se a variável é numérica exige saber a que padrão ela está ligada. É a situação exata do destaque da seção 4.2: uma dependência que sobe, alimentada por uma que desceu.
Construído o grafo do programa de exemplo, ele tem dezenove ocorrências de atributo, sete sintetizadas e doze herdadas, sem ciclo. Três leituras.
A primeira é que a ordem de avaliação não é pós-ordem nem pré-ordem, e a ordenação topológica é o que atende às duas direções ao mesmo tempo. Usei o algoritmo de Kahn precisamente pela razão dada na seção 4.3: o que sobra ao final, se sobrar algo, é o conjunto de atributos mutuamente dependentes.
A segunda é a classificação das Definições 4.6 e 4.7. A gramática não é S-atribuída, porque tem herdados; é L-atribuída, porque todo herdado depende apenas de um nó anterior na pré-ordem, nunca de irmão à direita. Pelo Teorema 4.3, isso significa que esta tradução poderia ser feita em um percurso da esquerda para a direita, durante a análise descendente, sem construir a árvore. Não é o que fazemos — a árvore existe porque as fases de síntese precisam dela —, mas a propriedade está verificada em vez de suposta.
A terceira é metodológica e vale mais do que as duas anteriores: a demonstração confronta os tipos que a ordenação topológica produz com os que o verificador calcula por recursão. Se divergirem, um dos dois está errado, e a divergência aponta o nó a investigar. Dois cálculos independentes da mesma coisa é a forma mais barata de teste que conheço para código de compilador.
1.9 Síntese
A análise semântica existe porque a gramática livre de contexto não alcança condições que relacionam pontos distantes do programa, e a impossibilidade tem demonstração: a linguagem \{wcw\} não é livre de contexto, porque a pilha reconhece correspondências aninhadas e não paralelas. O andar da hierarquia que capturaria essas condições existe e ninguém mora nele. A tabela de símbolos se projeta justificando cada campo pelo consumidor e escolhendo a estrutura de dados pelo padrão de uso; os escopos aninhados admitem duas implementações com compromissos invertidos, e qual escolher depende da profundidade que a sua linguagem realmente produz. O arcabouço é a tradução dirigida por sintaxe: sintetizados sobem, herdados descem, e quando as duas direções coexistem a ordem de avaliação é uma ordem topológica do grafo de dependências. A verificação de tipos é a aplicação mais visível disso, e escrevê-la antes como regras de inferência é o hábito que produz um verificador coerente. E o número de percursos sai de listar as verificações e perguntar o que cada uma precisa ter coletado antes.
Volto à cena da abertura. Aquele programa que passou com zero erros agora tem nome para cada falha: o nome não declarado é a instância concreta do resultado de impossibilidade; a operação numérica sobre algo que não é número é a regra de inferência que não fecha; a comparação entre incomparáveis é a política de coerção decidida em vez de omitida. E fica uma economia que eu não teria previsto: as operações booleanas sobre autômatos finitos foram construídas módulos atrás por teoria pura, e aqui decidem uma pergunta de sistema de tipos.
O próximo módulo muda de metade do compilador: até aqui estivemos na análise, que reconhece e verifica; a partir de agora, na síntese, que constrói. E a fase que acabamos de escrever já produz a primeira parte do que a síntese consome — a tabela preenchida e a árvore anotada com tipos são exatamente o que a geração intermediária lê.