Dilbilgisini Grafik Yapısı Olarak
Derleyici, kaynak kodu ayrıştırma ağacı oluşturarak çevirir — her düğüm uygulanmış bir dilbilgisi kuralını temsil eden, her yaprak bir terminal sembolü (değişken adı, hazır değer, işleç) temsil eden köklenmiş bir ağaç.
Ağaç Geometrisi
n düğümlü ve n−1 kenarlı ağaç. Derinlik d: kökten herhangi bir yaprağa olan maksimum mesafe. d derinlikli dengeli ikili ağaç: en fazla 2^d yaprak ve 2^(d+1)−1 toplam düğüm.
Tipik ifadeler için ayrıştırma ağaçları dengeli değildir: işleç önceliği sağa veya sola eğilmiş ağaçlar oluşturur. A + B C ifadesi, öğesinin + öğesinden daha derin olduğu bir ağaç üretir, bu da * öğesinin daha sıkı bağlandığını kodlar.
BNF & ALGOL
Backus-Naur Formu (BNF), ALGOL'u belirtmek için icat edilmiş, dilbilgisini üretim kuralları olarak resmileştirir:
``
<expr> ::= <term> | <expr> + <term>
<term> ::= <factor> | <term> * <factor>
<factor> ::= id | (<expr>)
``
Her üretim kuralı ağacın bir seviyesini tanımlar. Dilbilgisi, terminal olmayan semboller üzerine yönlendirilmiş bir graftır; bir cümleyi ayrıştırmak bu grafta başlangıç sembolünden yapraklara giden bir yol izler.
Ayrıştırma Ağacı Derinliği & İfade Karmaşıklığı
(A + B) * (C + D) ifadesi için, ayrıştırma ağacı standart işleç önceliği altında belirli bir yapıya sahiptir.
Ayrıştırma ağacının derinliği derleyici performansını etkiler: daha derin ağaçlar recursive descent ayrıştırması sırasında daha fazla yığın çerçevesi gerektirir.
Shannon Entropisi & Fazlalık
Hamming, konuşulan dilin ~%60 fazlalıklı, yazılı dilin ~%40 fazlalıklı olduğunu belirtti. Bunun kesin bir bilgi-teorik anlamı vardır.
Shannon Entropisi
A alfabesinden {p₁, p₂, ..., pₙ} olasılıklarıyla semboller üreten bir kaynak için:
H = −Σ pᵢ log₂(pᵢ) (sembol başına bitler)
Maksimum entropi: üniform dağılım (tüm semboller eşit olasılık). H_max = log₂(n) n sembol için.
Fazlalık R: hiçbir bilgi taşımayan bit fraksiyonu (içerik kaybı olmadan kaldırılabilir):
R = 1 − H / H_max
R = 0,4 (%40 fazlalıklı) ise: %40 bitler bağlamdan tahmin edilebilir. 8 bit/karakter hızında İngilizce metin taşıyan bir kanal, bilgi için kapasitesinin yalnızca %60'ını kullanıyor; %40'ı alıcının zaten bildiği yapıdır.
Hata algılama fazlalığı kullanır: %40 bite tahmin edilebilir ise, iletim hatası fazlalık yapısını ihlal eden bir dizi üretebilir — hata düzeltme kodları olmadan bile algılanabilir.
APL'nin yaklaşık-sıfır fazlalığı: tek bir karakter değişikliği neredeyse hiçbir zaman bağlamdan algılanamaz. İngilizce'nin %60 fazlalığı: çevresindeki bağlamdan, eksik veya yanlış bir harf olsa bile bir sözcüğü genellikle yeniden oluşturabilirsiniz.
Fazlalık Hesaplama
İngilizce harf sıklığı (yaklaşık): 'e' harfi zamanın ~%12,7'sinde görünür; 'z' ~%0,07'sinde görünür. İngilizce'nin gerçek entropisi, sözcük düzeyi bağlam dikkate alındığında yaklaşık H ≈ 1,0 bit/karakter'tir. 26 harfli alfabe için maksimum entropi: H_max = log₂(26) ≈ 4,70 bit/karakter.
Büyüme Eğrileri Geometri Olarak
Derleyici algoritmaları n boyutundaki programları işler (jetonlar, satırlar veya düğümler). Algoritma seçimi derleme zamanının program boyutuyla nasıl ölçeklenmesini belirler.
Yaygın Karmaşıklık Sınıfları
| Sınıf | Çalışma Süresi | Örnek | |---|---|---| | O(n) | doğrusal | sözcüksel tarama | | O(n log n) | yarı-doğrusal | optimal sıralama | | O(n²) | kare | naif yinelenen algılama | | O(n³) | kübik | matris çarpımı, CYK ayrıştırması | | O(2ⁿ) | üstel | naif teorem kanıtlama |
Geometrik resim: çalışma süresi vs n grafiği çizin. O(n) bir çizgidir. O(n²) bir paraboldür. O(2ⁿ) n=0'a yakın düz görünen, n=50'ye yakın neredeyse dikey görünen bir üstel eğridir.
Genel bağlam-bağımsız dilbilgisi ayrıştırması (CYK algoritması) O(n³)'te çalışır. Çoğu pratik programlama dili için dilbilgisi LR(1)-ayrıştırılabilir olacak şekilde tasarlanmış, O(n) ayrıştırmasına izin verir. ALGOL'un dilbilgisi FORTRAN'ınkından daha karmaşıktı, daha yavaş derleyicilere katkı sağladı — 1958'de derlemenin saatler aldığı dönemde önemli olan pratik bir sürtünme.
Geçiş Noktaları
Naif sembol-tablo araması n tanımlayıcılı bir program için O(n²) toplam işlem kullanır (her n araması için doğrusal tarama). Karma-tabel sembol tablosu O(n) beklenen toplam işlem kullanır.
Varsayalım: O(n²) algoritma 1958 donanımında 10⁶ işlem/saniyede çalışır. O(n) algoritma aynı hızda çalışır, ancak 100n kurulum işlemi gerektirir (karma tabel yapısı).