#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 с нуля. Исправляюсь: оригинал, перевод на хабре.

#prog #parsing

libphonenumber — библиотека для парсинга и форматирования телефонных номеров. Почему это необходимо? Ну, потому что телефонные номера — запутанная вещь.

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

Obliteratingly Fast Parser Combinators (pdf)

Lexers and parsers are typically defined separately and connected by a token stream. This separate definition is important for modularity, but harmful for performance.
We show how to fuse together separately-defined lexers and parsers, drastically improving performance without compromising modularity. Our staged parser combinator library, flap, provides a standard parser combinator interface, but generates psecialized token-free code that runs several times faster than ocamlyacc on a range of benchmarks.

(thanks @clayrat)

#prog #parsing #article

Why you should not use (f)lex, yacc and bison

#prog #parsing #article

Faster general parsing through context-free memoization (pdf, thanks @zukaboo)

(thanks @grammarware, @GabrielFallen)

We present a novel parsing algorithm for all context-free languages. The algorithm features a clean mathematical formulation: parsing is expressed as a series of standard operations on regular languages and relations. Parsing complexity w.r.t. input length matches the state of the art: it is worst-case cubic, quadratic for unambiguous grammars, and linear for LR-regular grammars. What distinguishes our approach is that parsing can be implemented using only immutable, acyclic data structures. We also propose a parsing optimization technique called context-free memoization. It allows handling an overwhelming majority of input symbols using a simple stack and a lookup table, similarly to the operation of a deterministic LR(1) parser. This allows our proof-of-concept implementation to outperform the best current implementations of common generalized parsing algorithms (Earley, GLR, and GLL). Tested on a large Java source corpus, parsing is 3–5 times faster, while recognition—35 times faster.

Честно скажу, я прочитал по диагонали, но фактически алгоритм выглядит, как parsing with derivatives, но сделанный правильно.

#prog #parsing #article

Parser generators vs. handwritten parsers: surveying major language implementations in 2021

Developers often think parser generators are the sole legit way to build programming language frontends, possibly because compiler courses in university teach lex/yacc variants. But do any modern programming languages actually use parser generators anymore?

To find out, this post presents a non-definitive survey of the parsing techniques used by various major programming language implementations.

#prog #parsing #rust #article

Practical Parsing in Rust with nom

#prog #parsing #rust #rustlib

Chumsky

A parser library for humans with powerful error recovery.

Пример парсера brainfuck:

use chumsky::prelude::*;

#[derive(Clone)]
enum Instr {
Left, Right,
Incr, Decr,
Read, Write,
Loop(Vec<Self>),
}

fn parser() -> impl Parser<char, Vec<Instr>, Error = Simple<char>> {
recursive(|bf| {
choice((
just('<').to(Instr::Left),
just('>').to(Instr::Right),
just('+').to(Instr::Incr),
just('-').to(Instr::Decr),
just(',').to(Instr::Read),
just('.').to(Instr::Write),
bf.delimited_by(just('['), just(']')).map(Instr::Loop),
))
.repeated()
})
}

#prog #parsing #rust #article

Parsing numbers into base-10 decimals with SIMD

When parsing number-dense JSON, much of the overhead is parsing numbers instead of parsing the JSON itself. For the typical case, most of the overhead within number parsing is converting into a form mantissa * 10^-exponent, not transforming into a proper floating point value.

Looking through high-quality number parsers such as rust_decimal’s or simd_json’s, they tend to avoid SIMD or only use it after ensuring there’s a long enough series of decimal characters. They also don’t support parsing in batches and concern themselves with problems like

* How do I avoid reading off the end of the number?
* How can I give precise error messages?
* How do I handle extremely long decimals?
* How do I handle separators?

In realistic parses, most of the above never apply! Invalid data is rare, long numbers are rare, weird separators are rare, and most numbers aren’t at the end of a buffer (with padding, none are). We can relax the above constraints and get something friendlier to a SIMD implementation. First, we assume:

1. All inputs have an extra 16 bytes of data off the end
2. Precise error reporting is not required
3. Inputs are not longer than 16 bytes
4. Inputs only contain digits and potentially 1 ‘.’
5. The sign is already processed (it’s just a simple check and pointer adjustment)
6. Optionally, we can parse many numbers at once

While these restrictions appear limiting, they’ll handle almost all actual cases, and a fallback can take the rest. With these considerations, we can go about writing a vectorized parser.

<...>

The elephant in the room is figuring out if this optimized parser is faster in real-world settings. It’s one thing to be faster in a very tight microbenchmark loop; replicating performance improvements in production is more challenging. Microbenchmarks can exacerbate coincidental interactions with microarchitecture that wouldn’t be relevant in the real world. Especially in parsing, there’s lots of complex, branchy, unpredictable surrounding code that complicates an otherwise clean sequence of instructions.

I’m experimenting with adding this to the rust port of simd-json, and adding unsafe fast-path parsers to rust_decimal. Hopefully we’ll see the desired real-world gains!

#prog #python #parsing #article

Now You Have Three Problems (перевод)

О реализации парсер-комбинаторов на Python и о том, какие неочевидные премущества они могут нести

#prog #rust #parsing #article

Resilient LL Parsing Tutorial

In this tutorial, I will explain a particular approach to parsing, which gracefully handles syntax errors and is thus suitable for language servers, which, by their nature, have to handle incomplete and invalid code. Explaining the problem and the solution requires somewhat less than a trivial worked example, and I want to share a couple of tricks not directly related to resilience, so the tutorial builds a full, self-contained parser, instead of explaining abstractly just the resilience.

The tutorial is descriptive, rather than prescriptive — it tells you what you can do, not what you should do.

* If you are looking into building a production grade language server, treat it as a library of ideas, not as a blueprint.
* If you want to get something working quickly, I think today the best answer is “just use Tree-sitter”, so you’d better read its docs rather than this tutorial.
* If you are building an IDE-grade parser from scratch, then techniques presented here might be directly applicable.

#prog #parsing #article

В Just write a parser (примечание к небольшому набору уроков по реализации парсера) автор выступает против глубокого изучения подходов к парсингу в курсах по обучению компиляторостроения и за то, чтобы забить на "академические" подходы и делать рекурсивный спуск руками. В качестве аргументов он приводит:

* Рекурсивный спуск очень хорошо даёт понять, как работает парсер, в отличие от генераторов парсеров.
* Это практичный навык: парсеры реальных компиляторов написаны вручную.
* Это не так уж и сложно.

В статье Why We Need to Know LR and Recursive Descent Parsing Techniques Laurence Tratt соглашается с первым тезисом (не перегружать курс по компиляторам подходами к парсингу), но оспаривает второй.

Именно, он указывает на LR-грамматики: такие грамматики точно являются однозначными, а то, является ли грамматика LR, можно проверить автоматически. Рекурсивный спуск же не даёт ясно понять, какова реализуемая парсером грамматика. В частности, реализуемая парсером грамматика может быть неоднозначной. Более того, то, что самописный рекурсивный спуск сам по себе вполне детерминирован, означает, что парсер таки разрешает неоднозначности грамматики, причём зачастую неочевидным способом.

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

> If writing a grammar in LR style is hard for you as the language author, it will almost certainly be hard for users to understand!

Разумеется, автор признаёт, что не для всех языков возможно написать LR-грамматику в принципе, но он отмечает, что попытка написать такую грамматику может как минимум подсказать, где в реализации парсера могут крыться баги из-за неоднозначности.

Разумеется, это не всё, что есть в статье, так что советую прочитать целиком.

#prog #parsing #article

LL and LR in Context: Why Parsing Tools Are Hard