Язык разметки Markdown

В этой статье даются практические советы по написанию парсера для языка разметки Markdown. На сегодняшний день информации в интернете по этому вопросу крайне мало.

Статья будет полезна тем, кто занимается созданием собственных CMS и фреймворков с нуля.

Кратко о языке

Разработчики Маркдауна ставили своей целью создать язык, код которого будет визуально схож с результатом его выполнения. За основу были взяты принятые правила оформления e-mail сообщений.

Вот пример кода:

Заголовок
=========

Нумерованные списки:
1. Первый пункт
2. Второй пункт
3. Третий пункт

> Комментарий
 > > Комментарий в комментарии

Можно **выделять часть** текста.

Такой код будет преобразован в правильный xHTML.

Синтаксис Маркдауна является с одной стороны более легким в освоении для технически неквалифицированных пользователей(в отличие, например, от BB кодов), а, с другой стороны, производит качественный выходной xHTML код, чего не скажешь о различных WYSIWYG редакторах. Эти преимущества делают Маркдаун хорошим выбором для форумных движков и CMS, где требуется возможность редактирования контента пользователями.

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

Создания компилятора языка

Маркдаун нельзя разобрать контекстно-свободными грамматиками. Он содержит контекстно-зависимые лексические элементы. Например, вложенность конструкций определяется выравниванием строк как в Пайтоне. Так что воспользоваться в явном виде YACCом и ANTLRом не получится. Среди решений этой проблемы я встречал следующие:

• Отказаться от использования генератора парсеров и написать парсер в ручную, используя местами регулярные выражения.
  
  Именно так был создан оригинальный парсер Маркдауна на Перле и большинство других реализаций. Недостаток решения в низкой производительности: во-первых, из-за использования регулярных выражений, во-вторых, потому что оптимизировать парсер в ручную до уровня, который обеспечивает автоматически сгенерированный, как правило очень сложная задача. Кроме того, если вы пишете на императивных языках(PHP, Java, C++), то реализовать и отлаживать самописный парсер будет очень трудно.
  
  
• Использовать генератор парсеров с поддержкой встроенных действий, и писать действия, имеющие обратный эффект.
  
  За счет использования встроенных действий с обратным эффектом можно, например, осуществлять анализ выравнивания данной строки относительно предыдущей, таким образом имитируя контекстно-зависимые правила. Недостаток в том, что контекстно-свободные грамматики не предназначены для этих целей, а использование обратного эффекта может привести к багам во время разбора.
  
  
• Рекурсивное применение парсера контекстно-свободной грамматики.
  
  На самом деле, можно сначала грубо разбить весь код на отдельные блоки(абзацы, комментарии одного уровня), а потом к ним применить еще раз этот же самый парсер. Это решение не приведет к непредсказуемым последствиям как в предыдущем варианте, и оно более правильно с идеологической точки зрения, но менее эффективно в плане производительности.
  
  Возможно, это будет самым простым в реализации решением.
  
  
• Предварительно в ручную обработать входные данные.
  
  Можно в ручную разбить код на строки, и циклом пройтись по ним, заменяя пробелы в начале каждой строки на символ указывающий ее сдвиг(влево или вправо) относительно предыдущей. Точно также можно обработать вложенность комментариев. Затем полученный массив строк можно склеить обратно, и уже разбирать его контекстно-свободной грамматикой. Полученный после фильтрации язык будет контекстно-свободным.
  
  Это решение по сложности сопоставимо с предыдущим. По производительности должно в общем случае быть более эффективным.
  
  

В качестве выбора генератора парсеров для Маркдауна, на мой взгляд, больше подходит PEG.

Ссылки по теме

1. Синтаксис Маркдауна на сайте автора: http://daringfireball.net/projects/markdown/syntax
2. Парсер для PHP: http://michelf.com/projects/php-markdown/extra/
3. Парсер для JavaScript и онлайн редактор: http://attacklab.net/showdown/
4. Обсуждение по теме на StackOverflow: http://stackoverflow.com/questions/605434/how-would-you-go-about-parsing-markdown