Немного о лексическом анализе

[RussDragon]

Что ж за неделя своих языков, парсеров и компиляторов такая? :)

[rjhdby]

Есть у меня смутное подозрение, что самописный конечный автомат будет для этой задачи сильно производительней (и, возможно, проще для понимания)

PS Теги для поиска по ним, а не для чтения. Спасибо за статью! :)

[SerafimArts]

Fesor уже пытался запилить его следуя этой же логике, адаптировав для этой цели re2c. Но что получилось в итоге не совсем понятно. Думаю, когда увидит моё упоминание — сможет поподробнее написать к чему пришёл в комментах.

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

[rjhdby]

простой цикл с проходом по буковкам в PHP довольно тормозной.

Это да. С другой стороны, никто не мешает работать не со строкой, а с массивом байт. Оно, по идее, должно быть сильно быстрее.

[SerafimArts]

Заголовок спойлера

<?php
$data = \file_get_contents(__FILE__);
$attempts = 100000;

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    foreach (\str_split($data) as $chars => $char) {
        // Do something
    }
}


/// =====================================


echo \number_format(\microtime(true) - $before, 4) . 's / ' . $chars . "\n";

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    foreach (\unpack('C*', $data) as $bytes => $byte) {
        // Do something
    }
}

echo \number_format(\microtime(true) - $before, 4) . 's / ' . $bytes . "\n";

1) 1.6975s на 573 символа для str_split
2) 11.5845s на 574 байта для unpack

UPD:
3) Ну и ~1.06s на тоже количество для "for" + "$byte = $data[$i]"

[rjhdby]

Как чувствовал — убрал упоминание unpack раньше появления вашего ответа. :)
Про массив байт — это я конечно маху дал, PHP же, какой массив байт?..

Зато добавил к вашему «тесту» третий вариант, с интересным результатом.

Заголовок спойлера

<?php
$data = \file_get_contents(__FILE__);
$attempts = 10000;

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    $data = \file_get_contents(__FILE__);
    foreach (\str_split($data) as $chars => $char) {
        // Do something
    }
}

echo 'str_split: ' . \number_format(\microtime(true) - $before, 4) . 's / ' . $chars . "\n";

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    $data = \file_get_contents(__FILE__);
    foreach (\unpack('C*', $data) as $bytes => $byte) {
        // Do something
    }
}

echo 'unpack   : ' . \number_format(\microtime(true) - $before, 4) . 's / ' . $bytes . "\n";

$before = \microtime(true);

for ($i = 0; $i < $attempts; $i++) {
    $handle=fopen(__FILE__,"r");
    while ($char = fread($handle,1)) {
        // Do something
    }
    fclose($handle);
}

echo 'fread    : ' . \number_format(\microtime(true) - $before, 4) . 's / ' . $bytes . "\n";

str_split: 0.5737s / 967
unpack   : 0.7472s / 968
fread    : 0.1524s / 968

[SerafimArts]

fread: 0.1524s / 968

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

Код тестов

<?php
$data = \file_get_contents(__FILE__);
$attempts = 10000;

function test(string $title, int $attempts, \Closure $expression)
{
    $before = \microtime(true);

    for ($i = 0; $i < $attempts; $i++) {
        $expression();
    }

    $after = number_format(\microtime(true) - $before, 4);

    echo \sprintf('%-13s: %ss', $title, $after) . "\n";
}



test('str_split', $attempts, function() {
    $data = \file_get_contents(__FILE__);

    foreach (\str_split($data) as $chars => $char) {
        // Do something
    }
});

test('unpack', $attempts, function() {
    $data = \file_get_contents(__FILE__);

    foreach (\unpack('C*', $data) as $bytes => $byte) {
        // Do something
    }
});

test('fread', $attempts, function() {
    $handle = fopen(__FILE__, 'rb+');

    while (! feof($handle)) {
        $char = fread($handle, 1);
    }

    fclose($handle);
});

test('$data[$i]', $attempts, function() {
    $data = \file_get_contents(__FILE__);

    for ($i = 0, $bytes = strlen($data); $i < $bytes; ++$i) {
        $char = $data[$i];
    }
});

test('fread + mem', $attempts, function() {
    $handle = fopen('php://memory', 'ab+');
    stream_copy_to_stream(fopen(__FILE__, 'rb+'), $handle);

    while (! feof($handle)) {
        $char = fread($handle, 1);
    }

    fclose($handle);
});

str_split    : 0.8728s
unpack       : 3.9583s
fread        : 1.4985s
$data[$i]    : 0.8127s
fread + mem  : 0.7095s

[bashkarev]

В тесте ошибка, после stream_copy_to_stream указатель не сбрасывается

[SerafimArts]

Это не обязательно. Интерпретатор автоматом закрывает потоки чтения/записи при refcount=0 (т.е. в данном случае при выходе за пределы анонимной функции). Но да, действительно так писать не очень хорошо и с моей стороны была допущена опечатка.

Добавил fclose внутреннего ресурса. Соотношение по скорости, естественно, не изменилось (всё на уровне погрешностей).

Заголовок спойлера

test('fread + mem', $attempts, function() {
    $handle = fopen('php://memory', 'ab+');
    stream_copy_to_stream($fp = fopen(__FILE__, 'rb+'), $handle);

    while (! feof($handle)) {
        $char = fread($handle, 1);
    }

    fclose($handle);
    fclose($fp);
});

