Jakie są argumenty przeciwko parsowaniu po Cthulhu?


24

Przydzielono mi zadanie wdrożenia języka specyficznego dla domeny dla narzędzia, które może stać się dość ważne dla firmy. Język jest prosty, ale nie trywialny, pozwala już na zagnieżdżanie pętli, łączenie łańcuchów itp. I jest praktycznie pewne, że wraz z postępem projektu zostaną dodane inne konstrukcje.

Wiem z doświadczenia, że ​​ręczne pisanie leksyk / parsera - chyba że gramatyka jest trywialna - jest procesem czasochłonnym i podatnym na błędy. Zostały mi więc dwie opcje: generator parsera à la yacc lub biblioteka kombinatora, taka jak Parsec. Ten pierwszy był również dobry, ale wybrałem ten drugi z różnych powodów i zaimplementowałem rozwiązanie w funkcjonalnym języku.

Rezultat jest dla mnie dość spektakularny, kod jest bardzo zwięzły, elegancki i czytelny / płynny. Przyznaję, że może to wyglądać nieco dziwnie, jeśli nigdy nie programowałeś w niczym innym niż java / c #, ale to byłoby prawdą w przypadku wszystkiego, co nie jest napisane w java / c #.

W pewnym momencie jednak dosłownie zostałem zaatakowany przez współpracownika. Po szybkim spojrzeniu na mój ekran oświadczył, że kod jest niezrozumiały i że nie powinienem na nowo wymieniać parsowania, ale po prostu użyć stosu i String.Split, jak wszyscy. Zrobił dużo hałasu i nie mogłem go przekonać, częściowo dlatego, że byłem zaskoczony i nie miałem jasnego wyjaśnienia, częściowo dlatego, że jego opinia była niezmienna (nie zamierzano grać słów). Zaproponowałem nawet, że wytłumaczę mu język, ale bezskutecznie.

Jestem pewien, że dyskusja pojawi się ponownie przed zarządem, dlatego przygotowuję solidne argumenty.

