Ayrıştırıcı birleştirici - Parser combinator

İçinde bilgisayar Programlama, bir ayrıştırıcı birleştirici bir üst düzey işlev Bu, birkaç ayrıştırıcıyı girdi olarak kabul eder ve çıktı olarak yeni bir ayrıştırıcı döndürür. Bu bağlamda, bir ayrıştırıcı dizeleri girdi olarak kabul eden ve bazı yapıları çıktı olarak döndüren bir işlevdir, tipik olarak bir ayrıştırma ağacı veya dizedeki ayrıştırmanın başarıyla durdurulduğu konumları temsil eden bir dizi dizin. Ayrıştırıcı birleştiriciler, yinelemeli iniş ayrıştırma modüler parçalı yapım ve testi kolaylaştıran strateji. Bu ayrıştırma tekniğine birleştirici ayrıştırma.

Birleştiriciler kullanılarak oluşturulan ayrıştırıcıların yapımı kolaydır, okunabilir, modüler, iyi yapılandırılmış ve bakımı kolay[kime göre? ]. Derleyicilerin ve işlemcilerin prototiplenmesinde yaygın olarak kullanılmıştır. alana özgü diller gibi doğal dil arayüzleri karmaşık ve çeşitli anlamsal eylemlerin sözdizimsel işleme ile yakından bütünleştirildiği veritabanlarına. 1989'da Richard Frost ve John Launchbury,[1] oluşturmak için ayrıştırıcı birleştiricilerinin kullanılması Doğal lisan tercümanlar. Graham Hutton ayrıca 1992'de temel ayrıştırma için üst düzey işlevleri kullandı.[2] SD. Swierstra, 2001 yılında ayrıştırıcı birleştiricilerin pratik yönlerini de sergiledi.[3] 2008'de Frost, Hafiz ve Callaghan[4] bir dizi ayrıştırıcı birleştirici tanımladı Haskell uzun süredir devam eden uyum sorununu çözen sol özyineleme ve eksiksiz olarak çalışın yukarıdan aşağıya ayrıştırma polinom zaman ve uzayda araç.

Temel fikir

Sahip herhangi bir programlama dilinde birinci sınıf işlevler ayrıştırıcı birleştiricileri, daha karmaşık kurallar için ayrıştırıcılar oluşturmak üzere temel ayrıştırıcıları birleştirmek için kullanılabilir. Örneğin, bir üretim kuralı bir bağlamdan bağımsız gramer (CFG), bir veya daha fazla alternatife sahip olabilir ve her alternatif, terminal olmayan (lar) ve / veya terminallerden oluşan bir diziden oluşabilir veya alternatif, tek bir terminal olmayan veya terminal veya boş diziden oluşabilir. Bu alternatiflerin her biri için basit bir ayrıştırıcı varsa, bu ayrıştırıcıların her birini birleştirmek için bir ayrıştırıcı birleştirici kullanılabilir ve alternatiflerin herhangi birini veya tümünü tanıyabilen yeni bir ayrıştırıcı döndürür.

Destekleyen dillerde operatör aşırı yükleme ayrıştırıcı birleştirici, bir infix işleci, tam bir kural oluşturmak için farklı ayrıştırıcıları yapıştırmak için kullanılır. Ayrıştırıcı birleştiriciler böylelikle ayrıştırıcıların yapısal gramer kurallarına benzer bir kod içinde gömülü bir tarzda tanımlanmasını sağlar. Bu nedenle, uygulamalar, tüm ilişkili avantajlarla birlikte yürütülebilir özellikler olarak düşünülebilir. (Özellikle: okunabilirlik)

Kombinatörler

Tartışmayı nispeten basit tutmak için, ayrıştırıcı birleştiricileri şu şekilde tartışıyoruz: tanıyıcılar sadece. Giriş dizesi uzunluğundaysa #giriş ve üyelerine bir dizin aracılığıyla erişilir jbir tanıyıcı, çıktı olarak, ayrıştırıcının pozisyonda başlayan bir dizi jetonu tanımayı başarıyla tamamladığı pozisyonları temsil eden bir dizi indis döndüren bir ayrıştırıcıdır. j. Boş bir sonuç kümesi, tanıyıcının dizinde başlayan herhangi bir sıralamayı tanımadığını gösterir. j. Boş olmayan bir sonuç kümesi, tanıyıcının farklı konumlarda başarıyla bittiğini gösterir.

  • boş tanıyıcı, boş dizeyi tanır. Bu ayrıştırıcı her zaman başarılı olur ve geçerli konumu içeren bir tekil küme döndürür:
  • Tanıyıcı dönem x terminali tanır x. Jeton konumdaysa j giriş dizesinde x, bu ayrıştırıcı içeren bir tekil küme döndürür j + 1; aksi takdirde boş kümeyi döndürür.

Aynı dizinde bitirirken bir dizeyi ayrıştırmanın birden fazla farklı yolu olabileceğini unutmayın: bu, belirsiz gramer. Basit tanıyanlar bu belirsizlikleri kabul etmezler; her olası sonlandırma indeksi, sonuç kümesinde yalnızca bir kez listelenir. Daha eksiksiz bir sonuç kümesi için, daha karmaşık bir nesne gibi ayrıştırma ağacı iade edilmelidir.

