#prog #parsing #regex #article (строго говоря, не про разбор, а про распознавание, но всё же)

Можно ли подсчитать производную от регулярного выражения? Можно и нужно!
Статья рассказывает о изученной и эффективной, но почему-то мало известной на практике технике построения распознающих конечных автоматов непосредственно из регулярных выражений. К сожалению, в статье рассматривается лишь задача о соответствии регулярного тексту, в ней ничего не говорится о, скажем, захвате соответствующих частей текста.

"In this paper, we have presented RE derivatives, which are an old, but largely forgotten, technique for constructing DFAs directly from REs. Our experience has been that RE derivatives are a superior technique for generating scanners from REs and they should be in the toolkit of any programmer. Specifically, RE derivatives have the following advantages:
• They provide a direct RE to DFA translation that is well suited to implementation in functional languages.
• They support extended REs almost for free.
• The generated scanners are often optimal in the number of states and are uniformly better than those produced by previous tools.
In addition to presenting the basic RE to DFA algorithm, we have also discussed a number of practical issues related to implementing a scanner generator that is based on RE derivatives, including supporting large character sets"

www.ccs.neu.edu/home/turon/re-deriv.pdf

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

Меня зовут Антон, я студент человек студенческого возраста и в настоящий момент я работаю программистом, по работе пишу в основном... Да, на Rust, а как вы догадались? Я люблю Rust и ненавижу примерно все остальные языки программирования. Круг моих интересов относительно широк, но на канал изливается в основном программирование (серьёзно, около половины постов с хештегом #prog). Этот канал изначально планировался как удобная свалка ссылок, материалов и #meme-ов, и... Он таковым, в сущности, и остался. В своё оправдание я могу сказать, что все статьи (выкладываемые с хештегом #article) я всегда читаю перед тем, как выложить, так что делюсь я тем, что считаю сто‌ящим своей аудитории.

Также ведение своего канала сподвигнуло меня на написание своих постов (и иногда даже перевод чужих статей), которые я выкладываю под хештегом #моё (как, впрочем, и созданные мною мемы). В их числе я хотел бы отметить:
- написание трейта, гарантирующего нулевой размер типа
- оптимизация размера итератора из стандартной библиотеки Rust (увы, не принятая)
- реализация zero-cost форматировщиков даты
- разбор различных способ реализации полиморфизма, с их достоинствами и недостатками
- эпические "Хроники замыканий" в 3 (пока что) частях: раз, два, три
- деликатный и глубокий анализ недостатков регулярных выражений

Для удобства привожу список всех хештегов на канале (может быть пополнен в будущем):

#3dcg
#abnormalprogramming
#algo
#amazingopensource
#anime
#art
#article
#bash
#bio
#blogrecommendation
#c
#cinema
#clojure
#cpp
#csharp
#db
#demoscene
#design
#dotnet
#erlang
#game
#go
#idris
#itsec
#haskell
#js
#java
#julia
#justrustaceanthings
#kbd
#life
#math
#mechanics
#meme
#menacingopensource
#ml
#mood
#music
#outoflinestorage
#parsing
#performancetrap
#php
#pixelart
#politota
#postgresql
#prog
#psy
#puzzle
#python
#quotes
#regex
#retroit
#r
#rust
#rustasync
#rustforlinux
#rustreleasenotes
#rustlib
#scala
#science
#serde
#shell
#soc
#softskills
#sql
#successstory
#suckassstory
#tips
#typescript
#video
#web
#zig

#бомбёжкипост
#культурнаяпрограмма
#лингво
#моё
#право
#трудовыебудни

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

Добро пожаловать на канал!

#prog #parsing #regex #article

Почему эта статься называется "Regular-expression derivatives reexamined"? Это не оригинальная статья, а более современный пересказ оригинальной статьи Брзозовски (вот pdf, но читать не советую — это просто довольно грубый скан с бумаги, над нормальной перепечаткой которого никто не заморачивался). Идея производной от регулярного выражения оказалось достаточно плодотворной, чтобы её можно было обобщить до более продвинутых конструкций. Собственно, в этой статье от Мэтта Майта и прочих (pdf) вводится в рассмотрение производная от контекстно-свободных грамматик (CFG), заданных при помощи взаимно-рекурсивных определений, содержащих альтернативы, конкатенацию и звезду Клини, и на основе этого определения реализуется на Racket парсер (именно парсер, а не распознаватель) таких грамматик. Весь код в итоге занял около 30 строк, но для корректной работы полагался на ленивость, мемоизацию и вычисление неподвижных точек функций (есть также реализация на Haskell, но она выглядит так себе, в частности, там зачем-то есть вызов unsafePerformIO).

Как показал себя этот парсер на практике? Паршиво: на разбор 31-строчного синтаксически корректного файла на Python у парсера ушло три минуты. Причина? Неконтролируемые взятия производной от грамматики приводят к тому, что ошмётки грамматики растут экспоненциально. Введение дополнительного шага обработки, названного авторами "сжатием" (compaction) и состоящей в преобразованиях грамматики, уменьшающей её размер, но сохраняющей поведение, привело к желаемому эффекту — повышению производительности. Тем не менее, производительность всё равно осталась достаточно низкой — на разбор того же 31-строчного файла теперь уходило две секунды. Многовато.

Так что же, парсинг с использованием производных (parsing with derivatives, PwD) является непрактичной игрушкой? Отнюдь, как было показано в статье Майкла Адамса. Сложность у этого алгоритма отнюдь не экспоненциальная, как считали авторы, а кубическая. Также оригинальная реализация была написана несколько неоптимально. Во-первых, вычисление неподвижных точек производилось при помощи многократного вызова одной и той же функции, что приводило в худшем случае к квадратичной сложности. Более умная реализация позволяет найти неподвижную точку за линейное время. Во-вторых, в правилах compaction были пропущены парочка правил переписывания грамматики, из-за отсутствия которых грамматика могла прийти в состояние, далёкому от оптимального, но к которому неприменимы операции переписывания. В-третьих, мемоизация в оригинальной реализации использовала хэш-таблицы (причём вложенные). Перемещение мемоизируемых данных из таблиц непосредственно в узлы грамматики положительно сказалось на производительности (надо отметить, что на практике в этих вложенных таблицах было не более одной записи. Хранение единственного значения, разумеется, снизило возможности мемоизации, но, как ни странно, на практике не сильно сказалось на производительности). Итого? Та же идея, но производительность выше на три порядка. Элегантность кода и краткость кода, впрочем, была потеряна.

Можно ли сделать лучше? В принципе, да. Последовательное взятие производной требует многократного прохода по одному и тому же графу, причём, как правило, обход с корня идёт по почти тому же самому пути. Для оптимизации работы над деревьями есть специальная структура данных, zipper (pdf), которая позволяет сфокусироваться на какой-то части дерева и иметь к ней быстрый доступ (кстати, сам автор, Huet, не считает себя изобретателем этой структуры данных, поскольку она переизобреталась неоднократно, статью же он написал главным образом ради того, чтобы идея была более известна). Встраивание зиппера в PwD позволяет повысить его производительность.

⬇️⬇️⬇️

#prog #regex #rust #rustlib #amazingopensource

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

github.com/pemistahl/grex

(thanks @nosingularity)

#prog #regex #parsing #haskell

Fix-ing regular expressions

TL;DR: We add variables, let bindings, and explicit recursion via fixed points to classic regular expressions. It turns out that the resulting explicitly recursive, finitely described languages are well suited for analysis and introspection.

Если читали мои претензии к регулярным выражениям, то наверняка помните, что одной из моих претензий было отсутствие декомпозируемости. В статье это решается за счёт добавления явных переменных (точнее, привязок в форме let x = r in re). Также добавление явного fix расширяет возможности языка и даёт возможность использовать рекурсию. На практике это означает, что подобное решение в состоянии распарсить известный пример грамматики, являющейся контекстно-зависимой: aⁿbⁿ.

К сожалению, не обошлось без ложки дёгтя: даже с некоторыми оптимизациями производительность итогового решения оставляет желать лучшего — что, в принципе, вполне ожидаемо, учитывая, что распознавание использует подход regular expression derivatives, который при применении в лоб приводит к сильному распуханию промежуточных структур данных. А ещё лично меня несколько расстраивает использование в финальной версии fix и полиморфной рекурсии — это означает, что итоговый результат не переносим в лоб на другие ЯП.

#prog #abnormalprogramming #regex #article

A regular expression to check for prime numbers

(thanks @nerdlair)

#prog #amazingopensource #regex #rust

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

(thanks @sergeysova)

#prog #regex #rust

Rustexp — A Rust regular expression editor & tester

В силу того, что используется скомпилированная в WASM библиотека regex (конкретно версии 1.3.9), поведение гарантированно то же, что и в ваших проектах.

#prog #regex #article

The true power of regular expressions

<...>

As the article was quite long, here a summary of the main points:

* The “regular expressions” used by programmers have very little in common with the original notion of regularity in the context of formal language theory.
* Regular expressions (at least PCRE) can match all context-free languages. As such they can also match well-formed HTML and pretty much all other programming languages.
* Regular expressions can match at least some context-sensitive languages.
* Matching of regular expressions is NP-complete. As such you can solve any other NP problem using regular expressions.

But don’t forget: Just because you can, doesn’t mean that you should. Processing HTML with regular expressions is a really bad idea in some cases. In other cases it’s probably the best thing to do.