Bağlamdan Bağımsız Diller ve Yığın Otomatları
Bağlamdan bağımsız gramerler, iç içe geçmiş, özyinelemeli yapıya sahip diller üretmektedir ve yığın otomatları, sonlu bir kontrol mekanizmasını sınırsız bir yığın ile güçlendirerek tam olarak bu dilleri tanımaktadır.
Tanım
Bağlamdan bağımsız bir dil, kuralları tek bir terminal olmayan sembolü bağlamdan bağımsız olarak yeniden yazan bir gramer tarafından üretilmektedir ve bu dil, sınırsız derinlikte son giren ilk çıkar (LIFO) bellek sağlayan bir yığın ile donatılmış sonlu bir otomat olan bir yığın otomatı tarafından tanınmaktadır.
Kapsam
Bu konu, bağlamdan bağımsız gramerleri ve türetmeleri, ayrıştırma ağaçlarını ve belirsizliği, bağlamdan bağımsız gramerlerin yığın otomatları ile eşdeğerliğini, Chomsky normal formu gibi normal formları, bağlamdan bağımsız diller için pompalama lemmasını ve bu sınıfı düzenli dillerden ayıran kapanış ve karar özelliklerini kapsamaktadır.
Temel sorular
- Ne tür iç içe geçmiş veya özyinelemeli desenler, sonlu bellek yerine bir yığın gerektirmektedir?
- Bağlamdan bağımsız gramerler ve yığın otomatları neden güç açısından eşdeğerdir?
- Bir gramer ne zaman belirsizdir ve belirsizlik ayrıştırma için neden önemlidir?
- Bağlamdan bağımsız diller için hangi karar problemleri çözülebilirdir ve hangileri değildir?
Temel kuramlar
- Gramer–otomat eşdeğerliği
- Bir dil, ancak ve ancak bir yığın otomatı tarafından kabul ediliyorsa bağlamdan bağımsızdır; bu nedenle, üretici gramer görüşü ve yığın makinesi görüşü aynı dil sınıfını tanımlamaktadır.
- Chomsky normal formu
- Her bağlamdan bağımsız gramer, her kuralın ya iki terminal olmayan sembol ya da tek bir terminal sembolü üreteceği şekilde yeniden yazılabilmektedir; bu, ayrıştırma algoritmalarının ve sınıf hakkındaki tümevarımsal kanıtların temelini oluşturan bir normal formdur.
- Bağlamdan bağımsız diller için pompalama lemmasu
- Bağlamdan bağımsız bir dildeki her yeterince uzun dizgi, iki parçasının birlikte pompalanabileceği şekilde bölünebilmektedir; bu özellik, yığın belleğinden daha fazlasını gerektiren diller için geçerli değildir ve bu dillerin bağlamdan bağımsız olmadığını kanıtlamaktadır.
Klinik önem
Bağlamdan bağımsız gramerler, hemen hemen her programlama dilinin ve birçok veri formatının sözdizimini belirtmektedir ve yığın tabanlı ayrıştırma algoritmaları, bu gramerleri derleyicilerin ve yorumlayıcıların temelini oluşturan sözdizimsel analizörlere dönüştürmektedir; bu da bu konuyu programlama dili işlemenin teorik temeli haline getirmektedir.
Tarihçe
Chomsky, bağlamdan bağımsız gramerleri 1950'lerin sonlarında kendi hiyerarşisinin bir parçası olarak tanıtmıştır ve Backus ile Naur tarafından ALGOL programlama dilinin sözdizimini tanımlamak için bağımsız olarak kullanılmışlardır. Yığın otomatları ile eşdeğerliği ve sınıfın yapısal teorisi 1960'lar boyunca geliştirilmiştir.
Öne çıkan isimler
- Noam Chomsky
- John Backus
- Seymour Ginsburg
- Sheila Greibach
İlgili konular
Temel eserler
- sipser2013
- hopcroft2006
Sıkça sorulan sorular
- Bir programlama dilini ayrıştırmak neden bir yığın gerektirmektedir?
- Programlar, parantezler, bloklar ve işlev çağrıları gibi eşleşme derinliği sınırsız olan iç içe geçmiş yapılar içermektedir. Bir yığın, her bitmemiş yapıyı kaydetmekte ve kapatıldığında onu çıkarmaktadır; bu da tam olarak bir yığın otomatının sağladığı ve sonlu bir otomatın sahip olmadığı bellek disiplinidir.
- Bir gramerin belirsiz olması ne anlama gelmektedir?
- Bir gramer, bazı dizgilerin birden fazla ayrıştırma ağacına sahip olması durumunda belirsizdir; bu da dizginin gerçekten farklı yapılarla türetilebileceği anlamına gelmektedir. Belirsizlik, kodun anlamını belirsiz bıraktığı için programlama dilleri için istenmeyen bir durumdur; bu nedenle dil tasarımcıları belirsiz olmayan gramerler aramaktadır veya belirsizliği giderme kuralları eklemektedir.