Pisanie analizatora składni (dla języka znaczników): Teoria i praktyka

Question

Chciałbym napisać parser idiomatyczny dla języka znaczników, takiego jak Markdown. Moja wersja będzie nieco inna, ale dostrzegam przynajmniej niewielką potrzebę czegoś takiego w Clojure i chciałbym się z tym pogodzić.

Nie chcę używać bałaganu RegExes (choć zdaję sobie sprawę, że niektóre będą prawdopodobnie potrzebne) i Chciałbym stworzyć coś równie potężnego, jak i idiomatycznego Clojure.

Zacząłem kilka różnych prób (głównie na papierze), ale jestem strasznie szczęśliwy z nich, ponieważ czuję, że jestem po prostu improwizacją. Byłoby dobrze, ale w ciągu ostatniego miesiąca lub dwóch zrobiłem wiele badań w języku Clojure i chciałbym, przynajmniej częściowo, podążać ścieżkami gigantów.

Chciałbym wskazówek, sugestii lub zasobów (książki od O'Reilly byłyby niesamowite - uwielbiają mnie niektóre książki elektroniczne - ale Amazon lub wszędzie tam, gdzie byłaby świetna). Cokolwiek możesz zaoferować.

EDYTOWANIE Brian Carper ma interesujący post na using ANTLR from Clojure.

Istnieją również clojure-pg i fnparse, które są generatorami parserów Clojure. fnparse nawet wygląda na to, że ma przyzwoitą dokumentację.

Nadal szukasz zasobów itp.! Pomyślałem, że zaktualizuję je o własne odkrycia.

Answer 1

Istnieje również clj-peg projekt, który pozwala określić gramatykę PEG w celu analizowania danych

Answer 2

Najlepsze co mogę myśleć to to, że Terrence Parr - facet, który prowadzi ANTLR parser generator - napisał język znaczników udokumentowany here. W każdym razie jest tam kod źródłowy do obejrzenia.

Answer 3

Dwa funkcjonalne tłumaczy znaczników są;

• Pandoc, obniżki realizowane w Haskell z source on github
• Simple_markdown realizowanego w SML.

Answer 4

Kolejny nie wymieniony tutaj jest clarsec, port biblioteki parsec Haskella.

Niedawno uczestniczyłem w bardzo podobnym zadaniu, aby utworzyć parser w Clojure. Przeszedłem dość daleko ścieżką fnparse, w szczególności za pomocą (jeszcze nie wydanego) fnparse 3, które można znaleźć w gałęzina github. Jest podzielony na dwie formy: hound (specjalnie dla parserów LL (1) single overhead) i cat, który jest parserem packrat. Oba są funkcjonalnymi parserami zbudowanymi na monadach (jak clarsec). fnparse ma imponującą pracę - umiejętność dokumentowania twojego parsera, budowania komunikatów o błędach itp. jest zadowalająca. Dokumentacja dotycząca gałęzi rozwijającej się nie istnieje, ale nie zawiera funkcji docstrukcji, które są całkiem dobre. Na koniec uderzyłem kilka bloków drogowych próbując sprawić, żeby LL (k) działało. Myślę, że jest to możliwe, aby działało, jest po prostu ciężko, bez przyzwoitego zestawu przykładów, jak zrobić dobry backtracking. Jestem również zaznajomiony z parserami, które dzielą leksykowanie i analizowanie, że trudno mi tak myśleć. Nadal jestem bardzo zainteresowany tym, jako dobrym rozwiązaniem w przyszłości.

W międzyczasie powróciłem do Antlr, który jest bardzo solidny, dobrze podróżował, dobrze udokumentowany (w 2 książkach), itp. Nie ma backlooka Clojure, ale mam nadzieję, że będzie w przyszłości, co sprawi, że będzie to naprawdę miłe dla pracy z parserem. Używam go do lexing, parsowania, transformacji drzewa i szablonów za pomocą StringTemplate. To nie było całkowicie bezbłędne, ale udało mi się znaleźć praktyczne rozwiązania wszystkich problemów. Unikalny algorytm LL (*) parsowania Antlr pozwala pisać dobrze czytelne gramatyki, ale nadal sprawiają, że są dość wydajne (i stopniowo zmieniają rzeczy, jeśli nie są).