Analyzátor rekurzivního výstupu - Recursive ascent parser - Wikipedia

v počítačová věda, analýza rekurzivního výstupu je technika pro implementaci Analyzátor LALR který používá spíše vzájemně rekurzivní funkce než tabulky. Analyzátor tedy je přímo zakódováno v hostitelském jazyce podobném jazyku rekurzivní sestup. Přímé kódování obvykle poskytuje analyzátor, který je rychlejší než jeho ekvivalent řízený tabulkou[1] ze stejného důvodu je kompilace rychlejší než interpretace. Je také (nominálně) možné ručně upravit rekurzivní analyzátor výstupu, zatímco tabulková implementace je pro průměrného člověka téměř nečitelná.

Rekurzivní výstup poprvé popsal Thomas Penello ve svém článku „Very fast LR parsing“. v roce 1986. Neměl v úmyslu vytvořit ručně upravitelnou implementaci analyzátoru LR, ale spíše udržovatelný a efektivní analyzátor implementovaný v montážní jazyk. Techniku ​​později vysvětlil G.H. Roberts[2] v roce 1988 a také v článku Leermakers, Augusteijn, Kruseman Aretz[3] v roce 1992 v časopise Teoretická informatika. Mimořádně čitelný popis této techniky napsali Morell a Middleton[4] v roce 2003. Dobrou expozici najdete také v článku TOPLAS od Sperbera a Thiemanna.[5]

Rekurzivní výstup byl také sloučen s rekurzivním sestupem, čímž se získá technika známá jako rekurzivní výstup / sestup. Tato implementační technika je prokazatelně snazší ručně upravit kvůli snížení stavů a ​​skutečnosti, že některé z těchto stavů jsou intuitivnější shora dolů než zdola nahoru. Může také přinést některá minimální zlepšení výkonu oproti běžnému rekurzivnímu výstupu.[6]

souhrn

Intuitivně je rekurzivní výstup doslovnou implementací Analýza LR pojem. Každá funkce v analyzátoru představuje jeden LR automat Stát. V rámci každé funkce se příkaz s více větvemi používá k výběru příslušné akce na základě aktuálního tokenu vyskočeného ze vstupního zásobníku. Jakmile je token identifikován, je provedena akce na základě kódovaného stavu. Na základě příslušného tokenu lze provést dvě různé základní akce:

  • Posun - Zakódováno jako volání funkce, efektivně skočí do nového stavu automatu.
  • Snížit - Kódováno odlišně podle rutina sémantické akce pro příslušné Výroba. Výsledek této rutiny je zabalen do ADT který je vrácen volajícímu. Akce redukce musí také zaznamenat počet tokenů, které byly posunuty předchozí ke snížení, předání této hodnoty zpět volajícímu spolu s hodnotou snížení. Tento čítač posunu určuje, ve kterém bodě zásobníku volání by se mělo zpracovat snížení.

K dispozici je také třetí akce automatu LR, kterou lze provést v daném stavu, ale pouze po redukci, kde je čítač posunu snížen na nulu (což naznačuje, že výsledek by měl zpracovat aktuální stav). To je jít do akce, což je v zásadě zvláštní případ posun navrženo pro manipulaci s jinými než terminály ve výrobě. Tuto akci je třeba zvládnout po příkaz s více větvemi, protože právě zde budou všechny výsledky redukce „znovu vynořeny“ z dále dolů v zásobníku volání.

Příklad

Zvažte následující gramatiku v bizon syntax:

expr: expr '+' výraz {$$ = $ 1 + $ 3; } | expr '-' termín {$$ = $ 1 - $ 3; } | termín {$$ = $ 1; }; výraz: '(' expr ')' {$$ = $ 2; } | počet {$$ = $ 1; }; num: '0' {$$ = 0; } | '1' {$$ = 1; };

Tato gramatika je LR (0) v tom, že je levo rekurzivní (v expr bez terminálu), ale nevyžaduje žádné vyhledávání. Rekurzivní výstup je také schopen zpracovat gramatiky, které jsou LALR (1), stejným způsobem, jakým tyto případy zpracovávají analyzátory řízené tabulkou (předběžným výpočtem řešení konfliktů na základě možného vyhledávání).

Toto je a Scala implementace analyzátoru rekurzivního výstupu na základě výše uvedené gramatiky:

