Здравствуйте. Хотел бы поделится своим опытом с сообществом 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, , 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 "":
$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 '<p class="bbcode">'.parent::getHTML().'</p>';
}
}
Чуть не забыл про один существенный минус в такой реализации: так как для каждого тега либо текста требуется новый класс — это может существенно нагружать память.
Итоги
У нас получился отличный парсер BBCode, написанный на php. Сам парсер я писал год назад, и вот только сейчас решил рассказать про проделанную работу. Не судите слишком сложно, это мой первый пост. В конце я предоставлю полный исходник парсера BBCode.
Исходный код
Здесь выкладывать не буду, так как весь исходник занимает около 500 строчек кода.
Ссылка на исходный код: pastebin.com/5Xpf3jZ6
Автор: wilcot
