Czy powinienem użyć generatora analizatora składni, czy też powinienem utworzyć własny niestandardowy leksykon i kod analizatora składni?

Jakie szczególne zalety i wady każdego sposobu pracy z gramatyką języka programowania?

Dlaczego / Kiedy powinienem wyrzucić własny? Dlaczego / Kiedy powinienem używać generatora?

Tak naprawdę są trzy opcje, wszystkie trzy są lepsze w różnych sytuacjach.

Opcja 1: generatory analizatora składni lub „musisz przeanalizować jakiś język i po prostu chcesz go uruchomić, do cholery”

Powiedzmy, że zostałeś poproszony o zbudowanie parsera dla jakiegoś starożytnego formatu danych TERAZ. Lub potrzebujesz, aby twój parser był szybki. Lub potrzebujesz parsera, aby był łatwy w utrzymaniu.

W takich przypadkach najlepiej jest użyć generatora analizatora składni. Nie musisz majstrować przy szczegółach, nie musisz mieć dużo skomplikowanego kodu, aby działać poprawnie, po prostu wypisz gramatykę, do której będzie się stosować dane wejściowe, napisz kod obsługi i parser presto: instant.

Korzyści są oczywiste:

• (Zazwyczaj) dość łatwo jest napisać specyfikację, szczególnie jeśli format wejściowy nie jest zbyt dziwny (opcja 2 byłaby lepsza, jeśli tak jest).
• W rezultacie powstaje bardzo łatwa do utrzymania praca, która jest łatwa do zrozumienia: definicja gramatyki zwykle płynie o wiele bardziej naturalnie niż kod.
• Parsery generowane przez dobre generatory parsera są zwykle znacznie szybsze niż odręczny kod. Odręczny kod może być szybszy, ale tylko wtedy, gdy znasz się na swoich rzeczach - dlatego najczęściej używane kompilatory używają ręcznie napisanego analizatora składni rekurencyjnej.

Jest jedna rzecz, na którą musisz uważać przy generatorach parserów: czasami mogą odrzucić twoje gramatyki. Aby zapoznać się z przeglądem różnych typów parserów i tego, jak mogą cię ugryźć, możesz zacząć tutaj . Tutaj znajdziesz przegląd wielu wdrożeń i typów gramatyk, które akceptują.

Opcja 2: ręcznie napisane parsery lub „chcesz zbudować własny parser i zależy ci na byciu przyjaznym dla użytkownika”

Generatory parsera są fajne, ale nie są zbyt przyjazne dla użytkownika (użytkownika końcowego, a nie ciebie). Zazwyczaj nie można podawać dobrych komunikatów o błędach, ani nie można zapewnić odzyskiwania po błędzie. Być może twój język jest bardzo dziwny i parsery odrzucają twoją gramatykę lub potrzebujesz większej kontroli, niż daje ci generator.

