How to become an author
Search
Write a publication
Pull to refresh

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

Reading time8 min
Views7.1K
PHP*
From sandbox
Здравствуйте. Хотел бы поделится своим опытом с сообществом Habrahabr. Речь пойдет о разработке не очень сложного парсера BBCode, который преобразует его в HTML. Парсер, который мы будем писать — это типичный конечный автомат.
Прошу не судить слишком строго, так как это мой первый опыт в написании статей на хабре.

Рассмотрим, чем отличаются обработчики BBCode, основанные на регулярных выражениях, от обработчиков, основанных на конечном автомате, а также их плюсы и минусы.

Парсер на регулярных выражениях:

+ Прост в написании;
+ Малый объем кода;
— Может некорректно обрабатывать BBCode (при правильном написании обрабатывает корректно);
— Медленно работает (обычно обрабатывает текст в несколько проходов, скорость зависит от объема текста, а также от набора поддерживаемых тегов).

Парсер на конечном автомате:

— Трудный в написании;
— Большой объем кода;
+ Обработка BBCode идет строго по матрице состояний;
+ Быстро работает (обрабатывает текст в один проход, скорость зависит только от объема текста).

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

Итак, приступим к написанию


Для начала нам нужно рассмотреть, из каких этапов будет состоять наш парсер 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 '<p class="bbcode">'.parent::getHTML().'</p>';
	}
	
}


Чуть не забыл про один существенный минус в такой реализации: так как для каждого тега либо текста требуется новый класс — это может существенно нагружать память.

Итоги


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

Исходный код


Здесь выкладывать не буду, так как весь исходник занимает около 500 строчек кода.

Ссылка на исходный код: pastebin.com/er43Kbmc
Tags:
Hubs:
Total votes 25: ↑13 and ↓12+1
Comments21
0
Karma
0
Rating
Иван Удовин @wilcot

User

Send message

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr