un

guest
1 / ?
back to lessons

Dilbilgisi Grafiği Olarak Yapı

Bir derleyici, kaynak kodu parse ağacı oluşturarak çevirir - her düğüm bir dil kuralına uygulanan kök bir ağaçtir ve her yaprak bir terminal sembolü (değişken adı,.literal, operatör) temsil eder.

Ağaç Geometrisi

n düğüm ve n-1 kenarlı bir ağaç. Derinlik d: kökten herhangi bir yaprağa olan en büyük mesafe. Dengeli bir ikili ağaç için derinlik d: en fazla 2^d yaprak ve 2^(d+1)-1 toplam düğüm.

Typical ifadeler için parse ağaçları dengesizdir: operator önceliği sağa eğimli veya sola eğimli ağaçlar üretir. A + B C üretirken, daha derindir +, * daha sıkı bir şekilde bağlanır.

BNF ve ALGOL

ALGOL'u belirtmek için Backus-Naur Formu (BNF) dilbilgisi üretim kurallarını formalize eder:

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

Her üretim kuralı bir ağaç seviyesi tanımlar. Dilbilgisi terminal semboller üzerinde yönlendirilmiş bir grafir; bir cümleyi analiz etmek için bu grafiğin start sembolünden yapraklara kadar bir yol izler.

Yazılım Geometrisi: Karmaşıklık ve Gereksizlik

Parse Ağaç Derinliği ve İfade Karmaşıklığı

Ifade (A + B) * (C + D) için, standart operator önceliği altında parse ağacı belirli bir yapının altında oluşur.

Ağacın derinliği, derleyicinin performansı etkiler: daha derin ağaçlar, geri döndürülmüş iniş analizi sırasında daha fazla stack çerçevesi gerektirir.

(A + B) * (C + D) ifadesinin parse ağacını yukarıdaki dilbilgisi kullanarak çiz veya açıklayın. Ağacın iç düğüm sayısı ne? Ağacın derinliği (kök = 0 derinlik)? Sonra: Devindirme indirimli bir parser O(derinlik) stack alanı kullanır. Tam olarak parantezli bir ifade (her biri n derinliğinde) n işleyici üzerinde, Big-O stack alanı nedir?

Shannon Entropisi & Redundans

Hamming, sözlü dilin %60 oranında, yazılı dilin %40 oranında redündan olduğunu belirtti. Bu, kesin bir bilgi teorisi anlamı taşır.

Shannon Entropisi

Alfabet A'dan semboller üreten bir kaynağın {p₁, p₂, ..., pₙ} olasılıkları ile:

H = −Σ pᵢ log₂(pᵢ) (semboller için bit)

En yüksek entropi: eşit olasılık dağılımı (tüm semboller eşit olasıktır). H_max = log₂(n) için n sembol.

Redundans R: bilgi taşımayan bitlerin oranını (içeriği kaybetmeden kaldırılabilir):

R = 1 − H / H_max

Eğer R = 0.4 (40% redündan): 40'lık bitlerin çoğu, bağlamdan tahmin edilebilir. İngilizce metin taşıyan bir kanal 8 bit/karakter kullanarak sadece %60'lık bir kapasiteyi bilgi için kullanmaktadır; %40'lık kısmı, alıcı zaten biliyor ve yapıdır.

Hata algılama, redündans kullanır: eğer 40'lık bitlerin çoğu bağlamdan tahmin edilebilir, bir iletim hatası, redüans yapısalı bir dizi üretir - hata düzeltme kodları olmadan bile algılanabilir.

APL'in neredeyse sıfır redündansı: bir karakter değişikliğin, bağlamdan sadece neredeyse hiç algılanamayabilir. İngilizce'nin %60'lık redüansı: bir harf eksik veya yanlış olsa bile, genellikle kelimeyi çevre bağlamından yeniden oluşturabilirsiniz.

Redundans Hesaplama

İngilizce harf sıklığı (tahmini): 'e' ~12.7 kez görülür; 'z' ~0.07 kez görülür. İngilizce'nin gerçek entropisi yaklaşık olarak H ≈ 1.0 bit/karakterdir (kelime düzeyinde bağlam dikkate alındığında). 26 harfli alfabet için maksimum entropi: H_max = log₂(26) ≈ 4.70 bit/karakter.

İngilizce için H = 1.0 bit/char ve H_max = log₂(26) kullanarak R = 1 − H/H_max redundansunu hesaplayın. Ardından, H = 3.5 bit/char olan ve aynı 26 sembol alfabesiyle olan bir dil için R'yi hesaplayın. Hangi dilde daha fazla hata algılama kapasitesi vardır ve ne kadar faktörle?

Büyüme eğrileri geometri

Derleyici algoritmaları, n (semboller, satırlar veya düğüm) boyutundaki programları işler. Algoritma seçimi, derleme süresinin program boyutuyla nasıl ölçeklendirildiğini belirler.

Sıklıkla Karşılaşılan Karmaşıklık Sınıfları

| Sınıf | Çalışma Süresi | Örnek | |---|---|---| | O(n) | lineer | sözdizim taraması | | O(n log n) | quasi-lineer | optimal sıralama | | O(n²) | kare | basit kopyalama algılama | | O(n³) | kübik | matris çarpımı, CYK analiz | | O(2ⁿ) | eksponansiyel | basit teorem kanıtı |

Geometrik resim: çalışma süresini n'ye karşı çizin. O(n) bir çizgi. O(n²) bir elips. O(2ⁿ) eksponansiyel bir eğri ve n=0 yakınlarında düz ve n=50 yakınlarında neredeyse dikey görünür.

Genel konteksiz dil kuralı taraması (CYK algoritması) O(n³) sürer. Pratik programlama dilleri için, dil genellikle LR(1) -parseable olarak tasarlanır, bu da O(n) tarama sağlar. ALGOL'un dilbilgisi, FORTRAN'ın dilbilgisinden daha karmaşık olup, daha yavaş derleyicilere katkıda bulunmuş, bu da 1958'de derleme süresinin saatler alması açısından uygulamada bir direnç yaratmıştır.

Kesişme Noktaları

Naif bir sembol tabanı araması, n tanımlayıcıdan oluşan bir program için O(n²) toplam işlem kullanır (her bir n arama için lineer tarama). Bir hash tablosu kullanarak sembol tabanı, O(n) beklenen toplam işlem kullanır.

Ön varsayım: O(n²) algoritma, 1958 donanımında 10⁶ işlem/saniye hıza sahip. O(n) algoritma aynı hızda çalışır ama 100n kurulum işlemi gerektirir (hash tabanı oluşturma).

Bir programın n = 1000 belirteci için: her iki algoritma için toplam zamanı (saniyede) hesaplayın. İki algoritma eşit zaman alırken n değerinin ne olduğu gösterilerek algebrasal hesaplar.