Як я розробляв транслятор мов розмітки

Ця історія почалася в далекому 2008 році. В одному з моїх проектів для протидії XSS-атак я вирішив використовувати BB-коди і почав шукати відповідні бібліотеки на Java. Гарненько погугливши, я так нічого і нічого не знайшов. Звичайно, тоді було і зараз є багато бібліотек для трансляції BB-кодів HTML, але всі вони мене не влаштовували по одному критерію — неможливість додавати або видаляти теги. Згадавши курс "Мови програмування і методи трансляції" (користь від класичного освіти!) я взявся за реалізацію своєї власної бібліотеки для парсингу BB-кодів. В результаті з'явився мій самий довгоживучий проект KefirBB.
Зараз KefirBB представляє собою конфігурується транслятор мов розмітки. В бібліотеку вже включені конфігурації для трансляції BBCode, фільтрації HTML, Textile, частково Markdown. Так само, користувач може реалізувати свою власну мову розмітки. Конфігурація може бути задана в XML-файлі або програмно.
Коротко про конфігураціїЄ 2 основні сутності: коди і області видимості (scope). Код являє собою зразок для парсингу BB-коду і шаблон для генерації HTML.
<code name="bold">
<pattern ignoreCase="true">[b]<var inherit="true"/>[/b]</pattern>
<template>&lt;b&gt;<var/>&lt;/b&gt;</template>
</code>

Для парсингу тексту всередині коду можуть використовуватися зовсім інші коди, ніж ті, які використовуються для парсингу поза. Для цього існують області видимості, які включають в себе декілька кодів. Різні області видимості можуть включати одні і ті ж коди. В даному прикладі область видимості успадковується від батьківського коду. Є область видимості за замовчуванням 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, додаю нові можливості, включаю нові мови розмітки. Буду радий будь-якої критики і коментарів.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.