Gramática como Estrutura de Gráfico
Um compilador traduz o código-fonte construindo uma árvore de análise sintática — uma árvore raiz onde cada nó representa uma regra de gramática aplicada e cada folha representa um símbolo terminal (nome de variável, literal, operador).
Geometria da Árvore
Uma árvore com n nós e n−1 arestas. Profundidade d: a distância máxima da raiz para qualquer folha. Para uma árvore binária balanceada de profundidade d: até 2^d folhas e 2^(d+1)−1 nós totais.
As árvores de análise sintática para expressões típicas não são balanceadas: a precedência dos operadores cria árvores inclinadas para a direita ou esquerda. A + B C produz uma árvore onde está mais profundamente que +, codificando que * se liga mais apertadamente.
BNF & ALGOL
A Notação de Backus-Naur (BNF), inventada para especificar ALGOL, formaliza a gramática como regras de produção:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Cada regra de produção define um nível da árvore. A gramática é um gráfico direcionado sobre símbolos não-terminais; a análise de uma sentença traça um caminho nesse gráfico da símbolo inicial até as folhas.
Profundidade da Árvore de Análise Sintática & Complexidade de Expressão
Para a expressão (A + B) * (C + D), a árvore de análise sintática tem uma estrutura específica sob a precedência padrão dos operadores.
A profundidade da árvore de análise sintática afeta o desempenho do compilador: árvores mais profundas requerem mais espaços de pilha durante a análise recursiva descendente.
Entropia de Shannon e Redundância
Hamming observou que a linguagem falada é ~60% redundante, a escrita ~40%. Isso tem um significado precisamente informacional.
Entropia de Shannon
Para uma fonte que gera símbolos de um alfabeto A com probabilidades {p₁, p₂, ..., pₙ}:
H = -Σ pᵢ log₂(pᵢ) (bits por símbolo)
Entropia máxima: distribuição uniforme (todos os símbolos igualmente prováveis). H_max = log₂(n) para n símbolos.
Redundância R: fração de bits que não carregam informação (poderiam ser removidos sem perder o conteúdo):
R = 1 - H / H_max
Se R = 0,4 (40% redundante): 40% dos bits podem ser previstos do contexto. Um canal que transmite texto em inglês a 8 bits/caractere está usando apenas 60% de sua capacidade para informação; 40% é estrutura que o receptor já sabe.
A detecção de erros usa redundância: se 40% dos bits são previsíveis, uma transmissão com erro pode produzir uma sequência que viola a estrutura de redundância - detectável mesmo sem códigos de correção de erros.
O APL tem quase zero de redundância: uma única alteração de caracteres quase nunca é detectável do contexto sozinho. Inglês 60% redundante: você pode muitas vezes reconstruir uma palavra do contexto circundante mesmo se uma letra está errada ou ausente.
Computando Redundância
Frequência das letras em inglês (aproximada): 'e' aparece ~12,7% das vezes; 'z' aparece ~0,07%. A entropia real do inglês é aproximadamente H ≈ 1,0 bit/caractere (considerando o contexto de nível de palavra). Entropia máxima para um alfabeto de 26 letras: H_max = log₂(26) ≈ 4,70 bits/caractere.
Curvas de Crescimento como Geometria
Algoritmos de compiladores processam programas de tamanho n (tokens, linhas ou nós). A escolha do algoritmo determina como o tempo de compilação cresce com o tamanho do programa.
Classes de Complexidade Comum
| Classe | Tempo de Execução | Exemplo | |---|---|---| | O(n) | linear | análise léxica | | O(n log n) | quase-linear | ordenação ótima | | O(n²) | quadrática | detecção de duplicatas ingênua | | O(n³) | cúbica | multiplicação de matrizes, análise CYK | | O(2ⁿ) | exponencial | provas de teoremas ingênuas |
A imagem geométrica: plote o tempo de execução contra n. O(n) é uma linha. O(n²) é uma parábola. O(2ⁿ) é uma curva exponencial que parece plano perto de n = 0 e quase vertical perto de n = 50.
A análise de gramática contextual geral (algoritmo CYK) leva O(n³). Para a maioria dos idiomas de programação práticos, a gramática é projetada para ser LR(1)-parseável, permitindo O(n) de análise. A gramática do ALGOL era mais complexa do que a do FORTRAN, o que contribuiu para compiladores mais lentos - uma fricção prática que importava em 1958 quando o tempo de compilação levava horas.
Pontos de Cruzamento
Uma busca na tabela de símbolos ingênua usa O(n²) operações totais para um programa de n identificadores (escaneamento linear para cada um dos n consultas). Uma tabela de hash usa O(n) operações totais esperadas.
Suponha: um algoritmo O(n²) executa 10⁶ operações por segundo em hardware de 1958. Um algoritmo O(n) executa na mesma velocidade, mas requer 100n operações de configuração (construção da tabela de hash).