İki temel tanıyıcının tanımlarını takiben p ve qalternatif ve sıralama için iki ana ayrıştırıcı birleştiricisi tanımlayabiliriz:

  • "Alternatif" ayrıştırıcı birleştirici, ⊕, her iki tanıyıcıyı aynı giriş konumunda uygular j ve her iki tanıyan tarafından döndürülen sonuçları özetler ve sonunda nihai sonuç olarak döndürülür. Aralarında infix operatörü olarak kullanılır. p ve q aşağıdaki gibi:
  • Tanıyıcıların sıralaması ⊛ ayrıştırıcı birleştirici ile yapılır. ⊕ gibi, arasında bir infix operatörü olarak kullanılır. p ve q. Ama ilk tanıyıcıyı uygular p giriş konumuna jve bu uygulamanın herhangi bir başarılı sonucu varsa, ikinci tanıyıcı q ilk tanıyıcı tarafından döndürülen sonuç kümesinin her öğesine uygulanır. ⊛ sonuçta bu q uygulamalarının birleşimini döndürür.

Örnekler

Oldukça belirsiz bir bağlamdan bağımsız gramer, s :: = 'x ’ler | ε. Daha önce tanımlanan birleştiricileri kullanarak, bu dilbilgisinin çalıştırılabilir notasyonlarını modern bir işlevsel dilde modüler olarak tanımlayabiliriz (ör. Haskell ) gibi s = "x" terimi <*> s <*> s <+> boş. Tanıyıcı s bir giriş dizisine uygulanır xxxxx pozisyonda 1yukarıdaki tanımlara göre bir sonuç kümesi döndürür {5,4,3,2}.

Eksiklikler ve çözümler

Ayrıştırıcı birleştiriciler, hepsi gibi yinelemeli iniş ayrıştırıcıları, bunlarla sınırlı değil bağlamdan bağımsız gramerler ve bu nedenle belirsizlikler için küresel arama yapmayın LL (k) ayrıştırma İlkk ve takip etk setleri. Bu nedenle belirsizlikler, girdi onları tetikleyene kadar çalışma zamanına kadar bilinmez. Bu gibi durumlarda, özyinelemeli iniş ayrıştırıcı varsayılan olarak (dilbilgisi tasarımcısı tarafından bilinmemektedir) olası belirsiz yollardan birine gidebilir ve bu da dilin kullanımında anlamsal karışıklığa (takma ad) neden olabilir. Bu, derleme sırasında rapor edilmeyen ve insan hatasıyla değil, belirsiz dilbilgisi ile ortaya çıkan belirsiz programlama dilleri kullanıcılarının hatalarına yol açar. Bu hataları ortadan kaldıran tek çözüm, belirsizlikleri ortadan kaldırmak ve bağlamdan bağımsız bir gramer kullanmaktır.

Ayrıştırıcı birleştiricilerinin basit uygulamalarının, yukarıdan aşağıya ayrıştırmada yaygın olan bazı eksiklikleri vardır. Naif birleşik ayrıştırma gerektirir üstel belirsiz bir bağlamdan bağımsız grameri ayrıştırırken zaman ve mekan. 1996 yılında, Frost ve Szydlowski nasıl olduğunu gösterdi hafızaya alma polinom için zaman karmaşıklığını azaltmak için ayrıştırıcı birleştiricilerle birlikte kullanılabilir.[5] Daha sonra Frost kullanıldı Monadlar hesaplama boyunca not tablosunun sistematik ve doğru bir şekilde işlenmesi için birleştiriciler oluşturmak.[6]

Yukarıdan aşağıya yinelemeli iniş ayrıştırma, geleneksel ayrıştırıcı birleştiriciler (yukarıda açıklanan birleştiriciler gibi) bir işlem sırasında sonlanmayacaktır. sol yinelemeli dilbilgisi (Örneğin. s :: = s <*> "x" terimi | boş). Doğrudan sol yinelemeli kurallarla belirsiz gramerleri barındıran bir tanıma algoritması Frost ve Hafiz tarafından 2006 yılında açıklanmıştır.[7] Algoritma, aksi takdirde sürekli büyüyen sol-yinelemeli ayrıştırmayı derinlik kısıtlamaları getirerek sınırlar. Bu algoritma, dolaylı ve doğrudan sol yinelemeyi barındırmak için eksiksiz bir ayrıştırma algoritmasına genişletildi. polinom zamanı ve 2007'de Frost, Hafiz ve Callaghan tarafından son derece belirsiz gramerler için potansiyel olarak üstel ayrıştırma ağacı sayısının kompakt polinom boyutlu temsillerini oluşturmak.[8] Bu genişletilmiş algoritma, "hesaplanmış bağlam" ı "mevcut bağlam" ile karşılaştırarak dolaylı sol özyinelemeyi barındırır. Aynı yazarlar, aynı algoritmaya dayalı olarak Haskell programlama dilinde yazılmış bir dizi ayrıştırıcı birleştiricinin uygulanmasını da açıkladılar.[4][9]

