Zalety Antlr (w porównaniu, powiedzmy, lex / yacc / bison) [zamknięte]

143

W przeszłości używałem lex i yacc (częściej bison) do różnych projektów, zwykle tłumaczy (takich jak podzbiór EDIF przesyłany strumieniowo do aplikacji EDA). Dodatkowo musiałem obsługiwać kod oparty na gramatykach lex / yacc sprzed dziesięcioleci. Więc znam się na narzędziach, chociaż nie jestem ekspertem.

Widziałem pozytywne komentarze na temat Antlr na różnych forach w przeszłości i jestem ciekawy, czego może mi brakować. Więc jeśli korzystałeś z obu, powiedz mi, co jest lepsze lub bardziej zaawansowane w Antlr. Moje obecne ograniczenia są takie, że pracuję w sklepie C ++, a żaden produkt, który dostarczamy, nie będzie zawierał Javy, więc otrzymane parsery musiałyby przestrzegać tej zasady.

Don Wakefield
źródło

Odpowiedzi:

145

Aktualizacja / ostrzeżenie: ta odpowiedź może być nieaktualna!


Jedną z głównych różnic jest to, że ANTLR generuje parser LL (*), podczas gdy YACC i Bison generują parsery LALR. Jest to ważne rozróżnienie dla wielu zastosowań, z których najbardziej oczywiste są operatorzy:

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

ANTLR jest całkowicie niezdolny do obsługi tej gramatyki tak, jak jest. Aby użyć ANTLR (lub innego generatora parsera LL), musiałbyś przekonwertować tę gramatykę na coś, co nie jest lewostronnie rekurencyjne. Jednak Bison nie ma problemu z gramatyką tej formy. Trzeba by zadeklarować „+” i „-” jako operatory asocjacyjne lewostronne, ale nie jest to ściśle wymagane dla rekurencji lewostronnej. Lepszym przykładem może być wysyłka:

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

Zwróć uwagę, że zarówno reguły , jak expri actualsreguły są lewostronne. Daje to znacznie bardziej wydajne AST, gdy przychodzi czas na generowanie kodu, ponieważ pozwala uniknąć konieczności stosowania wielu rejestrów i niepotrzebnego rozlewania (drzewo pochylone w lewo może zostać zwinięte, podczas gdy drzewo pochylone w prawo nie może).

Jeśli chodzi o osobiste upodobania, myślę, że gramatyki LALR są dużo łatwiejsze do skonstruowania i debugowania. Wadą jest to, że musisz radzić sobie z nieco tajemniczymi błędami, takimi jak zmiana-redukcja i (przerażająca) redukcja-redukcja. Są to błędy, które wyłapuje Bison podczas generowania parsera, więc nie wpływa to na wrażenia użytkownika końcowego, ale może uczynić proces rozwoju nieco bardziej interesującym. ANTLR jest ogólnie uważany za łatwiejszy w użyciu niż YACC / Bison właśnie z tego powodu.

Daniel Śpiewak
źródło
2
Tak więc dużą, prawdopodobnie pojedynczą zaletą Antlr w twojej percepcji jest to, że generuje mniej błędów, takich jak sr i rr na etapie budowy? Spodziewam się, że spróbuję, ale prawdopodobnie skończę z tym, co wiem ...
Don Wakefield,
1
Tak, to prawie wszystko. :-) Nie zgadzam się też z popularną opinią, że ANTLR jest łatwiejsze niż Bison, więc myślę, że zgodziłbym się z Twoją decyzją.
Daniel Spiewak
2
Czy reguła „wartości rzeczywistych” wymaga drugiej reguły, aby wskazać, że proste „wyrażenie” jest faktyczne? W przeciwnym razie miłe wyjaśnienie.
Jonathan Leffler
8
Inny komentarz, który znalazłem niedawno, choć sprzed dziesięciu lat, stanowi rozsądną obserwację wyników : compilers.iecc.com/comparch/article/98-11-040 : "ANTLR / PCCTS to LL, co utrudnia pisanie gramatyki, ale wygenerowany kod jest czytelny. Yacc będący LALR (oczywiście wiesz o tym) ułatwia pisanie gramatyki, ale wygenerowany kod równie dobrze może być hieroglifami. "
Don Wakefield
72
Właśnie ukończyłem natychmiastową obsługę lewostronnej rekurencji dla ANTLR w następnej wersji v3.4. Obsługuje reguły wyrażeń LR i podobne rzeczy, takie jak reguły deklaratora C. :)
Terence Parr
117

