Парсинг BBcode
 

Пишу сейчас, вернее уже дописываю парсинг BBcode регой.

Вид реги не имеет значения, суть такова:

Текст

[B]aaaa [B] bbbb[/B] aaa[/B]

парсится регой так:
Сначала находиться:

[B] bbbb[/B]

, затем нужно рекурсивно вызвать регу снова и она найдет:

[B]aaaa <b> bbbb</b> aaa[/B]

Меня всё устраивает, но выглядит идея как-то громоздко, хотя сохраняется вложенность, если таковая имеется и всякие там [color = red\]bububu[/color] не проблема, ведь мы получаем весь BBcode и можем потом с ним делать что хотим.

Раньше парсил быстрее, но раздельно начало и конец, но решение получалось какое-то заумное и разрозненное.

Есть идеи как можно быстрее парсить BBcode, нежели рекурсией?

ps: По BBcode-ам проходим циклом, b,u,i,s,img ...

Или может быть как-то отпарсить текст в стек, какой-нибудь универсальной регой, а затем уже с ним работать?
Однако опять не понятно что делать с вложенностью.

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

ну у меня только такой в голову вариант пока что пришел.

var text = 'test [b]bold[/b] blah [code]function(){}[/code] tar [quote]blah blah [i]ta[i]r[/i]am[/i] param[/quote]';

function parseBBCode( text ) {
    return text.replace( /\[(([a-z]+)(?:\=[^\]]+)?)\](.*)\[\/\2\]/gi, function( all, tag, tagAttr, content ) {
        return '<' + tagAttr + '>' + parseBBCode( content ) + '</' + tagAttr + '>';
    });
}

alert( parseBBCode( text ) );

можно сделать и так:

var text = 'test [b=color]bold[/b] blah [code run]function(){}[/code] tar [quote]blah blah [i]ta[i]r[/i]am[/i] param[/quote]';
 
function parseBBCode( text ) {
    return text.replace( /\[(([a-z]+)(?:(?:\=|\s)([^\]]+))?)\](.*)\[\/\2\]/gi, function( all, tagAttr, tag, attr, content ) {

        // tag - содержит имя тега BBCode
        // tagAttr - содержит и тег и его атрибут(ы)
        // attr - трибут(ы) текущего тега
        // content - собственно содержимое этого тега

        return '<' + tagAttr + '>' + parseBBCode( content ) + '</' + tag + '>';
    });
}
 
alert( parseBBCode( text ) );

BBCode теги он ищет такого вида:
[code]
[code=color]
[code run]
[code run hide]

Ну а дальше дело техники и воображения.

Понял, берем по максимуму и затем ужимаем, у меня брало по минимуму.

Хотя в том варианте у меня плохо обрабатывал он такой вариант:

test [b=color]bold[/b] tatata [b]blah[/b] tata

можно сделать немного иначе, сначала обработать не жадным методом, а на последок жадным, тем самым мы обработаем все теги корректно.

var text = 'test [b=color]bold[/b] tatata [b]blah[/b] [code run]function(){}[/code] tar [quote]blah blah [i]ta[i]r[/i]am[/i] param[/quote]';
  
function parseBBCode( text, greed ) {
    var re = new RegExp("\\[(([a-z]+)(?:(?:\\=|\\s)([^\\]]+))?)\\](.*" + ( greed ? '' : '?' ) + ")\\[\\/\\2\\]", "gi");
    return text.replace( re, function( all, tagAttr, tag, attr, content ) {
 
        // tag - содержит имя тега BBCode
        // tagAttr - содержит и тег и его атрибут(ы)
        // attr - трибут(ы) текущего тега
        // content - собственно содержимое этого тега

        return '<' + tagAttr + '>' + parseBBCode( content, greed ) + '</' + tag + '>';
    });
}
  
alert( parseBBCode( parseBBCode( text ), true ) );

в реге вместо [a-z]+ можно написать только разрешенные теги, типа:
b|i|u|img|code

В каком? Не понял.

Думаю не нужно, я проверяю уже когда в функцию прилетает выбранный кусок, так работать должно быстрее.

в первых двух
дело выбора :) как тебе удобнее конечно, с другой стороны твое решение и возможностей больше даст

Вложенность, она самая. Я по этому минимальным брал, а потом засомневался. Теперь вижу что пока зря. Я в минимальном сразу знаю что у меня вложенность нормальная, хотя и парсить будет медленнее.

Первый не жадным, а в рекурсию вписать жадный. Да, думаю так будет быстрее.

Ну уж не обязательно за пользователя делать все все все, не валидные BB я б не стал парсить, и обязательно искать теги по парам? Иначе можно без циклов и рекурсии, если, конечно не считать replace c global циклом

