Analyzátorový kombinátor - Parser combinator
v programování, a analyzátor analyzátoru je funkce vyššího řádu , který přijímá několik analyzátorů jako vstup a vrací nový analyzátor jako svůj výstup. V této souvislosti a analyzátor je funkce přijímající řetězce jako vstup a vrací nějakou strukturu jako výstup, obvykle a analyzovat strom nebo sada indexů představujících umístění v řetězci, kde se analýza úspěšně zastavila. Kombinátor analyzátorů umožňuje a analýza rekurzivního sestupu strategie, která usnadňuje modulární konstrukci a testování po částech. Tato technika analýzy se nazývá kombinační analýza.
Analyzátory vytvořené pomocí kombinátorů jsou snadno sestavitelné, čitelné, modulární, dobře strukturované a snadno udržovatelné[podle koho? ]. Byly široce používány v prototypování překladačů a procesorů pro jazyky specifické pro doménu jako rozhraní v přirozeném jazyce do databází, kde jsou složité a rozmanité sémantické akce úzce integrovány se syntaktickým zpracováním. V roce 1989 demonstrovali Richard Frost a John Launchbury[1] použití syntaktických analyzátorů pro konstrukci přirozený jazyk tlumočníci. Graham Hutton také použil funkce vyššího řádu pro základní analýzu v roce 1992.[2] S.D. Swierstra také vystavoval praktické aspekty syntaktických analyzátorů v roce 2001.[3] V roce 2008 Frost, Hafiz a Callaghan[4] popsal v roce sadu analyzátorů syntaktického analyzátoru Haskell které řeší dlouhodobý problém s ubytováním rekurze doleva a pracovat jako celek parsování shora dolů nástroj v polynomiálním čase a prostoru.
Základní myšlenka
V jakémkoli programovacím jazyce, který má prvotřídní funkce, kombinátor syntaktických analyzátorů lze použít ke kombinaci základních syntaktických analyzátorů ke konstrukci syntaktických analyzátorů pro složitější pravidla. Například a výrobní pravidlo a bezkontextová gramatika (CFG) může mít jednu nebo více alternativ a každá alternativa může sestávat ze sekvence neterminálů a / nebo terminálů, nebo alternativa může sestávat z jednoho neterminálu nebo terminálu nebo prázdného řetězce. Pokud je pro každou z těchto alternativ k dispozici jednoduchý syntaktický analyzátor, lze ke kombinování každého z těchto syntaktických analyzátorů použít kombinátor syntaktických analyzátorů a vrátit nový syntaktický analyzátor, který dokáže rozpoznat kteroukoli nebo všechny alternativy.
V jazycích, které podporují přetížení operátora, kombinátor syntaktických analyzátorů může mít formu infix operátor, který se používá k lepení různých analyzátorů k vytvoření úplného pravidla. Kombinátor analyzátorů tak umožňuje definovat analyzátory ve vloženém stylu v kódu, který je strukturou podobný pravidlům formální gramatiky. Jako takové lze implementace považovat za spustitelné specifikace se všemi přidruženými výhodami. (Pozoruhodně: čitelnost)
Kombinátory
Aby byla diskuse relativně přímočará, pojednáváme o kombinátorech syntaktických analyzátorů, pokud jde o rozpoznávače pouze. Pokud je vstupní řetězec délky #vstup
a jeho členové jsou přístupní prostřednictvím indexu j
, rozpoznávač je analyzátor, který jako výstup vrací sadu indexů představujících pozice, na kterých analyzátor úspěšně dokončil rozpoznávání sekvence tokenů, které začaly na pozici j
. Prázdná sada výsledků označuje, že rozpoznávač nedokázal rozpoznat jakoukoli sekvenci začínající indexem j
. Neprázdná sada výsledků naznačuje, že rozpoznávač úspěšně končí na různých pozicích.
- The
prázdný
rozpoznávač rozpozná prázdný řetězec. Tento analyzátor vždy uspěje a vrátí singletonovou sadu obsahující aktuální pozici:
- Rozpoznávač
období X
rozpozná terminálX
. Pokud je token na pozicij
ve vstupním řetězci jeX
, tento parser vrací sadu singleton obsahujícíj + 1
; v opačném případě vrátí prázdnou sadu.
Všimněte si, že může existovat několik odlišných způsobů, jak analyzovat řetězec při dokončování stejného indexu: označuje to nejednoznačná gramatika. Jednoduché rozpoznávače tyto nejasnosti neuznávají; každý možný cílový index je v sadě výsledků uveden pouze jednou. Pro úplnější sadu výsledků bude použit složitější objekt, například a analyzovat strom musí být vráceno.
V návaznosti na definice dvou základních rozpoznávačů p
a q
, můžeme definovat dva hlavní kombinátory syntaktických analyzátorů pro alternativní a sekvenční zpracování:
- „Alternativní“ kombinátor analyzátoru, ⊕, použije oba rozpoznávače na stejnou vstupní pozici
j
a shrnuje výsledky vrácené oběma rozpoznávači, které se nakonec vrátí jako konečný výsledek. Používá se jako operátor infix mezip
aq
jak následuje:
- Sekvenování rozpoznávačů se provádí kombinátorem analyzátoru ⊛. Stejně jako ⊕ se používá jako operátor infix mezi
p
aq
. Ale použije první rozpoznávačp
do vstupní polohyj
, a pokud existuje nějaký úspěšný výsledek této aplikace, pak druhý rozpoznávačq
se aplikuje na každý prvek sady výsledků vrácený prvním rozpoznávačem. ⊛ nakonec vrátí spojení těchto aplikací q.
Příklady
Zvažte velmi nejednoznačný bezkontextová gramatika, s :: = „x“ s | ε
. Pomocí dříve definovaných kombinátorů můžeme modulárně definovat spustitelné notace této gramatiky v moderním funkčním jazyce (např. Haskell ) tak jako s = výraz „x“ <*> s <*> s <+> prázdný
. Když rozpoznávač s
se aplikuje na vstupní sekvenci xxxxx
v poloze 1
, podle výše uvedených definic vrátí sadu výsledků {5,4,3,2}
.
Nedostatky a řešení
Analyzátorové kombinátory, jako všechny analyzátory rekurzivního sestupu, nejsou omezeny na bezkontextové gramatiky a tím pádem neprovádějte žádné globální hledání nejasností v LL (k) analýza za prvék a následujtek sady. Nejednoznačnosti tedy nejsou známy až za běhu, pokud a dokud je nespustí vstup. V takových případech může analyzátor rekurzivního sestupu výchozí (možná neznámý návrháři gramatiky) jednu z možných dvojznačných cest, což má za následek sémantický zmatek (aliasing) při používání jazyka. To vede k chybám uživatelů nejednoznačných programovacích jazyků, které nejsou hlášeny v době kompilace a které nejsou zavedeny lidskou chybou, ale nejednoznačnou gramatikou. Jediným řešením, které tyto chyby eliminuje, je odstranění nejasností a použití bezkontextové gramatiky.
Jednoduché implementace analyzátorů syntaktických analyzátorů mají některé nedostatky, které jsou běžné při analýze shora dolů. Naivní kombinační analýza vyžaduje exponenciální čas a prostor při analýze nejednoznačné bezkontextové gramatiky. V roce 1996 Frost a Szydlowski ukázali, jak na to memorování lze použít s kombinátory syntaktických analyzátorů ke snížení časové složitosti na polynomiální.[5] Později použil Frost monády konstruovat kombinátory pro systematické a správné navádění memo tabulky během celého výpočtu.[6]
Jako každý shora dolů analýza rekurzivního sestupu, běžné kombinátory syntaktického analyzátoru (jako výše popsané kombinátory) se během zpracování a levo rekurzivní gramatika (např. s :: = s <*> výraz „x“ | prázdný
). Algoritmus rozpoznávání, který pojímá nejednoznačné gramatiky s přímými pravidly leva rekurzivní, popsali Frost a Hafiz v roce 2006.[7] Algoritmus omezuje jinak stále rostoucí levou rekurzivní analýzu zavedením omezení hloubky. Tento algoritmus byl rozšířen na kompletní algoritmus syntaktické analýzy, který umožňuje nepřímou i přímou levou rekurzi polynomiální čas a generovat kompaktní reprezentace potenciálně exponenciálního počtu parsovacích stromů velikosti polynomu pro vysoce nejednoznačné gramatiky Frosta, Hafize a Callaghana v roce 2007.[8] Tento rozšířený algoritmus umožňuje nepřímou levou rekurzi porovnáním jeho „vypočítaného kontextu“ s „aktuálním kontextem“. Stejní autoři také popsali svou implementaci sady kombinátorů syntaktických analyzátorů napsaných v programovacím jazyce Haskell na základě stejného algoritmu.[4][9]
Poznámky
- ^ Frost & Launchbury 1989.
- ^ Hutton 1992.
- ^ Swierstra 2001.
- ^ A b Frost, Hafiz a Callaghan 2008.
- ^ Frost & Szydlowski 1996.
- ^ Frost 2003.
- ^ Frost & Hafiz 2006.
- ^ Frost, Hafiz a Callaghan 2007.
- ^ srov. X-SAIGA - eXecutable specifickýAtiz GrAmmars
Reference
- Burge, William H. (1975). Techniky rekurzivního programování. Programovací řada systémů. Addison-Wesley. ISBN 978-0201144505.
- Frost, Richard; Launchbury, John (1989). „Konstrukce tlumočníků přirozeného jazyka v líném funkčním jazyce“ (PDF). Počítačový deník. Zvláštní vydání o Lazy Functional Programming. 32 (2): 108–121. doi:10.1093 / comjnl / 32.2.108. Archivovány od originálu dne 06.06.2013.CS1 maint: ref = harv (odkaz) CS1 maint: BOT: status original-url neznámý (odkaz)
- Frost, Richard A .; Szydlowski, Barbara (1996). „Memoizing Purely Functional Top-Down Backtracking Language Processors“ (PDF). Sci. Comput. Program. 27 (3): 263–288. doi:10.1016/0167-6423(96)00014-7.CS1 maint: ref = harv (odkaz)
- Frost, Richard A. (2003). Monadické memorování k redukci vyhledávání chránící správnost (PDF). Sborník 16. konference kanadské společnosti pro výpočetní studia inteligence o pokroku v umělé inteligenci (AI'03). str. 66–80. ISBN 978-3-540-40300-5.CS1 maint: ref = harv (odkaz)
- Frost, Richard A .; Hafiz, Rahmatullah (2006). „Nový algoritmus syntézy shora dolů k přizpůsobení nejednoznačnosti a rekurzi doleva v polynomiálním čase“ (PDF). Oznámení ACM SIGPLAN. 41 (5): 46–54. doi:10.1145/1149982.1149988.CS1 maint: ref = harv (odkaz)
- Frost, Richard A .; Hafiz, Rahmatullah; Callaghan, Paul (2007). „Modulární a efektivní syntéza shora dolů pro nejednoznačné levo rekurzivní gramatiky“. Sborník z 10. mezinárodního semináře o technologiích analýzy (IWPT), ACL-SIGPARSE: 109–120. CiteSeerX 10.1.1.97.8915.CS1 maint: ref = harv (odkaz)
- Frost, Richard A .; Hafiz, Rahmatullah; Callaghan, Paul (2008). Parserové kombinátory pro nejednoznačné levo rekurzivní gramatiky. Sborník z 10. mezinárodního sympozia o praktických aspektech deklarativních jazyků (PADL). ACM-SIGPLAN. 4902. 167–181. CiteSeerX 10.1.1.89.2132. doi:10.1007/978-3-540-77442-6_12. ISBN 978-3-540-77441-9.CS1 maint: ref = harv (odkaz)
- Hutton, Graham (1992). "Funkce vyššího řádu pro analýzu" (PDF). Journal of Functional Programming. 2 (3): 323–343. CiteSeerX 10.1.1.34.1287. doi:10.1017 / s0956796800000411.CS1 maint: ref = harv (odkaz)
- Okasaki, Chris (1998). „Dokonce i funkce vyššího řádu pro analýzu nebo Proč by někdo někdy chtěl používat funkci šestého řádu?“. Journal of Functional Programming. 8 (2): 195–199. doi:10.1017 / S0956796898003001.
- Swierstra, S. Doaitse (2001). „Kombinátorové analyzátory: Od hraček k nástrojům“ (PDF). Elektronické poznámky v teoretické informatice. 41: 38–59. doi:10.1016 / S1571-0661 (05) 80545-6.CS1 maint: ref = harv (odkaz)
- Wadler, Philip (1985). Jak nahradit selhání seznamem úspěchů - Metoda pro zpracování výjimek, zpětné sledování a porovnávání vzorů v líných funkčních jazycích. Sborník konference o funkčních programovacích jazycích a počítačové architektuře. Přednášky z informatiky. 201. str. 113–128. doi:10.1007/3-540-15975-4_33. ISBN 978-0-387-15975-1.
externí odkazy
- analyzátor-kombinátor: Společný Lisp implementace kombinátoru analyzátoru
- Parsec: Průmyslová síla, kombinovaná knihovna monadického syntaktického analyzátoru pro Haskell
- parsec: Jít verze Parsec
- FParsec: F# adaptace Parsec
- csharp-monad: C# přístav Parsec
- Jparsec: Jáva přístav Parsec
- Arcsecond: Javascript kombinovaná knihovna monadického syntaktického analyzátoru kompatibilní s fantasy zemí
- Blouznit: R implementace kombinátoru analyzátoru
- nom: Rez implementace syntaktického analyzátoru pomocí nulové kopie.
- pyparsing: Krajta implementace syntaktického analyzátoru syntaktického analyzátoru, i když si to ve své dokumentaci nenazývá.
- ts-parsec: Strojopis knihovna kombinátoru analyzátorů
- Diesel: Rychlý knihovna kombinátoru analyzátorů