objekt ExprParser {  soukromé typ Výsledek = (NonTerminal, Int)    soukromé zapečetěný vlastnost NonTerminal {    val proti: Int  }    soukromé případ třída NTexpr(proti: Int, v: Proud[Char]) rozšiřuje NonTerminal  soukromé případ třída NTterm(proti: Int, v: Proud[Char]) rozšiřuje NonTerminal  soukromé případ třída NTnum(proti: Int, v: Proud[Char]) rozšiřuje NonTerminal    třída ParseException(zpráva: Tětiva) rozšiřuje RuntimeException(zpráva) {    def tento() = tento("")        def tento(C: Char) = tento(C.toString)  }    def analyzovat(v: Proud[Char]) = stav0(v)._1.proti    /*   * 0 $ přijmout:. expr $ konec   *   * '(' shift a přejděte do stavu 1   * Posun '0' a přejděte do stavu 2   * Posun '1' a přejděte do stavu 3   *   * expr přejít do stavu 4   * termín přejít do stavu 5   * počet přejít do stavu 6   */  soukromé def stav0(v: Proud[Char]) = v zápas {    případ voříšek #:: ocas => {      def smyčka(n-tice: Výsledek): Výsledek = {        val (res, jít do) = n-tice                -li (jít do == 0) {          smyčka(res zápas {            případ NTexpr(proti, v) => stát4(v, proti)            případ NTterm(proti, v) => stát5(v, proti)            případ NTnum(proti, v) => stát6(v, proti)          })        } jiný (res, jít do - 1)      }            smyčka(voříšek zápas {        případ '(' => stav1(ocas)        případ '0' => stav2(ocas)        případ '1' => stav3(ocas)        případ C => házet Nový ParseException(C)      })    }        případ Proud() => házet Nový ParseException  }    /*   * 4 výraz: '('. Expr ')'   *   * '(' shift a přejděte do stavu 1   * Posun '0' a přejděte do stavu 2   * Posun '1' a přejděte do stavu 3   *   * expr přejděte do stavu 7   * termín přejít do stavu 5   * počet přejít do stavu 6   */  soukromé def stav1(v: Proud[Char]): Výsledek = v zápas {    případ voříšek #:: ocas => {      def smyčka(n-tice: Výsledek): Výsledek = {        val (res, jít do) = n-tice                -li (jít do == 0) {          smyčka(res zápas {            případ NTexpr(proti, v) => stát7(v, proti)            případ NTterm(proti, v) => stát5(v, proti)            případ NTnum(proti, v) => stát6(v, proti)          })        } jiný (res, jít do - 1)      }            smyčka(voříšek zápas {        případ '(' => stav1(ocas)        případ '0' => stav2(ocas)        případ '1' => stav3(ocas)        případ C => házet Nový ParseException(C)      })    }        případ Proud() => házet Nový ParseException  }    /*   * 6 počet: „0“.   *   * $ default snížit pomocí pravidla 6 (počet)   */  soukromé def stav2(v: Proud[Char]) = (NTnum(0, v), 0)    /*   * 7 num: '1'.   *   * $ default snížit pomocí pravidla 7 (počet)   */  soukromé def stav3(v: Proud[Char]) = (NTnum(1, v), 0)    /*   * 0 $ přijmout: expr. $ konec   * 1 výraz: výraz '+' termín   * 2 | expr. '-' termín   *   * $ end shift a přejděte do stavu 8   * Posun '+' a přejděte do stavu 9   * '-' posun a přejděte do stavu 10   */  soukromé def stát4(v: Proud[Char], arg1: Int): Výsledek = v zápas {    případ voříšek #:: ocas => {      úbytek(voříšek zápas {        případ '+' => stát9(ocas, arg1)        případ '-' => stát10(ocas, arg1)        případ C => házet Nový ParseException(C)      })    }        případ Proud() => stát8(arg1)  }    /*   * 3 výraz: termín.   *   * $ default snížit pomocí pravidla 3 (expr)   */  soukromé def stát5(v: Proud[Char], arg1: Int) = (NTexpr(arg1, v), 0)    /*   * 5 termín: počet   *   * $ default snížit pomocí pravidla 5 (termín)   */  soukromé def stát6(v: Proud[Char], arg1: Int) = (NTterm(arg1, v), 0)    /*   * 1 výraz: výraz '+' termín   * 2 | expr. '-' termín   * 4 výraz: '(' expr. ')'   *   * Posun '+' a přejděte do stavu 9   * '-' posun a přejděte do stavu 10   * ')' a přejděte do stavu 11   */  soukromé def stát7(v: Proud[Char], arg1: Int): Výsledek = v zápas {    případ voříšek #:: ocas => {      úbytek(voříšek zápas {        případ '+' => stát9(ocas, arg1)        případ '-' => stát10(ocas, arg1)        případ ')' => stát11(ocas, arg1)        případ C => házet Nový ParseException(C)      })    }        případ Proud() => házet Nový ParseException  }    /*   * 0 $ přijmout: expr $ konec.   *   * $ default přijmout   */  soukromé def stát8(arg1: Int) = (NTexpr(arg1, Proud()), 1)    /*   * 1 expr: expr '+'. období   *   * '(' shift a přejděte do stavu 1   * Posun '0' a přejděte do stavu 2   * Posun '1' a přejděte do stavu 3   *   * termín přejít do stavu 12   * počet přejít do stavu 6   */  soukromé def stát9(v: Proud[Char], arg1: Int) = v zápas {    případ voříšek #:: ocas => {      def smyčka(n-tice: Výsledek): Výsledek = {        val (res, jít do) = n-tice                -li (jít do == 0) {          smyčka(res zápas {            případ NTterm(proti, v) => stát12(v, arg1, proti)            případ NTnum(proti, v) => stát6(v, proti)            případ _ => házet Nový AssertionError          })        } jiný (res, jít do - 1)      }            smyčka(voříšek zápas {        případ '(' => stav1(ocas)        případ '0' => stav2(ocas)        případ '1' => stav3(ocas)        případ C => házet Nový ParseException(C)      })    }        případ Proud() => házet Nový ParseException  }    /*   * 2 expr: expr '-'. období   *   * '(' shift a přejděte do stavu 1   * Posun '0' a přejděte do stavu 2   * Posun '1' a přejděte do stavu 3   *   * termín přejít do stavu 13   * počet přejít do stavu 6   */  soukromé def stát10(v: Proud[Char], arg1: Int) = v zápas {    případ voříšek #:: ocas => {      def smyčka(n-tice: Výsledek): Výsledek = {        val (res, jít do) = n-tice                -li (jít do == 0) {          smyčka(res zápas {            případ NTterm(proti, v) => stát13(v, arg1, proti)            případ NTnum(proti, v) => stát6(v, proti)            případ _ => házet Nový AssertionError          })        } jiný (res, jít do - 1)      }            smyčka(voříšek zápas {        případ '(' => stav1(ocas)        případ '0' => stav2(ocas)        případ '1' => stav3(ocas)        případ C => házet Nový ParseException(C)      })    }        případ Proud() => házet Nový ParseException  }    /*   * 4 výraz: '(' expr ')'.   *   * $ default snížit pomocí pravidla 4 (termín)   */  soukromé def stát11(v: Proud[Char], arg1: Int) = (NTterm(arg1, v), 2)    /*   * 1 výraz: výraz „+“.   *   * $ default snížit pomocí pravidla 1 (expr)   */  soukromé def stát12(v: Proud[Char], arg1: Int, arg2: Int) = (NTexpr(arg1 + arg2, v), 2)    /*   * 2 expr: expr '-' termín.   *   * $ default snížit pomocí pravidla 2 (expr)   */  soukromé def stát13(v: Proud[Char], arg1: Int, arg2: Int) = (NTexpr(arg1 - arg2, v), 2)    soukromé def úbytek(n-tice: Výsledek) = {    val (res, jít do) = n-tice    tvrdit(jít do != 0)    (res, jít do - 1)  }}

Viz také

Reference

  1. ^ Thomas J. Penello (1986). „Very fast LR parsing“.
  2. ^ G.H. Roberts (1988). "Rekurzivní výstup: analog LR k rekurzivnímu sestupu".
  3. ^ Leermakers, Augusteijn, Kruseman Aretz (1992). "Funkční analyzátor LR".CS1 maint: více jmen: seznam autorů (odkaz)
  4. ^ Larry Morell a David Middleton (2003). „Rekurzivní analýza výstupu“. Journal of Computing Sciences in Colleges. 18 (6). 186–201.
  5. ^ Sperber a Thiemann (2000). "Generování LR parserů částečným hodnocením".
  6. ^ John Boyland a Daniel Spiewak (2009). „ScalaBison rekurzivní generátor syntézy výstupu a sestupu“ (PDF).