Для одного проекта понадобилось разобрать на кусочки mysql-дамп. Да не просто разобрать, а привести его к такой структуре, с которой было бы удобно работать на PHP. Для решения этой проблемы были рассмотрены три варианта:

• найти готовый парсер mysql-дампов на php;
• быстренько накидать парсер на regexp-ах;
• написать свой лексический анализатор;

Пара запросов в гугл дала результаты, но жажда творить их поборола. Кроме того, необходимость в лексическом анализаторе возникала и раньше, поэтому было решено пойти последним путем и написать универсальный лексический анализатор.

Несколько лет назад решал подобную задачу на С++. Тогда для реализации парсера был выбран boost::spirit за его удобство, достаточно хорошую читаемость и сходство с расширенной формой Бэкуса-Наура (РФБН). Свой лексер тоже захотелось сделать максимально приближенным к ней.

За один вечер лексер был написан. Отмечу, что усиленному тестированию и отладке он не подвергался, потому как использовался пока что лишь для одной задачи. Код местами уродлив и имеет слабые места, о которых будет сказано в конце статьи. В планах его переработать — когда настанет черед следующего анализатора :)

Лучший способ объяснить как им пользоваться — продемонстрировать процесс разработки парсера. Для примера я решил сделать парсер простых математических выражений. Итак, приступим.

Задача.

Необходимо разработать парсер простых математических выражений. Парсер должен уметь разбирать выражения содержащие переменные, числа (десятичные дроби и натуральные), простейшие операции (+, -, *, /) и группировку с использованием скобок. Например, такое:

(a + b) / (c * 3 + d * 10) + (120 / 8 + 4)

Построим грамматику.

За основу возьмем РФБН, но для упрощения добавим возможность использовать регулярные выражения. Для их обозначения будем использовать уже привычные две косые черты. Итак, сначала определим «атомы», из которых состоит выражение.

number = /\d+(?:\.\d+)?/

variable = /[a-z]+/

op = "+" | "-" | "/" | "*"

Самое простейшее выражение — это одиночное число или переменная без использования каких-либо операций:

expression = number | variable

Теперь попробуем составить правило для более сложного выражения, содержащего оператор.

Правило должно выгледять примерно так:

expression = (number | variable) op (number | variable)

number и variable имеют одинаковую ценность для любых выражений (вместо любого числа мы можем подставить переменную равную этому числу и наборот), поэтому для упрощения и сокращения дальнейшей записи вынесем их в отдельное правило:

operand = number | variable

Тогда описание выражения будут иметь вид:

expression = operand op operand

Это уже работоспособные выражение, по которомы мы сможем, к примеру, сложить два числа. Но оно не учитывает простейшее выражение, состоящее из единственного операнда. Объеденим его с первым правилом для выражения:

expression = operand op operand | operand

Обратите внимание! Вторая часть выражения (operand) совпадает с началом первой части (operand op operand).

Если поместить их в другом порядке (т.е. «operand | operand op operand»), то лексер обнаружив первое совпадение выберет его, таким образом он никогда не достигнет второго правила. Например, если мы хотим разобрать строчку «2+3», лексер обнаружит совпадение с числом, а часть "+3" останется. Лексер завершит работу с ошибкой, так как не смог разобрать всю строчку. А еще лучше записать это правило так:

expression = operand [op operand]

или

expression = [operand op] operand

Это правило лишено возможности трактоваться двояко — сначала лексер найдет число, а потом уже проверит на наличие оставшейся части. Первый вариант предпочтительнее, потому как лексер на первом же шаге определит корректность подсутнутого ему выражения, тогда как второй при ошибке в первой части будет проверять вторую.

Итак, наше правило позволяет обработать число и операцию с двумя числами. А как быть, если чисел и операций в выражении больше? Можно сделать так:

expression = operand [{op operand}]

Другой вариант — рекурсия. Вместо того что бы складывать два операнда мы будем складывать операнд и выражение.

expression = operand [op expression]

Тут тоже следует заострить внимание на порядке в выражении. При рекурсии нельзя допускать что бы рекурсируемое правило было в начале (т.н. левая рекурсия), иначе лексер впадет в вечный цикл и никогда из него не вернется.

В моей реализации лексера рекурсия более удобный вариант, так как операция повторения требует на одно правило больше. Поэтому остановимся на рекурсии.

