Как я разрабатывал транслятор языков разметки
Эта история началась в далеком 2008 году. В одном из моих проектов для противодействия XSS-атакам я решил использовать BB-коды и начал искать подходящие библиотеки на Java. Хорошенько погуглив, я так ничего ничего и не нашел. Конечно, тогда было и сейчас есть много библиотек для трансляции BB-кодов в HTML, но все они меня не устраивали по одному критерию — невозможность добавлять или удалять тэги. Вспомнив курс «Языки программирования и методы трансляции» (польза от классического образования!) я принялся за реализацию своей собственной библиотеки для парсинга BB-кодов. В результате появился мой самый долгоживущий проект KefirBB.
Сейчас KefirBB представляет собой конфигурируемый транслятор языков разметки. В библиотеку уже включены конфигурации для трансляции BBCode, фильтрации HTML, Textile, частично Markdown. Так же, пользователь может реализовать свой собственный язык разметки. Конфигурация может быть задана в XML-файле или программно.
Есть 2 основные сущности: коды и области видимости (scope). Код представляет собой образец для парсинга BB-кода и шаблон для генерации HTML.
[b][/b]
<b></b>
Для парсинга текста внутри кода могут использоваться совсем другие коды, чем те которые используются для парсинга вне. Для этого существуют области видимости, которые включают в себя несколько кодов. Разные области видимости могут включать одни и те же коды. В данном примере область видимости наследуется от родительского кода. Есть область видимости по умолчанию ROOT.
Подробней обо всем этом можно прочитать в документации — Руководство пользователя
Здесь же я хотел бы поделиться тем опытом, который я приобрел по ходу разработки этого транслятора.
Первая проблема, с которой я столкнулся — это обработка ошибок. Транслятор изначально я создавал для контекстно зависимых грамматик. Но это я уже позже узнал. Т.е. работает он не на конечных автоматах. Парсер — это рекурсивный алгоритм. Худо бедно бороться с ошибками нас в университете, конечно, учили, но учили нас с расчетом на то что ошибки допускает программист в программе, а не злоумышленник, который хочет нас взломать. Самая первая версия транслятора уходила у медитацию от простого текста:
[b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b][b]
Происходило это потому что при встрече тэга [b] парсер распознавал его как тэг [b][/b] и начинал парсить внутренности как будто он уже внутри тэга [b]. Затем 2й, 3й, 4й и т.д. Когда доходил до последнего и до конца текста, парсер понимал, что его обманули. Тогда он решал, что последний тэг ошибочный и возвращался к предпоследнему. Тут же понимал, что и предпоследний ошибочный и начинал парсить последний тэг в контексте предпредпоследнего. Сперва решал что он правильный, потом что ошибочный, потом возвращался и т.д. Процесс заканчивался где-то в вечности. Сложность алгоритма O(2^N).
И, надо сказать, это была серьезная проблема. Я был почти в отчаянии и был уже готов все бросить. К счастью, мой однокурсник чемпион мира по программированию Ренат Муллаханов, которого, к сожалению, уже нет с нами, подсказал решение. Нужно запоминать места, в которых уже были ошибки и не парсить их повторно. В нашем примере, после того как транслятор поймет, что последний тэг ошибочный, он не будет пытаться его парсить в контексте предпоследнего тэга, а сразу вернет ошибку. Сложность алгоритма резко уменьшилась до O(N). Тогда в трансляторе еще не было областей видимости, с их появлением алгоритм пришлось переписать, но основная идея сохранилась.
Впоследствии транслятор развивался, расширялись его возможности и он прочно входил во все наши проекты. Однажды даже для перевода его использовали. И, в один прекрасный день, было замечено, что на одном из сайтов трансляция текста создает довольно серьезные проблемы. Трансляции среднего размера текста занимала 2 секунды. Что было неприемлемо. Началась длительная оптимизации.
Первое что вы должны усвоить при оптимизации кода — никогда не стоит обращать внимания на свои эвристические догадки. Только профайлер может помочь вам выявить проблемы производительности. Но даже это меня не спасло. Я смотрел в профайлер и видел, что большую часть времени отнимает метод, который определяет какой код следует использовать для парсинга в данный момент. Я долго и упорно его оптимизировал и ускорил его в сотни раз. Но, как оказалось, большую часть времени парсится текст вообще без кодов. Т.е. оптимизировать надо не парсинг кодов, а парсинг текста без кодов, потому что его, в реальных текстах, в десятки раз больше.
Как это сделать? На первом шаге KefirBB определяет символы, с которых может начинаться код. Этих символов, обычно, не так уж много. Например, для BB-кодов — это [, а для HTML — <. Затем проверка идет только на сравнение этих символов. Как ни удивительно, эта оптимизация ускорила обработку текстов в десятки раз.
Я продолжаю разработку KefirBB, добавляю новые возможности, включаю новые языки разметки. Буду рад любой критике и комментариям.
