Парсер BBCode без регулярных выражений

в 10:24, , рубрики: bbcode, php, конечный автомат, Регулярные выражения, метки: , , ,

Здравствуйте. Хотел бы поделится своим опытом с сообществом 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

Источник

Поделиться

* - обязательные к заполнению поля