Парсер данных по произвольной грамматике в 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" означал обычный пробел с кодом 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 всегда гораздо быстрее. Результаты тестирования в этом комментарии.
    UPD2: Это относится к универсальному движку, сгенерированный парсер на GDL работает быстрее 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: сделал, работает в 10 раз быстрее, чем ANTLR с SLL)


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


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

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 51

      +2
      Когда 2 года назад я начинал делать интерпретатор грамматики (а позднее уже и полноценный генератор парсера), мне это не показалось очень сложной задачей. Спустя ~30к строк кода моё мнение немного изменилось. Если планируете продолжать, почитайте книгу дракона (пару первых глав про лексический анализ). Говорить про скорость синтаксического анализатора(парсера) без отдельного лексического анализатора(лексера) и сравнивать с ANTLR ещё, возможно, рано. Для примера, можно попробовать несложную грамматику Json или Xml и проанализировать файл размером в 100мб.
        0

        Я знаю про книгу дракона, хоть и не читал ее. Я имею представление о том, что написано в первых 2 главах, статья как раз о том, что во-первых, это не так сложно, во-вторых, необязательно делать именно так, то есть делить на лексер и парсер и так далее.


        Кроме того, во всех примерах про парсинг, которые я встречал, парсинг выражения "A+B+C" представляется двоичным деревом. Сейчас проверил, в этой книге тоже так написано. Это сложно и неоптимально, правильнее делать произвольным деревом, так можно создать одну временную переменную и накапливать в ней результат. А с двоичным деревом будет несколько переменных, по одной на каждую пару операндов, и это надо будет дополнительно оптимизировать.


        Для примера, можно попробовать несложную грамматику Json или Xml и проанализировать файл размером в 100мб

        Так я проверил построение дерева на грамматике для полноценного языка программирования, какой смысл на более простых проверять?

          0

          Проверил на JSON, оказалось не все так просто. ANTLR работает быстрее. Думаю, тут сказывается работа со строками (ANTLR генерирует enum), а также то, что на простые правила вида AnySymbol: . создаются 2 объекта GdlNode, а не 1. На больших объемах данных это влияет на производительность, поправлю этот момент в статье.

            0
            Вот и я не читал книгу дракона в 1-й год написания своего велосипеда, и в моём интерпретаторе тоже не было отдельного лексического анализатора. Первый же тест Json документа на пару мб показал, что нужно почитать теорию. Почитайте немного про лексический/синтаксический анализ (а ещё немного про теорию формальных языков). То, что вы называете statement в правиле, называется продукцией. А результат синтаксического анализа текста представляется абстрактным синтаксическим деревом, а не бинарным. Если это представлять классом, то правило — это абстрактный класс, все продукции этого правила — это наследники этого класса. Каждый элемент продукции будет свойством этого класса. Квантификаторы — это операторы Клини, и ваша первая проблема с разбором комментариев по правилу '/*' .* '*/' элементарно решается лексическим анализатором на основе DFA. Если вы посмотрите профилировщиком, то проблема производительности вашего интерпретатора скорее всего окажется в лексическом анализе, хотя на самом деле при отдельном лексере (если лексическая часть грамматики контекстно независима), то лексер на основе DFA выполняет свою работу за O(n) и может занимать лишь пару процентов от всего времени работы парсера. И как уже написали ниже, наивный парсинг легко становится экспоненциальным, как пример (сильно упрощённый), грамматика выражений C# или Java:

            expression: assignment_expression | non_assignment_expression;
            non_assignment_expression : unary_expression | binary_expression ;
            assignment_expression : unary_expression '=' unary_expression ;
            unary_expression : number | member_invocation ;

            если мы хотим проанализировать выражения: a(b(c(d))) и a(b(c(d))) = 1, то пока мы не дойдём до самого конца этого выражения мы не будем знать, оно assignment_expression или non_assignment_expression, и на каждом вхождении в правило expression кол-во альтернатив будет удваиваться, и я нарочно поставил assignment_expression первой альтернативой, в реальной грамматике реального ЯП такие выражения будут редкостью, но наивный парсер такой порядок заставит выполнить полный перебор всех возможных комбинаций.
              0
              Почитайте немного про лексический/синтаксический анализ (а ещё немного про теорию формальных языков)

              Как я уже сказал, я знаком с этими темами. Целью статьи было показать, что можно сделать проще, хоть и работать это будет дольше.


              То, что вы называете statement в правиле, называется продукцией.

              А в ANTLR например альтернативой.


              А результат синтаксического анализа текста представляется абстрактным синтаксическим деревом, а не бинарным

              Вы путаетесь в терминах. "Бинарное" это характеристика дерева, а "абстрактное синтаксическое" это его назначение. Это независимые понятия, одно не исключает другое.


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

              А если не представлять, то не абстрактный класс) Это уже детали реализации. Если вам удобнее делать так, делайте так. Мне было удобнее сделать по-другому.


              Квантификаторы — это операторы Клини, и ваша первая проблема с разбором комментариев по правилу '/' . '*/' элементарно решается лексическим анализатором на основе DFA.

              Ну а как по-вашему этот лексический анализатор работает? Вот примерно так и работает, как описано в статье, с lookahead и всем прочим. Я же про это писал: "По сути мы и пишем продвинутый движок регулярных выражений".


              Если вы посмотрите профилировщиком, то проблема производительности вашего интерпретатора скорее всего окажется в лексическом анализе

              А почему вы уверены, что я не смотрел? У меня нет отдельной фазы лексического анализа, поэтому и проблемы производительности в ней быть не может. Более того, я про это написал в способах улучшения производительности: "Разбивать на лексемы обычным конечным автоматом, а потом парсить". Только с лексическим анализатором сложно делать грамматики для вставок asm { ... } или строк Nowdoc.
              Принципиально нет никакой разницы, читать из потока символ с кодом X или токен с кодом X, построение дерева от этого не меняется. Проблема производительности заключается в переборах и откатах, ну и в самой проверке вариантов, которые мы перебираем. Проверить токен T_RETURN можно за 1 сравнение, а строку 'return' от 1 до 6 сравнений. Ну да, это то, что соответствует лексическому анализу в традиционной архитектуре, я про это знаю. Из-за этого и сложно описывать некоторые конструкции, поэтому я не стал так делать.


              если мы хотим проанализировать выражения: a(b(c(d))) и a(b(c(d))) = 1, то пока мы не дойдём до самого конца этого выражения мы не будем знать, оно assignment_expression или non_assignment_expression

              Верно, поэтому надо делать через спуск с приоритетами. Примерно как здесь.

                0
                Если ваша цель показать, что все может быть гораздо проще и возможно реализовать интерпретатор произвольной грамматики в 400 строк, то ОК, вы справились с задачей. Я вас не критикую, а дал рекомендацию почитать теорию, в случае, если вы планируете продолжать свою работу, т.к. сам прошёл похожий путь. Вы говорите отдельный лексер не нужен, какой там у вас получился результат в парсинге Json в 100мб и какой результат у ANTLR? Если разница в 2-3...5 раз, то ладно, а если она в 100-1000 раз отличается в пользу ANTLR, то практического применения кроме как несложных грамматик и небольших документов немного. Когда я производил замеры производительности, то в в синтетическом тесте па парсингу большого Json документа мой интерпретатор работал раз в 20 медленней, чем парсер Newtonsoft Json (который написан вручную) и для меня это был неприемлемый результат, на сегодня этот тест (очень приблизительно, т.к. точных цифр не помню) чистый .Net Core и его парсер Json: ~80мс, мой интерпретатор ~250мс, Newtonsoft ~450мс (тут не очень честно, т.к. внутри получаемый документ сложнее), ANTLR ~1000-1200мс (очень неточно, т.к. проверял давно, но порядок примерно такой). И Json, с точки зрения его грамматики, просто примитивнейший пример. Как работает лексер я не то чтобы представляю, я его реализовал через DFA и там нет никаких lookahead. Продукция — это термин из теории формальных языков, в ANTLR его назвали альтернатовой, вы назвали statement, я вообще назвал transition, но моё мнение, что правильнее это называть продукцией.
                Абстрактное дерево — это действительно назначение, но ниже вам написали, что оно не бинарное, в общем случае оно n-арное, правило — это узел, из которого выходит n (= кол-ву элементов продукции) ветвей. Я не буду навязывать вам свою точку зрения, как-то вы критически воспринимаете мой комментарий. Делайте как считаете нужным, но как сказал Terence Parr:
                Despite the power of Parser Expression Grammars (PEGs) and GLR, parsing is not a solved problem ©, всё не так просто, как может показаться.
                Если вам(или кому-то) интересно и вы не читали «LL(*): The Foundation of the ANTLR Parser Generator»
                  0
                  Если разница в 2-3...5 раз, то ладно, а если она в 100-1000 раз отличается в пользу ANTLR, то практического применения кроме как несложных грамматик и небольших документов немного

                  На исходнике с PHP разница в 10 раз в пользу GdlParser. На JSON да, ANTLR лучше работает, разница где-то в 7 раз.
                  "Небольшие документы" — это 99% файлов с исходным кодом на каком-либо языке программирования.

                    0
                    А вы когда с ANTLR сравниваете производительность, вы проверяете 1-й одиночный запуск, или хотя бы 2-й? Во время первого запуска там ATN дессериализуется и DFA строится, а вот 2-й и следующие должны быть быстрее.
                      0

                      А, вот оно что. Я проверял несколько запусков консольного приложения, в пределах одного запуска парсинг происходит 1 раз. Да, если вызывать парсинг в коде 2 раза, второй раз значительно быстрее. Спасибо за информацию, поправлю статью.

                        0
                        И какие получились числа времени парсинга PHP и большого Json между GdlParser и ANTLR на 2-м запуске?
                          0

                          Для JSON разницы почти никакой, зато для PHP значительная, подробности ниже

                    0
                    я его реализовал через DFA и там нет никаких lookahead

                    Оно в таблице состояний закодировано. Примерно там, где состояние для входящего символа '*', и надо решить, заканчивается комментарий или нет. Но согласен, в явном виде его нет.
                    Регулярные выражения работают через конечные автоматы, и lookahead через них же работает.


                    но ниже вам написали, что оно не бинарное, в общем случае оно n-арное

                    Так это писали про мои слова "правильнее делать произвольным деревом". "Произвольное" — это и есть n-арное, то есть я про это и говорю.

                      0
                      Мы может друг друга не так понимаем (или я вас не так понимаю), но lookahead — это когда для принятия решения читается следующий символ из входящего потока и производится его анализ. Лексер и регулярные выражения на основе DFA не заглядывают в поток вперёд, они на каждом символе из потока переходят из 1-го детерминированного состояния в другое, очень примерно это выглядит так:
                      while ((ch = stream.ReadNext()) != -1)
                      {
                      	dfaState = dfaState.GetNext(ch);
                      	
                      	if (dfaState.Break)
                      		break;
                      }
                      

                      Вообще в регулярных выражениях используется расширение оператора Клини, ленивые квантификаторы, и тогда правило для комментария выглядит так '/*' .*? '*/', и в реализации конечного автомата при переходе из одного состояния в другое при прохождении символа через ленивый оператор такое состояние помечается атрибутом, который просто «запрещает» повторное вхождение в эту альтернативу. Но никакого lookahead там нет.
                        0
                        lookahead — это когда для принятия решения читается следующий символ из входящего потока и производится его анализ

                        В регулярных выражениях есть конструкция lookahead, я говорю про нее и аналогичную функциональность.


                        ленивые квантификаторы, и тогда правило для комментария выглядит так '/' .? '*/'

                        Да, я писал в статье про ленивые выражения.

                          0
                          Не знал про такой lookahead в регулярных выражения, спасибо, интересно.
                          0

                          Ну вообще лексер в ANTLR тоже контекстно-свободный и следующее правило там допустимо:


                          COMMENT: '/*' (COMMENT | .)*? '*/';

                          Такой вложенный комментарий распознает следующую строку:


                          /* level1 /* level2 */ level1 */

                          А обычное не жадное


                          COMMENT: '/*' .*? '*/'

                          на ней не сработает.

                            0
                            Да, я знаю, что в ANTLR можно рекурсивные правила в лексере писать, я тоже планировал добавить такую возможность в свой велосипед. Только такие правила уже не смогут работать через конечный автомат, получается на этих правилах лексер будет работать также, как и парсер со стеком, бэктрекингом, lookahead и т.д. Я это так понимаю, не вижу другой альтернативы (не смотрел как в ANTLR это реализовано), и, как следствие, снижение производительности в разы для таких правил. Но это крутая функция, т.к. позволяет на уровне лексера реализовать #if #else директивы из C#, или интерполированные строки представить в виде лексем.
                              0

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


                              Но это крутая функция, т.к. позволяет на уровне лексера реализовать #if #else директивы из C#, или интерполированные строки представить в виде лексем.

                              Здесь уже без семантических предикатов не обойтись.

                                0
                                Тут даже семантических предикатов мало, нужен уже полноценный парсер, чтобы #if #elif #else #endif реализовать. Я боялся, что это станет проблемой, но пока обошлось только обычным лексером с предикатами, правда для ограниченного сверху кол-ва #elif условий, получилось такое:

                                Лексер условных C# директив
                                // Conditional directive

                                @fragment
                                directive_eval_condition
                                : { return EvalCondition(context); }? directive_skip_condition
                                ;

                                @fragment
                                directive_inverse_eval_condition
                                : { return EvalCondition(context) == false; }?
                                ;

                                @fragment
                                directive_skip_condition
                                : ~[\n]*
                                ;

                                @fragment
                                directive_to_endif
                                : ~[#]* '#endif'
                                ;

                                @fragment
                                directive_to_elif
                                : ~[#]* '#elif'
                                ;

                                @fragment
                                directive_to_else
                                : ~[#]* '#else'
                                ;

                                @fragment
                                directive_to_else_or_endif
                                : ~[#]* ('#else' | '#endif')
                                ;

                                @fragment
                                directive_skip_to_endif
                                : directive_to_elif* directive_to_else? directive_to_endif
                                ;

                                @fragment
                                directive_skip_to_elif
                                : directive_to_elif
                                ;

                                @skip
                                directive_if
                                : '#if' (directive_eval_condition | directive_inverse_eval_condition (directive_try_elif | directive_try_else))
                                ;

                                @fragment
                                directive_try_elif
                                : directive_skip_to_elif (directive_eval_condition | directive_inverse_eval_condition (directive_try_elif_1 | directive_try_else))
                                ;

                                @fragment
                                directive_try_elif_1
                                : directive_skip_to_elif (directive_eval_condition | directive_inverse_eval_condition (directive_try_elif_2 | directive_try_else))
                                ;

                                @fragment
                                directive_try_elif_2
                                : directive_skip_to_elif (directive_eval_condition | directive_inverse_eval_condition (directive_try_elif_3 | directive_try_else))
                                ;

                                @fragment
                                directive_try_elif_3
                                : directive_skip_to_elif (directive_eval_condition | directive_inverse_eval_condition directive_try_else)
                                ;

                                @fragment
                                directive_try_else
                                : directive_to_else_or_endif
                                ;

                                @skip
                                directive_elif
                                : '#elif' directive_skip_to_endif
                                ;

                                @skip
                                directive_else
                                : '#else' directive_skip_to_endif
                                ;

                                @skip
                                directive_endif
                                : '#endif'
                                ;

                  0
                  Кроме того, во всех примерах про парсинг, которые я встречал, парсинг выражения "A+B+C" представляется двоичным деревом. Сейчас проверил, в этой книге тоже так написано. Это сложно и неоптимально, правильнее делать произвольным деревом, так можно создать одну временную переменную и накапливать в ней результат. А с двоичным деревом будет несколько переменных, по одной на каждую пару операндов, и это надо будет дополнительно оптимизировать.

                  Это ни правильно, ни неправильно. В одних случаях удобней бинарное или даже унарное представление, в других — n-арное. Первое используется в функциональном программировании, где все представляется функцией с одним аргументом (каррирование). Вторую запись удобней использовать для математических оптимизаций благодаря ассоциативности. Об этом я писал в статье по парсингу и упрощению математических выражений.


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

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

                    А зачем там именно дерево в AST? Массив из нескольких значений тоже можно преобразовать в последовательные вызовы функций с одним аргументом.

                  0
                  Из чистого любопытства — а что вы такого конкретно реализовали в ~30 тыс строк, и на каком это языке было? Я писал несколько раз парсер LL(1), там получается сильно меньше. Ну так где-то 5к наверное, не более. Хотя конечно, если делать аналог ANTLR с поддержкой разных целевых языков — то тут объемы могут быть любыми. Ну и LL(1) конечно, наверное самый простой и прямолинейный в реализации, другие могут побольше получиться.
                    0
                    Это на C#. ~30к строк кода — это все строки исходного кода, включая объявления классов/свойств и т.д., непосредственно исполнимых строк всего 7к (так считает метрики Visual Studio) ~5к это сам генератор, который по файлу грамматики создаёт C# код с описанием грамматики и классы синтаксического дерева, а оставшиеся 25к — это исполняющая среда. В результате оно и получается аналогом ANTLR (по функциональности), но целевой язык только C#.
                  +1

                  Какая асимптотика у алгоритма? Наивный парсинг легко становится экспоненциальным. Для контекстно-свободной грамматики возможен парсинг за O(n) для однозначной или за O(n^3) для неоднозначной грамматики.

                    0

                    Под n имеется в виду количество чтений из потока символов? Это точно больше O(n), так как при неудачном парсинге варианта происходит откат и парсинг следующего с той же позиции. Оценить точнее я затрудняюсь, так как можно написать грамматику с левой рекурсией, которая зациклит парсер. Но явно есть зависимость от количества вариантов в правилах.
                    Перебор это конечно медленно. Можно сказать, что сама грамматика это программа, а парсер это процессор. Какую грамматику напишете, так и будет работать. Если написать грамматику с большим уровнем вложенности правил, которые содержат много выражений и отличаются только последним, то это конечно будет долго работать, но это в любом движке будет долго работать.
                    Я писал, как можно заменить перебор на хеш-таблицу, это уменьшит алгоритмическую сложность.


                    Если взять пример для сложения отсюда, то неоднозначность правил никак не влияет, движок берет первый подходящий вариант правила. Вторая и более альтернативы получаются недоступными.

                    0
                    LR(1) парсер не пробовали реализовать? Должно помочь с проблемами по типу левой рекурсии. В свое время делал и рекурсивный спуск и LL(1) и LR(1) и LALR(1), как раз в контексте разбора произвольной грамматики, LR(1) показался мне самым эффективным из них. Хотя рекурсивный спуск, конечно, реализуется в разы проще.
                      0

                      Нет, я вообще в теории не очень разбираюсь, просто попробовал сделать на практике из интереса.


                      Я бы не сказал, что левая рекурсия это проблема, которую надо решать. Она ничем не помогает, то есть нет цели делать так, чтобы это работало. Просто не надо ее использовать, спуск по приоритетам с квантификаторами * удобнее в обработке.

                        0
                        Я бы не сказал, что левая рекурсия это проблема, которую надо решать. Она ничем не помогает, то есть нет цели делать так, чтобы это работало. Просто не надо ее использовать, спуск по приоритетам с квантификаторами * удобнее в обработке.

                        Опять-таки спорное утверждение. Во-первых, леворекурсивные правила легче для написания и восприятия, запись с ними короче. Во-вторых, для обработки тоже могут быть легче, если нужно обработать все бинарные выражения скопом, а не вызывать один и тот же метод в разных нелеворекурсивных альтернативах.

                          0

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

                          0
                          >левая рекурсия это проблема, которую надо решать
                          Ну, это зависит от алгоритма разбора. В зависимости от него некоторые виды рекурсии могут быть недопустимы. Ну то есть, если чисто формально, есть языки, которые являются LL(1) допустим (могут быть описаны такой грамматикой), но не все грамматики, которые их описывают, тоже будут LL(1). И если вы интуитивно написали леворекурсивную грамматику, то парсер ее не съест, а сделать из нее вручную не леворекурсивную не всегда просто.

                          В этом смысле рекурсия проблема.
                            0
                            Тут уже за меня всё ответили :)
                            Ни в коем случае не критикую ваш подход, как по мне — главное, чтобы поставленная задача была решена, конкретный способ и терминология — это уже детали.
                            LR(1) грамматики удобнее в том плане, что с их помощью можно описать большее количество грамматик, чем при помощи LL(1).
                            И ещё один момент — если вы подаёте на вход произвольные грамматики, рано или поздно на вход попадёт некорректная грамматика. Как решается эта проблема в случае с рекурсивным спуском?
                              0

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

                                0
                                А как быть, если грамматика неоднозначная, или есть недостижимые правила продукции?
                                  0

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

                          0
                          Смотрю в грамматику и немного недопонимаю.
                          «Листья» выражений описаны так:

                          PrimaryExpression:
                          | NewExpression
                          | FunctionCall
                          | VariableReference
                          | Literal
                          | '(' Expression ')'
                          ;


                          При этом Expression описан так:

                          Expression:
                          TernaryExpression AssignExpression?
                          ;


                          А что будет при разборе «x * (y + 2)»?
                          Ведь в скобках не присваивание и не тернарное выражение.

                          Я от php далек, могу чего-то не понимать )
                            0
                            Пардон, понял. Там у тернарного выражения правая часть может отсутствовать.
                            0
                            C:
                                | A1? A2* A3
                                | B1? B2+ B3
                            ;

                            Здесь специально так написано? Согласно ANTLR синтаксису здесь будет лишняя пустая альтернатива, которую лучше избегать. К тому же неявная.


                            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);
                            }

                            Это выглядит не оптимально, т.к. сравниваются строки, а не типы токенов в числовом виде.
                            Хотя об этом вы и так пишете в конце как о потенциальном улучшении.


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

                            Чтобы точно удостовериться: а вы же использовали в ANTLR быстрый режим SLL при измерении скорости?


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

                            Есть еще такая PHP грамматика в официальном репозитории и новый PHP рантайм, который появился с версии ANTLR 4.8. Вы не пробовали замерять их производительность?


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

                            Ну это по-любому не правильно, потому что условие выхода из рекурсии вообще отсутствует.


                            Кстати, добро пожаловать в компиляторный чат в Telegram, если вас еще там нет :)

                              0
                              Согласно ANTLR синтаксису здесь будет лишняя пустая альтернатива, которую лучше избегать.

                              Не, это уже пример грамматики. Мне вот эти мелочи и не нравятся в ANTLR. Зачем нужны пустые альтернативы, опциональность правила ведь можно квантификатором задать?


                              а вы же использовали в ANTLR быстрый режим SLL при измерении скорости?

                              Нет, я просто выполнил инструкции для C++, которые написаны в доках. Попробую так сделать.


                              Есть еще такая PHP грамматика в официальном репозитории и новый PHP рантайм, который появился с версии ANTLR 4.8. Вы не пробовали замерять их производительность?

                              У вас ссылка на грамматику на мой репозиторий ведет. Если вы про свою говорите, то пробовал. C рантаймом на JavaScript в Chrome парсит файл GdlParser.php минут 10, с рантаймом на PHP вообще не дождался, с рантаймом на C++ не помню точно сколько, но тоже многовато. В любом случае в статье надо было на одинаковых грамматиках сравнивать, а то можно сказать "а у вас там грамматика неточная, поэтому быстрее".


                              Кстати, хочу поблагодарить за грамматики для PHP и C#. Когда изучал ANTLR, они помогли разобраться, как это работает.


                              Кстати, добро пожаловать в компиляторный чат в Telegram, если вас еще там нет :)

                              Спасибо, может загляну как-нибудь)

                                0
                                Не, это уже пример грамматики. Мне вот эти мелочи и не нравятся в ANTLR. Зачем нужны пустые альтернативы, опциональность правила ведь можно квантификатором задать?

                                Кому-то удобней описывать опциональность таким способом. К тому же ANTLR генерирует предупреждения на правила с пустой альтернативой:


                                rule contains an optional block with at least one alternative that can match an empty string

                                Хотя соглашусь, что лучше всегда использовать квантификатор ?. Я никогда не использую пустые альтернативы.


                                Нет, я просто выполнил инструкции для C++, которые написаны в доках. Попробую так сделать.

                                Попробуйте, потому что это драматически увеличивает скорость для большинства грамматик и файлов.


                                У вас ссылка на грамматику на мой репозиторий ведет. Если вы про свою говорите, то пробовал. C рантаймом на JavaScript в Chrome парсит файл GdlParser.php минут 10, с рантаймом на PHP вообще не дождался, с рантаймом на C++ не помню точно сколько, но тоже многовато. В любом случае в статье надо было на одинаковых грамматиках сравнивать, а то можно сказать "а у вас там грамматика неточная, поэтому быстрее".

                                Прошу прощения, имел в виду свою грамматику. Странно, что у вас так медленно отработало. Я тестил производительность в 2016 году, и она была высокой:


                                WebGoat.PHP

                                Обработанных файлов — 885. Общее количество строк — 137 248, символов — 4 461 768. Приблизительное время работы — 00:00:31 сек (лексер 55%, парсер 45%).

                                К тому же лексер в текущий версии еще больше оптимизирован и занимает наверное меньше 5% от общего времени. Т.е. весь процесс должен ускоряться еще раза в 2.


                                Кстати, хочу поблагодарить за грамматики для PHP и C#. Когда изучал ANTLR, они помогли разобраться, как это работает.

                                Пожалуйста, хоть кому-то еще это пригодилось :)

                              0
                              Как уже вам и советовали, для начала, напишите парсер чего нибудь попроще, ini, csv, json, yaml или xml. Попробуйте улучшить, например, по потреблению памяти, и/или скорости работы.
                              После этого, попробуйте разбирать известные языки, минимальное подмножество Си или паскаля, например.
                              Уже на этом этапе у вас появится пища для размышлений, и, возможно, вы захотите уделить время теории.
                              Вы взялись за непосильную, для вас, а потому и бессмысленную работу. Будьте последовательны и терпеливы. Я искренне желаю вам удачи.
                                0
                                Как уже вам и советовали, для начала, напишите парсер чего нибудь попроще, ini, csv, json, yaml или xml.

                                Я уже универсальный написал)


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

                                Ну я вот в статье PHP разбирал, думаю тоже подойдет.

                                +1

                                KvanTTT xmetropol
                                Провел тестирование с учетом того, что вы писали в комментах. Для ANTLR парсинг запускался 2 раза в одном процессе, поэтому в выводе 2 результата.


                                JSON, размер 6.4 Мб, массив на 100000 объектов. Если делать больше, расходуется несколько гигабайт оперативной памяти и затрагивается swap.


                                Код для генерации JSON
                                <?php
                                echo '[' . "\n";
                                
                                $N = 100000;
                                for ($i = 0; $i < $N; $i++) {
                                    $data = [
                                        'id' => rand(1, 1000000000),
                                        'name' => preg_replace('/[^\w]/', '', random_bytes(20)),
                                        'data' => [
                                            'field1' => rand(1, 10),
                                            'field2' => preg_replace('/[^\w]/', '', random_bytes(10)),
                                        ],
                                    ];
                                    echo json_encode($data) . ($i === $N - 1 ? '' : ',') . "\n";
                                }
                                
                                echo ']' . "\n";

                                Запуск php > big.json


                                # ANTLR без SLL
                                Duration: 0.731091
                                Duration: 0.690472
                                
                                # ANTLR c SLL
                                Duration: 0.627404
                                Duration: 0.593009
                                
                                # GdlParser
                                Duration: 47.6176

                                ANTLR быстрее в 70 раз, SLL влияет мало, второй запуск занимает почти столько же, сколько и первый.


                                PHP, грамматика Php.g4 из статьи


                                # ANTLR без SLL
                                Duration: 0.220739
                                Duration: 0.079137
                                
                                # ANTLR c SLL
                                Duration: 0.146379
                                Duration: 0.003767
                                
                                # GdlParser
                                Duration: 0.022174

                                ANTLR без SLL медленнее в 4 раза, чем GdlParser, c SLL быстрее в 6 раз, первый запуск занимает значительно дольше.


                                PHP, грамматика PhpParser.g4+PhpParser.g4 из репозитория antlr/grammars-v4


                                # ANTLR без SLL
                                Duration: 1.69277
                                Duration: 0.361671
                                
                                # ANTLR с SLL
                                Duration: 1.29418
                                Duration: 0.004267
                                
                                # GdlParser
                                ---

                                SLL ускоряет в 90 раз, первый запуск занимает значительно дольше, GdlParser не проверялся, потому что грамматику долго портировать.


                                Вывод, ANTLR без SLL в некоторых случаях медленнее, с SLL всегда значительно быстрее.


                                код в main()
                                #include <iostream>
                                #include <chrono>
                                
                                #include "antlr4-runtime.h"
                                #include "PredictionMode.h"
                                #include "JSONLexer.h"
                                #include "JSONParser.h"
                                
                                using namespace antlrcpptest;
                                using namespace antlr4;
                                
                                void run()
                                {
                                    std::ifstream stream;
                                    stream.open("../demo/big.json");
                                
                                    ANTLRInputStream input(stream);
                                    JSONLexer lexer(&input);
                                    CommonTokenStream tokens(&lexer);
                                    tokens.fill();
                                
                                    JSONParser parser(&tokens);
                                
                                    parser.getInterpreter<atn::ParserATNSimulator>()->setPredictionMode(atn::PredictionMode::SLL);
                                    parser.removeErrorListeners();
                                    parser.setErrorHandler(std::make_shared<BailErrorStrategy>());
                                
                                    auto t1 = std::chrono::high_resolution_clock::now();
                                    try {
                                        parser.json();
                                    }
                                    catch (const ParseCancellationException& ex) {
                                        std::cout << "exception" << std::endl;
                                        exit(0);
                                    }
                                    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;
                                }
                                
                                int main(int , const char **)
                                {
                                    run();
                                    run();
                                }
                                  +1
                                  Вы когда в следующий раз будете проверять производительность парсера, делайте запуск 10-100 раз в цикле, замеряйте время выполнения и считайте среднее/медианное время (и на С++ и на PHP) Перед основным запуском лучше тоже запустить пару раз. И в тесте на производительность именно парсера лучше исключить чтение из файла на каждой итерации, по-хорошему надо загрузить сначала в оперативную память, и уже из памяти запускать парсер, чтобы исключить время чтения с диска на работу алгоритма. А так, то что с Json разница между 1-м и 2-м запуском небольшая — это потому что там размер грамматики крохотный и DFA строится очень быстро, вот на грамматике PHP это уже должно было отразиться.
                                    0

                                    Я знаю как замеряется производительность, я делал то же самое, только вручную. В выводе цифры, которые близки к средним. А еще в цикле на результат могут влиять всякие алгоритмы кеширования и бранч-предикторы в процессоре, которые не будут влиять при обычном использовании.
                                    Файл загружается в память движком ANTLR в функции ANTLRInputStream::load().

                                    0

                                    Интересные результаты. ANTLR можно еще ускорить, если не строить дерево разбора, т.е. установить BuildParseTree = false. Но это не бесплатно, так как нужно будет строить свое дерево разбора, причем восходящим образом. Либо же обрабатывать узлы и извлекать необходимую информацию во время вызова listener методов. Благодаря такой оптимизации нам удалось сократить потребление памяти в 2.5 раза и увеличить производительность на парсинге 30 Мб PL/SQL файла. Об этом я также писал в одном из комментов к статье Вредные советы при работе с ANTLR.


                                    Впрочем у lastrix в статьях описаны и другие советы, которые помогают добиться космической скорости с ANTLR :)

                                    0
                                    Также можно не использовать GdlParser как есть, а сделать генератор парсера по грамматике для конкретного языка.

                                    JSON, размер 6.4 Мб, массив на 100000 объектов.
                                    # ANTLR c SLL
                                    Duration: 0.627404
                                    Duration: 0.593009

                                    В общем, если кому-то интересно, я сделал генератор. Сгенерированный парсер для JSON работает в 3 раза быстрее, чем ANTLR c SLL.
                                    Ветка generator в репозитории.


                                    Сначала я проверил функцию json_decode() в PHP. Она обрабатывает этот файл в 4 раза быстрее.


                                    php
                                    <?php
                                    $content = file_get_contents('../big.json');
                                    $t1 = microtime(1);
                                    $a = json_decode($content);
                                    $t2 = microtime(1);
                                    echo ($t2 - $t1) . "\n";
                                    
                                    // 0.1377968788147

                                    Значит это возможно.


                                    Грамматика JSON несложная, я написал парсер вручную и попробовал оптимизировать.
                                    Основное время занимают вызовы new GdlNode. То есть если пробежать по файлу, возвращая один и тот же объект-заглушку, это занимает очень мало времени. Значит надо уменьшать количество узлов.


                                    Я добавил возможность указывать флаги для правила, флаги могут быть Skip, Lexeme, KeepSpaces ('-', 'L', 'S').
                                    Skip это вместо обработки "пропускаем названия с маленькой буквы".
                                    Lexeme это для того, чтобы не создавать безымянные узлы в правилах, которые состоят из одного символа. Например, AnySymbol(L): .; будет создавать 1 именованный узел со строковым значением, а не 2, как раньше.
                                    KeepSpaces это для отключения пропуска пробелов в правилах для строк или бинарных данных.
                                    Lexeme всегда содержит все символы, поэтому Lexeme и KeepSpaces взаимоисключающие, можно указать только один из них. Лексемы могут быть вложенные, результат всех составляющих лексем просто конкатенируется.


                                    Кстати, заголовок все еще актуальный, после этих изменений размер класса GdlParser в PHP версии 384 строки.


                                    В PHP объект создается при встрече первой пары, сама пара в парсере скорее всего стековая переменная. Следующие пары просто добавляются в существующий объект. То есть на саму пару динамическая память не выделяется.
                                    Также PHP не создает объектов на символы, задающие разметку — запятые, скобки и т.д.


                                    Я сделал генератор парсера, который работает аналогично — строки и числа это лексемы, для каждой лексемы создается 1 узел GdlNode, символы разметки пропускаются.
                                    Отдельной фазы лексического анализа при этом нет, просто по-другому обрабатывается результат. Функции для парсинга лексем при успешном парсинге возвращают длину, которую они распарсили, в вызывающей функции длины суммируются, можно сказать, что это ленивая конкатенация. объект GdlNode создается только в функции для парсинга обычного правила, которая вызвала парсинг лексемы верхнего уровня, из потока берется строка нужной длины.


                                    ./parser2
                                    Duration: 0.207239

                                    Если убрать из грамматики для JSON узел Pair, то есть скопировать его содержимое в узел Obj, время выполнения уменьшается до 0.16, почти так же, как в PHP. С одной стороны, у него еще свои внутренние действия есть, с другой в грамматике создается дополнительный узел Value на каждое значение.


                                    Если создавать узлы на все лексемы, то есть в том числе и на разметку, как делает ANTLR, то время парсинга увеличивается до 0.30. Все равно получается в 2 раза быстрее.

                                      0
                                      В общем, если кому-то интересно, я сделал генератор. Сгенерированный парсер для JSON работает в 3 раза быстрее, чем ANTLR c SLL.

                                      Ну по-моему не особо впечатляющий результат. Стоит ли овчинка выделки? А по парсингу PHP какое ускорение?


                                      Если создавать узлы на все лексемы, то есть в том числе и на разметку, как делает ANTLR, то время парсинга увеличивается до 0.30. Все равно получается в 2 раза быстрее.

                                      В ANTLR тоже можно выкинуть всякое, но нужно ли? Не пробовали парсинг с опцией BuildParseTree = false?

                                        0
                                        Стоит ли овчинка выделки?

                                        Думаю да.
                                        — Синтаксис грамматик удобнее
                                        — Проще задавать сложные конструкции
                                        — Работает быстрее


                                        А по парсингу PHP какое ускорение?

                                        Для PHP 0.0022, в 2 раза быстрее.


                                        В ANTLR тоже можно выкинуть всякое, но нужно ли?

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


                                        Не пробовали парсинг с опцией BuildParseTree = false?

                                        Не пробовал, но мой парсер же строит дерево, это будет некорректное сравнение.

                                          0

                                          Нашел способ, как построить дерево с использованием vector, без создания отдельных узлов через new. Декодирование JSON стало 0.08, для PHP ускорилось аналогично.

                                            0
                                            Думаю да.
                                            — Синтаксис грамматик удобнее
                                            — Проще задавать сложные конструкции
                                            — Работает быстрее

                                            Ну синтаксис — это субъективно. Я не нашел ничего принципиального, что упрощает процесс разработки грамматик. Можно еще раз краткую выжимку что проще описывается у вас по сравнению с ANTLR, прямо по пунктам?


                                            Скорость — насколько понимаю тесты производились с C++ рантаймом ANTLR. Но на моем опыте самые быстрые и оптимизированные рантаймы сейчас — Java и C# optimized. В идеале хотелось бы увидеть сравнение и с ними.


                                            А минусы такие:


                                            • Отсутствие коммьюнити и плагинов для разработки грамматик
                                            • Отсутствие базы грамматик (насколько понимаю — сейчас есть только PHP и Json)
                                            • Малое количество рантаймов (PHP и C++)
                                            • Потенциальные неучтенные критичные баги, которые пока что не вскрылись, потому что проект в начальной стадии разработки.
                                              +1

                                              С минусами согласен, но это у всех новых проектов так. Но я в общем-то не продвигаю этот проект, это просто в стиле "смотрите, так тоже можно".


                                              Проще описываются:
                                              — Конструкции наподобие asm-вставок в C++ asm { ... }. В GDL она ничем не отличается от любого другого правила. В ANLTR, как я понимаю, надо объявлять отдельную лексему asm { и возиться с push mode / pop mode.
                                              — Конструкции типа Nowdoc/Heredoc. В GDL можно просто поставить обработчик на начальный и конечный элемент, без изменения процесса парсинга в наследнике, как в ANTLR.
                                              — Элементы с lookahead. В ANTLR строка с кавычками и эскейпингом задается вот так:
                                              StringLiteral: '"' (~["\\] | EscapeSequence)* '"'
                                              Используется отрицание и дублируется завершающий элемент. В GDL вообще нет отрицания, просто пишется то что нужно:
                                              StringLiteral: '"' (EscapedSymbol | .)*>> '"'


                                              Также с флагами, о которых я писал в комментарии, можно любое правило превратить в лексему или пропустить, что улучшает производительность. Можно все правила объявить лексемами и получить валидатор формата (например, содержит ли файл валидный json) или listener, если задать для нужных правил функции-обработчики. Изменения грамматики минимальны.


                                              Рантайм для сгенерированного парсера всего 3 класса, в отличие от рантайма ANTLR.


                                              C Java и C# попробую сравнить, но можно и по C++ оценить. Для JSON, если сгенерировать парсер без добавления разметки в результат парсинга, GDL быстрее в 10 раз, чем ANTLR с SLL. С разметкой где-то в 4-6 раз. Если вместо StringDescriptor использовать std::string и копирование строк, выполнение замедляется в 2 раза. То есть если C# версия ANTLR быстрее C++ в 2-3 раза, то они работают плюс-минус одинаково.


                                              Замедление работы может быть заметно, если много ключевых слов или элементов разметки начинается с одинаковых символов (как в private | protected), потому что используется просто посимвольное сравнение и откат. Но это не такой уж частый случай.

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

                                        Самое читаемое