Написание парсера (для языка разметки): теория и практика

Question

Я хотел бы написать идиоматический парсер для языка разметки, например Markdown. Моя версия будет немного отличаться, но я чувствую, по крайней мере, небольшую потребность в чем-то подобном в Clojure, и я хотел бы получить это.

Я не хочу использовать беспорядок RegExes (хотя я понимаю, что некоторые, вероятно, понадобятся), и Я хотел бы сделать что-то мощное и в идиоматическом Clojure .

Я начал несколько разных попыток (в основном на бумаге), но я ужасно доволен ими, как будто я просто импровизирую. Это было бы хорошо, но я много изучал язык Clojure в течение последнего месяца или двух, и хотел бы, по крайней мере частично, идти по пути гигантов.

Мне бы хотелось несколько указателей, или предложений, или ресурсов (книги от О'Рейли были бы замечательными - любите меня некоторые электронные книги - но Amazon или везде, где тоже были бы хорошими). Все, что вы можете предложить.

РЕДАКТИРОВАТЬ У Брайана Карпера есть интересный пост на с использованием ANTLR из Clojure .

Также есть clojure-pg и fnparse , которые являются генераторами синтаксических анализаторов Clojure. fnparse даже выглядит так, как будто у него есть приличная документация.

Все еще ищите ресурсы и т. Д.! Просто подумал, что обновлю их своими собственными выводами.

Answer 1

Лучшее, о чем я могу думать, это то, что Терренс Парр - парень, который руководит генератором синтаксического анализатора ANTLR - написал язык разметки, задокументированный здесь . В любом случае, есть исходный код, на который можно посмотреть.

Answer 2

Существует также проект clj-peg , который позволяет задавать грамматику PEG для анализа данных

Answer 3

Другой, еще не упомянутый здесь, - clarsec , порт библиотеки Parsec Haskell.

Недавно я участвовал в очень похожем квесте по созданию парсера в Clojure. Я прошел довольно далеко по пути fnparse, в частности, используя (пока не выпущенный) fnparse 3, который вы можете найти в ветке develop на github. Он разбит на две формы: hound (специально для LL (1) парсеров с односторонним просмотром) и cat, который является синтаксическим анализатором пакетов. Оба являются функциональными синтаксическими анализаторами, построенными на монадах (например, clarsec). У fnparse есть впечатляющая работа - возможность документировать ваш парсер, создавать сообщения об ошибках и т. д. Документация по ветке разработки не существует, кроме строк документации, которые на самом деле довольно хороши. В конце концов я натолкнулся на некоторые препятствия, пытаясь заставить работать LL (k). Я думаю, что можно заставить это работать, это просто сложно без приличного набора примеров того, как сделать так, чтобы возвращение работало хорошо. Я также настолько знаком с парсерами, которые разделяют лексизм и парсинг, поэтому мне было трудно так думать. Я все еще очень заинтересован в этом как в хорошем решении в будущем.

Тем временем я вернулся к Antlr , который очень крепок, хорошо проработан, хорошо документирован (в 2 книгах) и т. Д. У него нет Back Cloure - конец, но я надеюсь, что это произойдет в будущем, что сделало бы его действительно полезным для работы парсера. Я использую его для лексирования, анализа, преобразования дерева и создания шаблонов через StringTemplate. Это не было полностью без ударов, но я был в состоянии найти выполнимые решения всех проблем до сих пор. Уникальный алгоритм синтаксического анализа LL (*) в Antlr позволяет вам писать действительно читаемые грамматики, но при этом делать их довольно эффективными (и постепенно настраивать их, если это не так).

Answer 4

Два функциональных переводчика разметки:

• Pandoc , уценка реализована в Haskell с источником на github
• Simple_markdown реализовано в OCaml.