Yinelemeli yükselme ayrıştırıcı - Recursive ascent parser - Wikipedia

İçinde bilgisayar Bilimi, yinelemeli yükselen ayrıştırma uygulamak için bir tekniktir LALR ayrıştırıcı tablolar yerine karşılıklı özyinelemeli işlevler kullanır. Böylelikle ayrıştırıcı doğrudan kodlanmış ana dilde benzer yinelemeli iniş. Doğrudan kodlama genellikle tablo tabanlı eşdeğerinden daha hızlı bir ayrıştırıcı verir[1] Aynı nedenle, derlemenin yorumlamadan daha hızlı olması. Aynı zamanda (nominal olarak) özyinelemeli bir yükselme ayrıştırıcısını elle düzenlemek mümkündür, oysa bir tablo uygulaması ortalama insan için hemen hemen okunamaz.

Yinelemeli yükseliş ilk olarak Thomas Penello tarafından makalesinde anlatılmıştır. "Çok hızlı LR ayrıştırma". 1986'da. Bir LR ayrıştırıcısının elle düzenlenebilir bir uygulamasını oluşturmak istemiyordu, bunun yerine, montaj dili. Teknik daha sonra G.H. Roberts[2] 1988'de ve Leermakers, Augusteijn, Kruseman Aretz'in bir makalesinde[3] 1992'de dergide Teorik Bilgisayar Bilimleri. Tekniğin son derece okunabilir bir açıklaması Morell ve Middleton tarafından yazılmıştır.[4] Sperber ve Thiemann tarafından yazılan TOPLAS makalesinde de iyi bir açıklama bulunabilir.[5]

Yinelemeli yükseliş de yinelemeli iniş ile birleştirildi ve olarak bilinen bir teknik ortaya çıktı. yinelemeli yükseliş / iniş. Durumların azalması ve bu durumlardan bazılarının aşağıdan yukarıya değil, sezgisel olarak yukarıdan aşağıya olması nedeniyle, bu uygulama tekniğinin elle düzenlenmesi tartışmasız daha kolaydır. Ayrıca geleneksel yinelemeli yükselmeye göre bazı minimum performans iyileştirmeleri sağlayabilir.[6]

Özet

Sezgisel olarak, yinelemeli yükseliş, gerçek bir uygulamasıdır. LR ayrıştırma kavram. Ayrıştırıcıdaki her işlev tek bir LR'yi temsil eder otomat durum. Her işlev içinde, giriş yığınından atılan geçerli belirteç temelinde uygun eylemi seçmek için çok dallı bir ifade kullanılır. Belirteç tanımlandıktan sonra, kodlanmakta olan duruma göre işlem yapılır. Söz konusu jetona bağlı olarak alınabilecek iki farklı temel işlem vardır:

  • Vardiya - Yeni bir otomatik duruma etkin bir şekilde atlayarak bir işlev çağrısı olarak kodlandı.
  • Azalt - Şuna göre farklı kodlanmış anlamsal eylem rutini ilgili için üretim. Bu rutinin sonucu bir ADT arayan kişiye iade edilir. Azaltma eylemi, kaydırılan token sayısını da kaydetmelidir önceki azaltmak için, bu değeri azaltma değeri ile birlikte arayana geri iletmek. Bu vardiya sayacı, azaltmanın çağrı yığınının hangi noktasında işlenmesi gerektiğini belirler.

Ayrıca, belirli bir durumda, ancak yalnızca kaydırma sayacının sıfıra düştüğü (mevcut durumun sonucu ele alması gerektiğini gösteren) bir azaltmadan sonra gerçekleştirilebilen üçüncü bir LR otomat eylemi vardır. Bu git esasen özel bir durum olan eylem vardiya bir üretimde terminal olmayanları işlemek için tasarlanmıştır. Bu eylem ele alınmalıdır sonra çok dallı deyim, çünkü burası herhangi bir azaltma sonucunun çağrı yığınının daha altından "yeniden ortaya çıkacağı" yerdir.

Misal

Aşağıdaki dilbilgisini düşünün bizon sözdizimi:

ifade: ifade '+' terim {$$ = 1 $ + 3 $; } | ifade '-' terim {$$ = 1 $ - 3 $; } | terim {$$ = 1 $; }; terim: '[' ifade ')' {$$ = $ 2; } | num {$$ = $ 1; }; num: '0' {$$ = 0; } | '1' {$$ = 1; };

Bu gramer LR (0) sol yinelemeli olmasıyla ( ifade terminal olmayan) ancak herhangi bir ilerleme gerektirmez. Özyinelemeli yükselme, aynı zamanda, LALR (1) olan gramerleri, tabloya dayalı ayrıştırıcıların bu tür durumları ele aldığı şekilde (olası önden başa göre çatışma çözümlerini önceden hesaplayarak) idare edebilir.

