Primary tabs

Регулярные выражения против комбинаторного анализа

Ссылка на оригинал - https://khanlou.com/2019/12/regex-vs-combinatorial-parsing/, автор публикации - Soroush Khanlou

Недавно я работал над музыкальным приложением, которое должно получить музыкальную последовательность (например, мелодию) от сервера к клиенту. Для этого мы используем формат под названием ABC. (О том, как работает музыкальная нотация ABC, вы можете прочитать здесь.) Мы выбрали формат ABC, потому что он более читабельный, чем MIDI, он довольно лаконичный, и он стандартный, так что мы не будем изобретать какой-то новый формат поверх JSON.

ABC - простой формат, и он отлично справляется с представлением музыки. Например, вот небольшая часть из «Für Elise» Бетховена, которую все знают:

e ^d e d e B =d c A2

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

Приложению необходимо преобразовать строку в некую структуру, которую секвенсор знает, как играть. Итак, нам нужно разобрать эту строку.

Регулярные выражения

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

^(\\^+|_+|=)?([a-gA-G])(,+|'+)?(\\d*)(\\/)?(\\d*)$

Есть 3 основных проблемы с этим регулярным выражением.

Это сложно понять

Почти невозможно определить, что делает этот регекс, глядя на него. Специально для чего-то вроде ABC, который использует знаки препинания для таких вещей, как случайности (^, _, и =), а также настройки октавы (' и ,), действительно трудно сказать, какие буквальные символы мы пытаемся сопоставить, а какие - регекс-символы управления, которые говорят шаблону, чтобы соответствовать нулю или более этой, опционально совпадают, и так далее.

Несмотря на свою непостижимость, регексы являются одним из самых сложных языков.

Это не композитно

Другая проблема с регулярными выражениями заключается в том, что составные компоненты не могут быть легко скомпонованы. Например, вышеприведенная последовательность Бетховена не включает в себя никаких остатков, но они обычно выглядят так же, как нота с буквой z вместо буквы тональности. Так, например, оставшаяся часть может выглядеть как z/2.

В идеале, мы хотели бы иметь возможность повторно использовать шаблон длительности, но в настоящее время он застрял внутри этого гигантского регекса. Чтобы скомпоновать эти регексы вместе, мы должны сначала разобрать их на части, а затем применить какое-нибудь конкатенирование строк:

let accidentalPattern = "(\\^+|_+|=)?"
let letterPattern = "([a-gA-G])"
let octaveAdjustmentPattern = "(,+|'+)?"
let durationPattern = "(\\d*)(\\/)?(\\d*)"
let restPattern = "z"

let noteRegex = try! NSRegularExpression(pattern: accidentalPattern + letterPattern + octaveAdjustmentPattern + durationPattern)

let restRegex = try! NSRegularExpression(pattern: restPattern + durationPattern

Это действительно единственный способ получить сочетаемость с регулярными выражениями. И, конечно же, поскольку это просто строки, которые мы объединяем, нет способа узнать, представляет ли наша конкатенация действительное преобразование базового регулярного выражения, поскольку оно не проверяется во время компиляции.

Требуется дополнительное преобразование

Наконец, даже после того, как мы успешно скомпилировали наш регекс-шаблон в регулярное выражение и разобрали строку, у нас все равно нет ничего полезного! Есть куча групп, с которыми нам нужно работать, чтобы получить конечный результат. Например, первая группа в регексе дает нам случайную строку. Это может быть либо ещё (^), ещё одно подчёркивание (_) либо знак равенства (=), но регекс не говорит нам, что это такое, поэтому нам нужно разобрать его дальше.

let numAccidentals = match.captureGroups[0].text.count
let accidentalChar = match.captureGroups[0].text.first

switch accidentalChar {
case "^":
    return .accidental(numAccidentals)
case "_":
    return .accidental(-numAccidentals)
case "=":
    return .natural
case "":
    return Accidental.none
default:
    return nil
}

Требование ручного вмешательства, когда мы должны преобразовать подходящую подстроку в наш объект домена, немного раздражает.

Комбинаторный парсинг

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

func consumeNote(abcString: Substring) -> (note: Note?, remainder: Substring)

Функция, которая возвращает кортеж, (T?, Substring) выглядела очень знакомо. Я видел это в коде Pointfree:

extension Parser {
    run(_ str: String) -> (match: A?, rest: Substring)
}

Это называется "комбинаторный синтаксический анализатор", потому что он относится к несколько неясной части информатики, называемой комбинаторы. Я не понимаю их полностью, но я передам его Дэниелу Стейнбергу, чтобы поделиться некоторыми классными примерами.

Я подумал, что если мы все равно пытаемся разобрать текст и вернуть что-то в этом формате, то, может быть, комбинаторный парсер подойдет. Так что я провел небольшое исследование на эту тему и начал процесс переосмысления нашего парсинга с помощью этой новой стратегии. Суть синтаксического анализа - это структура с одной функцией:

struct Parser<A> {
    let run: (inout Substring) -> A?
}

Вы даете ему строку (в данном случае подстроку из соображений производительности), и она потребляет символы из передней части буфера, чтобы посмотреть, сможет ли он создать из них универсальный тип. Если это успешно, он возвращает A. Если происходит сбой, он возвращается nil, гарантируя отсутствие изменений входного параметра.

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

static func literal(_ string: String) -> Parser<Void> {
    return Parser<Void>(run: { input in
        if input.hasPrefix(string) {
            input.removeFirst(string.count)
            return ()
        } else {
            return nil
        }
    })
}

Если у ввода есть префикс строки, которую мы ищем, отбросьте столько символов и верните правильное значение (в данном случае Void). Если нет, верните ноль - нет совпадения. Я не буду вдаваться в подробности о всех других помощниках здесь - вы можете найти их много в примере кода Pointfree.

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

let accidentalParser: Parser<Accidental> = Parsers.oneOf([
    Parsers.repeating("^").map({ .accidental($0.count) }),
    Parsers.repeating("_").map({ .accidental(-$0.count) }),
    Parsers.literal("=").map({ .natural }),
    Parsers.literal("").map({ .none }),
])

Это позволяет избежать практически всех подводных камней в регулярных выражениях.

Во-первых, код очень читабельный. Вы можете видеть, каким буквальным символам он соответствует, потому что это все еще строки, но все символы управления регексами превратились в именованные функции, которые доступны для людей, которые не являются экспертами по регексам.

Во-вторых, это очень композитно. Этот парсер состоит из меньших парсеров, таких как .repeating или .literal, и сам состоит из больших парсеров, таких как парсеры для нот и так далее. Вот случайный парсер в парсере нот.

var noteParser: Parser<Note> {
    return Parsers.zip(accidentalParser, pitchParser, durationParser)
        .map({ accidental, pitch, duration in
            return Note(accidental: accidental, pitch: pitch, duration: duration)
        })
}

(zip совпадает по порядку со всеми парсерами, которые ему даны, и не срабатывает, если какой-нибудь из них не срабатывает). В этом примере также очень приятно видеть, как все типы выстраиваются в линию. Вы получаете уверенность от компилятора, что все в порядке.

Последнее преимущество, которое формат имеет по сравнению с регексом: он производит фактическое значение, которое вы ожидаете. Используя операцию map, вы можете преобразовывать простые результаты, такие как подстрока или Void, в результаты, специфичные для домена, такие как Accidental или Note.

Единственное реальное место, где это проигрывает регексуалам - это терпкость, и когда вы добавляете код трансформации, который требуется регексуалам, это, по сути, "промывка".

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

Неправильно. Используя этот новый подход, мы смогли получить на 25% более шустрый парсинг по всем параметрам. Это шокировало меня. Обычно я принимаю небольшой спад по скорости, если это делает код приятнее (предполагая, что это не критический путь, не замеченный пользователем и т.д.), но в данном случае это даже не вызывало беспокойства, так как более приятный код тоже был более быстрым. Я в выигрыше! Думаю, что большая польза в скорости исходит от использования подстроек. Обрезка передней части подстроки эффективна, что делает многие из этих операций супер быстрыми.

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

Добавить комментарий

Plain text

  • No HTML tags allowed.
  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.

Не нашли ответ на свой вопрос? Возможно, вы найдете решение проблемы на нашем канале в Youtube! Здесь мы собрали небольшие, но эффективные инструкции. Смотрите и подписывайтесь на наш youtube-канал!

Смотреть на Youtube