Parsowanie bez skanera - Scannerless parsing

W informatyce , analizowania scannerless (zwany także lexerless parsowanie ) Wykonuje tokeny (łamanie strumień znaków w słowach) i parsowania (układając słowa we frazy) w jednym etapie, a nie łamanie go do rurociągu z lexer następnie parser , realizując jednocześnie . Gramatyka język jest scannerless jeśli używa pojedynczego formalizmu wyrazić zarówno leksykalnych (poziom słowo) i strukturę poziomu wyrażenie języka.

Dzielenie przetwarzania na lekser, po którym następuje parser, jest bardziej modułowe; parsowanie bez skanera jest używane głównie wtedy, gdy wyraźne rozróżnienie między leksyrem a parserem jest niepotrzebne lub niepożądane. Przykłady sytuacji, w których jest to właściwe, obejmują TeX , większość gramatyk wiki , pliki makefile , proste języki skryptowe specyficzne dla aplikacji i Raku .

Zalety

  • Potrzebny jest tylko jeden metajęzyk
  • Nieregularna struktura leksykalna jest łatwa w obsłudze
  • „Klasyfikacja żetonowa” jest niepotrzebna, co eliminuje potrzebę dostosowania projektu, takiego jak „ hack lexer ” i słowa zastrzeżone w języku (takie jak „while” w C )
  • Gramatyki mogą być kompozycyjne (można je łączyć bez interwencji człowieka)

Niedogodności

  • Ponieważ skanowanie leksykalne i analiza składniowa są połączone, wynikowy analizator składni jest zwykle bardziej skomplikowany, a przez to trudniejszy do zrozumienia i debugowania . To samo dotyczy powiązanej gramatyki, jeśli do wygenerowania parsera zostanie użyta gramatyka.
  • Wynikowy parser wydaje się być znacznie mniej wydajny niż potok lekser-parser zarówno pod względem czasu, jak i pamięci .

Wdrożenia

  • SGLR to parser dla modułowego SDF Definicja Składni Formalizm i jest częścią ASF + SDF Meta-Środowisko i systemu transformacji programu Stratego / XT .
  • JSGLR , czysta implementacja SGLR w Javie, również oparta na SDF .
  • TXL obsługuje analizę na poziomie znaków.
  • dparser generuje kod ANSI C dla bezskanerowych parserów GLR .
  • Spirit umożliwia zarówno parsowanie bez skanera, jak i na podstawie skanera.
  • SBP to parser bez skanera dla gramatyk boolowskich ( nadzbiór gramatyk bezkontekstowych), napisany w Javie.
  • Laja to dwufazowy generator parserów bez skanera z obsługą mapowania reguł gramatycznych na obiekty, napisany w Javie.
  • Funkcja gramatyki Raku w języku programowania ogólnego przeznaczenia Raku .
  • PyParsing to parser bez skanera napisany w czystym Pythonie.
  • META II Posiada wbudowane funkcje parsera tokenów.
  • TREE-META Podobnie jak META II również nie zawiera skanera i ma wbudowane funkcje leksera.
  • Kompilator CWIC do pisania i implementowania kompilatorów. Zawiera zasady tokenów jako część swojego języka. Reguły w CWIC zostały skompilowane w funkcje boolowskie zwracające sukces lub porażkę.

Uwagi

  • ^ Dzieje się tak, ponieważ analizowanie na poziomie znaków sprawia, że ​​język rozpoznawany przez parser staje się pojedynczym językiem bezkontekstowym zdefiniowanym na znakach, w przeciwieństwie do bezkontekstowego języka sekwencji ciągów w językach regularnych . Niektóre parsery bezlekserowe obsługują całą klasę języków bezkontekstowych, która jest zamknięta podczas kompozycji.

Bibliografia

Dalsza lektura