Najbardziej znaczącą różnicą między YACC / Bison i ANTLR jest rodzaj gramatyki, którą te narzędzia mogą przetwarzać. YACC / Bison obsługuje gramatyki LALR, ANTLR obsługuje gramatyki LL.

Często osoby, które przez długi czas pracowały z gramatykami LALR, będą miały trudność z gramatyką LL i odwrotnie. Nie oznacza to, że gramatyka lub narzędzia są z natury trudniejsze w obsłudze. To, które narzędzie uważasz za łatwiejsze w użyciu, sprowadza się głównie do znajomości rodzaju gramatyki.

Jeśli chodzi o zalety, są aspekty, w których gramatyki LALR mają przewagę nad gramatykami LL i są inne aspekty, w których gramatyki LL mają przewagę nad gramatykami LALR.

YACC / Bison generuje parsery sterowane tabelami, co oznacza, że ​​„logika przetwarzania” jest zawarta w danych programu parsera, a nie w kodzie parsera. Opłaca się to, że nawet parser dla bardzo złożonego języka ma stosunkowo niewielki ślad w kodzie. Było to ważniejsze w latach sześćdziesiątych i siedemdziesiątych, kiedy sprzęt był bardzo ograniczony. Generatory parserów sterowane tabelami sięgają do tej epoki, a mały ślad kodu był wówczas głównym wymaganiem.

ANTLR generuje rekurencyjne parsery zejścia, co oznacza, że ​​"logika przetwarzania" jest zawarta w kodzie parsera, ponieważ każda reguła produkcji gramatyki jest reprezentowana przez funkcję w kodzie parsera. Opłaca się to, że łatwiej jest zrozumieć, co robi parser, czytając jego kod. Ponadto parsery zstępujące rekurencyjnie są zwykle szybsze niż parsery sterowane tabelami. Jednak w przypadku bardzo złożonych języków ślad kodu będzie większy. To był problem w latach sześćdziesiątych i siedemdziesiątych XX wieku. Wtedy tylko stosunkowo małe języki, jak na przykład Pascal, były implementowane w ten sposób z powodu ograniczeń sprzętowych.

Parsery generowane przez ANTLR zwykle znajdują się w pobliżu 10.000 linii kodu i więcej. Odręczne rekursywne parsery zejścia często znajdują się w tym samym polu. Kompilator Oberon firmy Wirth jest prawdopodobnie najbardziej kompaktowy i zawiera około 4000 linii kodu, w tym generowanie kodu, ale Oberon to bardzo kompaktowy język z zaledwie około 40 regułami produkcyjnymi.

Jak ktoś już zauważył, dużym plusem dla ANTLR jest graficzne narzędzie IDE o nazwie ANTLRworks. Jest to kompletne laboratorium gramatyczne i projektowania języka. Wizualizuje reguły gramatyczne podczas ich wpisywania, a jeśli znajdzie jakiekolwiek konflikty, pokaże graficznie, czym jest konflikt i co go powoduje. Może nawet automatycznie refaktoryzować i rozwiązywać konflikty, takie jak lewostronna rekurencja. Kiedy już masz gramatykę wolną od konfliktów, możesz pozwolić ANTLRworks przeanalizować plik wejściowy twojego języka i zbudować dla ciebie drzewo parsowania i AST oraz pokazać je graficznie w IDE. Jest to bardzo duża zaleta, ponieważ pozwala zaoszczędzić wiele godzin pracy: zanim zaczniesz kodować, znajdziesz błędy koncepcyjne w projekcie swojego języka! Nie znalazłem takiego narzędzia do gramatyki LALR, wygląda na to, że nie ma takiego narzędzia.

