10.06.2020 16:42
michael_vostrikov 48 4100 Источник

Есть много существующих инструментов для парсинга файлов по заданной грамматике. Например, 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" означал обычный пробел с кодом 0x20, а не любой пробельный символ, как в обычных регулярных выражениях.


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


Комментарии, как же без них.


И тут мы встречаем хитрый момент. Логично было бы описать его вот так:


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'], но читаемость кода или на производительность (в объемах исходников на языке программирования) это почти не влияет, и вводить для этого отдельную сущность нет смысла. Но для парсинга больших файлов XML или JSON влияние на производительность будет заметно, так как на каждый символ создается 2 элемента, а мог бы быть 1.


С чего бы нам начать. У нас уже есть структурированный файл с собственной грамматикой, который мы могли бы распарсить и получить дерево, которое потом использовать в коде, но ведь парсер нам и надо написать. Можно пойти простым и длинным путем — написать код для парсинга с 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.


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 ';'", значит можно считать, что она там есть, и продолжить парсинг утверждения. Проверив все выражения в утверждении, мы вернем то, что удалось распарсить, это будет считаться успешным результатом, и проверки следующего варианта не будет. Это же позволит нам выводить все ошибки, а не только первую. Это конечно хак, но работает вполне приемлемо, хоть и не всегда так, как хотелось бы.


Для информативного сообщения об ошибке надо бы показывать, в каком правиле произошла ошибка. Поэтому надо сделать стек вызовов правил. Это поможет и при отладке.


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


diff 
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, обозначив этим, что парсинг элемента не удался. Ну и можно сразу сделать возможность задавать несколько функций.


diff 
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.


diff 
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, но иногда бывает и наоборот. То есть различие в пределах погрешности.


Можно делать и более сложные вещи. Сделаем грамматику для синтаксиса Nowdoc в PHP.


public function testComplexString()
{
    $mainRuleName = 'Grammar';
    $gdlParser = new GdlParser($this->getSelfGrammar());

    $grammarSource = <<<'SRC'
Data:
    ComplexString*
;

ComplexString:
    '<<<\'' StringTag={str,setStringStart} '\'' '\n' Content={str} '\n' StringTag={str,checkStringEnd} '\n'
;

Content:
    .*>('\n' StringTag={str,checkStringEnd})
;

StringTag:
    [a-zA-Z]+
;
SRC;
    $languageGrammar = $gdlParser->parse($mainRuleName, new Stream($grammarSource));

    $this->assertEmpty($gdlParser->getErrors());

    $mainRuleName = $languageGrammar->get('Rule')->get('RuleName')->getValue();

    $languageParser = new class($languageGrammar) extends GdlParser {
        protected $complexStringTag;

        public function setStringStart(GdlNode &$parsedElement)
        {
            $this->complexStringTag = $parsedElement->getValue();
        }

        public function checkStringEnd(GdlNode &$parsedElement)
        {
            if ($parsedElement->getValue() !== $this->complexStringTag) {
                $parsedElement = null;
            }
        }
    };

    $source = <<<'SRC'
<<<'test'
<<<'abc'
a b c
abc
test
<<<'tag'
1 2 3 4
tag

SRC;
    $tree = $languageParser->parse($mainRuleName, new Stream($source));

    $this->assertEmpty($languageParser->getErrors());
    $this->assertTrue($tree->toArray() === ['Data', [
        ['ComplexString', [
            ['', '<<<\''],
            ['StringTag', 'test'],
            ['', '\''],
            ['', "\n"],
            ['Content', "<<<'abc'\na b c\nabc"],
            ['', "\n"],
            ['StringTag', 'test'],
            ['', "\n"],
        ]],
        ['ComplexString', [
            ['', '<<<\''],
            ['StringTag', 'tag'],
            ['', '\''],
            ['', "\n"],
            ['Content', "1 2 3 4"],
            ['', "\n"],
            ['StringTag', 'tag'],
            ['', "\n"],
        ]],
    ]]);
}

Обратите внимание на конструкцию .*>('\n' StringTag={str,checkStringEnd}). В грамматике LookAhead сделан для Element, а не для Expression, поэтому там нельзя использовать квантификатор или функцию, но можно сделать inline-правило, внутри которого написать то, что нужно.