Для более лучшего понимания распишу по шагам действия лексера на примере выражения «1+2+3+4» и правила expression.

1. Лексер проверят на совпадение с первым подправилом (operand) и выделяет из выражения число («1»), оставшуюся строку ("+2+3+4") передает следующему подправилу.
2. Лексер проверят оставшуюся строку ("+2+3+4") на совпадение со вторым подправилом (op expression).
3. Согласно правилу op из строки выделяется оператор ("+"), после чего остаток строки («2+3+4») передается на обработку правилу expression.
4. Даньнешие действия аналогичны пп.1-3, до того момента пока в строке не останется символов.

А что, если мы хотим определять очередность расчета выражения скобочками? По сути скобочки содержат те же самые выражения, поэтому определим правило определяющее выражение в скобочках:

group = "(" expression ")"

Теперь остается лишь добавить это правило в правило операнда:

operand = number | variable | group

Мы получили следующий набор правил:

number = /\d+(?:\.\d+)?/

variable = /[a-z]+/

group = "(" expression ")"

operand = number | variable | group

op = "+" | "-" | "/" | "*"

expression = operand [op expression]

Обратите внимание, правило expression содержит правило operand, которое в свою очередь содержит правило group, а то в свою очередь — expression. При проектировании таких правил нужно быть предельно внимательным, так как достаточно просто отправить лексер в бесконечный цикл. Для проверки необходимо вручную проанализировать всю цепочку, раскрывая правила, например так:

expression = operand [op expression]

expression = {number | variable | group} [op expression]

expression = {number | variable | "(" expression ")"} [op expression]

На первом месте в правиле получилось одно из условий операнда, нас интересует только условие содержащее expression, поэтому можно опустить ненужные условия:

expression = "(" expression ")" [op expression]

Видим, что на первом месте стоит скобка, а значит лексер в цикл не попадет. Если бы мы забыли заключить в скобки expression в правиле group, то получилась бы следующая картина:

expression = expression [op expression]

На первом месте стоит expression — лексер попадает в цикл. В принципе все правила готовы и их можно уже использовать, но пока что лексер не учитывает возможные пробелы. Исправим этот недочет. Определяем правило пробела:

space = /[ \t\r\n]+/

По сути наш пробел это еще и таб и перевод каретки (новая строка). Теперь добавим это правила в остальные. В принципе, можно просто бездумно напихать пробелов куда попало:

expression = [space] operand [space] [[space] op [space] expression [space]] [space]

Выражение работать будет, но страдает его эффективность, так как местами возможно следование двух одинаковых правил подряд. В нашем примере правила не такие уж большие, и если немного подумать, то можно без труда определить эти места и исправить этот недочет. Но когда правил становится очень много, то я рекомендую использовать следующий принцип: Расчищаем дорогу себе, а что осталось сзади нас не волнует — расчистят следующие.

Логика этого принципа проста — если вы идете первым, то дорога еще не расчищена (а вы можете не знать, первым вы идете или нет). За собой же убирать не надо, так как исходя из предыдущего высказывания следующий сам почистит перед собой. То есть правило пробела вставляем только туда, где он может оказаться перед другим правилом.

number = /\d+(?:\.\d+)?/

variable = /[a-z]+/

group = "(" expression [space] ")"

# все эти три правила объеденены в одно, поэтому вместо того

# что бы добавлять пробел в каждое из них можно добавить только в общее

# в правиле group перед expression пробел не нужен, как будет ясно дальше

# единственное, где нужен пробел - перед закрывающей скобкой

operand = number | variable | group

# а это правило в свою очередь используется только в одном месте

# к тому же правило составное, что усложняет добавление пробела в него

op = "+" | "-" | "/" | "*"

# то же самое относится и к этому правилу

expression = [space] operand [[space ]op expression]

# Согласно предыдущим комментариям добавляем space перед operand и op

# Дополнительные пробелы добавлять в правило не требуется -

# в самом начале пробел от operand, между operand и op пробел так же уже

# имеется, между op и expression пробел не требуется, т.к. expression уже

# включает его в себя.

Получившейся набор правил удачно разберет такие строки:

"1+2+3"

"1 + 2 + 3"

" 1+2+3"

Если же пробел окажется в конце строки, то лексер вернет ошибку. Для исправления этой неприятности можно поступить несколькими способами:

