Analýza bez skeneru - Scannerless parsing

v počítačová věda, analýza bez skeneru (také zvaný lexerless parsování) provádí tokenizaci (rozdělení proudu znaků na slova) a analýzu (uspořádání slov do frází) v jednom kroku, místo aby ji rozdělil na potrubí a lexer následuje a analyzátor vykonávající současně. A jazyková gramatika je bez skeneru, pokud k vyjádření obou používá jediný formalismus lexikální (úroveň slov) a struktura jazyka na úrovni fráze.

Dělení zpracování na lexer následovaný analyzátorem je více modulární; syntaktická analýza bez skenování se primárně používá, když je jasný rozdíl lexer – parser nepotřebný nebo nechtěný. Mezi příklady, kdy je to vhodné, patří TeX, většina wiki gramatiky, makefiles, jednoduché pro konkrétní aplikaci skriptovací jazyky, a Raku.

Výhody

  • Pouze jeden metajazyk je potřeba
  • Nepravidelná lexikální struktura je snadno ovladatelný
  • „Klasifikace tokenů“ není nutná což odstraňuje potřebu designových ubytování, jako je „lexer hack "a jazyk vyhrazená slova (například „while“ v C )
  • Gramatiky mohou být kompoziční (lze sloučit bez lidského zásahu) [1]

Nevýhody

  • Jelikož jsou lexikální skenování a syntaktická analýza kombinovány, výsledný analyzátor má tendenci být komplikovanější a tudíž těžší pochopit a ladit. Totéž platí pro přidruženou gramatiku, pokud se ke generování analyzátoru použije gramatika.
  • Výsledný analyzátor má tendenci být významně méně efektivní než kanál lexer-parser s ohledem na oba čas a Paměť.[1]

Implementace

  • SGLR je analyzátor modulárního formalismu definice syntaxe SDF, a je součástí ASF + SDF Meta-prostředí a Stratego / XT systém transformace programu.
  • JSGLR, čistá implementace SGLR v Javě, také založená na SDF.
  • TXL podporuje analýzu na úrovni znaků.
  • dparser generuje kód ANSI C pro bezskener Analyzátory GLR.
  • Duch umožňuje analýzu bez skenování i skenování.
  • SBP je analyzátor bez skeneru pro booleovské gramatiky (nadmnožina bezkontextových gramatik) napsaná v Javě.
  • Laja je dvoufázový generátor syntaktických analyzátorů bez podpory skenerů s podporou mapování pravidel gramatiky na objekty napsané v Javě.
  • The Raku gramatiky funkce univerzálního programovacího jazyka Raku.
  • PyParsing je analyzátor bez skenování napsaný v čistém Pythonu.
  • META II Má zabudované funkce analyzátorů tokenů.
  • TREE-META Stejně jako META II je také bez skeneru s vestavěnými funkcemi lexeru.
  • CWIC Kompilátor pro psaní a implementaci překladačů. Má pravidla tokenu jako součást svého jazyka. Pravidla v CWIC byla kompilována do booleovských funkcí vracejících úspěch nebo neúspěch.

Poznámky

  • ^ Důvodem je, že při analýze na úrovni znaků je jazyk rozpoznávaný analyzátorem jediný bezkontextový jazyk definované na znacích, na rozdíl od bezkontextového jazyka sekvencí řetězců v běžné jazyky. Některé analyzátory bez lexerů zpracovávají celou třídu bezkontextových jazyků, která je uzavřena ve složení.

Další čtení

  • Visser, E. (srpen 1997). Analýza generalizovaného LR bez skenování. Nizozemsko: University of Amsterdam. CiteSeerX  10.1.1.37.7828.
  1. ^ Economopoulos, Giorgios; Klint, Paul; Vinju, Jurgen (2009). „Rychlejší analýza GLR bez skenování“ (PDF). Konstrukce kompilátoru. 5501: 126–141. doi:10.1007/978-3-642-00722-4_10.