[Из песочницы] Парсер BBCode без регулярных выражений
Здравствуйте. Хотел бы поделится своим опытом с сообществом Habrahabr. Речь пойдет о разработке не очень сложного парсера BBCode, который преобразует его в HTML. Парсер, который мы будем писать — это типичный конечный автомат.Рассмотрим, чем отличаются обработчики BBCode, основанные на регулярных выражениях, от обработчиков, основанных на конечном автомате, а также их плюсы и минусы.Парсер на регулярках:+ Прост в написании; — Может некорректно обрабатывать BBCode; — Медленно работает (скорость напрямую зависит от объема текста, а также набора поддерживаемых тегов).Парсер на конечном автомате: — Трудный в написании;+ Обработка BBCode идет строго по матрице состояний;+ Быстро работает (обрабатывает текст в один проход).Итак, приступим к написанию Для начала нам нужно рассмотреть, из каких этапов будет состоять наш парсер BBCode, что будет происходить в этих этапах, а также их результаты выполнения.1. Обработка BBCode: Заключается в преобразовании BBCode вида: [b]Hello World![/b] @l; bbcode/@r; [img=«hello_world.jpg»/] В массив:
Array ( [0] => Array ([type] => open, [text] => [b], [attrib] => Array (), [tag] => b) [1] => Array ([type] => text, [text] => Hello World!) [2] => Array ([type] => close, [text] => [/b], [attrib] => Array (), [tag] => b) [3] => Array ([type] => text, [text] => @l; bbcode/@r;) [4] => Array ([type] => open/close, [text] => [img=«hello_world.jpg»/], [attrib] => Array ([img] => hello_world.jpg), [tag] => img) ) Скорее всего это самый сложный процесс, в котором как раз и будет участвовать наш конечный автомат. Сам наш процесс разделен на 2 функции: getToken и parse.
getToken — эта функция которая разбивает текст на токены, рассмотрим какие типы токенов у нас будут:1 — [, 2 — ], 3 — », 4 — ', 5 — =, 6 — /, 7 — пробел, 8 — \r, \n, \0, \x0B, 9 — имя тега, 0 — Все остальное.
Ниже приведен код функции:
private function getToken () { $token = ''; $token_type = false; $char_type = false; while (true) { $token_type = $char_type; if (! isset ($this→source[$this→cursor])) { if ($char_type === false) { return false; } else { break; } } $char = $this→source[$this→cursor]; switch ($char) { case '[': $char_type = 1; break; case ']': $char_type = 2; break; case '»': $char_type = 3; break; case »'»: $char_type = 4; break; case '=': $char_type = 5; break; case '/': $char_type = 6; break; case ' ': $char_type = 7; break; case »\n»: $char_type = 8; break; case »\r»: $char_type = 8; break; case »\0»: $char_type = 8; break; case »\x0B»: $char_type = 8; break; default: $char_type = 0; break; } if ($token_type === false) { $token = $char; } else if ($token_type > 0) { break; } else if ($token_type == $char_type) { $token .= $char; } else { break; } $this→cursor++; } if ($token_type == 0 && isset ($this→tags[$token])) { $token_type = 9; } return array ($token_type, $token); } parse — это собственно наш конечный автомат, вся его логика заключена в массиве состояний: $finite_automaton. Начальное состояние автомата $mode = 0, при обработке токена состояние меняется на $mode = $finite_automaton[$mode][$token] и выполняется соответствующее номеру состояния действие.
Ниже приведен код конечного автомата:
private function parse () { $this→cursor = 0; $this→syntax = array (); $finite_automaton = array ( 0 => array (0, 1, 0, 0, 0, 0, 0, 0, 0, 0), 1 => array (7, 20, 7, 7, 7, 7, 3, 7, 7, 2), 2 => array (7, 20, 5, 7, 7, 19, 6, 8, 7, 7), 3 => array (7, 20, 7, 7, 7, 7, 7, 7, 7, 4), 4 => array (7, 20, 5, 7, 7, 7, 7, 7, 7, 7), 5 => array (0, 1, 0, 0, 0, 0, 0, 0, 0, 0), 6 => array (7, 20, 5, 7, 7, 7, 7, 7, 7, 7), 7 => array (0, 1, 0, 0, 0, 0, 0, 0, 0, 0), 8 => array (9, 20, 7, 7, 7, 19, 6, 7, 7, 9), 9 => array (7, 20, 7, 7, 7, 10, 6, 17, 7, 7), 10 => array (11, 20, 7, 12, 15, 7, 7, 18, 7, 11), 11 => array (7, 20, 5, 7, 7, 7, 6, 8, 7, 7), 12 => array (13, 20, 7, 14, 13, 13, 13, 13, 13, 13), 13 => array (13, 20, 7, 14, 13, 13, 13, 13, 13, 13), 14 => array (7, 20, 5, 7, 7, 7, 6, 8, 7, 7), 15 => array (16, 20, 7, 16, 14, 16, 16, 16, 16, 16), 16 => array (16, 20, 7, 16, 14, 16, 16, 16, 16, 16), 17 => array (7, 20, 7, 7, 7, 10, 6, 7, 7, 7), 18 => array (11, 20, 7, 12, 15, 7, 7, 7, 7, 11), 19 => array (11, 20, 7, 12, 15, 7, 7, 18, 7, 11), 20 => array (7, 20, 7, 7, 7, 7, 3, 7, 7, 2) ); $mode = 0; $pointer = -1; $last_tag = null; $last_attrib = null; while ($token = $this→getToken ()) { $mode = $finite_automaton[$mode][$token[0]]; switch ($mode) { case 0: if (isset ($this→syntax[$pointer]) && $this→syntax[$pointer]['type'] == 'text') { $this→syntax[$pointer]['text'] .= $token[1]; } else { $this→syntax[++$pointer] = array ('type' => 'text', 'text' => $token[1]); } break; case 1: $last_tag = array ('type' => 'open', 'text' => $token[1], 'attrib' => array ()); break; case 2: $last_tag['tag'] = $token[1]; $last_tag['text'] .= $token[1]; $last_attrib = $token[1]; break; case 3: $last_tag['type'] = 'close'; $last_tag['text'] .= $token[1]; break; case 4: $last_tag['tag'] = $token[1]; $last_tag['text'] .= $token[1]; break; case 5: $last_tag['text'] .= $token[1]; $pointer++; $this→syntax[$pointer] = $last_tag; $last_tag = null; break; case 6: $last_tag['type'] = 'open/close'; $last_tag['text'] .= $token[1]; break; case 7: $last_tag['text'] .= $token[1]; if (isset ($this→syntax[$pointer]) && $this→syntax[$pointer]['type'] == 'text') { $this→syntax[$pointer]['text'] .= $last_tag['text']; } else { $this→syntax[++$pointer] = array ('type' => 'text', 'text' => $last_tag['text']); } $last_tag = null; break; case 8: $last_tag['text'] .= $token[1]; break; case 9: $last_tag['text'] .= $token[1]; $last_tag['attrib'][$token[1]] = ''; $last_attrib = $token[1]; break; case 10: $last_tag['text'] .= $token[1]; break; case 11: $last_tag['text'] .= $token[1]; $last_tag['attrib'][$last_attrib] = $token[1]; break; case 12: $last_tag['text'] .= $token[1]; break; case 13: $last_tag['text'] .= $token[1]; $last_tag['attrib'][$last_attrib] .= $token[1]; break; case 14: $last_tag['text'] .= $token[1]; break; case 15: $last_tag['text'] .= $token[1]; break; case 16: $last_tag['text'] .= $token[1]; $last_tag['attrib'][$last_attrib] .= $token[1]; break; case 17: $last_tag['text'] .= $token[1]; break; case 18: $last_tag['text'] .= $token[1]; break; case 19: $last_tag['text'] .= $token[1]; $last_attrib = $last_tag['tag']; break; case 20: if ($this→syntax[$pointer]['type'] == 'text') { $this→syntax[$pointer]['text'] .= $last_tag['text']; } else { $this→syntax[++$pointer] = array ('type' => 'text', 'text' => $last_tag['text']); } $last_tag = array ('type' => 'open', 'text' => $token[1], 'attrib' => array ()); break; } } if (isset ($last_tag)) { if (isset ($this→syntax[$pointer]) && $this→syntax[$pointer]['type'] == 'text') { $this→syntax[$pointer]['text'] .= $last_tag['text']; } else { $pointer++; $this→syntax[$pointer] = array ('type' => 'text', 'text' => $last_tag['text']); } } } На этом наш этап заканчивается.
2. Нормализация На этом этапе мы преобразуем наш массив с учетом вложенности элементов. Не зря мы храним для каждого тега параметр text — в случае, если тег имеет некорректное расположение, он преобразуется в текст, который, собственно, и хранится у нас в параметре text.Ниже представлен код:
private function normalize () { $stack = array (); foreach ($this→syntax as $key => $node) { switch ($node['type']) { case 'open': if (count ($stack) == 0) { $allowed = $this→root_tags; } else { $allowed = $this→tags[$stack[count ($stack)-1]]['children']; } if (array_search ($node['tag'], $allowed) !== false) { if ($this→tags[$node['tag']]['closed']) { $this→syntax[$key]['type'] = 'open/close'; } else { array_push ($stack, $node['tag']); } } else { $this→syntax[$key] = array ('type' => 'text', 'text' => $node['text']); } break; case 'close': if (count ($stack) > 0 && $node['tag'] == $stack[count ($stack)-1]){ array_pop ($stack); } else { $this→syntax[$key] = array ('type' => 'text', 'text' => $node['text']); } break; case 'open/close': if (count ($stack) <= 0) { $allowed = $this->root_tags; } else { $allowed = $this→tags[$stack[count ($stack)-1]]['children']; } if (array_search ($node['tag'], $allowed) === false) { $this→syntax[$key] = array ('type' => 'text', 'text' => $node['text']); } break; } } } 3. Преобразование в DOM Самый последний и интересный этап — это преобразование массива в дерево объектов. Тут у нас будет 2 основных класса: класс Tag и класс Text. Tag — это родительский класс для всех тегов, Text — как вы уже догадались, это класс, хранящий Text. Оба эти класса наследуют класс Node, который просит реализовать функцию getHTML.Ниже приведен код этих 3 классов:
abstract class Node { abstract public function getHTML (); protected function specialchars ($string) { $chars = array ( '[' => '@l;', ']' => '@r;', '»' => '@q;', »'» => '@a;', '@' => '@at;' ); return strtr ($string, $chars); }
protected function unspecialchars ($string) { $chars = array ( '@l;' => '[', '@r;' => ']', '@q;' => '»', '@a;' => »'», '@at;' => '@' ); return strtr ($string, $chars); } }
class Tag extends Node { public $parent = null; public $children = array (); public $attrib = array (); public function __construct ($parent, $attrib) { $this→parent = $parent; $this→attrib = (array) $attrib; } public function getHTML () { $html = ''; foreach ($this→children as $child) { $html .= $child→getHTML (); } return $html; } public function getAttrib ($name) { return $this→unspecialchars ($this→attrib[$name]); } public function hasAttrib ($name) { return isset ($this→attrib[$name]); } }
class Text extends Node { public $parent = null; public $text = ''; public function __construct ($parent, $text) { $this→parent = $parent; $this→text = (string) $text; } public function getHTML () { return htmlspecialchars ($this→unspecialchars ($this→text)); } } Кстати, сам класс парсера BBCode наследует класс Tag, так как BBCode у нас — это корневой элемент.
Так, с классами для DOM мы разобрались, теперь давайте же создадим этот DOM. Ниже приведен код создания DOM:
private function createDOM () { $current = $this; foreach ($this→syntax as $node) { switch ($node['type']) { case 'text': $child = new Text ($current, $node['text']); array_push ($current→children, $child); break; case 'open': $tag_class = $this→tags[$node['tag']]['class']; $class = (class_exists ($tag_class, false)) ? $tag_class: 'Tag'; $child = new $class ($current, $node['attrib']); array_push ($current→children, $child); $current = $child; break; case 'close': $current = $current→parent; break; case 'open/close': $tag_class = $this→tags[$node['tag']]['class']; $class = (class_exists ($tag_class, false)) ? $tag_class: 'Tag'; $child = new $class ($current, $node['attrib']); array_push ($current→children, $child); break; } } } Вот и все, на этом обработка BBCode полностью завершена.
Теги и расширяемость Как уже писалось выше, все теги наследуют у нас класс Tag. Вот пример нашего тега: class Tag_P extends Tag { public function getHTML () { return '
'.parent: getHTML ().'
'; } } Чуть не забыл про один существенный минус в такой реализации: так как для каждого тега либо текста требуется новый класс — это может существенно нагружать память.Итоги У нас получился отличный парсер BBCode, написанный на php. Сам парсер я писал год назад, и вот только сейчас решил рассказать про проделанную работу. Не судите слишком сложно, это мой первый пост. В конце я предоставлю полный исходник парсера BBCode.Исходный код Здесь выкладывать не буду, так как весь исходник занимает около 500 строчек кода.Ссылка на исходный код: pastebin.com/5Xpf3jZ6
