Czy współczesne języki nadal używają generatorów analizatorów składni?

Szukałem na temat pakietu kompilator gcc Wikipedia tutaj , kiedy to pojawiły się:

GCC zaczęło od użycia parserów LALR wygenerowanych za pomocą Bison, ale stopniowo przestawiło się na ręcznie pisane parsery rekurencyjnego opadania; dla C ++ w 2004 r. oraz dla C i Objective-C w 2006 r. Obecnie wszystkie interfejsy używają ręcznie napisanych analizatorów składni rekurencyjnych

Tak więc przez ostatnie zdanie (i o ile ufam wikipedii) zdecydowanie mogę powiedzieć, że „C (gcc), C ++ (g ++), Objective-C, Objective-C ++, Fortran (gfortran), Java (gcj), Ada (GNAT), Go (gccgo), Pascal (gpc), ... Mercury, Modula-2, Modula-3, PL / I, D (gdc) i VHDL (ghdl) "są front-endami, których nie ma dłużej używaj generatora analizatora składni. Oznacza to, że wszyscy używają ręcznie napisanych parserów.

Moje pytanie brzmi zatem, czy ta praktyka jest wszechobecna? W szczególności szukam dokładnych odpowiedzi na „czy standardowa / oficjalna implementacja x ma ręcznie napisany parser” dla x w [Python, Swift, Ruby, Java, Scala, ML, Haskell]? (W rzeczywistości mile widziane są tutaj informacje na temat innych języków.) Jestem pewien, że mogę znaleźć to na własną rękę po wielu kopaniach. Ale jestem również pewien, że społeczność łatwo na to odpowiada. Dzięki!

— eatonphil
źródło

Punkt danych: CPython ma generator parsera LALR do parzenia domowego (pgen). Nie wiem o reszcie.

Punkt danych: Ghc (haskell) używa generatora analizatora składni LALR (szczęśliwy), podobnie jak OCaml.

— Twan van Laarhoven

Powinno to być „Wykonuj nowoczesne kompilatory o wysokiej wydajności ...” lub podobne, ponieważ językiem jest specyfikacja, a nie implementacja, podczas gdy to kompilator używa lub nie używa parsera generowanego maszynowo.

— dmckee,

@dmckee, tak, masz rację. Jednak nazewnictwo zaczyna być coraz dłuższe. Jeśli jednak jesteś bardziej kreatywny niż ja, możesz go edytować.

— eatonphil

Jeśli chodzi o ML: MLton używa generatora analizatora składni, który jest specyficzny dla ML, jestem w 90% pewien, że SML / NJ też, choć mniej go znam. Możesz chcieć lub nie brać pod uwagę tego „odręcznie”.

— Patrick Collins,

Odpowiedzi:

AFAIK, GCC używają parsowanych odręcznie parserów, w szczególności w celu poprawy diagnostyki błędów składniowych (tj. Przekazywania sensownych komunikatów o błędach składniowych).

Teoria analizy (i generujące ją generatory analizujące) polega głównie na rozpoznawaniu i analizowaniu poprawnej frazy wejściowej. Ale oczekujemy od kompilatorów, że przekazują znaczący komunikat o błędzie (i że są w stanie sensownie parsować resztę danych wejściowych po błędzie składniowym), dla niektórych niepoprawnych danych wejściowych.

Ponadto, starsze, starsze języki - jak C11 lub C ++ 11 - (które są koncepcyjnie stare, nawet jeśli ich najnowsza wersja ma zaledwie trzy lata) wcale nie są pozbawione kontekstu. Radzenie sobie z tego wrażliwości kontekstowego w gramatyk dla generatorów parsera (tj żubr lub nawet MENHIR ) jest nudno trudne.

— Basile Starynkevitch
źródło