1. Добавить [space] в конец expression. Способ рабочий, но в результате во время разбора лексер проверит пробел на конце строки столько раз, сколько было операндов, что не очень хорошо.

2. Добавить новое правило:

expression_space = expression [space]

и использовать именно его для разбора строк

3. Если это правило не используется как первичное, то оставить как есть, а пробел добавлять в родительское правило.

А теперь посмотрим как описать эти правила в скрипте лексера:

// space = /[ \t\r\n]+/

'space' => array(

'rule' => array('/[ \\t\\n\\r]+')

),

# Для записи регулярного выражения используется косая черта (слеш). Завершающий слеш <b>не требуется!</b>

// number = /\d+(?:\.\d+)?/

'number' => array(

'rule' => array('/\\d+(?:\\.\\d+)?')

),

// variable = /[a-z]+/

'variable' => array(

'rule' => array('/[a-z]+')

),

// group = "(" expression [space] ")"

'group' => array(

'rule' => array ('=(', '@expression', '?space', '=)')

),

# Если правило составное, то каждое составляющее является отдельным элементом массива.

# Для сравнения с строкой используется префикс =

# Для ссылки на другое правило префикс @

// operand = number | variable | group

'operand' => array(

'flags' => Lexer::Multi,

'rule' => array(

array('@number'),

array('@variable'),

array('@group')

)

),

# Логика ИЛИ реализуется через добавление флага Lexer::Multi, а составляющие правила записываются как элементы основного правила

// op = "+" | "-" | "/" | "*"

'op' => array(

'flags' => Lexer::Multi,

'rule' => array(

array('=+'),

array('=-'),

array('=/'),

array('=*')

)

),

// expression = [space] operand [[space] op expression]

// для организации необязательной части необходимо заводить отдельное правило

// вместо этого мы использовали логику ИЛИ, т.е. привели правило к виду:

// expression = [space] operand [space] op expression | [space] operand

'expression' => array(

'flags' => Lexer::Multi,

'rule' => array(

array('?space', '@operand', '?space', '@op', '@expression'),

array('?space', '@operand'),

)

)

В лексере существует еще один флаг, который не был использован в примере — Lexer::Repeat. Он аналогичен записи {… } в РФБН, т.е. означает повторение выражения любое число раз. Приведенный набор правил работает и способен разобрать простое математическое выражение, но на выходе ничего не выдаст, потому как не определены правила, которые необходимо учитывать. Для определения учитываемого правила используется элемент handler. Например, так:

'number' => array(

'rule' => array('/\\d+(?:\\.\\d+)?'),

'handler' => 'number'

)

Всем правилам, которые необходимо учитывать нужно указать handler. Наши правила должны принять такой вид:

'space' => array(

'rule' => array('/[ \\t\\n\\r]+')

),

# Пробел учитывать не надо, оставляем как есть

'number' => array(

'rule' => array('/\\d+(?:\\.\\d+)?'),

'handler' => 'number'

),

# Для каждого найденого числа в дерево обработки будет добавлен элемент number, с содержимым на котором правило сработало, т.е. числом

'variable' => array(

'rule' => array('/[a-z]+'),

'handler' => 'variable'

),

'group' => array(

'rule' => array ('=(', '@expression', '?space', '=)'),

'handler' => '@group'

),

# Префикс @ в данном случае означает, что в результат не попадет точное содержимое, на котором сработало правило

# Т.е. в дерево будет добавлен элемент group, но его содержимое (например, "(2 + 3)") добавлено не будет.

'operand' => array(

'flags' => Lexer::Multi,

'rule' => array(

array('@number'),

array('@variable'),

array('@group')

)

),

# операнду ничего не добавляем, т.к. каждое используемое им правило уже имеет handler.

'op' => array(

'flags' => Lexer::Multi,

'rule' => array(

array('=+'),

array('=-'),

array('=/'),

array('=*')

),

'handler' => 'operator'

),

'expression' => array(

'flags' => Lexer::Multi,

'rule' => array(

array('?space', '@operand', '?space', '@op', '@expression'),

array('?space', '@operand'),

)

)

# В выражение ничего не добавляем по той же причине, что и в операнд. Каждое используемое им правило

# уже имеет handler, напрямую (как @op) или косвенно (как @operand).

После отработки такого правила на выражении a + b + (9 / (4 + c) * 2) будет построено следующее дерево:

*

|--variable = "a"

|--operator = "+"

