Derleyici Tasarımı - Ayrıştırma Türleri
Sözdizimi çözümleyicileri, bağlamdan bağımsız dilbilgisi aracılığıyla tanımlanan üretim kurallarını izler. Üretim kurallarının uygulanma biçimi (türetme), ayrıştırmayı iki türe ayırır: yukarıdan aşağıya ayrıştırma ve aşağıdan yukarıya ayrıştırma.
Yukarıdan aşağıya Ayrıştırma
Ayrıştırıcı, başlangıç sembolünden ayrıştırma ağacını oluşturmaya başladığında ve ardından başlangıç sembolünü girişe dönüştürmeye çalıştığında, buna yukarıdan aşağıya ayrıştırma denir.
Recursive descent parsing: Yukarıdan aşağıya ayrıştırmanın yaygın bir biçimidir. Girdiyi işlemek için özyinelemeli prosedürler kullandığı için özyinelemeli olarak adlandırılır. Özyinelemeli alçalma ayrıştırma, geri dönüşten muzdariptir.
Backtracking: Bir üretimin türetilmesi başarısız olursa, sözdizimi analizcisinin aynı üretimin farklı kurallarını kullanarak süreci yeniden başlattığı anlamına gelir. Bu teknik, doğru üretimi belirlemek için giriş dizesini birden fazla işleyebilir.
Aşağıdan Yukarıya Ayrıştırma
Adından da anlaşılacağı gibi, aşağıdan yukarıya ayrıştırma, giriş sembolleriyle başlar ve başlangıç sembolüne kadar ayrıştırma ağacını oluşturmaya çalışır.
Example:
Giriş dizesi: a + b * c
Üretim kuralları:
S → E
E → E + T
E → E * T
E → T
T → idAşağıdan yukarıya ayrıştırmaya başlayalım
a + b * cGirişi okuyun ve herhangi bir üretimin girişle eşleşip eşleşmediğini kontrol edin:
a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S