Notlar

  1. ^ Frost ve Launchbury 1989.
  2. ^ Hutton 1992.
  3. ^ Swierstra 2001.
  4. ^ a b Frost, Hafız ve Callaghan 2008.
  5. ^ Frost ve Szydlowski 1996.
  6. ^ Frost 2003.
  7. ^ Frost ve Hafız 2006.
  8. ^ Frost, Hafız ve Callaghan 2007.
  9. ^ cf. X-SAIGA - exyürütülebilir sözelatbenons of grammars

Referanslar

  • Burge William H. (1975). Yinelemeli Programlama Teknikleri. Sistem programlama serisi. Addison-Wesley. ISBN  978-0201144505.
  • Frost, Richard; Launchbury, John (1989). "Tembel bir işlevsel dilde doğal dil tercümanları oluşturmak" (PDF). Bilgisayar Dergisi. Lazy Functional Programming üzerine özel sürüm. 32 (2): 108–121. doi:10.1093 / comjnl / 32.2.108. 2013-06-06 tarihinde orjinalinden arşivlendi.CS1 bakimi: ref = harv (bağlantı) CS1 bakım: BOT: orijinal url durumu bilinmiyor (bağlantı)
  • Frost, Richard A .; Szydlowski, Barbara (1996). "Tamamen İşlevsel Yukarıdan Aşağıya Geri İzleme Dil İşlemcilerini Hatırlamak" (PDF). Sci. Bilgisayar. Program. 27 (3): 263–288. doi:10.1016/0167-6423(96)00014-7.CS1 bakimi: ref = harv (bağlantı)
  • Frost Richard A. (2003). Aramada Doğruluğu Korumaya Yönelik Monadik Hafızaya Alma Azaltılması (PDF). Yapay Zeka Gelişmeleri Konferansı (AI'03) 16. Kanada Hesaplamalı Zeka Çalışmaları Derneği Bildirileri. sayfa 66–80. ISBN  978-3-540-40300-5.CS1 bakimi: ref = harv (bağlantı)
  • Frost, Richard A .; Hafız, Rahmatullah (2006). "Polinom Zamanında Belirsizliği ve Sol Özyinelemeyi Yerleştirmek için Yeni Bir Yukarıdan Aşağıya Ayrıştırma Algoritması" (PDF). ACM SIGPLAN Bildirimleri. 41 (5): 46–54. doi:10.1145/1149982.1149988.CS1 bakimi: ref = harv (bağlantı)
  • Frost, Richard A .; Hafız, Rahmatullah; Callaghan Paul (2007). "Belirsiz Sol-Özyinelemeli Dilbilgileri için Modüler ve Etkili Yukarıdan Aşağıya Ayrıştırma". 10. Uluslararası Ayrıştırma Teknolojileri Çalıştayı (IWPT), ACL-SIGPARSE Bildirileri: 109–120. CiteSeerX  10.1.1.97.8915.CS1 bakimi: ref = harv (bağlantı)
  • Frost, Richard A .; Hafız, Rahmatullah; Callaghan, Paul (2008). Belirsiz Sol-Özyinelemeli Dilbilgileri için Ayrıştırıcı Birleştiriciler. 10. Uluslararası Bildirge Dillerinin Pratik Yönleri Sempozyumu Bildirileri (PADL). ACM-SİGPLAN. 4902. s. 167–181. CiteSeerX  10.1.1.89.2132. doi:10.1007/978-3-540-77442-6_12. ISBN  978-3-540-77441-9.CS1 bakimi: ref = harv (bağlantı)
  • Hutton Graham (1992). "Ayrıştırma için daha yüksek dereceli işlevler" (PDF). Fonksiyonel Programlama Dergisi. 2 (3): 323–343. CiteSeerX  10.1.1.34.1287. doi:10.1017 / s0956796800000411.CS1 bakimi: ref = harv (bağlantı)
  • Okasaki, Chris (1998). "Ayrıştırma için daha yüksek düzeyli işlevler bile veya Neden biri altıncı düzey işlevi kullanmak ister ki?". Fonksiyonel Programlama Dergisi. 8 (2): 195–199. doi:10.1017 / S0956796898003001.
  • Swierstra, S. Doaitse (2001). "Combinator ayrıştırıcıları: Oyuncaklardan aletlere" (PDF). Teorik Bilgisayar Bilimlerinde Elektronik Notlar. 41: 38–59. doi:10.1016 / S1571-0661 (05) 80545-6.CS1 bakimi: ref = harv (bağlantı)
  • Wadler, Philip (1985). Başarısızlık bir başarı listesiyle nasıl değiştirilir - Tembel işlevsel dillerde istisna işleme, geri izleme ve kalıp eşleştirme yöntemi. Fonksiyonel Programlama Dilleri ve Bilgisayar Mimarisi Konferansı Bildirileri. Bilgisayar Bilimlerinde Ders Notları. 201. s. 113–128. doi:10.1007/3-540-15975-4_33. ISBN  978-0-387-15975-1.

Dış bağlantılar