Для сравнения можно посмотреть, как это реализовано в самом PHP.


Реальный пример


Теперь надо бы проверить парсер на настоящем языке.


Я сделал простую грамматику для PHP. Она не совсем точная, там минимальный набор правил, чтобы можно было распарсить файл GdlParser.php без ошибок. Под "распарсить" имеется в виду полное построение AST, которое готово для дальнейшей обработки.


Что тут нужно сделать. Парсить пробелы отдельным правилом, как в self.gdl, это слишком медленно. Можно сделать по-другому, переопределить функцию parseExpression(), и после парсинга каждого выражения читать $this->stream и пропускать пробелы. Но для правил, которые задают структуру строк, пробелы пропускать нельзя. Поэтому надо либо проверять название правила, либо сделать флаг, который устанавливать после парсинга открывающей кавычки и стирать после закрывающей. Также надо сделать обработку для ошибки парсинга после открывающей кавычки, это можно сделать через уровень рекурсии, который определяется как count($this->ruleCallStack). Надо сохранять уровень рекурсии при входе в строку, переопределить parseStatement() и добавить проверку, что если парсинг не удался и уровень меньше запомненного (то есть мы вышли из правила для строки или аналогичной структуры), стирать флаг. Получится универсальный текстовый парсер. Комментарии можно сделать конструкцией языка (IfStatement | ReturnStatement | comment), либо переопределять функцию пропуска пробелов в классе парсера для конкретного языка, так как комментарии зависят от синтаксиса.


В грамматике это выглядит так.


SingleQuoteString:
    '\''={setKeepSpaces} Symbol*>> '\''={clearKeepSpaces}
;

Код обработки находится в классе GdlTextParser.php.


public function testPhp()
{
    $mainRuleName = 'Grammar';
    $gdlParser = new GdlParser($this->getSelfGrammar());

    $grammarSource = file_get_contents(__DIR__ . '/php.gdl');
    $stream = new Stream($grammarSource);

    $t1 = microtime(1);
    $languageGrammar = $gdlParser->parse($mainRuleName, $stream);
    $t2 = microtime(1);
    echo ($t2 - $t1) . "\n";

    $this->assertEmpty($gdlParser->getErrors());

    $mainRuleName = $languageGrammar->get('Rule')->get('RuleName')->getValue();

    $languageParser = new class($languageGrammar) extends GdlTextParser {
        protected $complexStringTag;

        public function setStringStart(GdlNode &$parsedElement)
        {
            $this->complexStringTag = $parsedElement->getValue();
        }

        public function checkStringEnd(GdlNode &$parsedElement)
        {
            if ($parsedElement->getValue() !== $this->complexStringTag) {
                $parsedElement = null;
            }
        }

        protected function handleError(GdlNode $expression)
        {
            parent::handleError($expression);

            while (!$this->stream->eof()) {
                $symbol = $this->stream->readSymbol();
                if ($symbol === "\n") {
                    break;
                }
            }

            $i = count($this->ruleCallStack) - 1;
            while ($this->ruleCallStack[$i][0] == '()') { $i--; }
            $ruleName = $this->ruleCallStack[$i][0];

            if ($ruleName === 'FunctionDeclaration' || $ruleName === 'StatementBlock') {
                $level = 1;
                while (!$this->stream->eof()) {
                    $symbol = $this->stream->readSymbol();
                    if ($symbol === '{') {
                        $level++;
                    }
                    else if ($symbol === '}') {
                        $level--;
                        if ($level == 0) {
                            break;
                        }
                    }
                }
            }
        }
    };

    $source = file_get_contents(__DIR__ . '/GdlParser.php');

    $t1 = microtime(1);
    $tree = $languageParser->parse($mainRuleName, new Stream($source));
    $t2 = microtime(2);
    echo ($t2 - $t1) . "\n";

    $this->assertEmpty($languageParser->getErrors());
    $this->assertTrue(!empty($tree));
}