str_split    : 0.8551s
unpack       : 3.0591s
fread        : 1.2792s
$data[$i]    : 0.7279s
fread + mem  : 0.5827s

[bashkarev]

код во while не выполняется

test('fread + mem',$attempts, function () {
        $handle = fopen('php://memory', 'ab+');
        stream_copy_to_stream($fp = fopen(__FILE__, 'rb+'), $handle);

        echo 'ftell:', ftell($handle), ', feof:', feof($handle) ? 'true' : 'false', PHP_EOL;
        while (!feof($handle)) {
            $char = fread($handle, 1);
        }

        fclose($handle);
        fclose($fp);
    }
);

[SerafimArts]

Блин, точно! Добавил fseek на 0 и скорость сразу же просела до 1.6541s

[netch80]

> Есть у меня смутное подозрение, что самописный конечный автомат будет для этой задачи сильно производительней (и, возможно, проще для понимания)

Для освоения идеи — наверно, да. Но постоянно такое писать слишком неудобно, а часто и сопровождать.

К счастью, такие возможности медленно, но планомерно проникают в средства.
Даже во flex есть, там это зовётся conditions. re2c — аналогично; вообще, слово conditions тут, похоже, становится основным, хотя я бы предпочёл contexts.

[SerafimArts]

Вот, кстати и ответ на вопрос. Реализация на чистом конечном автомате (webonyx) проигрывает по скорости регуляркам примерно в два раза. Ну и прямо пропорционально по потреблению памяти в случае увеличения объёма сгружаемых туда данных. Можно попробовать самому убедиться, т.к. бенчи прилагаются: https://github.com/SerafimArts/graphql-bench

[Lure_of_Chaos]

Есть два вопроса:
Почему бы не сделать конечный автомат, а апгрейдить регулярки?
Зачем использовать php для такого хардкора?

Я понимаю, что можно и даже проще так, особенно если пока нет более глубокого понимания, но очень хочется, но всё же…

И да, ещё более странно, что говоря о компиляторах, парсерах, лексерах — ни разу не всплыл термин «грамматика», и далее уж КС, ЛКС и вот это вот все…

[SerafimArts]

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

Насколько я понял вопрос — имеется ввиду «почему не запилить НКА, вместо использования регулярок»?

Если есть желание поэкспериментировать с этим и/или переписать какой-нибудь re2c на php с сомнительным результатом (т.е. я намекаю на то, что в PREG, написанном на сях вполне возможно будет это дело работать быстрее, нежели на нативном php), то пожалуйста. Лично мне было откровенно лениво это всё писать, а задачи ДКА/НКА переложил на LL(k) парсер.

Зачем использовать php для такого хардкора?

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

Заголовок спойлера

В моём случае это был GraphQL SDL, который я реализовал полностью с нуля, включая парсер и «комплятор-компиляторов» грамматик: github.com/railt/railt/blob/master/resources/grammar/grammar.pp2, реализацию полноценного интерпретатора с прикручиванием отладчиков:

Но пилить до стабильной версии там ещё довольно много чего, хотя на продакшене уже кое-где используется.

И да, ещё более странно, что говоря о компиляторах, парсерах, лексерах — ни разу не всплыл термин «грамматика», и далее уж КС, ЛКС и вот это вот все…

Ну, как можно заметить по тексту — я сознательно постарался обойти остальные темы, упомянув их лишь вскользь и общими словами, чтобы просто иметь представление. А про BNF и EBNF стоит писать уже после раскрытия тем LL/LR/LALR/SLR парсеров, про которые понаписать можно довольно много чего.

P.S.

и далее уж КС, ЛКС

Эм? Что это за термины? Даже не гуглится ничего.

[pbatanov]

Рискну предположить, что в терминах грамматик под КС подразумевалась группа контекстно-свободных грамматик (то, что идет у вас под перечислением LL/LR/LALR/SLR)

[SerafimArts]

О, да, точно, вполне возможно.

[barbashovtd]

Хоть совершенно не люблю php и стараюсь его обходить, было интересно, особенно удивила обработка 600000 t/s.
Большое спасибо за материалы, сам сейчас занимаюсь разработкой языка, очень кстати подобные статьи, пилите еще, пожалуйста!))
P.S. А любителям Питона зайдет SLY, я думаю

[SerafimArts]

Я бы не хотел писать новую статью на эту тему, поэтому дополню в комментариях, думаю никто не будет против:

Есть один интересный ишью, который я создавал в группе Hoa: https://github.com/hoaproject/Compiler/issues/81

В комментариях к нему один из участников подсказал интересный способ — использовать *MARK символ + preg_match_all, вместо именованных групп + preg_replace_callback, о котором я написал в посте выше. Оказывается, этот вариант даёт ощутимый прирост производительности при использовании встроенного PCRE.

Для примера:
1) вот бенчмарки для multistate реализации preg_match (Hoa) vs preg_replace_callback + named groups (Railt): https://travis-ci.org/SerafimArts/lexer-benchmarks/jobs/506062681
2) а вот бенчмарки с обновлённой версией preg_match (Hoa) vs preg_match_all + mark (Railt): https://travis-ci.org/SerafimArts/lexer-benchmarks/jobs/508295208

И даже не учитывая того факта, что воркер для второго прогона в CI оказался чуть помедленнее первого — всё равно использование *MARK маркера даёт пятикратное ускорение.