Aşağıdaki bir Scala yukarıdaki dilbilgisine dayalı olarak yinelemeli bir çıkış ayrıştırıcısının uygulanması:

nesne ExprParser {  özel tip Sonuç = (NonTerminal, Int)    özel Mühürlü kişisel özellik NonTerminal {    val v: Int  }    özel durum sınıf NTexpr(v: Int, içinde: Akış[Char]) genişler NonTerminal  özel durum sınıf NTterm(v: Int, içinde: Akış[Char]) genişler NonTerminal  özel durum sınıf NTnum(v: Int, içinde: Akış[Char]) genişler NonTerminal    sınıf ParseException(msg: Dize) genişler Çalışma zamanı istisnası(msg) {    def bu() = bu("")        def bu(c: Char) = bu(c.toString)  }    def ayrıştırmak(içinde: Akış[Char]) = durum0(içinde)._1.v    /*   * 0 $ kabul et:. expr $ end   *   * '[' shift ve 1. duruma git   * '0' kayması ve 2. duruma git   * '1' vardiya ve 3. duruma git   *   * ifade 4 durumuna git   * terim 5 durumuna git   * num 6 durumuna git   */  özel def durum0(içinde: Akış[Char]) = içinde eşleşme {    durum cur #:: kuyruk => {      def döngü(demet: Sonuç): Sonuç = {        val (res, git) = demet                Eğer (git == 0) {          döngü(res eşleşme {            durum NTexpr(v, içinde) => durum4(içinde, v)            durum NTterm(v, içinde) => durum5(içinde, v)            durum NTnum(v, içinde) => durum6(içinde, v)          })        } Başka (res, git - 1)      }            döngü(cur eşleşme {        durum '(' => durum1(kuyruk)        durum '0' => durum2(kuyruk)        durum '1' => durum3(kuyruk)        durum c => atmak yeni ParseException(c)      })    }        durum Akış() => atmak yeni ParseException  }    /*   * 4 terim: '['. İfade ')'   *   * '[' shift ve 1. duruma git   * '0' kayması ve 2. duruma git   * '1' vardiya ve 3. duruma git   *   * ifade 7 durumuna git   * terim 5 durumuna git   * num 6 durumuna git   */  özel def durum1(içinde: Akış[Char]): Sonuç = içinde eşleşme {    durum cur #:: kuyruk => {      def döngü(demet: Sonuç): Sonuç = {        val (res, git) = demet                Eğer (git == 0) {          döngü(res eşleşme {            durum NTexpr(v, içinde) => durum7(içinde, v)            durum NTterm(v, içinde) => durum5(içinde, v)            durum NTnum(v, içinde) => durum6(içinde, v)          })        } Başka (res, git - 1)      }            döngü(cur eşleşme {        durum '(' => durum1(kuyruk)        durum '0' => durum2(kuyruk)        durum '1' => durum3(kuyruk)        durum c => atmak yeni ParseException(c)      })    }        durum Akış() => atmak yeni ParseException  }    /*   * 6 num: '0'.   *   * $ varsayılan, kural 6 (num) kullanılarak azalt   */  özel def durum2(içinde: Akış[Char]) = (NTnum(0, içinde), 0)    /*   * 7 num: '1'.   *   * $ varsayılan, kural 7 (num) kullanarak azaltma   */  özel def durum3(içinde: Akış[Char]) = (NTnum(1, içinde), 0)    /*   * 0 $ kabul et: ifade. $ end   * 1 ifade: ifade. '+' terimi   * 2 | ifade '-' terim   *   * $ end vardiya ve 8 durumuna git   * '+' shift ve 9 durumuna git   * '-' shift ve 10 durumuna git   */  özel def durum4(içinde: Akış[Char], arg1: Int): Sonuç = içinde eşleşme {    durum cur #:: kuyruk => {      azalma(cur eşleşme {        durum '+' => durum9(kuyruk, arg1)        durum '-' => durum10(kuyruk, arg1)        durum c => atmak yeni ParseException(c)      })    }        durum Akış() => durum8(arg1)  }    /*   * 3 ifade: terim.   *   * $ varsayılan azaltma kuralı 3 (ifade)   */  özel def durum5(içinde: Akış[Char], arg1: Int) = (NTexpr(arg1, içinde), 0)    /*   * 5 dönem: num.   *   * 5 numaralı kuralı (terim) kullanarak $ varsayılan indirim   */  özel def durum6(içinde: Akış[Char], arg1: Int) = (NTterm(arg1, içinde), 0)    /*   * 1 ifade: ifade. '+' terimi   * 2 | ifade '-' terim   * 4 terim: '[' ifade ')'   *   * '+' shift ve 9 durumuna git   * '-' shift ve 10 durumuna git   * ')' kaydırın ve 11 durumuna gidin   */  özel def durum7(içinde: Akış[Char], arg1: Int): Sonuç = içinde eşleşme {    durum cur #:: kuyruk => {      azalma(cur eşleşme {        durum '+' => durum9(kuyruk, arg1)        durum '-' => durum10(kuyruk, arg1)        durum ')' => durum11(kuyruk, arg1)        durum c => atmak yeni ParseException(c)      })    }        durum Akış() => atmak yeni ParseException  }    /*   * 0 $ kabul et: ifade $ end.   *   * $ varsayılan kabul   */  özel def durum8(arg1: Int) = (NTexpr(arg1, Akış()), 1)    /*   * 1 ifade: ifade '+'. dönem   *   * '[' shift ve 1. duruma git   * '0' kayması ve 2. duruma git   * '1' vardiya ve 3. duruma git   *   * terim 12 eyalete git   * num 6 durumuna git   */  özel def durum9(içinde: Akış[Char], arg1: Int) = içinde eşleşme {    durum cur #:: kuyruk => {      def döngü(demet: Sonuç): Sonuç = {        val (res, git) = demet                Eğer (git == 0) {          döngü(res eşleşme {            durum NTterm(v, içinde) => durum12(içinde, arg1, v)            durum NTnum(v, içinde) => durum6(içinde, v)            durum _ => atmak yeni Onaylama Hatası          })        } Başka (res, git - 1)      }            döngü(cur eşleşme {        durum '(' => durum1(kuyruk)        durum '0' => durum2(kuyruk)        durum '1' => durum3(kuyruk)        durum c => atmak yeni ParseException(c)      })    }        durum Akış() => atmak yeni ParseException  }    /*   * 2 ifade: ifade '-'. dönem   *   * '[' shift ve 1. duruma git   * '0' kayması ve 2. duruma git   * '1' vardiya ve 3. duruma git   *   * terim 13 eyalete git   * num 6 durumuna git   */  özel def durum10(içinde: Akış[Char], arg1: Int) = içinde eşleşme {    durum cur #:: kuyruk => {      def döngü(demet: Sonuç): Sonuç = {        val (res, git) = demet                Eğer (git == 0) {          döngü(res eşleşme {            durum NTterm(v, içinde) => durum13(içinde, arg1, v)            durum NTnum(v, içinde) => durum6(içinde, v)            durum _ => atmak yeni Onaylama Hatası          })        } Başka (res, git - 1)      }            döngü(cur eşleşme {        durum '(' => durum1(kuyruk)        durum '0' => durum2(kuyruk)        durum '1' => durum3(kuyruk)        durum c => atmak yeni ParseException(c)      })    }        durum Akış() => atmak yeni ParseException  }    /*   * 4 terim: '[' ifade ')'.   *   * 4 kuralı (terim) kullanarak $ varsayılan indirim   */  özel def durum11(içinde: Akış[Char], arg1: Int) = (NTterm(arg1, içinde), 2)    /*   * 1 ifade: ifade '+' terimi.   *   * 1. kural (ifade) kullanarak $ varsayılan azaltma   */  özel def durum12(içinde: Akış[Char], arg1: Int, arg2: Int) = (NTexpr(arg1 + arg2, içinde), 2)    /*   * 2 ifade: ifade '-' terimi.   *   * $ varsayılan azaltma kuralı 2 (ifade) kullanılarak   */  özel def durum13(içinde: Akış[Char], arg1: Int, arg2: Int) = (NTexpr(arg1 - arg2, içinde), 2)    özel def azalma(demet: Sonuç) = {    val (res, git) = demet    iddia etmek(git != 0)    (res, git - 1)  }}

Ayrıca bakınız

Referanslar

  1. ^ Thomas J Penello (1986). "Çok hızlı LR ayrıştırma".
  2. ^ G.H. Roberts (1988). "Özyinelemeli yükselme: özyinelemeli inişe bir LR analoğu".
  3. ^ Leermakers, Augusteijn, Kruseman Aretz (1992). "İşlevsel bir LR ayrıştırıcı".CS1 bakimi: birden çok ad: yazarlar listesi (bağlantı)
  4. ^ Larry Morell ve David Middleton (2003). "Yinelemeli yükselen ayrıştırma". Kolejlerde Bilgisayar Bilimleri Dergisi. 18 (6). s. 186–201.
  5. ^ Sperber ve Thiemann (2000). "Kısmi değerlendirme ile LR ayrıştırıcılarının oluşturulması".
  6. ^ John Boyland ve Daniel Spiewak (2009). "ScalaBison Recursive Ascent-Descent Parser Generator" (PDF).