Парсер 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 — & quot ;, 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/5Xpf3jZ6

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.