Zgodzić się. Odzyskiwanie po błędach parsowania (gdy nie chcesz przestać parsować przy pierwszym błędzie, np. Stary Borland Pascal) i tworzenie dobrej jakości komunikatów o błędach (w tym wskazówek i sugestii dotyczących rozwiązywania problemów, takich jak ludzie chcą) są z natury kontekstem wrażliwe, heurystyczne zadania. Można to zrobić na szczycie wyjściowego generatora parsera, ale jest to slog.

— Jonathan Eunice,

Dealing with that context sensitiveness in grammars for parser generators is boringly difficult. Jest to również mniej więcej niemożliwe, ponieważ narzędzia te generują parsery kontekstowe. Prawidłowe miejsce do sprawdzenia, czy wszystkie ograniczenia kontekstowe są obecne, to po wygenerowaniu drzewa analizy, jeśli używasz takich narzędzi.

— dtech,

Generatory parsera i silniki parsera są dość ogólne. Zaletą ogólności jest to, że szybkie budowanie dokładnego parsera i jego funkcjonalność jest łatwe, w ogólnym schemacie rzeczy.

Sam silnik analizatora składni cierpi z powodu ogólnej wydajności. Każdy odręczny kod zawsze będzie znacznie szybszy niż silniki analizatora składni sterowane tabelą.

Drugim obszarem, w którym generatory / silniki parsera mają trudności, jest to, że wszystkie prawdziwe języki programowania są wrażliwe na kontekst, często w dość subtelny sposób. Języki LR są pozbawione kontekstu, co oznacza, że istnieje wiele subtelności dotyczących pozycjonowania i środowiska, których nie można poprawnie przekazać w składni. Przypisani gramerzy próbują odnieść się do podstawowych zasad językowych, takich jak „deklaruj przed użyciem” itp. Podłączenie tej czułości kontekstowej do odręcznego kodu jest proste.

— BobDalgleish
źródło

Cytat dotyczący roszczenia dotyczącego wydajności? Kierowanie tabelami może być znaczącą optymalizacją wydajności, a generatory mają dostęp do algorytmów, które są bardzo wydajne, ale praktycznie nigdy nie są wdrażane ręcznie (właśnie dlatego, że są nieprzeniknionym bałaganem tabel i magicznych liczb).

I o drugim obszarze: Wiele wielu głównych prawdziwych języków programowania nie jest wrażliwych na kontekst w jakimkolwiek sensie, który ma zastosowanie ( po sprawdzeniu typu musiałbyś odwoływać się do zestawu wszystkich prawidłowych programów, co nigdy nie jest odręczne lub wygenerowany parser próbuje parsować). To prawda, że parsowane odręcznie parsery są bardziej elastyczne i jest to przydatne w niektórych językach, ale głównie w dziedzinie odzyskiwania i raportowania błędów, inkrementalności itp. - generatory parsera są rzadko unikane ze względu na moc rozpoznawania (czy chcesz chcę napisać taką gramatykę to inna historia). -1

Jeśli użyjesz informacji z tablicy symboli podczas analizowania, równie dobrze możesz nazwać ją kontekstową. Gramatyki przypisane zdecydowanie nie są wolne od kontekstu, chociaż nie sądzę, aby były w pełni wrażliwe na kontekst. Twoje pozostałe punkty dotyczące odzyskiwania błędów i raportowania są dobrze przemyślane.

— BobDalgleish

C i C ++ potrzebują informacji z tablicy symboli podczas analizowania (lub akceptują znacznie mniej szczegółowe drzewo analizy, gdzie nie ma rozróżnienia między, na przykład, wyrażeniami i deklaracjami zmiennych). Ale nie myślałem o nich. Języki takie jak Java, Lisps, JavaScript, Ruby, Python, Go, Rust, Scala, Swift, Haskell (i prawdopodobnie jeszcze kilka innych, może również C # i ML?) Nie potrzebują żadnych takich informacji, aby zbudować AST i tak chcę. Wiele z nich faktycznie ma gramatykę LL (1), a nawet gramatykę LALR.

cytat dla wszystkich prawdziwych języków jest zależny od kontekstu, proszę?

— psr