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 — Resumo
Esta é a versão de revisão. Recapitulo em ritmo de véspera o que este módulo tem de guardado; nenhuma demonstração aparece por inteiro, e para isso existem a versão completa do material e o livro. Use este texto para conferir se reconstrói de cabeça o caminho que vai de “zero erros” até um compilador que sabe discordar.
A cena é a mesma todo semestre: o analisador sintático responde zero erros, a árvore sai bonita, e o programa é um disparate — usa um nome que ninguém declarou, aplica operação numérica a algo que nunca será número, compara incomparáveis. O analisador fez o que lhe cabia. O programa atravessou a fronteira entre forma e sentido, e do outro lado existe uma fase inteira que ainda não foi escrita.
1.1 O que a gramática não alcança
Uma cadeia de tokens é sintaticamente correta quando existe derivação dela a partir do símbolo inicial, e isso a fase anterior decide por completo. A correção semântica estática exige condições dependentes de contexto, que relacionam pontos distantes do programa.
São três famílias. Declaração: todo nome usado precisa ter sido declarado, nenhum duas vezes no mesmo escopo, e visível dali. Tipos: cada operação exige operandos de certos tipos. Fluxo estático: não se lê um valor antes de atribuí-lo. O traço comum decide a arquitetura da fase: todas relacionam dois pontos distantes, e nenhuma dessas relações é local — a árvore exprime bem aninhamento e não exprime isso.
O argumento formal, porque “a gramática não lembra os nomes” é vago demais: a linguagem L_{du} = \{\, wcw \mid w \in \{a,b\}^+ \,\} — a declaração à esquerda do c, o mesmo nome no uso à direita — não é livre de contexto. Em z = a^p b^p c\, a^p b^p, o trecho bombeável não alcança ao mesmo tempo uma posição da metade esquerda e a correspondente da direita.
Pare e pense. Com o reverso no lugar da cópia, a linguagem seria livre de contexto. 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.
Consequência: nenhuma gramática livre de contexto descreve os programas corretos de uma linguagem com declarações — a que você escreveu aceita os corretos e mais uma infinidade de incorretos. O andar de cima da hierarquia existe e ninguém mora nele: a contabilidade custa dezenas de produções, a pertinência é exponencial e, razão decisiva, a gramática responderia sim ou não, quando o que se quer é a árvore anotada, a tabela preenchida e diagnósticos que nomeiem o identificador ofensor. E há o teto: esta fase decide propriedades do texto, não do comportamento, e entre as duas ficam as aproximações conservadoras.
1.2 A tabela de símbolos
A estrutura que sustenta a fase associa a cada nome os atributos da entidade que ele denota, de modo que a consulta feita de um ponto do programa devolva a declaração visível ali. É essa cláusula final 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"]
A regra que economiza retrabalho é apresentá-la pelo consumidor: nenhum campo entra por completude; cada campo entra porque alguma verificação precisa dele. O nome é a chave. A espécie separa categorias que dividem o espaço de nomes — sem ela, usar um nome de padrão onde se espera uma ligação passa batido. A posição serve à mensagem de redeclaração; o marcador de uso só é legível depois de percorrida a árvore inteira.
Daí uma lição que vale 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, e quem deixa o conceito escolher obtém algo elegante e lento: a operação dominante é a consulta por nome.
| Estrutura | Consulta | Inserção | Quando usar |
|---|---|---|---|
| Tabela de dispersão | O(1) médio | O(1) médio | caso geral |
| Árvore balanceada | O(\log n) | O(\log n) | listagem ordenada importa |
| Lista linear | O(n) | O(1) | escopos pequenos |
São quatro operações: inserção no escopo corrente reportando se o nome já existia ali; consulta visível, do escopo mais interno para o mais externo; consulta local, restrita ao corrente; e o par de entrada e saída de escopo. As duas consultas não são redundantes — uma responde “o que este nome significa aqui?”, a outra “este nome já foi declarado neste escopo?” —, e quem usa a visível para as duas coisas recusa programas válidos.
1.3 Escopos, visibilidade e as duas estratégias
O escopo de uma declaração é a região do texto em que ela dá significado ao nome; havendo mais de uma que contenha o ponto de uso, vale a do bloco mais interno, que sombreia as externas. É o escopo estático que ALGOL 60 consagrou, conhecido em tempo de compilação; o dinâmico das primeiras implementações de Lisp desapareceu porque empurra a resolução de nomes para a execução. E repito o alerta que mais gera defeito: redeclaração e sombreamento são situações distintas — a primeira é erro, a segunda é legítima e no máximo mau estilo, daí o aviso em vez do 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
Na estratégia empilhada, entrar empilha uma tabela vazia e sair desempilha; a consulta caminha do topo para a base e para no primeiro acerto — a regra do bloco mais interno é a ordem do percurso, sem código algum. Na encadeada, uma tabela única leva o nome à pilha de declarações ativas dele, e a consulta vira uma sondagem mais a leitura do topo. Sendo d a profundidade e m as declarações do escopo que se fecha: a empilhada consulta em O(d) e sai em O(1); a encadeada consulta em O(1) médio e sai em O(m), ao preço da trilha de desfazimento por nível, sua principal fonte de defeito.
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, e com blocos profundamente aninhados a conclusão se inverte. Instrumente as duas e meça.
Na Peneira as duas estão implementadas: dez consultas ao nome mais externo custam vinte sondagens na empilhada em profundidade um e noventa em profundidade oito, contra dez da encadeada. E a escolha ainda assim é a empilhada, porque a linguagem tem dois níveis de escopo.
1.4 Tradução dirigida por sintaxe
Temos uma árvore e queremos pendurar informação nos nós: parte flui de baixo para cima, como o tipo de uma soma; parte de cima para baixo, como o escopo visível. A formalização é de Donald Knuth, em 1968, e chama-se gramática de atributos; a contribuição foi dar à especificação forma declarativa — escrevem-se as equações, não a ordem — e derivar a ordem delas. Atributos sintetizados vêm dos filhos e sobem; herdados, do pai e dos irmãos, e descem. Uma produção só define os sintetizados do seu lado esquerdo e os herdados dos seus filhos.
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
A consequência mais importante da seção. Com 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 o contrário. A ordem correta é topológica sobre o grafo de dependências.
Uma ocorrência de atributo é um par de nó e atributo; o grafo de dependências as toma como vértices, com aresta de uma para outra quando a regra que define a segunda usa a primeira. Existe atribuição consistente se e somente se o grafo é acíclico. 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. E um ciclo não é erro do programa compilado, é erro da especificação — Jazayeri, Ogden e Rounds estabeleceram em 1975 que decidir a não circularidade é intrinsecamente exponencial. Daí as duas subclasses em que ela sai de graça: S-atribuída, só com sintetizados, onde a pós-ordem já é topológica; e L-atribuída, em que cada herdado depende só de herdados do pai e de irmãos à esquerda, e um percurso da esquerda para a direita basta — a tradução cabe na análise descendente, sem construir a árvore. Um esquema de tradução é a gramática com as ações intercaladas onde devem executar: a gramática de atributos com o quando já escolhido. No caso conduzido, o grafo tem dezenove ocorrências, sem ciclo, e sai verificado como L-atribuído.
1.5 Verificação de tipos
É a aplicação mais visível do arcabouço, e onde mora a maior parte do código da fase. Um sistema de tipos atribui um tipo a cada expressão bem formada, ou a declara maltipada, por julgamentos \Gamma \vdash e : \tau. Repara em quem é \Gamma: a tabela de símbolos na forma matemática — toda decisão de tipo é relativa às declarações visíveis, e é por isso que o escopo tinha de ser herdado. A consulta de um nome devolve o que a tabela registra,
\frac{\Gamma(x) = \tau}{\Gamma \vdash x : \tau}
e uma comparação produz booleano a partir de 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: uma regra que você não consegue escrever é uma decisão de projeto que ainda não tomou. Com construtores de tipo, “estes dois tipos são o mesmo?” se divide em equivalência estrutural — mesmo tipo básico ou mesmo construtor sobre tipos equivalentes — e equivalência por nome — mesma declaração, tenham a estrutura que tiverem. Sob a segunda, um tipo para metros e outro para segundos não se somam; sob a primeira, são o mesmo tipo. Uma coerção é a conversão que o compilador insere sem aparecer no texto, e transforma erro em silêncio; a política: a que perde informação deve ser explícita; a que preserva pode ser implícita.
O truque de melhor retorno da fase. Reserve um tipo de erro para toda expressão cujo tipo não foi determinado por causa de um defeito já reportado, com absorção: operação com operando desse tipo produz esse tipo e não gera diagnóstico novo. Sem isso, um defeito no fundo da árvore gera uma mensagem ali e mais uma em cada operador acima — e a absorção precisa valer em todas as regras.
Encerro com o caso que dá identidade à fase. Às vezes o tipo é derivável do que já foi escrito, e as saídas óbvias são ruins: anotação transfere ao autor uma verificação que o compilador faria; heurística erra nos dois sentidos, em silêncio. A terceira é decidir. Se os valores de um tipo formam L_\tau e a entidade produz L_e, a pergunta é a inclusão L_e \subseteq L_\tau, equivalente a L_e \setminus L_\tau = \emptyset — decidível para linguagens regulares, porque a classe é fechada sob complemento e interseção.
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"]
É assim que o compilador da Peneira descobre se um padrão casa sempre um número, reusando a diferença de autômatos e o teste de vacuidade de módulos atrás:
// 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); // 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;
}O alfabeto é parâmetro explícito porque o complemento só existe em relação a um alfabeto fixado — inferi-lo dos símbolos usados daria resposta errada, em silêncio, para os demais. No programa de exemplo, o padrão numérico dá diferença vazia e sai número; o de endereço eletrônico sai texto, sem anotação de tipo em lugar nenhum.
1.6 Percursos e diagnósticos
Sobra a decisão operacional: quantas travessias, e o que cada uma faz. Uma só basta quando a linguagem exige declaração antes do uso — não é acidente que várias linguagens antigas imponham isso, Pascal à frente: a restrição existe para permitir compiladores de uma passagem. Permitido referenciar um nome declarado depois, nenhuma esperteza local resolve.
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 pergunta que resolve a decomposição. Não decida pela arquitetura. Liste as verificações e pergunte, para cada uma: que informação preciso já ter coletado para 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.
Na Peneira isso dá dois, por dependência e não por gosto: o tipo da ligação depende do autômato do padrão, compilado no primeiro percurso, e a regra pode aparecer antes do padrão que referencia. O primeiro coleta padrões, compila autômatos e infere tipos; o segundo verifica ações, condições e emissões. Há ainda o grupo que não é percurso — o aviso de declaração sem uso, emitido depois sobre a tabela completa. O defeito característico da fase é o escopo desbalanceado: um retorno antecipado entre a entrada e a saída deixa o escopo aberto, e o sintoma é perverso, porque o compilador passa a aceitar programas errados. A defesa é barata: entrada e saída na mesma função, e a invariante de que a profundidade da tabela seja a mesma antes e depois. E as mensagens, que daqui em diante têm identificador, posição, declaração conflitante e os dois tipos, devem trazer os três componentes — identificação, posição e natureza do problema — sem parar no primeiro erro.
1.7 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, e a impossibilidade tem demonstração: a cópia não cabe na pilha, o reverso cabe. A tabela de símbolos se projeta justificando cada campo pelo consumidor e escolhendo a estrutura pelo padrão de uso; os escopos admitem duas implementações com compromissos invertidos. O arcabouço é a tradução dirigida por sintaxe: sintetizados sobem, herdados descem, e com as duas direções a ordem é topológica. A verificação de tipos é a aplicação mais visível disso, e o número de percursos sai de perguntar, verificação por verificação, o que precisa estar coletado antes. Volto à abertura: aquele programa de zero erros agora tem nome para cada falha — e fica a economia que eu não teria previsto, com as operações booleanas sobre autômatos finitos, construídas por teoria pura, decidindo uma pergunta de sistema de tipos. O próximo módulo troca de metade do compilador, da análise para a síntese, e a tabela preenchida com a árvore anotada é o que ela lê.