Gramática como Estrutura de Grafo
Um compilador traduz código-fonte construindo uma árvore de análise sintática — uma árvore enraizada onde cada nó representa uma regra de gramática aplicada, & cada folha representa um símbolo terminal (nome de variável, literal, operador).
Geometria de Árvore
Uma árvore com n nós & n−1 arestas. Profundidade d: a distância máxima da raiz até qualquer folha. Para uma árvore binária balanceada de profundidade d: até 2^d folhas & 2^(d+1)−1 nós totais.
As árvores de análise sintática para expressões típicas não são balanceadas: precedência de operador cria árvores inclinadas para a direita ou para a esquerda. A + B C produz uma árvore onde é mais profundo que +, codificando que * vincula-se mais fortemente.
BNF & ALGOL
Forma de Backus-Naur (BNF), inventada para especificar ALGOL, formaliza 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 grafo direcionado em símbolos não-terminais; analisar uma sentença traça um caminho através desse grafo do símbolo inicial até as folhas.
Profundidade de Árvore de Análise & 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 precedência de operador padrão.
A profundidade de uma árvore de análise sintática afeta o desempenho do compilador: árvores mais profundas requerem mais quadros de pilha durante análise de descida recursiva.
Entropia de Shannon & Redundância
Hamming observou que a linguagem falada é ~60% redundante, linguagem escrita ~40%. Isto tem um significado preciso teorético de informação.
Entropia de Shannon
Para uma fonte gerando símbolos do 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 transportam informação (poderiam ser removidos sem perder conteúdo):
R = 1 − H / H_max
Se R = 0.4 (40% redundante): 40% dos bits podem ser previstos a partir do contexto. Um canal transportando texto em inglês em 8 bits/caractere está usando apenas 60% de sua capacidade para informação; 40% é estrutura que o receptor já conhece.
Detecção de erro usa redundância: se 40% dos bits são previsíveis, um erro de transmissão pode produzir uma sequência que viola a estrutura de redundância — detectável mesmo sem códigos de correção de erro.
Redundância quase nula de APL: uma mudança de caractere único quase nunca é detectável apenas pelo contexto. Redundância de 60% do inglês: você muitas vezes pode reconstruir uma palavra do contexto circundante mesmo se uma letra estiver faltando ou errada.
Calculando Redundância
Frequência de letra em inglês (aproximada): 'e' aparece ~12.7% do tempo; 'z' aparece ~0.07%. A entropia real do inglês é aproximadamente H ≈ 1.0 bit/caractere (levando em conta contexto de nível de palavra). Entropia máxima para alfabeto de 26 letras: H_max = log₂(26) ≈ 4.70 bits/caractere.
Curvas de Crescimento como Geometria
Algoritmos de compilador processam programas de tamanho n (tokens, linhas, ou nós). A escolha do algoritmo determina como o tempo de compilação escala com o tamanho do programa.
Classes de Complexidade Comuns
| Classe | Tempo de Execução | Exemplo | |---|---|---| | O(n) | linear | análise lexical | | O(n log n) | quasi-linear | ordenação ótima | | O(n²) | quadratic | detecção ingênua de duplicatas | | O(n³) | cubic | multiplicação de matriz, análise CYK | | O(2ⁿ) | exponential | prova ingênua de teorema |
A imagem geométrica: plote tempo de execução vs n. O(n) é uma linha. O(n²) é uma parábola. O(2ⁿ) é uma curva exponencial que parece plana perto de n=0 e quase vertical perto de n=50.
Análise de gramática livre de contexto geral (algoritmo CYK) funciona em O(n³). Para a maioria das linguagens de programação práticas, a gramática é projetada para ser analisável como LR(1), permitindo análise O(n). A gramática de ALGOL era mais complexa que a de FORTRAN, contribuindo para compiladores mais lentos — um atrito prático que importava em 1958 quando a compilação levava horas.
Pontos de Cruzamento
Uma busca ingênua de tabela de símbolos usa O(n²) operações totais para um programa de n identificadores (varredura linear para cada uma de n buscas). Uma tabela de símbolos de tabela hash usa O(n) operações totais esperadas.
Suponha: algoritmo O(n²) funciona a 10⁶ operações/seg em hardware de 1958. Algoritmo O(n) funciona na mesma velocidade mas requer 100n operações de configuração (construção de tabela hash).