#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 #rust #parsing #article

Традиционные парсеры формальных языков обычно прекращают работа сразу после того, как встретят первую ошибку. Для использования в IDE такие парсеры не подходят: пользователь ожидает, что различные фичи IDE (подсветка синтаксиса, автодополнение, переименование) будут работать и в том случае, когда код ещё не дописан до той степени, что он проходит синтаксическую проверку. Для таких целей нужны парсеры, которые в состоянии восстанавливаться после ошибок и продолжать разбор текста.

В этой статье рассказывается о консервативном расширении PEG, добавляющем семантику восстановления после ошибки разбора. Чуда не случилось в том смысле, что много чего надо писать руками, но авторам удалось побить ANTLR — как по качеству сообщений об ошибках, так и по быстроте работы.
А вот также статья, адаптирующая этот подход к парсер-комбинаторам (конкретно к nom)

#prog #parsing #article

Разбор различных подходов к парсингу. TL;DR: используйте LR-парсеры.

#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 #rust #rustlib #parsing #amazingopensource

Жора Geoffroy Couprie aka Geal в очередной раз переписал nom. На раст. С раста.

Стоило ли оно того? Определённо.

Во-первых, парсер-комбинаторы теперь вместо impl Fn(...) -> ... возвращают impl FnMut(...) -> .... Функциональность от этого не пострадала, но теперь из них убрано лишнее ограничение. Да, это означает, что теперь можно очень легко написать stateful парсер. Смиритесь с этим.

Во-вторых, парсер теперь — это не что-то, реализующее FnMut(I) -> IResult<O, E>, а что-то реализующее nom::Parser. Помимо того, что это изменение поменяло ограничения на типы аргументов комбинаторов, оно позволяет теперь некоторые комбинаторы использовать не в качестве свободных функций, а в качестве методов этого трейта. Это сильно влияет на эргономику — теперь можно написать .map(...) прямо на парсере, а также набирать альтернативные варианты парсинга цепочкой .or(...) вместо того, чтобы передавать кортеж парсеров в alt. Разумеется, у трейта есть blanket impl для замыканий, так что все старые комбинаторы продолжат работать.

В-третьих, в nom теперь должно быть удобнее пользоваться ошибками. Ошибки из nom теперь реализуют std::error::Error, комбинатор Parser::into позволяет сделать новый парсер, который применяет From к результату и ошибке парсера, а к самим ошибкам можно прицепить контекст — к сожалению, на текущий момент это может быть только &'static str.

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

#prog #rust #parsing #rustlib

fast_float — библиотека для быстрого парсинга чисел с плавающей точкой. Судя по бенчмаркам, быстрее lexical_core, да и вообще практически всех библиотек.

Является портом одноимённой библиотеки для C++ за авторством небезызвестного Даниела Лемира.

#prog #rust #parsing #rustlib

nom_supreme — библиотека, расширяющая функционал nom. Новые комбинаторы-методы, очень подробный тип ошибок, функция для быстрого создания парсера любого типа, реализующего FromStr и ещё по мелочи.

В примерах используется cool_asserts — библиотека для более пригодных для использования в #[test]-функциях ассертов.

#prog #rust #parsing #моё

Хочу поделиться своей техникой написания наколеночного парсера, которую я применил для этой утилиты. Она очень простая и потому не очень мощная, но для разбора простых форматов хватает. При этом, как показала практика, она может быть быстрее регулярок. Сразу скажу, что этот подход не подойдёт, если требуются детальные сообщения об ошибках.

Начнём с определения центральной структуры для разбора:

#[derive(Clone)]
struct Lexer<'a> {
    s: &'a str,
}

impl<'a> Lexer<'a> {
    fn of(s: &'a str) -> Self {
        Self { s }
    }
}

Да, всё верно, это буквально обёртка над строковым слайсом. Все последующие методы будут принимать мутабельную ссылку на Lexer и будут возвращать Option<Something>, где Some означает, что нечто удалось распарсить, а None будет обозначать ошибку. При этом все эти методы будут следовать одному правилу: если что-то распарсить не удалось, то Lexer остаётся ровно в том же состоянии, что был до вызова.

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

fn end(&mut self) -> Option<()> {
    if self.s.is_empty() {
        Some(())
    } else {
        None
    }
}

Следующий метод не очень полезен сам по себе, но он потребуется для других методов. Он просто будет сдвигать позицию, с которой производится парсинг:

fn shift(&mut self, pos: usize) {
    self.s = &self.s[pos..];
}

Что ж, теперь напишем самый простой метод, который действительно что-то парсит, а именно — конкретную переданную строку:

fn literal(&mut self, literal: &str) -> Option<()> {
    self.s = self.s.strip_prefix(literal)?;
    Some(())
}

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

fn before_literal(&mut self, literal: &str) -> Option<&'a str> {
    let pos = self.s.find(literal)?;
    let ret = &self.s[..pos];
    self.shift(pos + literal.len());
    Some(ret)
}

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

fn number<Num: std::str::FromStr>(&mut self) -> Option<Num> {
    let pos = self
        .s
        .as_bytes()
        .iter()
        .position(|ch| !ch.is_ascii_digit())
        .unwrap_or(self.s.len());
    let ret = self.s[..pos].parse().ok()?;
    self.shift(pos);
    Some(ret)
}

Clippy тут, к сожалению, ругается на вызов .unwrap_or(self.s.len())... Точнее, ругался раньше, теперь это исправили. Отлично!

Казалось бы, что можно сделать с таким набором методов? Ну, этого уже достаточно, чтобы распарсить IPv4-адрес:

#[derive(PartialEq, Debug)]
struct Ip4Addr([u8; 4]);

fn parse_ip(s: &str) -> Option<Ip4Addr> {
    let mut p = Lexer::of(s);
    let a = p.number()?;
    p.literal(".")?;
    let b = p.number()?;
    p.literal(".")?;
    let c = p.number()?;
    p.literal(".")?;
    let d = p.number()?;
    p.end()?;
    Some(Ip4Addr([a, b, c, d]))
}

fn main() {
    assert_eq!(parse_ip("12.32.200.21"), Some(Ip4Addr([12, 32, 200, 21])));
}

Обратите внимание, благодаря выводу типов нам не пришлось уточнять тип для p.number().

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

fn optional<T, F: FnOnce(&mut Self) -> Option<T>>(&mut self, f: F) -> Option<T> {
    let backtrack = self.clone();
    let ret = f(self);
    if ret.is_none() {
        *self = backtrack;
    }
    ret
}

В принципе, теперь мы можем распарсить IP4-адрес с опциональной маской подсети, но я покажу кое-что более интересное: парсинг из задачи Advent of Code 2020.

#prog #rust #parsing #article

Почему-то в блоге не было ссылки на доходчивую статью про реализацию парсер-комбинаторов на Rust с нуля. Исправляюсь: оригинал, перевод на хабре.