Методы парсинга BBCode?

Question

[divanikus]

Подскажите, какие еще есть методы парсинга кроме регулярных выражений. Регулярки, как известно, не предназначены для парсинга вложенных конструкций. Если есть реализации — ткните пожалуйста.

Answer 1

[LastDragon]

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

Для примера:
1) Существующий парсер xbb.uz/

2) Собственный велосипед:
Код:http://pastebin.mozilla-russia.org/106940
Диаграмма: habrastorage.org/storage/b55a4b42/f4942156/b245ccd6/9426eb87.png
(оригинал в VP-UML, если кому-то будет нужна — пишите)

Скорее всего есть ошибки (сейчас как раз отлаживаю).

Comments

[divanikus]

Сам об этом же думал. По идее самый прямой подход. Вопрос только в скорости разбора.
А конечные автоматы имхо удобнее таблицами переходов изображать.

[FloppyFormator]

Регулярки тоже описывают конечный автомат, в этом и причина невозможности разбора вложенных конструкций.
В статье про компиляторы шла речь о магазинных автоматах.

[divanikus]

AFAIK автомат с магазинной памятью все равно конечный :)

Answer 2

[zibada]

> Регулярки, как известно, не предназначены для парсинга вложенных конструкций.

Действительно, теория нам подсказывает, что одной могучей регуляркой грамматику ббкодов не одолеть.
Но это не значит, что регулярки в данной задаче вообще применять нельзя.
(загляните в парсеры популярных форумов, например)

Вкратце — одним проходом матчим самую глубоко вложенную пару тегов и заменяем на нечто, их не содержащее, повторяем в цикле, пока находится совпадение.

Comments

[divanikus]

Смотрел и даже более того, раньше так и делал. Но это не совсем правильный подход (или вообще неправильный). Особенно если тэги вдруг перехлестнулись.

Answer 3

[Арвид Годюк]

Смотря какой язык используете. Если PHP — то есть PECL модуль bbcode. Пользуюсь — удобно, быстро, функционально за счёт callbacks и никаких извращений :)

Comments

[divanikus]

Хороший вариант, надо посмотреть реализацию. Но, имхо, применение ограничено тем, что надо компилировать и подключать на целевой системе, что не всегда доступно.
А язык — PHP, можно Perl — меня и просто сами подходы интересуют.

[Арвид Годюк]

Лучший подход — это конечный автомат с callback функциями (т.к. иногда народу нужно не совсем стандартное решение). К сожалению нормальных реализаций не видел пока. А так же всё ищу конечный автомат для разбора HTML… уже 4-й год ищу — одна ужасть.

Answer 4

[LastDragon]

> Вопрос только в скорости разбора.
Не очень быстро. Не тестировал. Тоже было бы интересно сравнить в другими вариантами парсеров.

> А конечные автоматы имхо удобнее таблицами переходов изображать
Возможно. Но диаграмма по-моему более наглядна.

> Особенно если тэги вдруг перехлестнулись
При использовании данного парсера можно как угодно обрабатывать, в данный момент вложенный незакрытый бб-код будет закрыт принудительно ([a][b][/a][/b] => [a][b][/b][/a][/b])

Comments

[LastDragon]

Промахнулся :(, это ответ на предыдущий комментарий divanikus

[divanikus]

> Но диаграмма по-моему более наглядна.
Ну я это и имел ввиду, что таблица нагляднее. Хотя кому как и зависит от количества состояний.

> При использовании данного парсера можно как угодно обрабатывать
Это понятно, я имел ввиду парсинг регулярками.

Answer 5

[exception13]

использовать парсер-генератор и формальное описание в РБНФ =]

Comments

[divanikus]

А он не конечный автомат в итоге даст?

Answer 6

[LastDragon]

Напишу еще один вариант*:
— Перебираем бб-коды в цикле:
1) находим открывающий тег "[bbcode"
2) находим "]" (все что между это аттрибуты)
3) если одиночный разбираем
4) если нет — ищем первый закрывающий тег "[/bbcode]"
5) все что между "[bbcode...]" и "[/bbcode]" это тело (оно форматируется в зависимости от bbкода)
6) continue;

Основная проблема в том, что невозможно определить к чему относится "]" из-за этого результат зависит от порядка разбора бб-кодов* В IPB для решения этой проблемы используется экранирование "]" в атрибутах…

* не нужно его использовать… именно так написан парсер бб-кодов в IP.Board… в нем было (да и сейчас есть) очень много ошибок из-за различного порядка вложенности bb-кодов и их атрибутов (в т.ч. XSS и падения Apache… небольшое количество подробностей можно найти на форуме IBR в постах Ritsuka)

Comments

[divanikus]

Про IPB в курсе, смотрел давным давно эти методы, но там постоянно XSS из-за них возникают.

На IBR кстати тоже зареген с 2003-го года, но последние годы как-то без надобности — другая сфера деятельности

Answer 7

[vgrayster]

Сам использую парсер xbb.uz, мне немного не понравился код который он генерирует, но после напильника все ок.

А какая вам скорость нужна? я парсю только один раз, при сохранении, потом результат кеширую и когда нужно отдаю из кеша.

Comments

[divanikus]

Простая, на мой взгляд, логика — быстрее работает, значит жрет меньше процессорного времени, т.е. меньше грузит машину.
Насчет сохранения результата тоже интересный вопрос. phpBB, например, хранит оба вариант — изначальный и парсенный. А вот IPB преобразует туда-обратно на лету. Даже и не знаю какой лучше.

[LastDragon]

IPB2 — хранил html
IPB3 — хранит бб-коды, но для постов (и некоторых др. данных) можно кешировать html

[divanikus]

Т.е. IPB3 рисует html из bbcode на каждый запрос? Ну если с отключенным кэшированием? Просто последняя версия, что я видел была 2.2.1 кажется.

[vgrayster]

IPB3 — кеширует отпарсенный bbcode

Answer 8

[LastDragon]

> Т.е. IPB3 рисует html из bbcode на каждый запрос?
Да. (плюсы есть, но минусов наверное больше)

Comments

[LastDragon]

снова промахнулся :( это ответ на предыдущий комментарий divanikus

[vgrayster]

Вы уверены? я его несколько недель наза смотрел, там точно была таблица где хранились распарсенный html

[LastDragon]

Уверен — бб-коды парсятся при выводе, но таблица тоже есть — называется «кэш содержимого» и хранит только *некоторые* данные (посты, подписи, ...) и *только* при включенном кэше. Все остальное парсится каждый раз. Самое «замечательное», что в своих приложениях реализовывать кэширование придется самостоятельно.