Здесь можно обратить внимание на функцию handleError(). При ошибке, для того, чтобы продолжить парсинг с другого места, можно переопределить handleError() и проматывать $this->stream до нужной позиции, например до символа ';' или '}' нужного уровня вложенности.
Но это будет работать не так как надо для конструкций типа '{'! Statement+ '}' и незавершенного Statement в исходном коде. Парсер сначала получит ошибку парсинга очередного Statement, закончит парсинг выражения с квантификатором, потом попробует проверить '}', и выдаст ошибку Expected '}'. Для это надо изменить обработку ошибок в parseExpression(), чтобы если парсинг элемента не удался, связанная с ним функция все равно вызывалась. В ней можно проверять результат на null и создавать объект GdlNode вручную с названием правила наподобие IncompleteStatement. Но это потребует добавлять проверку на null во всех произвольных функциях, поэтому я не стал так делать.


Код в GdlParser.php синтаксически правильный, поэтому handleError() не вызывается, она тут просто для демонстрации.


Производительность


Это медленно. Но не так чтобы очень медленно.


Во время парсинга каждая функция parse* вызывается несколько тысяч раз. Так как это нагруженная часть, там нужен минимум проверок. Поэтому например нет проверки на правильность quantifierType. Есть всего 2 проверки на правильность: на наличие правила, потому что название берется из внешего источника — файла с грамматикой, и на тип элемента выражения, так как там все равно нужна проверка, чтобы вызвать нужную обработку.


php parser_test.php testPhp
0.44992613792419
1.7462248802185

Первое время это парсинг грамматики для PHP, второе это парсинг файла GdlParser.php.
Скорость парсинга грамматики большого значения не имеет, грамматика парсится один раз и потом применяется для многих файлов с исходным кодом.


Почти 2 секунды это медленно, но эй, это же PHP. Что если переписать на C++?


Версия на C++


В C++ версии нет всех тестов, там только код для парсинга PHP. Вызов функции по названию делается через if со сравнением строк. Для сборки есть скрипт make.sh, там одна команда, сборка делается с оптимизацией -O3.
Код не предназначен для использования в production! В коде много new и ни одного delete. Вернее один есть, но это можно не считать.


Приведу цифры, полученные на одном и том же железе. Проверялся парсинг файла GdlParser.php грамматикой php.gdl.


GdlParser на PHP парсит исходник за 1.8 секунды.
GdlParser на C++ с оптимизацией -O3 за 0.022 секунды.
PHP через eval обрабатывает полностью за 0.001 секунды.
ANTLR на C++ с оптимизацией -O3 за 0.2 секунды.


То есть да, GdlParser в 10 раз быстрее ANTLR.


./parser 
PHP grammar parsing OK
PHP source parsing OK
Duration: 0.022794

UPD: В комментариях подсказали, что в ANTLR есть режим парсинга SLL, который работает значительно быстрее, но по умолчанию отключен, а также что при первом запуске в пределах процесса ANTLR парсит значительно дольше. Для грамматики php.gdl GdlParser в 4 раза быстрее ANTLR без SLL при втором запуске, для большого JSON-файла ANTLR быстрее в 70 раз, ANTLR c SLL всегда гораздо быстрее. Результаты тестирования в этом комментарии.


Для ANTLR я сделал грамматику Php.g4, которая аналогична php.gdl.


Как скомпилировать ANTLR для C++ под Linux

Скачать "antlr-4.8-complete.jar" отсюда, раздел "ANTLR tool and Java Target", ссылка "Complete ANTLR 4.8 Java binaries jar"


Скачать runtime и demo оттуда же, раздел "C++ Target", ссылка "antlr4-cpp-runtime-4.8-source.zip (.h, .cpp)"


Поместить в одну папку, распаковать архив с runtime и demo в папку "antlr4-cpp-runtime-4.8-source", открыть терминал в этой папке


Удалить файлы "TLexer.g4" и "TParser.g4"
Скопировать "Php.g4" и "GdlParser.php" в "demo/"
Заменить "TLexer" и "TParser" на "PhpLexer" и "PhpParser" в "demo/Linux/main.cpp, demo/generate.sh, demo/CMakeLists.txt", но "TParserBaseListener" на "PhpBaseListener" и остальные 3 файла рядом аналогично.


В main.cpp использовать код:


#include <chrono>

#include "PhpLexer.h"
#include "PhpParser.h"

std::ifstream stream;
stream.open("../demo/GdlParser.php");
ANTLRInputStream input(stream);

PhpLexer lexer(&input);
CommonTokenStream tokens(&lexer);

tokens.fill();

