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
- Visser, E. (sierpień 1997). Parsowanie uogólnione LR bez skanera . Holandia: Uniwersytet Amsterdamski. CiteSeerX 10.1.1.37.7828 .