Oto kilka pierwszych powodów, dla których przychodzi mi na myśl, aby uniknąć rozwiązania opartego na String.Split:

  • potrzebujesz wielu ifs do obsługi specjalnych przypadków, a rzeczy szybko wymykają się spod kontroli
  • wiele zakodowanych indeksów tablic sprawia, że ​​konserwacja jest bolesna
  • niezwykle trudne do obsługi rzeczy takich jak wywołanie funkcji jako argument metody (np. add ((add a, b), c)
  • bardzo trudno podać znaczące komunikaty o błędach w przypadku błędów składniowych (bardzo prawdopodobne, że tak się stanie)
  • Jestem za prostotą, klarownością i unikaniem niepotrzebnych inteligentnych, tajemniczych rzeczy, ale uważam również, że błędem jest ogłuszanie każdej części bazy kodu, aby nawet łopatka burgera mogła to zrozumieć. To ten sam argument, który słyszę za nieużywaniu interfejsów, nieprzystosowywaniu separacji problemów, kopiowaniu i wklejaniu kodu itp. W końcu do pracy nad projektem oprogramowania wymagane są minimalne kompetencje techniczne i chęć do nauki. (Nie użyję tego argumentu, ponieważ prawdopodobnie zabrzmi to ofensywnie, a rozpoczęcie wojny nikomu nie pomoże)

Jakie są twoje ulubione argumenty przeciwko parsowaniu po Cthulhu ? *

* oczywiście, jeśli zdołasz mnie przekonać, że ma rację, również będę całkowicie szczęśliwy


9
Wydaje mi się, że twój współpracownik chętnie wykonuje dla ciebie projekt DSL!
GrandmasterB,

23
„Nie powinienem od nowa wymieniać parsowania, ale po prostu użyć stosu i String.Split, jak wszyscy” - cholera, ten facet powinien się cieszyć, że ignorancja nie zaszkodzi ...
Michael Borgwardt,

4
Radzę współpracownikowi, aby nie wracał do tej dyskusji, chyba że przeczyta całą Dragon Book i przejdzie test. W przeciwnym razie nie ma prawa dyskutować na temat parsowania.
SK-logic,

4
przepraszam, kto wymyślił parsowanie?
rwong

2
Myślę, że moja głowa dosłownie eksploduje, kiedy następnym razem zobaczę, jak ktoś używa słowa „dosłownie” w przenośni.

Odpowiedzi:


33

Krytyczna różnica między tymi dwoma podejściami polega na tym, że ten, który uważa za jedyny właściwy sposób, jest konieczny, a twój jest deklaratywny.

  • Twoje podejście wyraźnie deklaruje reguły, tzn. Reguły gramatyki są (prawie) bezpośrednio zakodowane w kodzie, a biblioteka parserów automatycznie przekształca dane wejściowe w przetworzone dane wyjściowe, jednocześnie dbając o stan i inne rzeczy, które są trudne do obsługi. Twój kod jest napisany w ramach jednej warstwy abstrakcji, która pokrywa się z domeną problemową: analizą. Rozsądnie jest zakładać poprawność parsec, co oznacza, że ​​jedynym miejscem na błąd jest to, że twoja definicja gramatyki jest niepoprawna. Ale z drugiej strony masz w pełni kwalifikowane obiekty reguł i można je łatwo przetestować w izolacji. Warto również zauważyć, że dojrzałe biblioteki analizatorów są dostarczane z jedną ważną funkcją: raportowaniem błędów. Przyzwoite odzyskiwanie po błędach podczas analizowania nie jest łatwe. Jako dowód przywołuję PHP parse error, unexpected T_PAAMAYIM_NEKUDOTAYIM: D

  • Jego podejście manipuluje ciągami, jawnie utrzymuje stan i ręcznie podnosi surowe dane wejściowe do danych analizowanych. Musisz sam wszystko napisać, w tym zgłaszanie błędów. A kiedy coś pójdzie nie tak, jesteś całkowicie zagubiony.

Ironia polega na tym, że poprawność parsera napisanego z twoim podejściem można stosunkowo łatwo udowodnić. W jego przypadku jest to prawie niemożliwe.

Istnieją dwa sposoby konstruowania projektu oprogramowania: Jednym ze sposobów jest uczynienie go tak prostym, aby oczywiście brakowało braków, a drugim sposobem jest uczynienie go tak skomplikowanym, aby nie było oczywistych braków. Pierwsza metoda jest znacznie trudniejsza.

CAR Hoare

Twoje podejście jest prostsze. Wyklucza to jedynie poszerzenie horyzontu. Rezultat jego podejścia będzie zawsze zawiły, bez względu na to, jak szeroki będzie twój horyzont.
Szczerze mówiąc, wydaje mi się, że facet jest po prostu ignorantem, głupcem, który cierpi na zespół blub , wystarczająco arogancki, by zakładać, że się mylisz i krzyczeć na ciebie, jeśli cię nie rozumie.

Ostatecznie jednak pytanie brzmi: kto będzie musiał to utrzymać? Jeśli to ty, to twój telefon, bez względu na to, co ktoś mówi. Jeśli to będzie on, to istnieją tylko dwie możliwości: Znajdź sposób, aby sprawił, że zrozumie bibliotekę parserów lub napisze dla niego imperatywny parser. Sugeruję wygenerowanie go ze struktury parsera: D


Doskonałe wyjaśnienie różnicy między tymi dwoma podejściami.
smarmy53

6
Najwyraźniej masz link do TVTropes dla programistów. Żegnaj popołudnie ...
Izkata,

10

Gramatyka wyrażeń parsujących (takich jak parser Packrat) lub kombinator parserów nie wymyślają na nowo parsowania. Są to dobrze ugruntowane techniki w funkcjonalnym świecie programowania i, we właściwych rękach, mogą być bardziej czytelne niż alternatywy. Kilka lat temu widziałem dość przekonującą demonstrację PEG na C #, która faktycznie uczyniłaby go moim narzędziem pierwszego zastosowania dla stosunkowo prostych gramatyk.

Jeśli masz eleganckie rozwiązanie wykorzystujące kombinatory parsera lub PEG, powinno to być stosunkowo łatwe do sprzedania: jest dość rozszerzalne, zwykle stosunkowo łatwe do odczytania, gdy przestaniesz bać się programowania funkcjonalnego, a czasem jest łatwiejsze do odczytania niż typowy generator parsera oferta narzędzi, choć zależy to w dużej mierze od gramatyki i poziomu doświadczenia z każdym zestawem narzędzi. Testowanie testów jest również dość łatwe. Oczywiście, istnieją pewne niejednoznaczności gramatyczne, które mogą powodować całkiem okropną wydajność analizowania w najgorszych przypadkach (lub duże zużycie pamięci w Packrat), ale średnia wielkość liter jest całkiem przyzwoita i faktycznie niektóre niejasności gramatyczne lepiej radzić sobie z PEG niż LALR, ponieważ Oddzwonię.

Używanie podziału i stosu działa z prostszymi gramatykami niż PEG lub może je obsługiwać, ale jest wysoce prawdopodobne, że z czasem albo zaczniesz na nowo wymyślać rekurencyjne zejście, albo będziesz mieć niestabilny zestaw zachowań, które będziesz pasować - pomoc w przekazywaniu na koszt bardzo nieustrukturyzowanego kodu. Jeśli masz tylko proste reguły tokenizacji, prawdopodobnie nie jest tak źle, ale gdy dodasz złożoność, prawdopodobnie będzie to najmniej możliwe do utrzymania rozwiązanie. Zamiast tego sięgnę po generator parsera.

Osobiście moją pierwszą skłonnością, kiedy muszę zbudować DSL, byłoby użycie czegoś takiego jak Boo (.Net) lub Groovy (JVM), ponieważ czerpię całą siłę istniejącego języka programowania i niesamowitą możliwość dostosowywania, budując makra i proste modyfikacje do potoku kompilatora, bez konieczności implementowania żmudnych rzeczy, które musiałbym zrobić, gdybym zaczął od zera (pętle, zmienne, model obiektowy itp.). Gdybym był w sklepie zajmującym się programowaniem w Ruby lub Lisp, użyłbym po prostu idiomów, które mają tam sens (metaprogramowanie itp.)

Ale podejrzewam, że twój prawdziwy problem dotyczy kultury lub ego. Czy jesteś pewien, że twój współpracownik nie wystraszyłby się równie dobrze, gdybyś użył Antlr lub Flex / Bison? Podejrzewam, że „argumentowanie” za twoim rozwiązaniem może być przegraną bitwą; być może będziesz musiał poświęcić więcej czasu na bardziej miękkie podejście, które wykorzystuje techniki budowania konsensusu, zamiast odwoływać się do lokalnego organu zarządzającego. Sparuj programowanie i zademonstruj, jak szybko możesz wprowadzić zmiany w gramatyce bez poświęcania łatwości konserwacji, a także zrobienie brązowego worka w celu wyjaśnienia techniki, jej historii itd. Może pójść dalej niż 10 punktorów i „niegrzeczne pytania” spotkanie konfrontacyjne.


9

Nie jestem dobrze zaznajomiony z algorytmami parsowania i tym podobnymi, ale myślę, że dowodem na budyń jest jedzenie. Więc jeśli wszystko inne zawiedzie, możesz zaoferować mu wdrożenie parsera na swój sposób. Następnie

  • porównaj czas zainwestowany w jedno z rozwiązań,
  • uruchom oba rozwiązania poprzez kompleksowy test akceptacyjny, aby zobaczyć, które ma mniej błędów, i
  • niech niezależny sędzia porówna wynikowy kod pod względem wielkości i przejrzystości z twoim.

Aby testy były naprawdę uczciwe, możesz chcieć, aby oba rozwiązania implementowały ten sam interfejs API i korzystały ze wspólnej platformy testowej (lub znanej wam obojgu platformie testowania jednostek). Obaj moglibyście napisać dowolną liczbę i rodzaj funkcjonalnych przypadków testowych i upewnić się, że jego własne rozwiązanie przejdzie wszystkie. I oczywiście idealnie, że żadne z was nie powinno mieć dostępu do implementacji drugiej strony przed upływem terminu. Decydującym testem byłoby wówczas przetestowanie obu rozwiązań przy użyciu zestawu testów opracowanego przez innego programistę.


to świetny pomysł! Łatwo byłoby również użyć frameworka do testowania jednostek commont.
smarmy53

1
+1 za to, że współpracownik wykonał wersję dzieloną ... Operacja polegała na utworzeniu PO, więc to on najprawdopodobniej będzie musiał go wesprzeć - nie współpracownik. Samo zasugerowanie mu tego obok jego drugiej pracy może wystarczyć, aby oderwać go od twoich pleców.
Izkata,

7

Zadałeś to pytanie, jakbyś miał pytanie techniczne, ale jak zapewne już wiesz, nie ma tutaj pytania technicznego. Twoje podejście jest znacznie lepsze niż zhakowanie czegoś na poziomie postaci.

Prawdziwy problem polega na tym, że twój (prawdopodobnie bardziej doświadczony) kolega jest niepewny i czuje się zagrożony twoją wiedzą. Nie przekonasz go argumentami technicznymi ; dzięki temu będzie bardziej defensywny. Zamiast tego będziesz musiał znaleźć sposób na złagodzenie jego obaw. Nie mogę zaoferować wielu sugestii, ale możesz spróbować okazać szacunek dla jego wiedzy na temat starszego kodu.

Wreszcie, jeśli twój menedżer zgadza się z jego podstępnymi argumentami technicznymi i odrzuca twoje rozwiązanie, to myślę, że będziesz musiał poszukać innego stanowiska. Najwyraźniej byłbyś bardziej wartościowy i ceniony w bardziej wyrafinowanej organizacji.


Masz rację, już wiedziałem, że moje podejście jest lepsze, ale nie udało mi się znaleźć dobrego, przekonującego wyjaśnienia - to jest informacja techniczna, której szukam. Uzgodniono, że strona problemu „interakcji międzyludzkich” jest równie ważna jak strona techniczna (jeśli nie więcej).
smarmy53,

4

Będę krótko:

Przetwarzanie w stylu Cthulhu jest trudne. To najprostszy i najbardziej przekonujący argument przeciwko niemu.

Może to załatwić sprawę w przypadku prostych języków; powiedzmy, zwykłe języki. Prawdopodobnie nie będzie to łatwiejsze niż wyrażenie regularne.

Może to również rozwiązać problem w przypadku nieco bardziej złożonych języków.

Chciałbym jednak zobaczyć parser Cthulhu dla dowolnego języka z zagnieżdżaniem lub po prostu „znacząco stanowy” - wyrażenia matematyczne lub twój przykład (zagnieżdżone wywołania funkcji).

Wyobraź sobie, co by się stało, gdyby ktoś próbował cthulhu analizatora składni dla takiego (nietrywialnego, pozbawionego kontekstu) języka. Zakładając, że jest wystarczająco inteligentny, aby napisać poprawny parser, założę się, że podczas kodowania „odkryłby” najpierw tokenizaton, a następnie parsowanie rekurencyjne - w jakiejś formie.

Po tym rzecz jest prosta: „Hej, napisałeś coś, co nazywa się rekurencyjnym parserem pochodzenia! Czy wiesz, że można go wygenerować automatycznie na podstawie prostego opisu gramatycznego, podobnie jak wyrażeń regularnych?


Krótko mówiąc:
jedyną rzeczą, która może powstrzymać kogoś przed zastosowaniem cywilizowanego podejścia, jest jego ignorancja.


1

Być może ważna jest także praca nad dobrą semantyką DSL (liczy się składnia, ale także semantyka). Jeśli nie jesteś zaznajomiony z tymi zagadnieniami, sugerowałbym przeczytanie niektórych książek, takich jak Programowanie języków pragmatycznych (autor: M. Scott) i Christian Queinnec. Lisp In Small Pieces . Cambridge University Press, 1996.

Czytanie najnowszych artykułów na konferencjach DSL, np. DSL2011 powinno być również .

Projektowanie i implementacja języka specyficznego dla domeny jest trudne (a większość nie jest analizie!).

Naprawdę nie rozumiem, co masz na myśli, analizując sposób Cthulhu ; Wydaje mi się, że chcesz po prostu przeanalizować w jakiś dziwny sposób.


Dobre linki. Co do Cthulhu, przepraszam, zapomniałem linku. Jest to odniesienie do klasycznego artykułu o horrorze kodowania : codinghorror.com/blog/2009/11/parsing-html-the-cthulhu-way.html . Zaktualizowałem oryginalny post.
smarmy53,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.