PhpParser parser(&tokens);
auto t1 = std::chrono::high_resolution_clock::now();
tree::ParseTree* tree = parser.program();
auto t2 = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count();
std::cout << "Duration: " << ((double)duration / 1000000) << std::endl;

Выполнить эти команды, аналогичны указанным в разделе "Compiling on Linux" в файле README.md


mkdir build && mkdir run && cd build
cmake .. -DANTLR_JAR_LOCATION=../../antlr-4.8-complete.jar -DWITH_DEMO=True
make
demo/antlr4-demo

Что можно сделать для улучшения производительности:


  • Заменить все строковые константы в коде на значения enum или индекс правила в массиве правил. Поле name в GdlNode тоже будет целочисленным.
  • Сделать свой итератор вместо getArray(name), который возвращает std::vector через стек. Я так не пробовал, но я пробовал везде вместо цикла по результату getArray(name) сделать цикл по listValue с проверкой названия, это работает на 20% быстрее.
  • Сделать локальный конечный автомат для выбора вариантов правила. При инициализации парсера для кажого правила (включая inline) проходим по всем узлам грамматики до строк и регэкспов, берем ноды Symbol, для диапазонов в регэкспах генерируем список, все значения символов добавляем в таблицу стейтментов. При парсинге берем текущий символ из потока, определяем, какие варианты с него могут начинаться, и проверяем только их. То же самое можно сделать и для середины стейтмента, для последовательностей вида A* B? C. Я проверял в версии на PHP только для вариантов, это ускоряет обработку раза в полтора.
  • Разбивать на лексемы обычным конечным автоматом, а потом парсить. Для этого надо немного поменять файл Stream и проверку символов. В сочетании с заменой на enum и конечным автоматом это может заметно повысить производительность.

Также можно не использовать GdlParser как есть, а сделать генератор парсера по грамматике для конкретного языка. То есть вместо parseRule(getRule('Program')) будет parseProgram(), вместо parseExpression() с проверкой квантификатора будет один вызов parseRule() или цикл while, и т.д.
(UPD: сделал, работает быстро)


Общая информация


Парсер получился контекстно-зависимый, в том смысле, что можно объявить переменную с названием class. Но определению контекстно-зависимой грамматики это не соответствует. Там есть пример для последовательности a...b...c..., где количество одинаковых символов a, b, c должно быть одинаковым, для него нельзя придумать грамматику без использования функций, по которой этот парсер сможет распарсить такую последовательность. С функциями это тривиально, но это уже не совсем грамматика, а cинтаксически управляемая трансляция.


Но называть переменные ключевыми словами все равно не получится.
Возьмем такой пример:


return [2];

Это оператор return, который возвращает константное значение, или это получение элемента массива с индексом 2 из переменной с названием return?


a[2];
return[2];

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


Можно конечно рассмотреть вариант, когда все ключевые слова языка программирования начинаются со специального символа. Ну а что, в PHP переменные начинаются со специального символа, а тут будет наоборот. @public @static @class Math. Без значков как-то привычнее все-таки.


Основные проблемы в грамматиках это бесконечная рекурсия и неоднозначность. Первую относительно несложно отследить вручную или написать анализатор. Вторую сложно отследить, но парситься всегда будет первый подходящий вариант, поэтому можно в списке вариантов помещать правила, начинающиеся с конкретных строк, раньше остальных. То есть вариант, которой начинается с 'return', выше варианта, который начинается с ID.


Основные правила составления грамматик — не делать правила грамматики, которые могут быть пустые, заменять иx на + в правиле и ? в месте вызова, и не делать левую рекурсию, заменять ее на постепенный спуск по более конкретным правилам. Пустые правила всегда парсятся успешно, но позиция потока не двигается, и может произойти зацикливание. Потенциально пустым можно делать главное правило, если нужен успешный парсинг данных длиной 0 байт.


// неправильно
C: D A;
A: B*;

// правильно
C: D A?;
A: B+;

// неправильно
Expression: Expression ('+' | '-') Expression;

// правильно
Expression: MulExpression ('+' | '-') MulExpression;
MulExpression: ...

Результат


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


Полный код находится здесь.


Код под лицензией MIT, можно портировать на другие языки, дорабатывать и использовать в своем проекте на свой страх и риск.