La grammatica come struttura di grafo
Un compilatore traduce il codice sorgente costruendo un albero di parsing — un albero radicato dove ogni nodo rappresenta una regola grammaticale applicata, & ogni foglia rappresenta un simbolo terminale (nome di variabile, letterale, operatore).
Geometria dell'albero
Un albero con n nodi & n−1 archi. Profondità d: la distanza massima dalla radice a qualsiasi foglia. Per un albero binario bilanciato di profondità d: fino a 2^d foglie & 2^(d+1)−1 nodi totali.
Gli alberi di parsing per espressioni tipiche non sono bilanciati: la precedenza degli operatori crea alberi inclinati a destra o a sinistra. A + B C produce un albero dove è più profondo di +, codificando che * si lega più strettamente.
BNF & ALGOL
La forma Backus-Naur (BNF), inventata per specificare ALGOL, formalizza la grammatica come regole di produzione:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Ogni regola di produzione definisce un livello dell'albero. La grammatica è un grafo diretto su simboli non terminali; l'analisi sintattica di una frase traccia un percorso attraverso quel grafo dal simbolo di inizio alle foglie.
Profondità dell'albero di parsing & complessità dell'espressione
Per l'espressione (A + B) * (C + D), l'albero di parsing ha una struttura specifica sotto la precedenza degli operatori standard.
La profondità di un albero di parsing influisce sulle prestazioni del compilatore: alberi più profondi richiedono più frame dello stack durante l'analisi ricorsiva discendente.
Entropia di Shannon & ridondanza
Hamming ha notato che il linguaggio parlato è ~60% ridondante, il linguaggio scritto ~40%. Questo ha un significato preciso nella teoria dell'informazione.
Entropia di Shannon
Per una fonte che genera simboli dall'alfabeto A con probabilità {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (bit per simbolo)
Entropia massima: distribuzione uniforme (tutti i simboli ugualmente probabili). H_max = log₂(n) per n simboli.
Ridondanza R: frazione di bit che non portano informazioni (potrebbe essere rimossa senza perdere contenuto):
R = 1 − H / H_max
Se R = 0,4 (40% ridondante): il 40% dei bit può essere previsto dal contesto. Un canale che trasporta testo inglese a 8 bit/carattere sta usando solo il 60% della sua capacità per l'informazione; il 40% è una struttura che il ricevente conosce già.
La rilevazione degli errori utilizza la ridondanza: se il 40% dei bit è prevedibile, un errore di trasmissione potrebbe produrre una sequenza che viola la struttura di ridondanza — rilevabile anche senza codici di correzione degli errori.
La ridondanza quasi nulla di APL: un singolo cambiamento di carattere è quasi mai rilevabile dal contesto da solo. La ridondanza del 60% dell'inglese: spesso puoi ricostruire una parola dal contesto circostante anche se una lettera manca o è sbagliata.
Calcolo della ridondanza
Frequenza delle lettere inglesi (approssimativa): 'e' appare ~12,7% delle volte; 'z' appare ~0,07%. L'entropia effettiva dell'inglese è approssimativamente H ≈ 1,0 bit/carattere (considerando il contesto a livello di parola). Entropia massima per alfabeto di 26 lettere: H_max = log₂(26) ≈ 4,70 bit/carattere.
Curve di crescita come geometria
Gli algoritmi del compilatore elaborano programmi di dimensione n (token, righe o nodi). La scelta dell'algoritmo determina come il tempo di compilazione si scala con le dimensioni del programma.
Classi di complessità comuni
| Classe | Runtime | Esempio | |---|---|---| | O(n) | lineare | scansione lessicale | | O(n log n) | quasi-lineare | ordinamento ottimale | | O(n²) | quadratico | rilevazione ingenua dei duplicati | | O(n³) | cubico | moltiplicazione di matrici, parsing CYK | | O(2ⁿ) | esponenziale | prova ingenua dei teoremi |
La figura geometrica: traccia il runtime rispetto a n. O(n) è una linea. O(n²) è una parabola. O(2ⁿ) è una curva esponenziale che sembra piatta vicino a n=0 e quasi verticale vicino a n=50.
L'analisi generale della grammatica context-free (algoritmo CYK) viene eseguita in O(n³). Per la maggior parte dei linguaggi di programmazione pratici, la grammatica è progettata per essere analizzabile LR(1), consentendo analisi O(n). La grammatica di ALGOL era più complessa di quella di FORTRAN, contribuendo a compilatori più lenti — un attrito pratico che aveva importanza nel 1958 quando la compilazione richiedeva ore.
Punti di intersezione
Una ricerca ingenua nella tabella dei simboli utilizza O(n²) operazioni totali per un programma di n identificatori (scansione lineare per ciascuna delle n ricerche). Una tabella dei simboli di hash table utilizza O(n) operazioni totali attese.
Supponiamo: l'algoritmo O(n²) viene eseguito a 10⁶ operazioni/sec su hardware del 1958. L'algoritmo O(n) funziona alla stessa velocità ma richiede 100n operazioni di configurazione (costruzione della tabella hash).