Комментарии 51
Я знаю про книгу дракона, хоть и не читал ее. Я имею представление о том, что написано в первых 2 главах, статья как раз о том, что во-первых, это не так сложно, во-вторых, необязательно делать именно так, то есть делить на лексер и парсер и так далее.
Кроме того, во всех примерах про парсинг, которые я встречал, парсинг выражения "A+B+C" представляется двоичным деревом. Сейчас проверил, в этой книге тоже так написано. Это сложно и неоптимально, правильнее делать произвольным деревом, так можно создать одну временную переменную и накапливать в ней результат. А с двоичным деревом будет несколько переменных, по одной на каждую пару операндов, и это надо будет дополнительно оптимизировать.
Для примера, можно попробовать несложную грамматику Json или Xml и проанализировать файл размером в 100мб
Так я проверил построение дерева на грамматике для полноценного языка программирования, какой смысл на более простых проверять?
Проверил на JSON, оказалось не все так просто. ANTLR работает быстрее. Думаю, тут сказывается работа со строками (ANTLR генерирует enum), а также то, что на простые правила вида AnySymbol: . создаются 2 объекта GdlNode, а не 1. На больших объемах данных это влияет на производительность, поправлю этот момент в статье.
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 первой альтернативой, в реальной грамматике реального ЯП такие выражения будут редкостью, но наивный парсер такой порядок заставит выполнить полный перебор всех возможных комбинаций.
Почитайте немного про лексический/синтаксический анализ (а ещё немного про теорию формальных языков)
Как я уже сказал, я знаком с этими темами. Целью статьи было показать, что можно сделать проще, хоть и работать это будет дольше.
То, что вы называете 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
Верно, поэтому надо делать через спуск с приоритетами. Примерно как здесь.
Абстрактное дерево — это действительно назначение, но ниже вам написали, что оно не бинарное, в общем случае оно 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»
Если разница в 2-3...5 раз, то ладно, а если она в 100-1000 раз отличается в пользу ANTLR, то практического применения кроме как несложных грамматик и небольших документов немного
На исходнике с PHP разница в 10 раз в пользу GdlParser. На JSON да, ANTLR лучше работает, разница где-то в 7 раз.
"Небольшие документы" — это 99% файлов с исходным кодом на каком-либо языке программирования.
А, вот оно что. Я проверял несколько запусков консольного приложения, в пределах одного запуска парсинг происходит 1 раз. Да, если вызывать парсинг в коде 2 раза, второй раз значительно быстрее. Спасибо за информацию, поправлю статью.
Для JSON разницы почти никакой, зато для PHP значительная, подробности ниже
я его реализовал через DFA и там нет никаких lookahead
Оно в таблице состояний закодировано. Примерно там, где состояние для входящего символа '*', и надо решить, заканчивается комментарий или нет. Но согласен, в явном виде его нет.
Регулярные выражения работают через конечные автоматы, и lookahead через них же работает.
но ниже вам написали, что оно не бинарное, в общем случае оно n-арное
Так это писали про мои слова "правильнее делать произвольным деревом". "Произвольное" — это и есть n-арное, то есть я про это и говорю.
while ((ch = stream.ReadNext()) != -1)
{
dfaState = dfaState.GetNext(ch);
if (dfaState.Break)
break;
}
Вообще в регулярных выражениях используется расширение оператора Клини, ленивые квантификаторы, и тогда правило для комментария выглядит так '/*' .*? '*/', и в реализации конечного автомата при переходе из одного состояния в другое при прохождении символа через ленивый оператор такое состояние помечается атрибутом, который просто «запрещает» повторное вхождение в эту альтернативу. Но никакого lookahead там нет.
lookahead — это когда для принятия решения читается следующий символ из входящего потока и производится его анализ
В регулярных выражениях есть конструкция lookahead, я говорю про нее и аналогичную функциональность.
ленивые квантификаторы, и тогда правило для комментария выглядит так '/' .? '*/'
Да, я писал в статье про ленивые выражения.
Ну вообще лексер в ANTLR тоже контекстно-свободный и следующее правило там допустимо:
COMMENT: '/*' (COMMENT | .)*? '*/';Такой вложенный комментарий распознает следующую строку:
/* level1 /* level2 */ level1 */А обычное не жадное
COMMENT: '/*' .*? '*/'на ней не сработает.
Согласен — я тоже стараюсь избегать рекурсивные правила, но встречал, что новички часто используют их на ровном месте.
Но это крутая функция, т.к. позволяет на уровне лексера реализовать #if #else директивы из 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'
;
Кроме того, во всех примерах про парсинг, которые я встречал, парсинг выражения "A+B+C" представляется двоичным деревом. Сейчас проверил, в этой книге тоже так написано. Это сложно и неоптимально, правильнее делать произвольным деревом, так можно создать одну временную переменную и накапливать в ней результат. А с двоичным деревом будет несколько переменных, по одной на каждую пару операндов, и это надо будет дополнительно оптимизировать.
Это ни правильно, ни неправильно. В одних случаях удобней бинарное или даже унарное представление, в других — n-арное. Первое используется в функциональном программировании, где все представляется функцией с одним аргументом (каррирование). Вторую запись удобней использовать для математических оптимизаций благодаря ассоциативности. Об этом я писал в статье по парсингу и упрощению математических выражений.
К тому же и с двоичным деревом можно накапливать результат, если не строить дерево, а обрабатывать узлы сразу. Но это более сложный подход, в котором используется восходящая обработка.
Какая асимптотика у алгоритма? Наивный парсинг легко становится экспоненциальным. Для контекстно-свободной грамматики возможен парсинг за O(n) для однозначной или за O(n^3) для неоднозначной грамматики.
Под n имеется в виду количество чтений из потока символов? Это точно больше O(n), так как при неудачном парсинге варианта происходит откат и парсинг следующего с той же позиции. Оценить точнее я затрудняюсь, так как можно написать грамматику с левой рекурсией, которая зациклит парсер. Но явно есть зависимость от количества вариантов в правилах.
Перебор это конечно медленно. Можно сказать, что сама грамматика это программа, а парсер это процессор. Какую грамматику напишете, так и будет работать. Если написать грамматику с большим уровнем вложенности правил, которые содержат много выражений и отличаются только последним, то это конечно будет долго работать, но это в любом движке будет долго работать.
Я писал, как можно заменить перебор на хеш-таблицу, это уменьшит алгоритмическую сложность.
Если взять пример для сложения отсюда, то неоднозначность правил никак не влияет, движок берет первый подходящий вариант правила. Вторая и более альтернативы получаются недоступными.
Нет, я вообще в теории не очень разбираюсь, просто попробовал сделать на практике из интереса.
Я бы не сказал, что левая рекурсия это проблема, которую надо решать. Она ничем не помогает, то есть нет цели делать так, чтобы это работало. Просто не надо ее использовать, спуск по приоритетам с квантификаторами * удобнее в обработке.
Я бы не сказал, что левая рекурсия это проблема, которую надо решать. Она ничем не помогает, то есть нет цели делать так, чтобы это работало. Просто не надо ее использовать, спуск по приоритетам с квантификаторами * удобнее в обработке.
Опять-таки спорное утверждение. Во-первых, леворекурсивные правила легче для написания и восприятия, запись с ними короче. Во-вторых, для обработки тоже могут быть легче, если нужно обработать все бинарные выражения скопом, а не вызывать один и тот же метод в разных нелеворекурсивных альтернативах.
Ну, это зависит от алгоритма разбора. В зависимости от него некоторые виды рекурсии могут быть недопустимы. Ну то есть, если чисто формально, есть языки, которые являются LL(1) допустим (могут быть описаны такой грамматикой), но не все грамматики, которые их описывают, тоже будут LL(1). И если вы интуитивно написали леворекурсивную грамматику, то парсер ее не съест, а сделать из нее вручную не леворекурсивную не всегда просто.
В этом смысле рекурсия проблема.
Ни в коем случае не критикую ваш подход, как по мне — главное, чтобы поставленная задача была решена, конкретный способ и терминология — это уже детали.
LR(1) грамматики удобнее в том плане, что с их помощью можно описать большее количество грамматик, чем при помощи LL(1).
И ещё один момент — если вы подаёте на вход произвольные грамматики, рано или поздно на вход попадёт некорректная грамматика. Как решается эта проблема в случае с рекурсивным спуском?
Если грамматика синтаксически правильная, то может быть только ошибка с несуществующим правилом, в этом случае выдается исключение. Если синтаксически неправильная, то будет сообщение об ошибке при парсинге грамматики, ошибки сохраняются в массив в классе парсера и доступны через геттер.
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, если вас еще там нет :)
Согласно ANTLR синтаксису здесь будет лишняя пустая альтернатива, которую лучше избегать.
Не, это уже пример грамматики. Мне вот эти мелочи и не нравятся в ANTLR. Зачем нужны пустые альтернативы, опциональность правила ведь можно квантификатором задать?
а вы же использовали в ANTLR быстрый режим SLL при измерении скорости?
Нет, я просто выполнил инструкции для C++, которые написаны в доках. Попробую так сделать.
Есть еще такая PHP грамматика в официальном репозитории и новый PHP рантайм, который появился с версии ANTLR 4.8. Вы не пробовали замерять их производительность?
У вас ссылка на грамматику на мой репозиторий ведет. Если вы про свою говорите, то пробовал. C рантаймом на JavaScript в Chrome парсит файл GdlParser.php минут 10, с рантаймом на PHP вообще не дождался, с рантаймом на C++ не помню точно сколько, но тоже многовато. В любом случае в статье надо было на одинаковых грамматиках сравнивать, а то можно сказать "а у вас там грамматика неточная, поэтому быстрее".
Кстати, хочу поблагодарить за грамматики для PHP и C#. Когда изучал ANTLR, они помогли разобраться, как это работает.
Кстати, добро пожаловать в компиляторный чат в Telegram, если вас еще там нет :)
Спасибо, может загляну как-нибудь)
Не, это уже пример грамматики. Мне вот эти мелочи и не нравятся в 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, они помогли разобраться, как это работает.
Пожалуйста, хоть кому-то еще это пригодилось :)
После этого, попробуйте разбирать известные языки, минимальное подмножество Си или паскаля, например.
Уже на этом этапе у вас появится пища для размышлений, и, возможно, вы захотите уделить время теории.
Вы взялись за непосильную, для вас, а потому и бессмысленную работу. Будьте последовательны и терпеливы. Я искренне желаю вам удачи.
KvanTTT xmetropol
Провел тестирование с учетом того, что вы писали в комментах. Для ANTLR парсинг запускался 2 раза в одном процессе, поэтому в выводе 2 результата.
JSON, размер 6.4 Мб, массив на 100000 объектов. Если делать больше, расходуется несколько гигабайт оперативной памяти и затрагивается swap.
<?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.6176ANTLR быстрее в 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.022174ANTLR без 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 всегда значительно быстрее.
#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();
}Я знаю как замеряется производительность, я делал то же самое, только вручную. В выводе цифры, которые близки к средним. А еще в цикле на результат могут влиять всякие алгоритмы кеширования и бранч-предикторы в процессоре, которые не будут влиять при обычном использовании.
Файл загружается в память движком ANTLR в функции ANTLRInputStream::load().
Интересные результаты. ANTLR можно еще ускорить, если не строить дерево разбора, т.е. установить BuildParseTree = false. Но это не бесплатно, так как нужно будет строить свое дерево разбора, причем восходящим образом. Либо же обрабатывать узлы и извлекать необходимую информацию во время вызова listener методов. Благодаря такой оптимизации нам удалось сократить потребление памяти в 2.5 раза и увеличить производительность на парсинге 30 Мб PL/SQL файла. Об этом я также писал в одном из комментов к статье Вредные советы при работе с ANTLR.
Впрочем у lastrix в статьях описаны и другие советы, которые помогают добиться космической скорости с ANTLR :)
Также можно не использовать 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 раза быстрее.
В общем, если кому-то интересно, я сделал генератор. Сгенерированный парсер для JSON работает в 3 раза быстрее, чем ANTLR c SLL.
Ну по-моему не особо впечатляющий результат. Стоит ли овчинка выделки? А по парсингу PHP какое ускорение?
Если создавать узлы на все лексемы, то есть в том числе и на разметку, как делает ANTLR, то время парсинга увеличивается до 0.30. Все равно получается в 2 раза быстрее.
В ANTLR тоже можно выкинуть всякое, но нужно ли? Не пробовали парсинг с опцией BuildParseTree = false?
Стоит ли овчинка выделки?
Думаю да.
— Синтаксис грамматик удобнее
— Проще задавать сложные конструкции
— Работает быстрее
А по парсингу PHP какое ускорение?
Для PHP 0.0022, в 2 раза быстрее.
В ANTLR тоже можно выкинуть всякое, но нужно ли?
У меня ничего не выкинуто в плане парсинга. Парсер идет по файлу, строится дерево, которое можно использовать в компиляторе, вызываются произвольные функции. В сгенерированном парсере даже утечек памяти нет, все созданные узлы добавляются в массив и удаляются в деструкторе. Разве что ошибки обрабатывать можно получше, чтобы незавершенные выражения не отменяли парсинг. Но это не будет влиять на парсинг синтаксически правильного исходника.
Не пробовали парсинг с опцией BuildParseTree = false?
Не пробовал, но мой парсер же строит дерево, это будет некорректное сравнение.
Нашел способ, как построить дерево с использованием vector, без создания отдельных узлов через new. Декодирование JSON стало 0.08, для PHP ускорилось аналогично.
Думаю да.
— Синтаксис грамматик удобнее
— Проще задавать сложные конструкции
— Работает быстрее
Ну синтаксис — это субъективно. Я не нашел ничего принципиального, что упрощает процесс разработки грамматик. Можно еще раз краткую выжимку что проще описывается у вас по сравнению с ANTLR, прямо по пунктам?
Скорость — насколько понимаю тесты производились с C++ рантаймом ANTLR. Но на моем опыте самые быстрые и оптимизированные рантаймы сейчас — Java и C# optimized. В идеале хотелось бы увидеть сравнение и с ними.
А минусы такие:
- Отсутствие коммьюнити и плагинов для разработки грамматик
- Отсутствие базы грамматик (насколько понимаю — сейчас есть только PHP и Json)
- Малое количество рантаймов (PHP и C++)
- Потенциальные неучтенные критичные баги, которые пока что не вскрылись, потому что проект в начальной стадии разработки.
С минусами согласен, но это у всех новых проектов так. Но я в общем-то не продвигаю этот проект, это просто в стиле "смотрите, так тоже можно".
Проще описываются:
— Конструкции наподобие 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), потому что используется просто посимвольное сравнение и откат. Но это не такой уж частый случай.
Парсер данных по произвольной грамматике в 400 строк