Tata Bahasa sebagai Struktur Grafik
Kompiler menerjemahkan kode sumber dengan membangun pohon penguraian — pohon berakar di mana setiap simpul mewakili aturan tata bahasa yang diterapkan, & setiap daun mewakili simbol terminal (nama variabel, literal, operator).
Geometri Pohon
Pohon dengan n simpul & n−1 tepi. Kedalaman d: jarak maksimum dari akar ke daun mana pun. Untuk pohon biner seimbang dengan kedalaman d: hingga 2^d daun & 2^(d+1)−1 total simpul.
Pohon penguraian untuk ekspresi khas tidak seimbang: urutan operator menghasilkan pohon miring ke kanan atau ke kiri. A + B C menghasilkan pohon di mana lebih dalam dari +, menyandikan bahwa * mengikat lebih erat.
BNF & ALGOL
Bentuk Backus-Naur (BNF), yang ditemukan untuk menentukan ALGOL, memformalkan tata bahasa sebagai aturan produksi:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Setiap aturan produksi menentukan satu level pohon. Tata bahasa adalah grafik berarah pada simbol non-terminal; penguraian kalimat melacak jalur melalui grafik itu dari simbol awal ke daun.
Kedalaman Pohon Penguraian & Kompleksitas Ekspresi
Untuk ekspresi (A + B) * (C + D), pohon penguraian memiliki struktur spesifik di bawah urutan operator standar.
Kedalaman pohon penguraian memengaruhi kinerja kompiler: pohon yang lebih dalam memerlukan lebih banyak bingkai tumpukan selama penguraian descent rekursif.
Entropi Shannon & Redundansi
Hamming mencatat bahwa bahasa lisan adalah ~60% berlebihan, bahasa tertulis ~40%. Ini memiliki makna teori informasi yang tepat.
Entropi Shannon
Untuk sumber yang menghasilkan simbol dari alfabet A dengan probabilitas {p₁, p₂, ..., pₙ}:
H = −Σ pᵢ log₂(pᵢ) (bit per simbol)
Entropi maksimum: distribusi seragam (semua simbol kemungkinan sama). H_max = log₂(n) untuk n simbol.
Redundansi R: fraksi bit yang tidak membawa informasi (bisa dihapus tanpa kehilangan konten):
R = 1 − H / H_max
Jika R = 0,4 (40% berlebihan): 40% bit dapat diprediksi dari konteks. Saluran yang membawa teks Inggris pada 8 bit/karakter hanya menggunakan 60% kapasitasnya untuk informasi; 40% adalah struktur yang sudah diketahui penerima.
Deteksi kesalahan menggunakan redundansi: jika 40% bit dapat diprediksi, kesalahan transmisi dapat menghasilkan urutan yang melanggar struktur redundansi — terdeteksi bahkan tanpa kode koreksi kesalahan.
Redundansi APL yang hampir nol: perubahan karakter tunggal hampir tidak pernah terdeteksi dari konteks saja. Redundansi Inggris 60%: Anda sering dapat merekonstruksi kata dari konteks sekitarnya bahkan jika huruf hilang atau salah.
Menghitung Redundansi
Frekuensi huruf Inggris (perkiraan): 'e' muncul ~12,7% sepanjang waktu; 'z' muncul ~0,07%. Entropi sebenarnya dari Inggris sekitar H ≈ 1,0 bit/karakter (memperhitungkan konteks tingkat kata). Entropi maksimum untuk alfabet 26 huruf: H_max = log₂(26) ≈ 4,70 bit/karakter.
Kurva Pertumbuhan sebagai Geometri
Algoritma kompiler memproses program ukuran n (token, baris, atau simpul). Pilihan algoritma menentukan bagaimana waktu kompilasi diskalakan dengan ukuran program.
Kelas Kompleksitas Umum
| Kelas | Runtime | Contoh | |---|---|---| | O(n) | linear | pemindaian leksikal | | O(n log n) | quasi-linear | pengurutan optimal | | O(n²) | kuadratik | deteksi duplikat naif | | O(n³) | kubik | perkalian matriks, penguraian CYK | | O(2ⁿ) | eksponensial | pembuktian teorema naif |
Gambar geometris: plot runtime vs n. O(n) adalah garis. O(n²) adalah parabola. O(2ⁿ) adalah kurva eksponensial yang terlihat datar di dekat n=0 & hampir vertikal di dekat n=50.
Penguraian tata bahasa konteks-bebas umum (algoritma CYK) berjalan dalam O(n³). Untuk sebagian besar bahasa pemrograman praktis, tata bahasa dirancang untuk dapat dianalisis LR(1), memungkinkan penguraian O(n). Tata bahasa ALGOL lebih kompleks daripada FORTRAN, berkontribusi pada kompiler yang lebih lambat — gesekan praktis yang penting pada tahun 1958 ketika kompilasi memakan waktu berjam-jam.
Titik Persimpangan
Pencarian tabel simbol naif menggunakan operasi total O(n²) untuk program n pengidentifikasi (pemindaian linear untuk masing-masing dari n pencarian). Tabel simbol tabel hash menggunakan operasi total O(n) yang diharapkan.
Misalkan: algoritma O(n²) berjalan pada 10⁶ operasi/detik pada perangkat keras 1958. Algoritma O(n) berjalan dengan kecepatan yang sama tetapi memerlukan operasi setup 100n (konstruksi tabel hash).