var BB = new function () {
			
	this.tags = {
		U: "ins",
		I: "em",
		B: "strong",
		S: "del"
	}
			
	function parseAttr(attr) {
		
		//	не реализовано
		return "ATTR";
	}
		
	var BB = /(?:\[(\/)?\s*(?:((?:\\[\s\S]|[^\[\]\s\=\/])+)(?:\s*=\s*((?:(?:(?:"[^"]*")|(?:'[^']*'))|(?:\\[\s\S]|[^\[\]\s\/]))+))?)\s*\])/g;
			
	this.toHtml = function (string) {
				
		var self = this;
				
		return string.replace(BB, function (m, closed, name, attr) {
			name = name.toUpperCase();
			
			return self.tags[name] ?
				"<" + (closed || "") + self.tags[name] +
					(attr ? " " + parseAttr(attr) : "") + ">" : m;
		});
	}
		
		
}();
		
var str = "[B]bold [B]bold [B = SOME]bold [I] ITALIC FONT[/I] foo[/B] bar [/B] zot [/B] zorg";
		
alert(BB.toHtml(str))

Извиняюсь если ерунду ляпнул, голова к вечеру квадратная

Совсем недавно мне тоже приходилось писать регу для парсинга bbcode, правда всего одного, условного, для подсветки кода. Если принимать во внимание, что писал я ее после ~ недели знакомства с regexp, то, думаю получилось приемлемо (пример, код). Решения, примененные там, считаю далеко не оптимальными)
По вопросу. Признаться, на данный момент, вряд ли я чем смогу Вам помочь и заранее извиняюсь за разведенный флуд, но не могу понять, как может этоработать, при вашем условии

alert(/\[B\].*?\[\/B\]/.exec("[B]aaaa [B] bbbb[/B] aaa[/B]")); // не жадно
alert(/\[B\].*\[\/B\]/.exec("[B]aaaa [B] bbbb[/B] aaa[/B]")); // жадно

Моя логика подсказывает, что в данном конкретном случае, надо "откусить кусок побольше", а уже потом "чавкать" :)
Ссыллки на гугл давать не буду, но кое-что посоветую (если не читали): 4, 5, 6 главы "Дж.Фридл - Регулярные выражения, 3-е изд.[2008]". Если не ошибаюсь, там как раз обсуждаются вопросы эффективности построения регулярных выражений.

p.s.: все это моя субъективная точка зрения, Вы, я думаю, опытнее будите в выше обозначенных вопросах, поэтому если что не так, извиняйте)

Если считать валидностью наличие пары, то получается, что парсите :)

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

var text = 'test [b=color]bold[/b] tatata [b]blah[/b] tata [code run]function(){}[/code] tar [quote]blah blah [i]ta[i]r[/i]am[/i] param[/quote]';
  
function parseBBCode( text ) {
    return text.replace( /\[(([a-z]+)(?:(?:\=|\s)([^\]]+))?)\](.*)/gi, function( all, tagAttr, tag, attr, end ) {
        var re = new RegExp( "(.*?)(\\[\\/(" + tag + ")\\]|\\[([a-z]+.*?)\\])(.*)", "i" );
        return parseBBCode( end.replace( re, function( subAll, content, tags, closeTag, openTag, subEnd ) {
            if ( openTag ) {
                return '[' + tagAttr + ']' + parseBBCode( subAll );
            } else {

                // tag - содержит имя тега BBCode
                // tagAttr - содержит и тег и его атрибут(ы)
                // attr - трибут(ы) текущего тега
                // content - собственно содержимое этого тега

                alert( [ tagAttr, content, closeTag ].join("\n") );
                return '<' + tag + '>' + content + '</' + closeTag + '>' + subEnd;
            }
        }));
    });
}
  
alert( parseBBCode( text ) );

Ты не можешь понять потому, что я делаю не так как ты. Приведенный тобой пример ни к чему не относится.

Я делаю почти так же как написал devote, идея та же - собственно он мне её и подсказал, но реализация чуть сложнее, проверки разные и т.д.

Да, Вы правы. Прогнал код devote в отладчике. Вроде в голове чуть прояснилось) Без опыта программирования на js и в частности механизма построения и использования эффективных регулярный выражений, мне фигово :) Отсюда неверные выводы.

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

Gozar, вы об этом и говорили, наверное... Но я повторюсь. Можно делать так, как тут. То есть в цикле убираем самые вложенные (путём замены их на нормальные теги) и цикл гоняем до тех пор, пока можем найти хоть один непреобразованный bb-код.

От цикла я давно отказался, рекурсия рулет/торт:).
Я делаю именно так как писал выше. Без всяких new RegExp.
Сначала выбираем из текста максимум, как бы горку, а потом горку просматриваем от самого вложенного(минимального).

Этого должно быть достаточно чтобы не сканить весь текст и не было багов какой-нибудь вложенности, скорость ещё не тестировал, но пока всё нормально и реги мне понятны. Нет никаких end и if, только последовательность, сначала максимум всего, затем уже минимум конкретных тегов рекурсией.

Рекурсия памяти больше жрёт) Но в любом случае, это ваш выбор)

Любые действия жрут память.

Ты написал парсер BBcode и он работает быстрее? Он легкий в понимании и легко расширяем? Он правильно работает, ты уверен?

Ты пользуешься функцией sort? Будешь её использовать или она тоже память жрёт?

