Yukarıdan Aşağıya Ayrıştırma – Bilgisayar Bilimleri Ödevleri – Bilgisayar Bilimleri Ödev Hazırlatma – Bilgisayar Bilimleri Alanında Tez Yazdırma – Bilgisayar Bilimleri Ödev Yaptırma Fiyatları
Yukarıdan Aşağıya Ayrıştırma
Yukarıdan aşağıya ayrıştırma yöntemini ve bunun bir dizi özyinelemeli prosedür biçiminde uygulanmasını göstermek için, aritmetik ifadeler için aşağıdaki grameri kullanıyoruz.
Bu iki yorum, gösterilen iki ayrıştırma ağacı tarafından gösterilmektedir. ALGOL 60 “Gözden Geçirilmiş Rapor”da, bu belirsizlik dilbilgisi tarafından tamamen ortadan kaldırılmıştır ve örnek, sözdizimsel olarak doğru bir ifade değildir. Pascal’da doğru bir ifadedir ve Pascal raporunda İngilizce olarak (ama biçimsel olarak değil) ikinci yorumun amaçlanan yorum olduğu belirtilmiştir.
Bu bölümde belirsiz gramerlerden kaçınıyoruz. Nedeni şudur. Dilbilgisi, bir dizi diziyi tanımlamak için kullanılır ve ikinci aşamada, dizilere bir tür anlam eklenir. Örneğin, anlam, yürütüldüğünde etki olabilir.
Birinci yorumda etkisi yoktur ve ikinci yorumda st1 etkisi vardır. Genel olarak, bu nedenle, belirsiz dilbilgisinden kaçınmak iyi bir fikirdir ve bu bölümde kendimizi belirsiz olmayan dilbilgisi ile sınırlayacağız. Bir dilbilgisini girdi olarak alan ve dilbilgisinin belirsiz olup olmadığına karar veren bir programa sahip olmak güzel olurdu.
Bir sonraki bölümde, tüm sorunların bilgisayarlarla çözülemeyeceğini ve ne yazık ki belirsizlik testinin bunlardan biri olduğunu göstereceğiz. Yukarıdan aşağıya ayrıştırma veya tahmine dayalı ayrıştırma keşiflerimize basit fikirli ve son derece verimsiz bir algoritma ile başlıyoruz. Bu bir tür yukarıdan aşağıya, soldan sağa bir stratejidir.
Bunu domino oyununun terminolojisinde yapıyoruz. Süreç resimli. Konfigürasyon sırası soldan sağa doğru gösterilir. İlk konfigürasyon, gramerin ilk dizisine karşılık gelen dizenin, tahtanın tepesinde düz tabanlı parçalarla ve giriş dizisinin, tahtanın altında düz üstlü parçalarla ayarlanmasıdır.
Bundan sonra hangi domino taşının oynanacağına dair kural şudur. En soldaki eşsiz düz tabanı seçin. Giriş dizisinin bir parçası olan en soldaki eşleşmemiş düz tepedeki terminal sembolüne eşit olan bir terminal sembolü içeriyorsa, o zaman bir eşleşmemiz olur ve iki düz taraf birbirine karşı konumlanır; iki terminal sembolü farklıysa, eşleşme olmaz ve mevcut türetme başarısız olur.
Bununla birlikte, en soldaki eşleşmeyen düz taban uçsuz bucaksız bir sembol içeriyorsa, o zaman karşılık gelen tüm domino taşlarını deneriz. Tüm domino taşlarını denemek, genellikle önce birini deneyerek ve türetme başarısız olursa, ilkinin denendiği aynı konfigürasyondan başlayarak diğerini deneyerek gerçekleştirilir. İkinci eyleme geri izleme denir. Tüm düz taraflar ortadan kaldırıldığında oyunun başarıyla sona erdiği söylenir.
Bu basit strateji mutlaka verimli değildir; aslında, birkaç ilginç olmayan durum dışında tümünde son derece verimsizdir. Kullandığımız dilbilgisinde, E — E + T gibi yinelemeli üretimlere çok dikkat edilmelidir çünkü oyunun oyuncusunu bu domino taşının tekrar tekrar oynandığı ve başarılı olunmadığı hiç bitmeyen bir döngüye sokabilirler. herhangi bir düz tarafı ortadan kaldırırken.
Verimsizliğin kaynağı, terminal olmayan bir sembol için çeşitli üretim kuralları arasındaki seçimdir. “Yanlış” seçim yapılırsa, oyunun ilerleyen bölümlerinde bazı geri dönüşler olur. “Doğru” üretim kuralını seçecek bir mekanizmaya ihtiyacımız var.
LL(k) ayrıştırma (k pozitif bir tamsayıdır) durumunda tercih edilen mekanizma şu şekildedir: seçim, giriş dizesindeki en soldaki k eşleşmemiş sembole bunlara önden bakma sembolleri denir.
Bu, tek kısıtlamanın, girdinin önden bakışın ötesinde kalan kısmının dikkate alınmaması olduğu anlamına gelir. Bu stratejinin geçerli olduğu bir dilbilgisine sahip olursak, ayrıştırmanın çok daha verimli bir şekilde yapılabileceği açıktır: geri izleme gerekmez.
Hatta biraz daha ileri gidebilir ve seçimi yalnızca k önden bakma sembolüne ve en soldaki eşleşmeyen düz dipli sembole dayandırabiliriz. Buna güçlü LL(k) ayrıştırması denir. Bir seçim yapılırken çok daha az sembol dikkate alındığından, LL(k) ayrıştırmasından bile daha verimlidir. Aşağıda, bu seçimin nasıl yapıldığını tartışacağız.
Aşağıdan yukarıya ve yukarıdan aşağıya süreçler
Aşağıdan yukarıya ve yukarıdan aşağıya süreçler örnek
Aşağıdan yukarıya işleme örnek
Aşağıdan yukarıya işleme Psikoloji
Aşağıdan yukarıya bilgi İşleme
Bottom-up processing nedir
Bottom up nedir
LL(k)’deki ilk L, girişi soldan sağa okumak anlamına gelir. İkinci L, bir üretim kuralındaki soldan sağa aynı olan domino taşlarını yukarıdan aşağıya oynamayı temsil eder. Parametre k, önden okuma sembollerinin sayısı anlamına gelir. Kendimizi k = 1 durumuyla sınırlıyoruz. Bir üretim kuralının sağ tarafının sol tarafa indirgendiği ayrıştırma stratejileri de hayal edilebilir. Buna LR(k) ayrıştırması denir.
İlk olarak, bir LL(l) ayrıştırıcısında kararın tam olarak nasıl verildiğini tartışıyoruz; daha sonra panodaki konfigürasyonun geri kalanında etrafa bakmanın yardımcı olmadığını gösteriyoruz – bu güvenle göz ardı edilebilir.
Her üretim kuralına A — u, sözde bir ileri görüş kümesi L(A — u) karşılık gelir. Önden okuma seti, bir terminal sembolleri setidir; dilbilgisine bağlıdır, ancak giriş dizesine bağlı değildir. (Tanımını bir sonraki paragrafta veriyoruz.)
Örneğin A – u ve A – u’ arasında önden okuma sembolü a iken bir karar verilecekse, aEL(A- u) ise A – u seçilirken A –+ u’ seçilir eğer aEL(A-u’). L£(1) ayrıştırma stratejisi, aynı sol tarafa sahip tüm kurallar için ileriye dönük kümeler ayrık olduğunda uygulanabilir.
İleriye dönük bir setin tanımı teknik bir sorun teşkil eder. Sorun şu ki, tüm giriş sembolleri zaten itibari para dipleriyle eşleşebilse de, diğer bazı itibari para dipleri hala eşleşmemiş durumda; yani, daha fazla ileriye dönük sembol yoktur, ancak oyun henüz bitmemiştir. Bu durum, bu fiat dipler için f üretimimiz varsa ortaya çıkabilir.
Çıkış yolu, girdiyi, girdi dizisinin sonunu açıkça temsil eden bir sembolle genişletmektir. Bu amaçla ..l sembolünü kullanıyoruz. Başlangıç dizisi S’yi başlangıç dizisi S ..l ile değiştirerek gramer mar’ını artırıyoruz. ..l’nin gramerde ve girdide başka hiçbir yerde bulunmadığından emin oluruz. O zaman iki ..l’nin birleştirilmesi LL( 1) çözümleyicisinin son eylemidir ve ileriye dönük sembollerin tükenmesi sorunumuz ortadan kalkar.
İşte ileriye dönük kümeleri tanımlamaya yönelik ilk girişimimiz. Her A-u kuralı için, u terminal sembolü a ile başlıyorsa, görünüm kulaklığı L(A—+ u) {a} olarak tanımlanır; u bir terminal olmayanla başlıyorsa, örneğin B, o zaman önden bakış kümesi, B’den türetilebilen herhangi bir dizgenin ilk sembolü olarak gösterilebilen tüm terminallerin kümesidir.
Bir karmaşıklık var: boş dizgenin B’den türetilebileceğini varsayalım. Bu durumda, u’dan gelen ikinci sembol, L(A – u) önden bakış kümesine dahil edilmelidir, vb. Ne yazık ki, “ve benzeri” ile ilgili bir sorun var. u’nun tamamı boş dizgeye indirgenebiliyorsa, hangi terminal sembolleri dahil edilmelidir? Bazı türetmelerde A’yı takip edebilen tüm sembollerin kümesidir.
Aşağıdan yukarıya bilgi İşleme Aşağıdan yukarıya işleme örnek Aşağıdan yukarıya işleme Psikoloji Aşağıdan yukarıya ve yukarıdan aşağıya süreçler Aşağıdan yukarıya ve yukarıdan aşağıya süreçler örnek Bottom up nedir Bottom-up processing nedir