|--variable = "b"

|--operator = "+"

`--group

|--number = "9"

|--operator = "/"

|--group

| |--number = "4"

| |--operator = "+"

| `--variable = "c"

|--operator = "*"

`--number = "2"

Дальше уже средствами PHP можно обойти это дерево и произвести необходимые вычисления. У меня получилась вот такая функция:

// $res - разобранное дерево (e.g. a + 2 / (3 + b))

// $vars - значения переменных (a => 6, b => 1)

function calculate($res, &$vars) {

// $prep - массив для вектора с вычислениями

$prep = array();

// пробегаемся по дереву с целью получения вектора простых операций

foreach ($res as $k => $v) {

// если попалась группа, то рекурсивно обрабатываем ее этой же функцией

// и заносим во временный массив

// (3 + b) -> 4

if ($v['handler'] == '@group') {

array_push($prep, calculate($v['c'], $vars));

}

// если попалось число или оператор, то просто добавляем в массив

elseif ($v['handler'] == 'number' || $v['handler'] == 'operator') {

array_push($prep, $v['text']);

}

// если попалась переменная, то добавляем ее значение в массив

// a -> 6, b -> 1

elseif ($v['handler'] == 'variable') {

array_push($prep, $vars[$v['text']]);

}

}

// 3 + b -> 3 + 1

// a + 2 / (3 + b) -> 6 + 2 / 4

// пробегаемся по получившемуся вектору

// сначала производим вычисления с первостепенными операциями (*, /)

for ($i = 0; $i < count($prep);) {

$k = $prep[$i];

if ($k == '/') {

$c = $prep[$i - 1] / $prep[$i + 1];

array_splice($prep, $i - 1, 3, $c);

}

elseif ($k == '*') {

$c = $prep[$i - 1] * $prep[$i + 1];

array_splice($prep, $i - 1, 3, $c);

}

else {

$i++;

}

}

// 3 + 1 -> 3 + 1

// 6 + 2 / 4 -> 6 + 0.5

// а теперь с второстепенными (+, -)

$res = $prep[0];

for ($i = 1; $i < count($prep); $i+=2) {

if ($prep[$i] == '+') {

$res += $prep[$i + 1];

}

elseif ($prep[1] == '-') {

$res -= $prep[$i + 1];

}

}

// 3 + 1 -> 4

// 6 + 0.5 -> 6.5

// и возвращаем результат!

return $res;

}

Объеденив весь код в кучу получим скрипт, который обрабатывает математическое выражение и выводит результат. Я пошел немного дальше и сделал интерпретатор, небольшого математического калькулятора.

Интерпретатор имеет операцию присваивания и комманду print. Ему можно скормить, например, следующий код:

a = 1 + 4;

b = 128 * 32 + (a / 30);

print "a = ";

print a;

print "\nb = ";

print b;

print "\na + 3 = ";

print a + 3;

print "\n";

В примере интерпретатора вы можете найти еще один способ обработки правила — пользовательские функции.

Правило с пользовательской функцией задается так:

'string' => array(

'rule' => array('_parse_string'),

'handler' => 'string'

);

Префикс "_" означает что для проверки правила будет вызвана следующая за ним функция, в данном случае parse_string(&$str). Пользовательская функция получает в качестве параметра строку $str, если функция нашла необходимое вхождение, то строке $str она должна присвоить остаток строки, а возвращаемое значение должно быть найденным вхождением. Если вхождение не было найдено, то функция должна вернуть false. На примере это выглядит так:

// e.g: $str == 'SUPER string'

function is_SUPER(&$str) {

if (substr($str, 0, 5) == 'SUPER') {

$res = substr($str, 0, 5); // $res = 'SUPER';

// $res == 'SUPER';

$str = substr($str, 5);

// $str == ' string';

return $res;

}

return false;

}

Вот, пожалуй, и всё.

Остается лишь сказать о существенном недостатке текущей версии лексера. В данном виде он не предназначен для обработки больших объемов данных. Алгоритм работает сразу со всем объемом, при этом прибегая к постоянному копированию данных. Поэтому, для решения своей задачи мне пришлось использовать предварительный парсер, разрезающий mysql-дамп на отдельные выражения (до ";" или другого разделителя) для последующей обработки их лексером. В следующей версии я постараюсь избавиться от этого недостатка, используя потоки (streams) и указатели, вместо копирования целой строки.