ps: Учитывая то, как я делаю парсинг, вопросы памяти меня касаться не будут.

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

trikadin,
У тебя проблемы с восприятием. Я ни одного наезда не написал, а только вопросы.

Не различаешь наезды и вопросы?

Я логично предположил, что ты не писал подобный парсер, т.к. выводы твои не очень в тему. Либо ты не вник в суть проблемы.

trikadin,
Как ты получишь количество тэгов для цикла в произвольном тексте? Экономия на блохах.

Gozar, я предложил, наверное, не совсем то, что вы хотели.

Я предложил сразу производить замену. То есть нашёл - сразу заменил. Ещё раз нашёл - ещё раз сразу заменил. И так до тех пор, пока в тексте не останется ни одного нужного нам bb-тега.

Если вы хотите получить их, скажем, в объекте или массиве - мой способ определённо не подходит.

Не совсем понял... Какое количество каких тегов?

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

Просто предложил делать это по-другому. Это всё, что я хотел сказать)

Как?
В while засунуть регу и гонять её в цикле? Я правильно понял?

Может ты и прав что экономия будет.
Я тут реальные тесты прогнал на слабенькой машине и понял, что можно оставить так, так как проблем с памятью не наблюдается. Если будет не лень, то может перепишу на while, посмотрю на разницу.

Да. Я давал ссылку на пример, где так делается.

Было бы неплохо, ибо сам я этого точно не сделаю.

Переписал на while и сравнил по времени выполнения и затратам процессора и памяти. Тестировал на очень слабой машине с 500мб памяти.

Однако с тэстами напряг, т.к. оба варианта в среднем выдают по нолям (0 ms) == сильно форматированная страница форума на 20-40 сообщений. Причем даже без оптимизации, которую я тут по ходу дела сделал для while, разница между вариантами настолько не существенна, что нужен спец. тест чтобы её понять. Скачков процессора и расхода памяти тоже замечено не было. Спец. тест писать точно не буду.

Вывод такой: в данном, конкретном случае разница не существенна. Возможно на каком-то страшном(длинном) форуме выигрыш будет за while, но к жизни это похоже мало имеет отношения.

Всем спасибо за участие вопрос решать дальше смысла нет.

Варианты подходят оба.

Всё таки не дала мне покоя эта тема и я переписал while.

Результаты такие:

Если в while использовать регу, то разницы между рекурсией и while никакой нет.

221 - 300 ms
220 - 340 ms

на 300 циклах for.

Однако, путём хитрой оптимизации можно сильно ускорить while. Нужно просто полностью отказаться от проверки реги в нём. Результат не заставил себя ждать:

145ms - 176ms

trikadin, этот ответ специально для тебя, ну и ещё тех кто поймет твой код по ссылке:

Сделать это можно следующим образом:

var i = 0, 
    j = 0;

function fuRep(){
    i = 1;
}

while (i != j) {
    i = 0, j = 0;
    str = str.replace(rega, fuRep);
}

Смысл сего: гоняем цикл если совпадение есть, если нет то не гоняем, таким образом проверочная рега только одна, дополнительных не нужно. Предполагается что дополнительная уже была и мы знаем что в коде есть BB коды.

Таким образом мы разбираемся со вложенностью.

Решение может и не очень красивое, но прирост скорости на лицо.

ps: к тестам не придираемся, они вполне себе адекватные.

Gozar,
Ну ты бы сразу сказал бы что для тебя скорость важна... Я бы может чего друго состряпал бы.. Я просто старался не писать лишнего, что бы код был более оптимален, но на про скорость я не задумывался. А так да, чем больше регов, тем дольше все это работает.

Позволю себе заметить, что от качества реги тоже многое зависит. Я, например, не смог правильно ответить на этот вопрос

//что вернут скобки?
var x = "Copyright 2003.";
var z = /^.*([0-9]+)/g;
alert(z.exec(x)[1]);

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

Мне казалось я намекал на скорость:
Я не против если ты сможешь навскидку придумать что-то быстрее. Я даже пока представить ничего не могу.

Этим ты глаза вряд ли кому-то откроешь. Да и дело не в реге, а в подходе. Я за регу спокоен, а вот структура кода меня беспокоила.

Была у меня ещё одна идея, грузить всё в дерево и затем уже манипулировать DOM, но так я её и не додумал.

Сначала точка скушает всё вместе с цифирками до последней точки, а затем вернется на один символ назад в сохраненное состояние и получит совпадение с тройкой.

Но вопрос был всё таки только отчасти о регах.

Gozar,
:victory: i != i ;)

Gozar, я наконец дошёл до разбирания того, что ты написал...

Хорошая идея, мне нравится.

P. S. Вообще, то, что по ссылке - ни разу не оптимизированная версия, там просто концепт.

Gozar,
как вариант ...

var i = true;
function fuRep(){
    i = true;
}
while (i) {
    i = false;
    str = str.replace(rega, fuRep);
}

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

Да, мне нравится.

ps: решение мне приснилось, поэтому об оптимизации я и не задумался :)