un

guest
1 / ?
back to lessons

Grammar sebagai Struktur Graf

Sebuah compiler menerjemahkan kode sumber dengan membangun pohon analisis - sebuah pohon dengan akar di mana setiap node mewakili aturan grammar yang diterapkan, & setiap daun mewakili simbol terminal (nama variabel, literal, operator).

Geometri Pohon

Pohon dengan n node & n−1 edge. 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 node.

Pohon analisis untuk ekspresi biasa tidak seimbang: urutan operator menciptakan pohon yang condong ke kanan atau kiri. A + B C menghasilkan pohon di mana lebih dalam dari +, yang mengkodekan bahwa * lebih erat ikatannya.

BNF & ALGOL

Backus-Naur Form (BNF), yang dibuat untuk menetapkan ALGOL, mem formalisasi grammar sebagai aturan produksi:

`` <expr> ::= <term> | <expr> + <term> <term> ::= <factor> | <term> * <factor> <factor> ::= id | (<expr>) ``

Setiap aturan produksi mendefinisikan satu tingkat pohon. Grammar adalah graf arco pada simbol non-terminal; parsing kalimat mengikuti jalur melalui graf itu dari simbol start ke daun.

Geometri Perangkat Lunak: Kompleksitas & Redundansi

Kedalaman Pohon Analisis & Kompleksitas Ekspresi

Untuk ekspresi (A + B) * (C + D), pohon analisis memiliki struktur khusus di bawah kebiasaan urutan operator.

Kedalaman pohon pengaruh kinerja compiler: pohon yang lebih dalam membutuhkan frame stack yang lebih banyak selama parsing turun rekursif.

Gambar atau deskripsikan pohon analisis untuk `(A + B) * (C + D)` menggunakan grammar di atas. Berapa banyak node internal yang ada? Apa itu kedalaman pohon (akar = kedalaman 0)? Kemudian: seorang parser turun rekursif menggunakan ruang stack O(kedalaman). Untuk ekspresi yang sepenuhnya ditulis dengan tanda kurung dari n operator (setiap operator di kedalaman proporsional terhadap n), apa itu ruang stack Big-O?

Entropi Shannon & Redundansi

Hamming mencatat bahwa bahasa lisan sekitar 60% redundan, bahasa tulis 40%. Hal ini memiliki arti informasi-teoretis 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 sama kemungkinan). H_max = log₂(n) untuk n simbol.

Redundansi R: fraksi bit yang tidak mengandung informasi (dapat dihapus tanpa kehilangan konten):

R = 1 − H / H_max

Jika R = 0,4 (40% redundan): 40% bit dapat diprediksi dari konteks. Saluran yang mengirim teks Bahasa Inggris dengan 8 bit/character menggunakan hanya 60% kapasitasnya untuk informasi; 40% adalah struktur yang penerima sudah tahu.

Deteksi kesalahan menggunakan redundansi: jika 40% bit dapat diprediksi, kesalahan transmisi mungkin menghasilkan seri yang melanggar struktur redundansi - detektable bahkan tanpa kode pengkoraksian kesalahan.

APL hampir nol redundansi: perubahan karakter tunggal hampir tidak pernah terdeteksi dari konteks sendiri. Bahasa Inggris 60% redundan: Anda dapat sering mengkonstruksi kata dari konteks sekitar bahkan jika sebuah huruf hilang atau salah.

Menghitung Redundansi

Frekuensi huruf Inggris (sekitar): 'e' muncul ~12,7% waktu; 'z' muncul ~0,07%. Entropi aktual Inggris adalah sekitar H ≈ 1,0 bit/karakter (mengacu pada konteks kata). Entropi maksimum untuk abjad 26 huruf: H_max = log₂(26) ≈ 4,70 bit/karakter.

Hitung redundansi R = 1 − H/H_max untuk Bahasa Inggris dengan H = 1,0 bit/char dan H_max = log₂(26). Kemudian hitung R untuk bahasa dengan H = 3,5 bit/char dan alfabet 26 simbol yang sama. Bahasa mana yang memiliki kapasitas deteksi kesalahan lebih besar, dan oleh faktor apa?

Grafik Pertumbuhan sebagai Geometri

Algoritma compiler memproses program dengan ukuran n (token, baris, atau node). Pilihan algoritma menentukan bagaimana waktu kompilasi berkembang dengan ukuran program.

Kelas Kemampuan Umum

| Kelas | Waktu | Contoh | |---|---|---| | O(n) | linear | pemindaian leksikal | | O(n log n) | quasi-linear | pengurutan optimal | | O(n²) | kuadrat | deteksi duplikat sederhana | | O(n³) | kubik | perkalian matrix, parsing CYK | | O(2ⁿ) | eksponensial | pembuktian teorema sederhana |

Gambarkan gambar geometri: plot waktu vs n. O(n) adalah garis. O(n²) adalah parabola. O(2ⁿ) adalah kurva eksponensial yang terlihat datar di dekat n = 0 dan hampir vertikal di dekat n = 50.

Pemrosesan grammar konteks bebas umum (algoritma CYK) berjalan dalam O(n³). Untuk kebanyakan bahasa pemrograman praktis, grammar dirancang untuk dapat diparsing LR(1), memungkinkan O(n) parsing. Grammar ALGOL lebih kompleks daripada FORTRAN, yang menyumbang pada kompilator yang lebih lambat - fraksi praktis yang berarti pada 1958 ketika kompilasi memakan waktu jam.

Titik Silang

Pencarian tabel simbol yang mudah secara total menggunakan O(n²) operasi untuk program dengan n identifier (scan linear untuk setiap dari n pencarian). Tabel hash menggunakan O(n) operasi total yang diharapkan.

Misal: Algoritma O(n²) berjalan pada 10⁶ operasi/detik pada perangkat 1958. Algoritma O(n) berjalan dengan kecepatan yang sama tetapi membutuhkan 100n operasi pengaturan (konstruksi tabel hash).

Untuk program dengan n = 1000 identifier: hitung waktu total untuk kedua algoritma (dalam detik). Pada nilai apa dari n kedua algoritma menghabiskan waktu yang sama? Tunjukkan aljabar.