Парсер данных по произвольной грамматике в 400 строк
Есть много существующих инструментов для парсинга файлов по заданной грамматике. Например, ANTLR или Yacc. Они используют конечные автоматы и генерируют большие файлы с исходным кодом для парсинга. Действительно ли это так сложно? Попробуем сделать сами.
В этой статье я покажу, как можно сделать такой парсер методом рекурсивного спуска. Для сравнения я буду говорить об ANTLR, другие парсеры не рассматриваются.
Будем делать парсер для грамматик в ANTLR-like виде. Вот в таком:
C:
| A1? A2* A3
| B1? B2+ B3
;Делать будем на языке PHP. А если получится нормально, перепишем на C++.
(Под катом много примеров кода)
Зачем? Ну у того же ANTLR есть свои ограничения. Например, довольно сложно сделать грамматику для ассемблерной вставки в языке C++ asm { ... }, внутри которой другой синтаксис, или синтаксис строк Nowdoc в PHP. Также есть неудобные мелочи, в файле грамматики приходится писать »:» на другой строке, чтобы выравнивалось с »|». И вообще, это большая и сложная штука, вдруг можно сделать проще.
Определимся с терминологией.
Все описание целиком — это правило (Rule). В примере выше определяется правило C. Правило состоит из одного или нескольких вариантов.
Один вариант правила — это утверждение (Statement). По аналогии со «statement» в языках программирования, законченное действие, состоящее из нескольких частей. Здесь у правила 2 варианта. Можно было бы назвать Variant (или Alternative, как в ANTLR), но у большинства правил один вариант, и это название как-то не очень подходит.
Statement состоит из одного или нескольких выражений (Expression). По аналогии с regular expressions, потому что похожи по функциональности, и с языками программирования, как составная часть statement. Здесь по 3 выражения в каждом варианте.
Expression состоит из элемента (Element) и необязательного квантификатора (Quantifier). Quantifier это стандартный значок из регулярных выражений — ?, *, +.
Element может быть названием другого правила либо терминальным элементом — строкой в одиночных кавычках из одного или нескольких символов ('a') или простым регулярным выражением для одного символа: для конкретного символа в квадратных скобках ([a-z]) или для любого символа в виде точки (.). В примере не показаны. В тексте этой статьи, если речь идет о грамматике, под названием «регулярное выражение» всегда подразумевается выражение для одного символа.
Грамматика
Такую структуру можно описать языке грамматик. Грамматика для парсинга грамматик.
Начнем с главного правила.
Grammar:
delimiter* Rule*
;
delimiter:
| space
| comment
;
space:
[\s\n\t\r]+
;Сначала будем парсить каждый байт, включая пробелы. Потом я покажу, как это можно изменить. Я сделал для универсальности чтобы »\s» означал обычный пробел с кодом 0×20, а не любой пробельный символ, как в обычных регулярных выражениях.
Но пробелы в результате парсинга нам не нужны. Сделаем так, будем обозначать такие правила названием с маленькой буквы и будем пропускать их в обработке.
Комментарии, как же без них.
И тут мы встречаем хитрый момент. Логично было бы описать его вот так:
comment:
'/*' .* '*/'
;Но выражение .* будет парсить любой символ включая начало закрывающей последовательности '*', и комментарий никогда не закончится. Значит надо как-то обозначать, что нужно всегда проверять следующий элемент, и заканчивать обработку квантификатора '*' если он встретился. В регулярных выражениях это называется lookahead.
Сделаем вот так:
comment:
'/*' AnySymbol*>> '*/'
;Заодно вынесем точку в отдельное правило для лучшей читаемости. Оно пригодится и для строк.
Но может быть так, что квантификатор находится в другом правиле, поэтому нужна возможность задавать заканчивающий элемент без добавления его в результат парсинга.
comment:
'/*' content '*/'
;
content:
AnySymbol*>'*/'
;То есть две стрелочки означают, что элемент для lookahead берется из следующего выражения, а одна что элемент указан сразу после нее и в парсинге сам по себе не участвует. Квантификатор для него не нужен, так как достаточно встретить его 1 раз.
В обычных регулярных выражениях используются 2 разных формы, ленивые выражения 'a*? b' и специальная конструкция 'a*(?=b)'. Вторую сложнее парсить, а первая содержит 2 квантификатора, это сложнее обрабатывать и вообще не очень наглядно.
Структура правила. Ну тут все просто.
Rule:
RuleName delimiter* ':' delimiter* RuleBody ';' delimiter*
;
RuleName:
ID
;
ID:
[a-zA-Z_] [a-zA-Z_0-9]*
;Разделитель надо ставить после каждого элемента, который в своем составе не имеет разделителя в конце. Для начальных пробелов есть delimiter* в начале главного правила Grammar.
Варианты правила.
RuleBody:
'|'? delimiter* Statement ('|' delimiter* Statement)*
;
Statement:
Expression+
;Нам нужна конструкция для задания inline-правила без названия. Можно обойтись только именованными, но так нагляднее, и код так проще.
Выражение и элемент.
Expression:
Element Quantifier? LookAhead? delimiter*
;
Element:
| RuleName
| StringLiteral
| RegexpLiteral
| InlineRule
;
Quantifier:
| '*'
| '?'
| '+'
;
LookAhead:
| '>>'
| '>' Element
;
InlineRule:
'(' RuleBody ')'
;Элемент содержит 4 варианта, для которых нужно будет задать обработку. Квантификатор для конкретного количества тоже добавим, но позже.
Строки и регэкспы.
StringLiteral:
'\'' Symbol+>> '\''
;
RegexpLiteral:
| '[' SymbolRange+>> ']'
| AnySymbolLiteral
;
SymbolRange:
Symbol>']' ('-' Symbol>']')?
;
Symbol:
| HexCodeSymbol
| EscapedSymbol
| AnySymbol
;
HexCodeSymbol:
'\\x' HexDigit HexDigit
;
HexDigit:
[0-9A-F]
;
EscapedSymbol:
'\\' AnySymbol
;
AnySymbol:
.
;
AnySymbolLiteral:
'.'
;Здесь надо отметить, что RegexpLiteral задает отдельный символ, квантификаторы обрабатываются на другом уровне, так как применяются к любым элементам. По сути мы и пишем продвинутый движок регулярных выражений.
Пустые строки и регэкспы в описании грамматики запрещены. Для регэкспа надо задавать закрывающий символ через lookahead отдельно, иначе такие выражения как [] или [a-] будут парситься неправильно.
Для универсальности символ можно задавать через его шестнадцатеричный код. Например, пробел можно задать через \x20. Это дает возможность парсить двоичные данные.
Это минимальная рабочая структура. Дальше мы ее дополним, но пока этого достаточно.
Как можно заметить, этот язык имеет свои особенности. Я назвал его GDL — Grammar Definition Language.
Скопируем все это в файл и назовем его self.gdl.
Парсер
Парсер будет работать следующим образом.
Результат парсинга выражения — это массив значений вида (название элемента, результат парсинга элемента). Можно считать, что любое выражение содержит квантификатор, который задает допустимое количество элементов в массиве. Пустой массив для квантификаторов * и ? это правильное значение. Название элемента это название правила либо пустая строка для строк и регэкспов. Название у всех значений получается одно и то же, но плоский массив удобнее в обработке. Результат парсинга элемента это тоже массив либо строка. То есть получается дерево.
Результат парсинга утверждения — это конкатенация результатов парсинга всех выражений. Такой же массив, только больше.
Результат парсинга правила — это результат парсинга первого подходящего утверждения.
Результат парсинга строк и регэкспов — это строка из входных данных. Понятно, что для строк результат парсинга совпадает со строкой, заданной в грамматике.
Ошибка парсинга обозначается значением null.
При парсинге правила, если утверждение возвращает ошибку, проверяется следующее утверждение (логический оператор ИЛИ).
При парсинге утверждения, если выражение возвращает ошибку, сразу возвращается ошибка (логический оператор И).
При парсинге выражения, если количество не совпадает с заданным квантификатором, возвращается ошибка.
Входные данные: aaab.
/* грамматика */
Data:
'a'* 'b' 'c'?
;
/* результат парсинга */
['Data', [
['', 'a'],
['', 'a'],
['', 'a'],
['', 'b'],
]]
/* грамматика */
Data:
R1* R2 R3?
;
R1: 'a';
R2: 'b';
R3: 'c';
/* результат парсинга */
['Data', [
['R1', [
['', 'a'],
]],
['R1', [
['', 'a'],
]],
['R1', [
['', 'a'],
]],
['R2', [
['', 'b'],
]],
]]Может показаться, что скобок слишком много для ситуации, когда в правилах по одному элементу, но подход «массив либо строка» простой и универсальный.
Можно было бы сделать специальную форму правила R1:= 'a'; и брать первый элемент из результата, тогда результат был бы ['R1', 'a'], но на производительность или читаемость кода это почти не влияет, и вводить для этого отдельную сущность нет смысла.
С чего бы нам начать. У нас уже есть структурированный файл с собственной грамматикой, который мы могли бы распарсить и получить дерево, которое потом использовать в коде, но ведь парсер нам и надо написать. Можно пойти простым и длинным путем — написать код для парсинга с preg_match() и explode(), распарсить файл, экспортировать результат в виде объявления массива в PHP файл, и переписать код нормально. А можно посложнее, но короче — представить как должен работать движок, какой он должен выдавать результат, и написать массив вручную. Тут главное не запутаться где что, где парсинг грамматики, а где парсинг по правилу этой грамматики, где правило StringLiteral, а где парсинг строковой константы по этому правилу.
Если у нас будет готовый массив-дерево, то парсить файл self.gdl нам конечно уже не нужно. Но файл с грамматикой это просто массив байтов. Если мы напишем такой движок, который его распарсит по грамматике из написанного вручную массива, мы сможем им парсить вообще любые файлы по заданной грамматике, а не только наш. То есть например, сначала парсим с помощью своей грамматики из массива файл с грамматикой PHP, а потом тем же движком с помощью грамматики PHP парсим файл с исходным кодом на PHP.
С учетом правил, написанных выше, получится такой массив:
$selfGrammar = ['Grammar', [
['Rule', [
['RuleName', 'Grammar'],
['RuleBody', [
['Statement', [
['Expression', [
['Element', [
['RuleName', 'delimiter'],
]],
['Quantifier', [['', '*']]],
]],
['Expression', [
['Element', [
['RuleName', 'Rule'],
]],
['Quantifier', [['', '*']]],
]],
]],
]],
]],
['Rule', [
['RuleName', 'delimiter'],
['RuleBody', [
['Statement', [
['Expression', [
['Element', [
['RuleName', 'space'],
]],
]],
]],
['Statement', [
['Expression', [
['Element', [
['RuleName', 'comment'],
]],
]],
]],
]],
]],
['Rule', [
['RuleName', 'space'],
['RuleBody', [
['Statement', [
['Expression', [
['Element', [
['RegexpLiteral', [
['SymbolRange', [
['Symbol', [['AnySymbol', [['', ' ']]]]],
]],
['SymbolRange', [
['Symbol', [['EscapedSymbol', [['AnySymbol', [['', 'n']]]]]]],
]],
['SymbolRange', [
['Symbol', [['EscapedSymbol', [['AnySymbol', [['', 't']]]]]]],
]],
['SymbolRange', [
['Symbol', [['EscapedSymbol', [['AnySymbol', [['', 'r']]]]]]],
]],
]],
]],
['Quantifier', [['', '+']]],
]],
]],
]],
]],
...
]];Полный код можно найти в репозитории.
Для понятности приведу отдельный символ с другим форматированием.
['Symbol', [
['EscapedSymbol', [
['AnySymbol', [
['', 'n'],
]],
]],
]],Дальше я покажу, как можно сделать символ обычной строкой без введения специальных проверок в коде движка, работаем мы по своей грамматике или по другой.
Значение RuleName на самом деле тоже должно раскладываться на символы, об этом ниже, но в виде строки получается более читабельно.
Напрашивается мысль, что для структуры (название элемента, результат парсинга элемента) надо завести отдельный класс. Так и сделаем. Это узел дерева, назовем его GdlNode.
class GdlNode
{
/** @var string */
protected $name;
/** @var static[]|string */
protected $value;
protected $hashValue = [];
public function __construct($name, $value)
{
$this->name = $name;
$this->value = $value;
$this->init();
}
public function init()
{
if (is_array($this->value)) {
foreach ($this->value as &$element) {
$this->hashValue[$element->getName()][] = $element;
}
unset($element);
}
}
public function getName()
{
return $this->name;
}
public function getValue()
{
return $this->value;
}
public function setValue($value)
{
$this->value = $value;
$this->init();
}
public function get($name): ?GdlNode
{
return $this->hashValue[$name][0] ?? null;
}
public function getFirst()
{
return $this->value[0];
}
/**
* @param string $name
* @return GdlNode[]
*/
public function getArray($name): array
{
return $this->hashValue[$name] ?? [];
}
public function toString()
{
if (is_null($this->value)) {
return null;
}
if (is_string($this->value)) {
return $this->value;
}
$str = [];
foreach ($this->value as $n => $item) {
$str[] = $item->toString();
}
return implode('', $str);
}
public function toArray()
{
$name = $this->getName();
$value = [];
if (is_array($this->value)) {
foreach ($this->value as $element) {
$elementRes = $element->toArray();
$value[] = $elementRes;
}
}
else {
$value = $this->value;
}
return [$name, $value];
}
}Тут надо обратить внимание на функции get($name) и getArray($name). Это основные функции для работы с деревом, $name это название правила.
Использование выглядит так:
/** @var GdlNode $grammar */
foreach ($grammar->getArray('Rule') as $rule) {
echo $rule->get('RuleName')->toString() . "\n";
}Еще есть полезная функция toString(), если значение узла это массив, она рекурсивно собирает его в одну строку. Ее можно использовать в коде или для отладки.
RuleName в нашей граммамтике определяется через регулярное выражение [a-zA-Z_] [a-zA-Z_0-9]*, поэтому если мы напишем правильный парсер в соответствии с правилами выше, в результате парсинга значением RuleName будет массив отдельных символов, а не строка, как задано в массиве $selfGrammar. toString() позволяет убрать это различие. Но ее постоянное использование при парсинге замедляет выполнение, поэтому потом мы ее уберем. Для узлов Symbol можно было бы тоже написать не ['AnySymbol', [['', ' ']]], а ['AnySymbol', ' '] и использовать toString(), но я описал их подробно, чтобы показать, что происходит под капотом, и как они будут изменяться при изменениях движка.
В коде приложения массив с грамматикой преобразуется в объект GdlNode отдельной функцией. Можно было бы сразу писать для всех элементов new GdlNode(...), но с массивом лучше читается, и так редактировать проще.
Также в репозитории есть класс для потока символов Stream. Это не файловый поток, на вход передается обычная PHP-строка. Он хранит текущую позицию и при чтении символа увеличивает ее. Есть функции для получения и установки позиции, они нужны для работы парсинга.
Теперь можно делать сам парсер.
class GdlParser
{
/** @var GdlNode[] Keys are rule names */
protected $ruleMap;
/** @var Stream */
protected $stream;
public function __construct(GdlNode $grammar)
{
$this->initRules($grammar);
}
public function initRules(GdlNode $grammar)
{
$this->ruleMap = [];
foreach ($grammar->getArray('Rule') as $rule) {
$this->ruleMap[$rule->get('RuleName')->toString()] = $rule;
}
}
public function parse(string $mainRuleName, Stream $stream)
{
$this->stream = $stream;
$rule = $this->getRule($mainRuleName);
$result = $this->parseRule($rule);
return $result;
}
...
}Конструктор и точка входа. Сделано таким образом, чтобы можно было один раз создать объект парсера и парсить им разные файлы.
protected function parseRule(GdlNode $rule)
{
$ruleName = $rule->get('RuleName');
$ruleNameStr = ($ruleName !== null ? $ruleName->toString() : '()');
$parsedRule = null;
$statementList = $rule->get('RuleBody')->getArray('Statement');
$initialPos = $this->stream->getPos();
foreach ($statementList as $statement) {
$parsedRule = $this->parseStatement($statement);
if ($parsedRule !== null) {
break;
}
// try parse next variant from same position
$this->stream->setPos($initialPos);
}
return ($parsedRule === null ? null : new GdlNode($ruleNameStr, $parsedRule));
}Реализуем оператор ИЛИ для Statement. Запоминаем позицию потока, проверяем по очереди каждый Statement, если парсинг не удался, восстанавливаем позицию и проверяем следущий.'()' это специальное название для inline-правила без названия. Оно нужно временно, чтобы вызывающая функция могла отличить его от строк. Мы не можем использовать текстовое название, так как оно может совпадать с каким-то названием правила в грамматике, у нас же универсальный парсер для любой грамматики. Можно было вынести в константу, но тогда все строки надо выносить в константы.
protected function parseStatement(GdlNode $statement)
{
$parsedStatement = [];
$expressionList = $statement->getArray('Expression');
foreach ($expressionList as $i => $expression) {
$lookAheadElement = null;
$lookAhead = $expression->get('LookAhead');
if ($lookAhead !== null) {
if ($lookAhead->get('Element') !== null) {
$lookAheadElement = $lookAhead->get('Element');
}
elseif (isset($expressionList[$i + 1])) {
$lookAheadElement = $expressionList[$i + 1]->get('Element');
}
}
$parsedExpression = $this->parseExpression($expression, $lookAheadElement);
if ($parsedExpression === null) {
$parsedStatement = null;
break;
}
if (!empty($parsedExpression)) {
// skip elements with name started with small letter
$name = $parsedExpression[0]->getName(); // all parsed elements in expression have same name
$isSmallLetter = (!empty($name) && ($name[0] >= 'a' && $name[0] <= 'z'));
if (!$isSmallLetter) {
if ($name === '()') {
foreach ($parsedExpression as $inlineRule) {
$this->addToParsedStatement($parsedStatement, $inlineRule->getValue());
}
}
else {
$this->addToParsedStatement($parsedStatement, $parsedExpression);
}
}
}
}
return $parsedStatement;
}
protected function addToParsedStatement(array &$parsedStatement, array $parsedExpression)
{
foreach ($parsedExpression as $parsedElement) {
$parsedStatement[] = $parsedElement;
}
}Реализуем оператор И для Expression. Парсим каждый Expression, если парсинг одного не удался, значит не удался парсинг всего Statement. Учитываем LookAhead. Названия правил с маленькой буквы пропускаем. Для inline-правил есть специальная обработка, содержимое каждого узла добавляем в результат парсинга.
Пропускать результаты с пустыми названиями нельзя, потому что тогда мы вообще ничего не распарсим, так как всё сводится к строкам и регэкспам.
protected function parseExpression(GdlNode $expression, ?GdlNode $lookAheadElement = null)
{
$element = $expression->get('Element');
$quantifier = $expression->get('Quantifier');
$quantifierType = null;
if ($quantifier !== null) {
$quantifierType = $quantifier->get('')->getValue();
}
$parsedElementList = [];
while (true) {
$initialElementPos = $this->stream->getPos();
$parsedLookAheadElement = null;
if ($lookAheadElement !== null) {
$parsedLookAheadElement = $this->parseElement($lookAheadElement);
$this->stream->setPos($initialElementPos);
if ($parsedLookAheadElement !== null) {
break;
}
}
$parsedElement = $this->parseElement($element);
if ($parsedElement !== null) {
$parsedElementList[] = $parsedElement;
}
else {
$this->stream->setPos($initialElementPos);
break;
}
if ($quantifierType === null || $quantifierType === '?') {
break;
}
}
$countDoesNotMatch = (($quantifierType === null || $quantifierType === '+') ? empty($parsedElementList) : false);
if ($countDoesNotMatch) {
$parsedElementList = null;
}
return $parsedElementList;
}Реализуем обработку квантификатора и LookAhead. Несовпадение количества означает, что парсинг не удался.
protected function parseElement(GdlNode $element)
{
$specificElement = $element->getFirst();
$elementType = $specificElement->getName();
if ($elementType === 'RuleName') {
$rule = $this->getRule($specificElement->toString());
$parsedElement = $this->parseRule($rule);
}
elseif ($elementType === 'StringLiteral') {
$parsedElement = $this->parseStringLiteral($specificElement);
}
elseif ($elementType === 'RegexpLiteral') {
$parsedElement = $this->parseRegexpLiteral($specificElement);
}
elseif ($elementType === 'InlineRule') {
$parsedElement = $this->parseRule($specificElement);
}
else {
throw new Exception('Unknown element type: ' . $elementType);
}
return $parsedElement;
}Реализуем выбор обработки в зависимости от типа элемента, тип определяется по названию правила. Inline-правило и обычное правило обрабатываются одной функцией.
Тут на самом деле спорный вопрос, где правильнее создавать объект GdlNode, в parseElement() или в конкретных функциях. Если будет нужна возможность задавать label для выражения, как в ANTLR, тогда создавать его в parseRule() не получится, ну или надо будет делать метод setName() в GdlNode, что выглядит не так чисто.
protected function parseStringLiteral(GdlNode $element)
{
$parsedValue = null;
$symbolList = $element->getArray('Symbol');
foreach ($symbolList as $symbol) {
if ($this->stream->eof()) {
$parsedValue = null;
break;
}
$contentSymbol = $this->stream->readSymbol();
$str = $this->getSymbolStr($symbol);
if ($contentSymbol !== $str) {
$parsedValue = null;
break;
}
$parsedValue .= $contentSymbol;
}
return ($parsedValue === null ? null : new GdlNode('', $parsedValue));
}Парсинг строки, каждый символ должен совпадать.
protected function parseRegexpLiteral(GdlNode $element)
{
$parsedValue = null;
if (!$this->stream->eof()) {
$contentSymbol = $this->stream->readSymbol();
if ($element->get('AnySymbolLiteral') !== null) {
$parsedValue = $contentSymbol;
}
else {
$symbolRangeList = $element->getArray('SymbolRange');
foreach ($symbolRangeList as $symbolRange) {
$symbolList = $symbolRange->getArray('Symbol');
if (count($symbolList) === 2) {
$strFrom = $this->getSymbolStr($symbolList[0]);
$strTo = $this->getSymbolStr($symbolList[1]);
// use build-in PHP string comparison
if ($contentSymbol >= $strFrom && $contentSymbol <= $strTo) {
$parsedValue = $contentSymbol;
break;
}
}
elseif (count($symbolList) === 1) {
$str = $this->getSymbolStr($symbolList[0]);
if ($contentSymbol === $str) {
$parsedValue = $contentSymbol;
break;
}
}
}
}
}
return ($parsedValue === null ? null : new GdlNode('', $parsedValue));
}Парсинг регулярного выражения, один символ. Обработка диапазонов и выражения для любого символа.
protected $escapedSymbols = ['s' => ' ', 't' => "\t", 'r' => "\r", 'n' => "\n"];
protected function getSymbolStr(GdlNode $symbol)
{
$str = null;
$specificElement = $symbol->getFirst();
$elementType = $specificElement->getName();
if ($elementType === 'AnySymbol') {
$str = $specificElement->get('')->getValue();
}
elseif ($elementType === 'EscapedSymbol') {
$str = $specificElement->get('AnySymbol')->get('')->getValue();
$str = (isset($this->escapedSymbols[$str]) ? $this->escapedSymbols[$str] : $str);
}
elseif ($elementType === 'HexCodeSymbol') {
list($hexDigit1, $hexDigit2) = $specificElement->getArray('HexDigit');
$intValue1 = ord($hexDigit1->get('')->getValue()) - 0x30;
$intValue2 = ord($hexDigit2->get('')->getValue()) - 0x30;
$intValue1 -= ($intValue1 >= 0x0A ? 0x07 : 0);
$intValue2 -= ($intValue2 >= 0x0A ? 0x07 : 0);
$code = $intValue1 * 0x10 + $intValue2;
$str = chr($code);
}
return $str;
}Получение конкретного строкового значения для символа с учетом экранирования и hex-кода.
Всего несколько несложных функций.
Для проверки работы парсера можно сделать так. Создаем парсер с грамматикой из self.php, парсим файл self.gdl, получаем новую грамматику. Логически они должны совпадать, но в новой грамматике есть всякие символы, которые мы не пропускаем, но которые не написали в self.php за ненадобностью — например символы кавычек в элементах StringLiteral. Поэтому нужен еще один шаг. Парсим по новой грамматике файл self.gdl еще раз, получаем еще одну грамматику. Теперь можно преобразовать их в массивы и сравнить. Если парсинг происходит правильно, они должны совпадать.
Тут можно поспорить, что может быть такой баг, при котором парсинг происходит неправильно, но результаты совпадают и при этом логически отличаются от исходного массива. Можно пойти другим путем — сделать правила с маленькими буквами для всех строковых констант в правилах с большими буквами. И все RuleName разбить на символы. Тогда можно будет сравнивать с исходным массивом.
В коде проекта есть файл с тестами, проверка осуществляется в функции testSelfParsing().
php parser_test.php testSelfParsing
0.077260971069336
0.12426900863647Цифры это время в секундах, результат microtime(). Первое время это время парсинга по грамматике из self.php, второе это время повторного парсинга по новой грамматике. Цифры для сравнения между собой, поэтому конфигурация железа неважна. Здесь видно, что toString() заметно замедляет парсинг. В self.php название правила это строка, и она сразу возвращает результат, а в новой грамматике это массив, и она проходит по нему рекурсивно.
Обработка ошибок
Сейчас, если данные в каком-то месте не соответствуют грамматике, движок перебирает все варианты правил на всех уровнях вложенности, и в результате все равно возвращает null.
Можно сделать отсечение, как в Прологе. Например, если мы начали проверять правило ReturnStatement и встретили в исходном коде строку return, значит это точно ReturnStatement, и дальше может быть только какое-то выражение, либо сразу ';'. А если ни того ни другого нет, значит можно выдать ошибку «Expected ';'». Для этого в грамматике надо поставить отсечение после return.
Чтобы работало совсем как в Прологе, нужно обрабатывать это на уровне parseRule(), это сложно, и мы сделаем по-другому. Раз мы знаем, что там точно «Expected ';'», значит можно считать, что она там есть, и продолжить парсинг утверждения. Проверив все выражения в утверждении, мы вернем то, что удалось распарсить, это будет считаться успешным результатом, и проверки следующего варианта не будет. Это же позволит нам выводить все ошибки, а не только первую. Это конечно хак, но работает вполне приемлемо, хоть и не всегда так, как хотелось бы.
Для информативного сообщения об ошибке надо бы показывать, в каком правиле произошла ошибка. Поэтому надо сделать стек вызовов правил. Это поможет и при отладке.
Привожу только основные изменения, детали реализации можно найти в репозитории. Все шаги из статьи сделаны отдельными коммитами.
GdlParser.php
protected function parseRule(GdlNode $rule)
{
$ruleName = $rule->get('RuleName');
$ruleNameStr = ($ruleName !== null ? $ruleName->toString() : '()');
+ $this->ruleCallStack[] = [$ruleNameStr, $this->stream->getPos()];
...
+ array_pop($this->ruleCallStack);
+
return ($parsedRule === null ? null : new GdlNode($ruleNameStr, $parsedRule));
}
protected function parseStatement(GdlNode $statement)
{
$parsedStatement = [];
$expressionList = $statement->getArray('Expression');
+ $cut = false;
foreach ($expressionList as $i => $expression) {
...
$parsedExpression = $this->parseExpression($expression, $lookAheadElement);
if ($parsedExpression === null) {
- $parsedStatement = null;
- break;
+ if ($cut) {
+ $this->handleError($expression);
+ continue;
+ }
+ else {
+ $parsedStatement = null;
+ break;
+ }
}
+
+ if ($expression->get('Cut') !== null) {
+ $cut = true;
+ }
...
}
...
}
+ protected function handleError(GdlNode $expression)
+ {
+ $elementType = $expression->get('Element')->getFirst()->getName();
+ if ($elementType === 'StringLiteral' || $elementType === 'RegexpLiteral') {
+ $name = $expression->toString();
+ }
+ else {
+ $name = $expression->get('Element')->getFirst()->toString();
+ }
+
+ $i = count($this->ruleCallStack) - 1;
+ while ($this->ruleCallStack[$i][0] == '()') { $i--; }
+ $ruleInfo = $this->ruleCallStack[$i];
+
+ $this->errors[] = 'Expected ' . $name . ' at ' . implode(':', $this->stream->getLineAndColumn()) . ' (' . $this->stream->getPos() . ')'
+ . ' in ' . $ruleInfo[0] . ' at ' . implode(':', $this->stream->getLineAndColumn($ruleInfo[1])) . ' (' . $ruleInfo[1] . ')';
+ }
self.gdl
Rule:
- RuleName delimiter* ':' delimiter* RuleBody ';' delimiter*
+ RuleName! delimiter* ':' delimiter* RuleBody ';' delimiter*
;
...public function testParsingErrors()
{
$mainRuleName = 'Grammar';
$gdlParser = new GdlParser($this->getSelfGrammar());
$grammarSource = <<<'SRC'
Program:
;
Test:;
SRC;
$languageGrammar = $gdlParser->parse($mainRuleName, new Stream($grammarSource));
foreach ($languageGrammar->getArray('Rule') as $rule) {
$rule->get('RuleName')->setValue($rule->get('RuleName')->toString());
}
$this->assertTrue($languageGrammar->toArray() === ['Grammar', [
['Rule', [
['RuleName', 'Program'],
['', ':'],
['', ';'],
]],
['Rule', [
['RuleName', 'Test'],
['', ':'],
['', ';'],
]],
]]);
$this->assertTrue($gdlParser->getErrors() === [
'Expected RuleBody at 2:1 (9) in Rule at 1:1 (0)',
'Expected RuleBody at 4:6 (17) in Rule at 4:1 (12)',
]);
$grammarSource = <<<'SRC'
SRC;
$languageGrammar = $gdlParser->parse($mainRuleName, new Stream($grammarSource));
$this->assertTrue($languageGrammar->toArray() === ['Grammar', []]);
$this->assertEmpty($gdlParser->getErrors());
}Дополнительные возможности
Шестнадцатиричные коды символов позволяют парсить бинарные данные, а также задавать правила с использованием UTF-8. Символы UTF-8 в конструкциях типа AnySymbol* работают автоматически ввиду природы UTF-8, хоть и представлены в результате отдельными байтами.
Чтобы использовать группу байтов как один символ, надо добавлять поддержку UTF в класс потока символов Stream. Мы это делать не будем.
public function testUtf8()
{
$mainRuleName = 'Grammar';
$gdlParser = new GdlParser($this->getSelfGrammar());
$grammarSource = <<<'SRC'
Grammar:
(Word={str} '\n')*
;
Word:
Utf8RussianLetter+
;
Utf8RussianLetter:
| [\xD0][\x90-\xBF] /* А-Яа-п */
| [\xD1][\x80-\x8F] /* р-я */
| [\xD0][\x01] /* Ё */
| [\xD1][\x91] /* ё */
;
SRC;
$languageGrammar = $gdlParser->parse($mainRuleName, new Stream($grammarSource));
$this->assertEmpty($gdlParser->getErrors());
$mainRuleName = $languageGrammar->get('Rule')->get('RuleName')->getValue();
$languageParser = new GdlParser($languageGrammar);
$source = <<<'SRC'
тест
тест
абв
SRC;
$tree = $languageParser->parse($mainRuleName, new Stream($source));
$this->assertEmpty($languageParser->getErrors());
$this->assertTrue($tree->toArray() === ['Grammar', [
['Word', 'тест'],
['', "\n"],
['Word', 'тест'],
['', "\n"],
['Word', 'абв'],
['', "\n"],
]]);
}Но парсить бинарные структуры типа TCP-пакетов все равно нельзя. Сейчас можно парсить такие структуры, где начало и конец узлов задаются определенными последовательностями символов, но нельзя такие, где границы узлов задаются через количество или смещение.
Допустим, есть данные, где количество элементов указывается в начале, а потом идет их список.
3
Element1
Element2
Element3Это так просто не решить. Количество элементов указывается строкой или в бинарном виде? В десятичной или другой системе? В big-endian или little-endian?
Нужна функциональность для вызова произвольных функций.
В ANTLR произвольный программный код задается в фигурных скобках. Но фигурные скобки в регулярных выражениях задают количество, обработку которого нам тоже надо добавить, поэтому чтобы не замедлять парсинг грамматик, будем начинать эту часть со знака =. И сделаем привязку кода к элементу. А так как у нас кругом ООП, то вместо кода достаточно писать название функции, куда будет передаваться узел с результатом парсинга. Передавать его лучше по ссылке, чтобы функция могла присвоить ему значение null, обозначив этим, что парсинг элемента не удался. Ну и можно сразу сделать возможность задавать несколько функций.
GdlParser.php
protected function parseExpression(GdlNode $expression, ?GdlNode $lookAheadElement = null)
{
$element = $expression->get('Element');
+ $elementFunctionNameList = null;
+ if ($expression->get('FunctionCall') !== null) {
+ foreach ($expression->get('FunctionCall')->getArray('FunctionName') as $functionName) {
+ $elementFunctionNameList[] = $functionName->toString();
+ }
+ }
+
$quantifier = $expression->get('Quantifier');
$quantifierType = null;
+ $countVal = 0;
if ($quantifier !== null) {
- $quantifierType = $quantifier->get('')->getValue();
+ $count = $quantifier->get('Count');
+ if ($count === null) {
+ $quantifierType = $quantifier->get('')->getValue();
+ }
+ else {
+ $quantifierType = '{}';
+ if ($count->get('IntValue') !== null) {
+ $countVal = intval($count->get('IntValue')->toString());
+ }
+ elseif ($count->get('FunctionCall') !== null) {
+ $countFunctionName = $count->get('FunctionCall')->get('FunctionName')->toString();
+ $countVal = $this->$countFunctionName();
+ }
+ }
}
$parsedElement = $this->parseElement($element);
+ if ($elementFunctionNameList !== null && $parsedElement !== null) {
+ foreach ($elementFunctionNameList as $elementFunctionName) {
+ $this->$elementFunctionName($parsedElement);
+ if ($parsedElement === null) {
+ break;
+ }
+ }
+ }
- if ($quantifierType === null || $quantifierType === '?') {
+ if ($quantifierType === null || $quantifierType === '?' || $quantifierType === '{}' && count($parsedElementList) === $countVal) {
break;
}
}
- $countDoesNotMatch = (($quantifierType === null || $quantifierType === '+') ? empty($parsedElementList) : false);
+ $countDoesNotMatch = (($quantifierType === null || $quantifierType === '+') ? empty($parsedElementList)
+ : (($quantifierType === '{}') ? count($parsedElementList) !== $countVal : false)
+ );
if ($countDoesNotMatch) {
$parsedElementList = null;
}
self.gdl
Expression:
- Element Quantifier? LookAhead? Cut? delimiter*
+ Element FunctionCall? Quantifier? LookAhead? Cut? delimiter*
;
Quantifier:
| '*'
| '?'
| '+'
+ | '{' Count '}'
;
+
+Count:
+ | IntValue
+ | FunctionCall
+;
+
+IntValue:
+ [0-9]+
+;
+
+FunctionCall:
+ '={'! FunctionName (',' FunctionName)* '}'
+;
+
+FunctionName:
+ ID
+;Функция привязывается к элементу, и для выражений с квантификатором вызывается для каждого распарсенного элемента. Наверно можно было бы поместить Function внутрь Element, но особой необходимости в этом нет.
Функции для Count и FunctionCall имеют разную сигнатуру. Функция для Count должна возвращать int, и передача элемента для нее не требуется.
В грамматике это будет выглядеть так.
public function testCount()
{
$mainRuleName = 'Grammar';
$gdlParser = new GdlParser($this->getSelfGrammar());
$grammarSource = <<<'SRC'
Data:
Count={setCount} '\n' Element{={getCount}}
;
Count:
[0-9]{4}
;
Element:
[a-zA-Z0-9]+ '\n'
;
SRC;
$languageGrammar = $gdlParser->parse($mainRuleName, new Stream($grammarSource));
$this->assertEmpty($gdlParser->getErrors());
$mainRuleName = $languageGrammar->get('Rule')->get('RuleName')->toString();
$languageParser = new class($languageGrammar) extends GdlParser {
protected $cnt;
public function setCount(GdlNode &$parsedElement)
{
$this->cnt = intval($parsedElement->toString());
}
public function getCount(): int
{
return $this->cnt;
}
};
$source = <<<'SRC'
0006
Element1
Element2
Element3
Element4
Element5
Element6
SRC;
$tree = $languageParser->parse($mainRuleName, new Stream($source));
$tree->get('Count')->setValue($tree->get('Count')->toString());
$tree->get('')->setValue($tree->get('')->toString());
foreach ($tree->getArray('Element') as $element) {
$element->setValue($element->toString());
}
$this->assertEmpty($languageParser->getErrors());
$this->assertTrue($tree->toArray() === ['Data', [
['Count', '0006'],
['', "\n"],
['Element', "Element1\n"],
['Element', "Element2\n"],
['Element', "Element3\n"],
['Element', "Element4\n"],
['Element', "Element5\n"],
['Element', "Element6\n"],
]]);
}Это дает очень широкие возможности. Мы можем убрать вызов toString() из кода, вернее перенести ее в другое место, где она будет меньше влиять на производительность. Делаем специальную функцию str, где будем вызывать toString(), и в грамматике везде где используется RuleName добавляем вызов функции RuleName={str}. Таким образом, в результате парсинга self.gdl там всегда будет строка, и медленную $ruleName->toString() можно заменить на быструю $ruleName->getValue(). Для символов можно сделать свою функцию symbolStr и заменить их все в self.php.
GdlParser.php
public function initRules(GdlNode $grammar)
{
$this->ruleMap = [];
foreach ($grammar->getArray('Rule') as $rule) {
- $this->ruleMap[$rule->get('RuleName')->toString()] = $rule;
+ $this->ruleMap[$rule->get('RuleName')->getValue()] = $rule;
}
}
protected function parseRule(GdlNode $rule)
{
$ruleName = $rule->get('RuleName');
- $ruleNameStr = ($ruleName !== null ? $ruleName->toString() : '()');
+ $ruleNameStr = ($ruleName !== null ? $ruleName->getValue() : '()');
$this->ruleCallStack[] = [$ruleNameStr, $this->stream->getPos()];
foreach ($expression->get('FunctionCall')->getArray('FunctionName') as $functionName) {
- $elementFunctionNameList[] = $functionName->toString();
+ $elementFunctionNameList[] = $functionName->getValue();
+ protected function str(GdlNode &$parsedElement)
+ {
+ $parsedElement->setValue($parsedElement->toString());
+ }
+
+ protected function symbolStr(GdlNode &$parsedElement)
+ {
+ $parsedElement->setValue($this->getSymbolStr($parsedElement));
+ }
+
protected function parseStringLiteral(GdlNode $element)
{
$contentSymbol = $this->stream->readSymbol();
- $str = $this->getSymbolStr($symbol);
+ $str = $symbol->getValue();
protected function parseRegexpLiteral(GdlNode $element)
{
if (count($symbolList) === 2) {
- $strFrom = $this->getSymbolStr($symbolList[0]);
- $strTo = $this->getSymbolStr($symbolList[1]);
+ $strFrom = $symbolList[0]->getValue();
+ $strTo = $symbolList[1]->getValue();
elseif (count($symbolList) === 1) {
- $str = $this->getSymbolStr($symbolList[0]);
+ $str = $symbolList[0]->getValue();
self.gdl
Rule:
- RuleName! delimiter* ':' delimiter* RuleBody ';' delimiter*
+ RuleName={str}! delimiter* ':' delimiter* RuleBody ';' delimiter*
;
Element:
- | RuleName
+ | RuleName={str}
| StringLiteral
| RegexpLiteral
| InlineRule
;
Count:
- | IntValue
+ | IntValue={str}
| FunctionCall
;
FunctionCall:
- '={'! FunctionName (',' FunctionName)* '}'
+ '={'! FunctionName={str} (',' FunctionName={str})* '}'
;
StringLiteral:
- '\''! Symbol+>> '\''
+ '\''! Symbol={symbolStr}+>> '\''
;
SymbolRange:
- Symbol>']' ('-'! Symbol>']')?
+ Symbol={symbolStr}>']' ('-'! Symbol={symbolStr}>']')?
;
self.php
['RegexpLiteral', [
['SymbolRange', [
- ['Symbol', [['AnySymbol', [['', ' ']]]]],
+ ['Symbol', " "],
]],
['SymbolRange', [
- ['Symbol', [['EscapedSymbol', [['AnySymbol', [['', 'n']]]]]]],
+ ['Symbol', "\n"],
]],
['SymbolRange', [
- ['Symbol', [['EscapedSymbol', [['AnySymbol', [['', 't']]]]]]],
+ ['Symbol', "\t"],
]],
['SymbolRange', [
- ['Symbol', [['EscapedSymbol', [['AnySymbol', [['', 'r']]]]]]],
+ ['Symbol', "\r"],
]],
]],
]],
...Что у нас получилось с парсингом собственной грамматики?
php parser_test.php testSelfParsing
0.10463285446167
0.10712099075317Время выполнения выровнялось и стало чуть больше времени первой проверки из прошлого раза и меньше второго. Напомню, первое время это время парсинга self.gdl по грамматике из self.php, второе это время повторного парсинга по грамматике из первого парсинга.
Это потому что в прошлый раз в первой проверке мы не вызывали toString() на массивах, названия правил в self.php всегда были написаны строками. Сейчас же toString() вызывается сразу после успешного парсинга узла RuleName, где результат массив, и это влияет на первое время.
Второе время обычно чуть больше первого, потому что там больше мелких элементов типа кавычек вокруг строковых литералов, которых нет в self.php, но иногда бывает и наоборо