W takich przypadkach prawdopodobnie najlepiej jest użyć odręcznego analizatora składni rekurencyjnej. Właściwe wykonanie tej czynności może być skomplikowane, ale masz pełną kontrolę nad swoim parserem, dzięki czemu możesz robić różne fajne rzeczy, których nie możesz zrobić z generatorami parsera, takie jak komunikaty o błędach, a nawet odzyskiwanie błędów (spróbuj usunąć wszystkie średniki z pliku C # : kompilator C # będzie narzekał, ale i tak wykryje większość innych błędów bez względu na obecność średników).

Parsowane odręcznie parsery również zwykle działają lepiej niż generowane, zakładając, że jakość parsera jest wystarczająco wysoka. Z drugiej strony, jeśli nie uda ci się napisać dobrego parsera - zwykle z powodu (kombinacji) braku doświadczenia, wiedzy lub projektu - wtedy wydajność jest zwykle wolniejsza. W przypadku leksyków sytuacja jest odwrotna: generalnie leksykony korzystają z wyszukiwania tabel, dzięki czemu są one szybsze niż (większość) ręcznie pisanych.

Jeśli chodzi o edukację, pisanie własnego parsera nauczy Cię więcej niż korzystania z generatora. W końcu musisz pisać coraz bardziej skomplikowany kod, a ponadto musisz dokładnie zrozumieć, w jaki sposób analizujesz język. Z drugiej strony, jeśli chcesz nauczyć się tworzyć własny język (więc zdobądź doświadczenie w projektowaniu języka), preferowana jest opcja 1 lub opcja 3: jeśli opracowujesz język, prawdopodobnie wiele się zmieni, a opcje 1 i 3 ułatwią ci to.

Opcja 3: ręcznie napisane generatory parsera lub „próbujesz wiele nauczyć się z tego projektu i nie miałbyś nic przeciwko, aby skończyć z ciekawym fragmentem kodu, którego możesz często ponownie używać”

Oto ścieżka, którą aktualnie idę: piszesz własny generator parsera. Chociaż jest to wysoce nietrywialne, robienie tego prawdopodobnie nauczy Cię najwięcej.

Aby dać ci wyobrażenie o tym, co wymaga realizacja takiego projektu, opowiem ci o moich postępach.

Generator leksykalny

Najpierw stworzyłem własny generator leksyk. Zwykle projektuję oprogramowanie, zaczynając od sposobu użycia kodu, więc pomyślałem o tym, jak chcę móc użyć mojego kodu i napisałem ten fragment kodu (jest w C #):

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    { // This is just like a lex specification:
      //                    regex   token
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

foreach (CalculatorToken token in
             calculatorLexer.GetLexer(new StringReader("15+4*10")))
{ // This will iterate over all tokens in the string.
    Console.WriteLine(token.Value);
}

// Prints:
// 15
// +
// 4
// *
// 10

Wejściowe pary łańcuch-token są przekształcane w odpowiednią rekurencyjną strukturę opisującą wyrażenia regularne, które reprezentują, przy użyciu pomysłów stosu arytmetycznego. Jest on następnie przekształcany w NFA (niedeterministyczny automat skończony), który z kolei jest przekształcany w DFA (deterministyczny automat skończony). Następnie możesz dopasować ciągi znaków do DFA.

W ten sposób masz dobry pomysł na to, jak dokładnie działają leksykon. Ponadto, jeśli zrobisz to we właściwy sposób, wyniki z generatora leksykalnego mogą być z grubsza tak szybkie, jak profesjonalne wdrożenia. Nie tracisz także żadnej ekspresji w porównaniu z opcją 2, i niewiele ekspresji w porównaniu z opcją 1.

Zaimplementowałem mój generator leksykalny w nieco ponad 1600 liniach kodu. Ten kod sprawia, że ​​powyższe działa, ale nadal generuje leksykon w locie za każdym razem, gdy uruchamiasz program: Zamierzam dodać kod, aby zapisać go na dysku w pewnym momencie.

Jeśli chcesz wiedzieć, jak napisać własne lexer, to jest to dobre miejsce, aby rozpocząć.

Generator analizatora składni

Następnie piszesz generator parsera. Odwołuję się tutaj ponownie, aby uzyskać przegląd różnych rodzajów parserów - z reguły im więcej mogą parsować, tym wolniej działają.

Szybkość nie jest dla mnie problemem, zdecydowałem się na wdrożenie parsera Earley. Zaawansowane implementacje parsera Earley okazały się około dwa razy wolniejsze niż inne typy parsera.

W zamian za to uderzenie prędkości masz możliwość przeanalizowania dowolnej gramatyki, nawet dwuznacznej. Oznacza to, że nigdy nie musisz się martwić, czy w twoim parserze jest jakaś lewostronna rekurencja, czy czym jest konflikt redukujący przesunięcie. Możesz także łatwiej zdefiniować gramatykę, używając niejednoznacznych gramatyk, jeśli nie ma znaczenia, które drzewo parsowania jest wynikiem, na przykład nie ma znaczenia, czy parsujesz 1 + 2 + 3 jako (1 + 2) +3 lub jako 1 + (2 + 3).

Tak może wyglądać fragment kodu za pomocą mojego generatora analizatora składni:

Lexer<CalculatorToken> calculatorLexer = new Lexer<CalculatorToken>(
    new List<StringTokenPair>()
    {
        new StringTokenPair("\\+",  CalculatorToken.Plus),
        new StringTokenPair("\\*",  CalculatorToken.Times),
        new StringTokenPair("(",    CalculatorToken.LeftParenthesis),
        new StringTokenPair(")",    CalculatorToken.RightParenthesis),
        new StringTokenPair("\\d+", CalculatorToken.Number),
    });

Grammar<IntWrapper, CalculatorToken> calculator
    = new Grammar<IntWrapper, CalculatorToken>(calculatorLexer);

// Declaring the nonterminals.
INonTerminal<IntWrapper> expr = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> term = calculator.AddNonTerminal<IntWrapper>();
INonTerminal<IntWrapper> factor = calculator.AddNonTerminal<IntWrapper>();

// expr will be our head nonterminal.
calculator.SetAsMainNonTerminal(expr);

// expr: term | expr Plus term;
calculator.AddProduction(expr, term.GetDefault());
calculator.AddProduction(expr,
                         expr.GetDefault(),
                         CalculatorToken.Plus.GetDefault(),
                         term.AddCode(
                         (x, r) => { x.Result.Value += r.Value; return x; }
                         ));

// term: factor | term Times factor;
calculator.AddProduction(term, factor.GetDefault());
calculator.AddProduction(term,
                         term.GetDefault(),
                         CalculatorToken.Times.GetDefault(),
                         factor.AddCode
                         (
                         (x, r) => { x.Result.Value *= r.Value; return x; }
                         ));

// factor: LeftParenthesis expr RightParenthesis
//         | Number;
calculator.AddProduction(factor,
                         CalculatorToken.LeftParenthesis.GetDefault(),
                         expr.GetDefault(),
                         CalculatorToken.RightParenthesis.GetDefault());
calculator.AddProduction(factor,
                         CalculatorToken.Number.AddCode
                         (
                         (x, s) => { x.Result = new IntWrapper(int.Parse(s));
                                     return x; }
                         ));

IntWrapper result = calculator.Parse("15+4*10");
// result == 55

(Zauważ, że IntWrapper jest po prostu Int32, z wyjątkiem tego, że C # wymaga, aby była klasą, dlatego musiałem wprowadzić klasę otoki)

Mam nadzieję, że widzisz, że powyższy kod jest bardzo potężny: każda gramatyka, którą możesz wymyślić, może zostać przeanalizowana. Do gramatyki można dodawać dowolne fragmenty kodu, które mogą wykonywać wiele zadań. Jeśli uda ci się to wszystko uruchomić, możesz ponownie użyć wynikowego kodu, aby bardzo łatwo wykonać wiele zadań: wyobraź sobie zbudowanie interpretera wiersza poleceń przy użyciu tego fragmentu kodu.

Jeśli nigdy nie napisałeś parsera, polecam to zrobić. To jest fajne i uczysz się, jak rzeczy działają, i uczysz się doceniać wysiłek, jaki generatory parsera i lexera oszczędzają od zrobienia następnym razem, gdy potrzebujesz parsera.

Sugeruję również, abyś spróbował przeczytać http://compilers.iecc.com/crenshaw/, ponieważ ma bardzo przyziemne podejście do tego, jak to zrobić.

Zaletą pisania własnego parsera rekurencyjnego jest to, że można generować wysokiej jakości komunikaty o błędach dotyczące błędów składniowych. Za pomocą generatorów analizatorów składni można tworzyć produkcje błędów i dodawać niestandardowe komunikaty o błędach w określonych punktach, ale generatory analizatorów składni po prostu nie pasują do pełnej kontroli nad analizowaniem.

Kolejną zaletą pisania własnych jest to, że łatwiej jest parsować prostszą reprezentację, która nie ma korespondencji jeden do jednego z twoją gramatyką.

Jeśli Twoja gramatyka jest ustalona, ​​a komunikaty o błędach są ważne, zastanów się nad stworzeniem własnego lub przynajmniej skorzystaniem z generatora analizatora składni, który wyświetla potrzebne komunikaty o błędach. Jeśli gramatyka ciągle się zmienia, powinieneś rozważyć użycie generatorów analizatora składni.

Bjarne Stroustrup opowiada o tym, jak wykorzystał YACC do pierwszej implementacji C ++ (patrz Projektowanie i ewolucja C ++ ). W tym pierwszym przypadku żałował, że nie napisał własnego parsera rekurencyjnego zejścia!

Opcja 3: Ani (Rzuć własny generator parsera)

Tylko dlatego, że nie ma powodu, aby nie używać ANTLR , bizony , Coco / R , Grammatica , javacc , Lemon , parzony , sablecc , Quex , etc - to nie znaczy, należy natychmiast toczyć własną parser + lexer.

Zidentyfikuj, dlaczego wszystkie te narzędzia nie są wystarczająco dobre - dlaczego nie pozwalają Ci osiągnąć celu?

O ile nie masz pewności, że osobliwości gramatyczne, z którymi masz do czynienia, są unikalne, nie powinieneś po prostu tworzyć dla nich pojedynczego niestandardowego parsera + leksykonu. Zamiast tego utwórz narzędzie, które stworzy to, czego chcesz, ale może być również wykorzystane do zaspokojenia przyszłych potrzeb, a następnie wypuść je jako wolne oprogramowanie, aby zapobiec innym osobom mającym taki sam problem jak ty.

Rzutowanie własnego parsera zmusza cię do bezpośredniego myślenia o złożoności twojego języka. Jeśli język jest trudny do przeanalizowania, prawdopodobnie będzie trudny do zrozumienia.

Na początku zainteresowanie generatorami parserów było bardzo skomplikowane (niektórzy powiedzieliby „torturowany”) język. JOVIAL był szczególnie złym przykładem: wymagał dwóch symboli z wyprzedzeniem, w czasie, gdy wszystko inne wymagało co najwyżej jednego symbolu. To spowodowało, że wygenerowanie parsera dla kompilatora JOVIAL było trudniejsze niż się spodziewano (ponieważ General Dynamics / Fort Worth Division nauczył się na własnej skórze, kiedy nabyli kompilatory JOVIAL dla programu F-16).

Obecnie rekurencyjne zejście jest powszechnie preferowaną metodą, ponieważ jest łatwiejsze dla autorów kompilatorów. Kompilatory rekurencyjnego zapisu zdecydowanie nagradzają prosty, czysty projekt języka, ponieważ o wiele łatwiej jest napisać parser rekurencyjnego zapisu dla prostego, czystego języka niż dla skomplikowanego, bałaganu.

Na koniec: Czy zastanawiałeś się nad osadzeniem swojego języka w LISP i pozwoleniem tłumaczowi LISP wykonać za Ciebie ciężkie prace? AutoCAD to zrobił i stwierdził, że ich życie stało się znacznie łatwiejsze. Istnieje wiele lekkich interpreterów LISP, z których część można osadzić.

Raz napisałem parser dla aplikacji komercyjnej i użyłem yacc . Był konkurencyjny prototyp, w którym programista napisał całość ręcznie w C ++ i działał około pięć razy wolniej.

Jeśli chodzi o leksykon tego parsera, napisałem go całkowicie ręcznie. Zajęło - przepraszam, to było prawie 10 lat temu, więc nie pamiętam dokładnie - około 1000 linii w C .

Powodem, dla którego napisałem leksyk ręcznie, była gramatyka wejściowa parsera. Było to wymaganie, coś, co moja implementacja parsera musiała spełnić, w przeciwieństwie do czegoś, co zaprojektowałem. (Oczywiście, że zaprojektowałbym to inaczej. I lepiej!) Gramatyka była silnie zależna od kontekstu, a nawet leksykalizacja zależała od semantyki w niektórych miejscach. Na przykład średnik może być częścią tokena w jednym miejscu, ale separatorem w innym miejscu - na podstawie semantycznej interpretacji jakiegoś elementu, który został wcześniej przeanalizowany. Tak więc „zakopałem” takie semantyczne zależności w ręcznie pisanym lekturze, co dało mi dość prosty BNF, który był łatwy do wdrożenia w yacc.

DODANO w odpowiedzi na Macneila : yacc zapewnia bardzo potężną abstrakcję, która pozwala programiście myśleć w kategoriach terminali, terminali, produkcji i podobnych rzeczy. Ponadto podczas implementacji yylex()funkcji pomogłem skoncentrować się na zwrocie bieżącego tokena i nie martwić się o to, co było przed nim lub po nim. Programista C ++ pracował na poziomie postaci, bez korzyści z takiej abstrakcji i ostatecznie stworzył bardziej skomplikowany i mniej wydajny algorytm. Doszliśmy do wniosku, że mniejsza prędkość nie miała nic wspólnego z samym C ++ ani żadnymi bibliotekami. Zmierzyliśmy czystą szybkość analizowania plików załadowanych do pamięci; gdybyśmy mieli problem z buforowaniem plików, yacc nie byłby naszym najlepszym wyborem do jego rozwiązania.

RÓWNIEŻ CHCĘ DODAĆ : nie jest to przepis na pisanie parserów w ogóle, tylko przykład tego, jak to działało w jednej konkretnej sytuacji.

To zależy całkowicie od tego, co musisz przeanalizować. Czy potrafisz rzucić własnym szybciej, niż mógłbyś trafić w krzywą uczenia się leksykonu? Czy rzeczy, które należy przeanalizować, są na tyle statyczne, że później nie pożałujesz tej decyzji? Czy istniejące wdrożenia są zbyt skomplikowane? Jeśli tak, baw się dobrze tocząc własne, ale tylko wtedy, gdy nie uchylasz się od krzywej uczenia się.

Ostatnio bardzo polubiłem parser cytrynowy , który jest prawdopodobnie najprostszym i najłatwiejszym, jakiego kiedykolwiek używałem. Aby ułatwić utrzymanie, po prostu używam tego do większości potrzeb. SQLite używa go, a także niektórych innych ważnych projektów.

Ale w ogóle nie interesuję się leksykonami, poza tym nie przeszkadzają mi, gdy muszę je użyć (stąd cytryna). Możesz być, a jeśli tak, to dlaczego nie stworzyć? Mam wrażenie, że wrócisz do korzystania z takiego, który istnieje, ale podrap swędzenie, jeśli musisz :)

To zależy od tego, jaki jest twój cel.

Próbujesz dowiedzieć się, jak działają parsery / kompilatory? Następnie napisz własny od zera. To jedyny sposób, aby naprawdę nauczyć się doceniać wszystkie tajniki tego, co robią. Piszę jeden w ciągu ostatnich kilku miesięcy i było to interesujące i cenne doświadczenie, zwłaszcza „ah, więc dlatego język X robi to…”.

Czy musisz szybko coś złożyć w celu złożenia wniosku w terminie? Następnie użyj narzędzia do analizowania składni.

Czy potrzebujesz czegoś, na czym będziesz chciał się rozwijać w ciągu następnych 10, 20, a może nawet 30 lat? Napisz własne i nie spiesz się. Będzie tego warte.

Czy zastanawiałeś się nad podejściem do warsztatu językowego Martina Fowlersa ? Cytowanie z artykułu

Najbardziej oczywistą zmianą, jaką językowy stół roboczy wprowadza do równania, jest łatwość tworzenia zewnętrznych DSL. Nie musisz już pisać parsera. Musisz zdefiniować składnię abstrakcyjną - ale w rzeczywistości jest to dość prosty krok modelowania danych. Ponadto DSL dostaje potężne IDE - chociaż musisz poświęcić trochę czasu na zdefiniowanie tego edytora. Generator jest nadal czymś, co musisz zrobić, i mam wrażenie, że nie jest to dużo łatwiejsze niż kiedykolwiek. Ale zbudowanie generatora dla dobrego i prostego DSL jest jedną z najłatwiejszych części ćwiczenia.

Czytając to, powiedziałbym, że dni pisania własnego parsera już minęły i lepiej jest użyć jednej z dostępnych bibliotek. Po opanowaniu biblioteki wszystkie te listy DSL, które utworzysz w przyszłości, skorzystają z tej wiedzy. Inni też nie muszą uczyć się twojego podejścia do parsowania.

Edytuj, aby ukryć komentarz (i poprawione pytanie)

Zalety toczenia własnego

1. Będziesz właścicielem analizatora składni i zdobędziesz to cudowne doświadczenie, zastanawiając się nad złożoną serią problemów
2. Możesz wymyślić coś wyjątkowego, o czym nikt inny nie pomyślał (mało prawdopodobne, ale wydajesz się sprytnym facetem)
3. Pozwoli ci to zająć się interesującym problemem

Krótko mówiąc, powinieneś rzucić swój własny, jeśli naprawdę chcesz włamać się głęboko do wnętrzności poważnie trudnego problemu, który masz silną motywację do opanowania.

Zalety korzystania z cudzej biblioteki

1. Unikniesz ponownego wynalezienia koła (wspólny problem w programowaniu, na który się zgodzisz)
2. Możesz skoncentrować się na wyniku końcowym (lśniącym nowym języku) i nie martwić się zbytnio o jego analizę
3. Zobaczysz swój język w akcji znacznie szybciej (ale twoja nagroda będzie mniejsza, bo to nie wszystko)

Dlatego jeśli chcesz uzyskać szybki efekt końcowy, skorzystaj z biblioteki innej osoby.

Ogólnie rzecz biorąc, sprowadza się to do wyboru tego, ile chcesz mieć problem, a tym samym rozwiązania. Jeśli chcesz tego wszystkiego, rzuć własnym.

Dużą zaletą pisania własnych jest to, że będziesz wiedział, jak pisać własne. Dużą zaletą korzystania z narzędzia takiego jak yacc jest to, że wiesz, jak z niego korzystać. Jestem fanem wierzchołka drzewa do pierwszej eksploracji.

Dlaczego nie rozwidlić generatora analizatora składni o otwartym kodzie źródłowym i uczynić go swoim własnym? Jeśli nie użyjesz generatorów parsera, kod będzie bardzo trudny w utrzymaniu, jeśli wprowadzisz duże zmiany w składni swojego języka.

W moich parserach używałem wyrażeń regularnych (mam na myśli styl Perla), aby tokenizować i używać niektórych funkcji wygody, aby zwiększyć czytelność kodu. Jednak kod generowany przez analizator składni może być szybszy, tworząc tablice stanów i długie switch- cases, co może zwiększyć rozmiar kodu źródłowego, chyba że ty .gitignore.

Oto dwa przykłady moich niestandardowych parserów:

https://github.com/SHiNKiROU/DesignScript - dialekt BASIC, ponieważ byłem zbyt leniwy, aby pisać lookaheads w notacji tablicowej, poświęciłem jakość komunikatu o błędzie https://github.com/SHiNKiROU/ExprParser - kalkulator formuły. Zauważ dziwne sztuczki z metaprogramowaniem

„Czy powinienem użyć tego sprawdzonego„ koła ”, czy też wynaleźć go na nowo?”