Nawet dla osób, które nie chcą generować swoich parserów, ale ręcznie je kodują, ANTLRworks jest doskonałym narzędziem do projektowania / prototypowania języka. Całkiem możliwe, że najlepsze dostępne takie narzędzie. Niestety, to nie pomaga, jeśli chcesz zbudować parsery LALR. Przejście z LALR na LL po prostu w celu skorzystania z ANTLRworks może być opłacalne, ale dla niektórych osób zmiana gramatyki może być bardzo bolesnym doświadczeniem. Innymi słowy: YMMV.

trijezdci
źródło
4
lubię to, ponieważ wyjaśnia historię różnych mechanizmów, które sprawiają, że ludzie są rozumiani od
razu
35

Kilka zalet ANTLR:

  • może generować parsery w różnych językach - Java nie jest wymagana do uruchomienia wygenerowanego parsera.
  • Niesamowite GUI ułatwia debugowanie gramatyki (np. Możesz zobaczyć wygenerowane AST bezpośrednio w GUI, nie są wymagane żadne dodatkowe narzędzia)
  • Wygenerowany kod jest w rzeczywistości czytelny dla człowieka (to jeden z celów ANTLR) i fakt, że generuje parsery LL z pewnością pomaga w tym względzie.
  • definicja terminali również jest bezkontekstowa (w przeciwieństwie do wyrażenia regularnego w (f) lex) - pozwala to na przykład na definicję terminali zawierających odpowiednio zamknięte nawiasy

Mój 0,02 $

Cristian Diaconescu
źródło
9

Kolejną zaletą ANTRL jest to, że możesz używać ANTLRWORKS , chociaż nie mogę powiedzieć, że jest to ścisła zaleta, ponieważ mogą istnieć podobne narzędzia również dla innych generatorów.

John z waflem
źródło
9
  • Bison i Flex skutkują mniejszym zużyciem pamięci, ale nie masz graficznego IDE.
  • antlr zużywa więcej pamięci, ale masz antlrworks, graficzne IDE.

Użycie pamięci Bison / Flex wynosi zazwyczaj jeden MB. Porównaj to z antlr - zakładając, że wykorzystuje 512 bajtów pamięci na każdy token w pliku, który chcesz przeanalizować. 4 miliony tokenów i zabraknie pamięci wirtualnej w systemie 32-bitowym.

Jeśli plik, który chcesz przeanalizować jest duży, antlr może zabraknąć pamięci, więc jeśli chcesz tylko przeanalizować plik konfiguracyjny, byłoby to realne rozwiązanie. W przeciwnym razie, jeśli chcesz przeanalizować plik z dużą ilością danych, wypróbuj Bison.

tylko ja
źródło
7
Jestem ciekawy. Czy możesz wskazać dokumentację opisującą zużycie 512 bajtów pamięci na token? Nie przypominam sobie, żebym widział tę dyskusję. Mój wybór słów kluczowych Google również nie daje satysfakcji ...
Don Wakefield
2
Czy mówisz o śladzie pamięci generatora parsera podczas generowania parsera, czy też mówisz o śladzie pamięci generowanego parsera podczas analizowania danych wejściowych dla języka źródłowego? Miliony żetonów w gramatyce byłyby absolutnie szalone. Powinieneś zostać zamknięty w szpitalu psychiatrycznym, jeśli poważnie próbowałeś sprzedać taki pomysł. Jeśli chodzi o pliki wejściowe dla samego parsera, mogą wystąpić przypadki, w których mogą one mieć bardzo dużą liczbę tokenów, ale większość języków ma charakter modułowy, nie analizuje się całego wejścia w jednym pliku, poszczególne moduły są mniejsze.
trijezdci