Во вторник, 19 ноября, представлен релиз re2c – генератора лексических анализаторов (он же компилятор регулярных выражений в код на целевом языке программирования). re2c специализируется на генерации быстрых и легко встраиваемых лексеров. Он отличается от более известного аналога flex гибким интерфейсом, генерацией оптимизированных нетабличных лексеров и поддержкой захватов (submatch extraction) на основе детерминированных конечных автоматов с тэгами (TDFA). re2c используется в проектах, где важна скорость работы лексера, например в Ninja и в PHP.

( читать дальше... )

>>> Подробности

В четверг 27 января состоялся релиз генератора лексических анализаторов re2c 3.0. Основное изменение — добавлена кодогенерация в Rust.

Напомним, что re2c специализируется на генерации быстрых и легко встраиваемых лексеров. Он отличается от более известного аналога flex гибким интерфейсом, генерацией оптимизированных нетабличных лексеров и поддержкой захватов (submatch extraction) на основе детерминированных конечных автоматов с тэгами (TDFA). re2c используется в проектах, где важна скорость работы лексера, например в Ninja и в PHP.

На сайте есть много примеров, теперь и на языке Rust.

>>> Подробности

RE2C — генератор лексических анализаторов для языков C и C++, созданный в 1993 году Питером Бамбулисом в качестве альтернативы небезызвестному Flex. Основной целью RE2C является генерация очень быстрых лексеров: по скорости исполнения они должны не уступать коду, написанному и оптимизированному вручную (в пределах разумного). В отличие от Flex, RE2C не использует табличную модель лексера: он кодирует конечный автомат прямо в виде программы на С, состоящей из меток и условных переходов. Полученный лексер оказывается не только быстрее, но часто ещё и меньше [1] (RE2C минимизирует конечный автомат и применяет ряд других оптимизаций). Другая особенность RE2C — отсутствие жёсткого интерфейса: в отличие от Flex, он не генерирует код «обвязки» между лексером и внешним миром. Ответственность за написание этого кода остаётся на пользователе, что даёт большую свободу и позволяет приспосабливать лексеры к уже существующему программному окружению.

Смена мажорной версии (впервые за всю историю проекта) объясняется не поломкой обратной совместимости, а нетривиальным расширением возможностей генератора: кроме обычного распознавания регулярных грамматик (англ. recognition) RE2C теперь умеет частичный синтаксический разбор (англ. submatch extraction). Эта возможность легко реализуема на основе недетерминированных автоматов, и поэтому давно присутствует во многих утилитах (grep, sed), библиотеках регулярных выражений (RE2) и языках (Perl, JS). А вот в генераторах лексеров эта возможность обычно отсутствует (Lex, Flex, Quex), корректно работает только на малой части случаев (Ragel) или реализована путём серьёзного усложнения модели (Tlex). Одно из следствий невозможности синтаксического разбора средствами детерминированных конечных автоматов — изначально поломанный оператор предпросмотра в Lex и Flex.

Алгоритм разбора, заложенный в основе RE2C, был предложен Вилле Лаурикари в 2000 году [2]. Этот алгоритм хорош тем, что усложняет модель вычислений ровно настолько, насколько того требует детализация синтаксического разбора в каждом конкретном случае: для обычных задач распознавания модель Лаурикари соответствует простому детерминированному автомату. RE2C использует «улучшенную и дополненную» версию алгоритма, предложенную автором сего поста [3].

[1] Cтатья 1993 года, в которой проведён сравнительный анализ RE2C, Flex и других генераторов

[2] Статья 2000 года, которая описывает быстрый алгоритм разбора

[3] Статья 2017 года, которая описывает новый ещё более быстрый алгоритм разбора

>>> Подробности

Состоялся релиз flex 2.6.2 — генератора быстрых лексических анализаторов.

Основные изменения:

• Для configure добавлена опция --enable-warnings, включающая предупреждения компилятора при сборке.
• Добавлен словенский перевод.
• Исправлено множество ошибок, в том числе ошибка сегментирования при вызове yyrestart(NULL).

>>> Подробности

Apache представил первый выпуск FlexJS, продолжающего развитие Flex SDK в направлении ухода от привязки к технологиям Adobe Flash. FlexJS позволяет компилировать Flex-приложения, написанные с использованием MXML и ActionScript, в формат SWF и в форму web-приложений на базе CSS, JavaScript и HTML5. Компилированный таким образом, Flex-проект может быть выполнен в обычном браузере без установки дополнительных плагинов. Компиляция осуществляется при помощи кросс-компилятора Flex FalconJX.

>>> Подробности

JavaFX не продемонстрировала выдающейся производительности, зато самое скоростное исполнение анимации на стороне клиента продемонстрировал апплет на чистом Java-коде, далее приводятся результаты замера теста 128 шариков:

Flash/Flex на равных с JavaFX набирает: 21fps
Silverlight/CLR: 40fps
Flash/cacheAsBitmap: 64fps
Java/Swing (optimized): 163fps
Java/PulpCore: 200fps

На системе автора поста тест в конфигурации со спрайтами (Image) на 128 шариках набирает 42fps

>>> Подробности

В этой статье на примере создания простого калькулятора показано, как создать анализатор при помощи инструментов lex/flex и yacc/bison, а затем более подробно рассмотрено, как применить эти принципы к синтаксическому разбору текста. Синтаксический разбор текста - анализ и извлечение ключевых частей текста - важная часть многих приложений. В UNIX® многие элементы операционной системы зависят от синтаксического анализа текста: оболочка, которая используется для взаимодействия с системой, распространенные утилиты и команды типа awk или Perl, вплоть до компилятора Си, используемого для разработки приложений. Анализаторы собственной разработки можно использовать в UNIX-программах (и не только UNIX) для создания простых анализаторов конфигурации или даже для создания своего собственного языка программирования.

>>> Подробности