[Перевод] Если вы отказались от регулярных выражений, то теперь у вас три проблемы10.04.2023 19:46

Известная шутка программистов гласит, что если решение вашей проблемы включает в себя парсинг текста при помощи регулярного выражения, то теперь у вас есть две проблемы. Некоторые программисты, прочитав шутку, решают попробовать иной подход. Возможно, регулярные выражения не так уж нужны. Возможно, задачу можно решить простым split строки или чем-то подобным. Однако другие могут задуматься немного глубже и задаться вопросом: «А если я сделаю нечто настолько дерзкое, что в результате получу три проблемы?» Мой пост написан в таком духе!

В нём используется код на Python, однако его легко можно адаптировать под любой язык с поддержкой функций высшего порядка.

▍ Элементарные частицы

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

def shift(inp):
    return bool(inp) and (inp[0], inp[1:])

Получая входную последовательность inp, она возвращает первый элемент inp[0] и все оставшиеся элементы inp[1:]. Если входных данных не было, она возвращает False. Функция выглядит странно, но вот как она работает пошагово для символов строки:

>>> shift('bar')
('b', 'ar')
>>> shift('ar')    # Применяется к оставшимся символам 'ar'
('a', 'r')
>>> shift('r')
('r', '')
>>> shift('')
False
>>>

Всегда полезно бывает создать для каждой функции обратную ей функцию. По крайней мере, этому я научился, работая над ПО для физических расчётов. Что противоположно потреблению входных данных? Разумеется, отсутствие потребления входных данных. Давайте напишем эту функцию:

def nothing(inp):
    return (None, inp)

nothing() не выполняет обработку. Она возвращает None для любых входных данных. Также она возвращает полученные входные данные (без изменений).

>>> nothing('bar')
(None, 'bar')
>>>

nothing() отличается от отсутствия доступных входных данных. Она просто означает, что вы решили НЕ делать ничего с имеющимися входными данными.

Обе эти функции являются примерами того, что я буду называть «парсер». Парсер — это функция, определяемая своей сигнатурой вызова и соглашением о возвращаемых данных. В частности, парсер — это любая функция, принимающая какие-то входные данные (inp), а в случае успеха возвращающая кортеж (value, remaining), где value — это некое нужное значение, а remaining — все оставшиеся входные данные, парсинг которых нужно выполнить. При неудаче парсер возвращает False.

Хотя эти функции и так короткие, можно ещё больше их сократить при помощи lambda:

shift   = lambda inp: bool(inp) and (inp[0], inp[1:])
nothing = lambda inp: (None, inp)

Преимущество lambda в том, что она делает код компактным и наглядным. Кроме того, она не позволяет разработчикам пытаться добавлять значимые имена, документацию или type hint к тому, что будет развёрнуто.

Кстати, lambda — это третья проблема. Сдвиг, ничего и лямбда — это три проблемы. Давайте двигаться дальше.

▍ Система парсинга

То, что мы получили, называется системой для парсинга. Как и у любой другой системы, у неё есть правила. В этой системе мы можем использовать только два имеющихся парсера (shift и nothing). Также можно использовать lambda для создания новых парсеров из имеющихся. Вот и всё.

▍ Модификаторы парсеров

Давайте напишем правило, применяющее предикат к результату парсера:

filt = lambda predicate: (
         lambda parser:
           lambda inp: (m:=parser(inp)) and predicate(m[0]) and m)

Три лямбды??! Моржовый оператор? Вычисление по краткой схеме? Что за ужас здесь творится? Да, я мог использовать вместо этого четыре лямбды:

filt = lambda predicate: (
         lambda parser:
           lambda inp:
             (lambda m: m and predicate(m[0]) and m)(parser(inp)))

Однако читаемость важна. К тому же — бог любит троицу. Три проблемы. Три лямбды. Три бивня. Не четыре лямбды и ни одного бивня.

Функция filt() получает на входе предикат и парсер и комбинирует их, чтобы создать новый парсер. Это выглядит немного странно, но работает схоже с декоратором. Вот пример того, как это использовать:

>>> digit = filt(str.isdigit)(shift)
>>> letter = filt(str.isalpha)(shift)
>>> digit('456')
('4', '56')
>>> letter('456')
False
>>>

Возвращаемое значение False в данном случае означает, что парсинг не сработал. Точно так же, как shift() возвращает False, когда заканчиваются входные данные, созданный при помощи filt() парсер возвращает False, если созданное значение не соответствует переданному предикату.

Забавная формулировка filt() позволяет вам легко создавать другие типы полезных фильтров, просто передавая произвольные предикаты. Вот фильтр для точного соответствия литералу:

literal = lambda value: filt(lambda v: v == value)

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

memberof = lambda values: filt(lambda v: v in values)

Вот несколько примеров применения этих фильтров к имеющемуся парсеру:

>>> dot = literal('.')(shift)
>>> even = memberof('02468')(digit)   # Да, digit, не shift.
>>> dot('.456')
('.', '456')
>>> dot('45.6')
False
>>> even('456')
('4', '56')
>>> even('345')
False
>>>

Естественно, можно продолжить всё упрощать. Чтобы выявлять соответствия отдельным символам, можно написать следующую вспомогательную функцию:

char = lambda v: literal(v)(shift)

>>> dot = char('.')
>>> dot('.456')
('.', '456')
>>>

Аналогично тому, что задача filt() заключается в игнорировании элементов, противоположностью игнорирования является какое-то действие. Поэтому, чтобы сохранить баланс кода, нам нужна противоположная сила. Давайте назовём эту операцию fmap():

fmap = lambda func: (
         lambda parser:
           lambda inp: (m:=parser(inp)) and (func(m[0]), m[1]))

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

>>> ndigit = fmap(int)(digit)
>>> ndigit('456')
(4, '56')
>>> tenx = fmap(lambda x: 10*x)
>>> tenx(ndigit)('456')
(40, '56')
>>> tenx(digit)('456')
('4444444444', '56')
>>>

Примечание: map и filter — имена встроенных функций, которые Python использует для работы с итерируемыми элементами. Я бы использовал их, если бы это не запутывало присвоение имён. Поэтому я выбрал fmap и filt. Концептуально наши функции служат семантически схожей цели.

▍ Повторение

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

digits = one_or_more(digit)

Чтобы сделать это, мы можем использовать функциональные техники, задействующие рекурсию. Однако скажем напрямую — Python ужасно справляется с рекурсией по различным «причинам», меньшей из которых является его внутреннее ограничение на рекурсии. Этого мы делать не будем. Вместо этого вдохновимся театром и «сломаем четвёртую стену», повернувшись к зрителям и признав, что мы всё-таки пишем код на Python. Ладно, да будет так:

def one_or_more(parser):
    def parse(inp):
        result = [ ]
        while (m:=parser(inp)):
            value, inp = m
            result.append(value)
        return bool(result) and (result, inp)
    return parse

Да, цикл while не согласуется с нашей системой лямбд. Однако можно сказать, что это «pythonic» просто потому, что не ломает ограничения на рекурсии, поэтому давайте сделаем так. Как и другие наши функции, one_or_more() принимает на входе парсер и создаёт на выходе новый парсер. Он многократно вызывает переданный парсер, пока больше не найдётся совпадений. Список создан.

>>> digit = filt(str.isdigit)(shift)
>>> digits = one_or_more(digit)
>>> digits('456')
(['4','5','6'], '')
>>> digits('1abc')
(['1'], 'abc')
>>> digits('abc')
False
>>>

Если вам не нравится, что цифры разделены на список, то используйте fmap, чтобы снова соединить их:

>>> digits = fmap(''.join)(one_or_more(digit))
>>> digits('456')
('456', '')
>>>

Если вам нужно числовое значение, то добавьте ещё одну fmap:

>>> value = fmap(int)(digits)
>>> value('456')
(456, '')
>>>

Примечание: если вы покажете своим коллегам функцию one_or_more(), то они, вероятно, рассердятся, потому что вы не соблюдаете руководство по стилю. Они скажут: «Тебе нужно было использовать лямбду». Исправить это не так просто, но, возможно, вам удастся их обмануть при помощи functools.wraps():

from functools import wraps

@wraps(lambda parser:_)
def one_or_more(parser):
    @wraps(lambda inp:_)
    def parse(inp):
        ...
    return parse

По крайней мере, в этом случае функция выглядит так, как будто берётся из лямбды, если кто-то не потратит время на изучение её определения.

Домашнее задание: или же можно просто переписать one_or_more(), не пользуясь ничем, кроме как лямбдой и рекурсией.

▍ Последовательность

Иногда вам нужно спарсить одно после другого. Для этого можно написать оператор последовательности:

def seq(*parsers):
    def parse(inp):
        result = [ ]
        for p in parsers:
            if not (m:=p(inp)):
                return False
            value, inp = m
            result.append(value)
        return (result, inp)
    return parse

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

>>> seq(letter, digit, letter)('a4x')
(['a', '4', 'x'], '')
>>> seq(letter, digit, letter)('abc')
False
>>> seq(letter, fmap(''.join)(one_or_more(digit)))('x12345')
(['x', '12345'], '')
>>> 

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

left = lambda p1, p2: fmap(lambda p: p[0])(seq(p1, p2))
right = lambda p1, p2: fmap(lambda p: p[1])(seq(p1, p2))

Вот пример:

>>> left(letter, digit)('a4')
('a', '')
>>> right(letter, digit)('a4')
('4', '')
>>>

Домашнее задание: напишите версию seq() с использованием лямбды.

▍ Выбор

Создание последовательности требует, чтобы все парсеры совпадали. Какой будет обратная операция? Возможно, это функция, которая требует, чтобы совпадал только один из переданных парсеров. Давайте назовём эту операцию either():

either = lambda p1, p2: (lambda inp: p1(inp) or p2(inp))

Вот пример:

>>> alnum = either(letter, digit)
>>> alnum('4a')
('4', 'a')
>>> alnum('a4')
('a', '4')
>>> alnum('$4')
False
>>>

either() позволяет создавать необязательные параметры и, наконец, даёт возможность воспользоваться nothing. Например:

maybe = lambda parser: either(parser, nothing)

>>> maybe(digit)('456')
('4', '56')
>>> maybe(digit)('abc')
(None, 'abc')
>>>

Также можно использовать её для реализации zero_or_more():

zero_or_more = lambda parser: either(one_or_more(parser), seq())

>>> zero_or_more(digit)('456')
(['4','5','6'], '')
>>> zero_or_more(digit)('abc')
([], 'abc')
>>>

И последнее: можно использовать either() для создания более мощной функции choice(), позволяющей выбирают между любым количеством переданных парсеров.

choice = lambda parser, *parsers: (
           either(parser, choice(*parsers)) if parsers else parser)

Домашнее задание: перепишите choice() так, чтобы не использовалась рекурсия.

Домашнее задание: , а действительно ли нам нужна nothing? Можно ли создать nothing из чего-то?

▍ Пример: числа

Давайте рассмотрим задачу парсинга чисел. Предположим, что числа поступают в двух вариациях. Целые числа имеют вид 1234, а десятичные дроби — 12.34. Однако с десятичными дробями всё чуть сложнее, потому что их можно записывать с замыкающим десятичным разделителем, например, 12. или с начальным десятичным разделителем, например, .34. Допустим, нам нужно преобразовать целые числа в integer языка Python, а десятичные дроби — во float. Как вы будете парсить числа? Вот как это можно сделать:

dot = char('.')
digit = filt(str.isdigit)(shift)
digits = fmap(''.join)(one_or_more(digit))
decdigits = fmap(''.join)(choice(
               seq(digits, dot, digits),
               seq(digits, dot),
               seq(dot, digits)))

integer = fmap(int)(digits)
decimal = fmap(float)(decdigits)
number = choice(decimal, integer)

Давайте проверим нашу функцию number().

>>> number('1234')
(1234, '')
>>> number('12.3')
(12.3, '')
>>> number('.123')
(0.123, '')
>>> number('123.')
(123.0, '')
>>> number('.xyz')
False
>>>

▍ Пример: пары «ключ-значение»

Допустим, вам нужно спарсить пары «ключ-значение» в вид name=value;, где name состоит из букв, а value — это любое численное значение. Также предположим, что вокруг каждой из пар могут быть произвольные пробелы (которые нужно игнорировать). Вот как это можно сделать:

letter = filt(str.isalpha)(shift)
letters = fmap(''.join)(one_or_more(letter))
ws = zero_or_more(filt(str.isspace)(shift))
token = lambda p: right(ws, p)
eq = token(char('='))
semi = token(char(';'))
name = token(letters)
value = token(number)
keyvalue = seq(left(name, eq), left(value, semi))

Давайте проверим:

>>> keyvalue('xyz=123;')
(['xyz', 123], '')
>>> keyvalue('   pi = 3.14  ;')
(['pi', 3.14], '')
>>>

Обработка пробелов может потребовать небольшого исследования. Решением станет использование особой функции token() для отбрасывания начального пробела.

▍ Пример: построение словаря

Допустим, вы хотите расширить возможности парсера, чтобы он преобразовывал произвольное число в пары «ключ-значение», записываемые как key1=value1; key2=value2; key3=value3; в словарь Python с теми же ключами и значениями. Вот как это сделать:

keyvalues = fmap(dict)(zero_or_more(keyvalue))

Пример:

>>> keyvalues('x=2; y=3.4; z=.789;')
({'x': 2, 'y': 3.4, 'z': 0.789}, '')
>>> keyvalues('')
({}, '')
>>>

▍ Пример: валидация ключей словаря

Допустим, нужно написать парсер, принимающий только словари с ключами x и y. Для проверки этого можно использовать filt():

xydict = filt(lambda d: d.keys() == {'x', 'y'})(keyvalues)

Пример:

>>> xydict('x=4;y=5;')
({'x': 4, 'y': 5}, '')
>>> xydict('y=5;x=4;')
({'y': 5, 'x': 4}, '')
>>> xydict('x=4;y=5;z=6;')
False
>>>

Этот пример показывает, как можно интересным образом сочетать возможности. Раньше функция filt() использовалась для фильтрации отдельных символов, а теперь она применяется к словарям.

▍ Обсуждение: композиция

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

def parser(inp):
    ...
    if success:
        return (value, remaining)
    else:
        return False

Всё остальное создаётся на этом фундаменте. Всё множество различных функций наподобие filt(), fmap(), zero_or_more(), seq() и choice() создаёт новые парсеры, имеющие идентичный интерфейс. Поэтому всё работает со всем и везде. Возможно, основным источником проблем может быть fmap(). Так как она применяет пользовательскую функцию к подвергающемуся парсингу значению, очевидно, что передаваемая функция должна быть совместимой.

▍ Обсуждение: анализ концепций

Задумаемся на минуту над формулировкой filt(). Когда вы использовали filt(), то, вероятно, думали, что это выглядит немного забавно. Примерно так:

digit = filt(str.isdigit)(shift)

Почему shift находится снаружи? Кроме того, разве это не внутренняя подробность реализации? Разве мы не можем спрятать её вот так:

filt = lambda predicate: (
         lambda inp: (m:=shift(inp)) and predicate(m[0]) and m)

digit = filt(str.isdigit)

Да, это можно сделать, однако перемещение её внутрь ограничивает полезность filt() до отдельных символов. Я предпочту filt(), которая опасно гибка. Исходная формулировка позволяет применять предикат к ЛЮБОМУ парсеру, даже к сложным, которые возвращают структуры данных. И это здорово. Этого нельзя было бы сделать, если бы выбор парсера находился внутри.

Ещё один вопрос по filt() (и связанным с ней функциям) относится к её странному формату вызова. Почему входной предикат и аргументы парсера обрабатываются вызовами отдельной функции, а не передаются вместе одной функции? Например, почему не сделать вот так?

filt = lambda predicate, parser: (
         lambda inp: (m:=parser(inp)) and predicate(m[0]) and m)

digit = filt(str.isdigit, shift)

Если сформулировать функцию таким образом, то определять полезные варианты наподобие literal станет неудобнее. Ранее literal определялась, завися только от части с предикатом. Вот так:

literal = lambda value: filt(lambda v: v == value)

Это сжатая и изящная запись. Однако, если filt() потребуется дополнительный аргумент, это этот аргумент растекается на внешние функции, заставляя нас писать такой код:

literal = lambda value, parser: filt(lambda v: v == value, parser)

Это некрасиво. В исходном случае нам не требуется знать дополнительные подробности о filt().

▍ Магия

Давайте обсудим функцию shift(). В исходной формулировке она разбивает входную строку на её первый символ и оставшийся текст. Вот как выглядел код:

shift = lambda inp: bool(inp) and (inp[0], inp[1:])

А вот как он работал:

>>> shift('hello world')
('h', 'ello world')
>>>

Это неэффективный способ обработки текста на Python. На самом деле, вероятно, это наихудший способ обработки текста, который только можно придумать. На моей машине тест парсинга строки с 100000 парами «ключ-значение» в словарь занял почти 2,5 минуты! Ужас!

Основная проблема заключается в копировании памяти, происходящем при вычислении inp[1:]. На самом деле, каждый вызов shift() выполняет почти полную копию входного текста. Можно ли этого избежать?

Внимательный наблюдатель заметит, что во всём представленном коде ничего не делается со входным значением inp, за исключением его передачи в другое место. Единственный код, который с ним работает — это функция shift()! Более того, никакой код никогда не смотрит на значение оставшегося текста. Поэтому мы можем поменять описание данных для этих частей на нечто совершенно иное. Вместо того чтобы представлять входные данные в виде строки, мы, возможно, сможем использовать кортеж (text, n), где n — это integer, обозначающий текущую позицию. Давайте попробуем переписать shift() следующим образом:

def shift(inp):
    text, n = inp
    return n < len(text) and (text[n], (text, n+1))

Вот как работает новая версия:

>>> shift(('abc', 0))     # Обратите внимание, что теперь используется кортеж
('a', ('abc', 1))
>>> shift(('abc', 1))
('b', ('abc', 2))
>>> shift(('abc', 2))
('c', ('abc' 3))
>>> shift(('abc', 3))
False
>>>

Обратите внимание, что входная строка никогда не меняется. Не происходит ни копирования, ни нарезания. По сути, Python передаёт строку как ссылку. Единственное изменяющееся значение — это целочисленный индекс.

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

>>> keyvalues(('x=2; y=3.4; z=.789;', 0))    # Обратите внимание: здесь кортеж
({'x': 2, 'y': 3.4, 'z': 0.789}, ('x=2; y=3.4; z=.789;', 19))
>>>

Чтобы сокрыть часть подробностей входных данных, я могу добавить специальную функцию Input() для преобразования передаваемого пользователем ввода в мой внутренний формат. Например:

Input = lambda inp: (inp, 0)

# Пример
result = keyvalues(Input('x=2; y=3.4; z=.789'))

Я назвал Input с заглавной, чтобы оставить пространство для манёвра. Возможно, когда-нибудь я превращу её в класс. Возможно, я просто делаю это, чтобы высказать своё «фи» PEP-8. Кто знает?

Как бы то ни было, при тестировании на тех же входных данных с 100000 парами «ключ-значение» время парсинга упало с 2,5 минуты до примерно 2,3 секунды. Это потрясающе. Мы решили проблему производительности, изменив представление входных данных и подправив одну строку кода.

Почему это сработало? Думаю, потому, что всё написанная нами функциональность основана не на прямых манипуляциях с входными данными, а на композиции функций. Изменение представления данных не повлияло на композицию частей.

▍ Ещё немного магии

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

from sly import Lexer

class KVLexer(Lexer):
    tokens = { EQ, SEMI, NAME, INTEGER, FLOAT }
    ignore = ' \t\n'
    FLOAT = r'(\d+\.\d+)|(\d+\.)|(\.\d+)'
    INTEGER = r'\d+'
    NAME = r'[a-zA-Z]+'    
    EQ = r'='
    SEMI = r';'

Лексический анализатор создаёт токены, не символы. Например:

>>> lexer = KVLexer()
>>> list(lexer.tokenize("x=2;"))
[Token(type='NAME', value='x', lineno=1, index=0, end=1),
 Token(type='EQ', value='=', lineno=1, index=1, end=2),
 Token(type='INTEGER', value='2', lineno=1, index=2, end=3),
 Token(type='SEMI', value=';', lineno=1, index=3, end=4)]
>>>

Можем ли мы использовать свой фреймворк парсинга с таким токенизатором? Конечно! Для этого нужно заменить низкоуровневую работу с символами на использвание токенов, но во всём оставив парсер неизменным. Вот как выглядит новый парсер:

expect = lambda ty:\
           fmap(lambda tok: tok.value)(filt(lambda tok: tok.type == ty)(shift))
name = expect('NAME')
integer = fmap(int)(expect('INTEGER'))
decimal = fmap(float)(expect('FLOAT'))
value = choice(decimal, integer)
keyvalue = seq(left(name, expect('EQ')), left(value, expect('SEMI')))
keyvalues = fmap(dict)(zero_or_more(keyvalue))

Input = lambda inp: (list(KVLexer().tokenize(inp)), 0)

Давайте убедимся, что он работает:

>>> r = keyvalues(Input('x=2; y=3.4; z=.789;'))
>>> r[0]
{'x': 2, 'y': 3.4, 'z': 0.789}
>>>

При тестировании на моих больших входных данных эта версия выполняется около 0,9 секунды, что примерно в 2,5 раза быстрее, чем раньше.

▍ Бум!

Я задумался о бесчисленных часах, потраченных мной на микрооптимизации парсера LALR (1) в моих инструментах наподобие PLY и SLY. Серьёзно, я потратил кучу времени на изучение этого кода, пытаясь убрать всё, что мешало производительности. Поэтому эти инструменты уже давно являются самыми быстрыми реализациями парсеров на чистом Python. Как моя новая методика будет выглядеть по сравнению с ними?

Чтобы протестировать это, я задал схожий парсер пар «ключ-значение» в SLY:

from sly import Parser

class KVParser(Parser):
    tokens = KVLexer.tokens

    @_('{ keyvalue }')
    def keyvalues(self, p):
        return dict(p.keyvalue)

    @_('NAME EQ value SEMI')
    def keyvalue(self, p):
        return (p.NAME, p.value)

    @_('INTEGER')
    def value(self, p):
        return int(p.INTEGER)

    @_('FLOAT')
    def value(self, p):
        return float(p.FLOAT)

Вот как его можно использовать для парсинга нашего примера:

>>> lexer = KVLexer()
>>> parser = KVParser()
>>> tokens = lexer.tokenize('x=2; y=3.4; z=.789;')
>>> parser.parse(tokens)
{'x': 2, 'y': 3.4, 'z': 0.789}
>>>

А теперь я попробую его на моих входных данных с 100000 пар «ключ-значение». Выполнение заняло 2,3 секунды. Это в три раза медленнее предыдущего теста, в котором использовался тот же поток токенов! Он даже немного медленнее, чем исходная «магическая» версия, которая просто работала с отдельными символами. Как такое может быть?

Такого результата я не ожидал. Парсер LALR (1) управляется только поиском по таблице и автоматом. В нём отсутствует поиск с возвратом и он не использует глубокий стек композиции функций.

В качестве последней надежды я решил заново реализовать весь парсер при помощи PLY, имеющего более оптимизированную реализацию. Он выполняется примерно за 1,2 секунды. Получается, он тоже проигрывает.

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

▍ Примечание: итерация

В Python концепция итерации определена чётко. Логично спросить, почему не использовать для этого итератор или функцию-генератор? Можно ли переписать shift() таким образом?

shift = lambda inp: (x:=next(inp, False)) and (x, inp)

Похоже, эксперимент подтверждает, что это может сработать:

>>> inp = iter('abc')
>>> shift(inp)
('a', )
>>> shift(inp)
('b', )
>>> shift(inp)
('c', )
>>> shift(inp)
False
>>>

К сожалению, на самом деле это не работает, потому что в нашей методике парсинга используется поиск с возвратом, особенно при принятии решения в функциях either(), maybe() и choice(). При обработке either() парсинг какое-то время может выполняться успешно, а потом внезапно завершиться неудачно. Когда такое происходит, всё откатывается назад и проверяется другая ветвь парсинга.

Для отката назад стандартного итератора Python механизмы отсутствуют. Хотя иногда можно скопировать итератор или использовать какую-нибудь магию из itertools, это выглядит довольно сложным. Хуже того, чтобы это заработало, необходимо вносить тонкие изменения во всей реализации, а не изолировать их в одном месте. Пока я оставлю это в качестве домашнего задания.

▍ Полный код

Вот полная реализация базового фреймворка парсинга, описанного в этой статье. Я решил, что будет интересно просто увидеть его целиком.

# -- Фреймворк парсинга

def shift(inp):
    text, n = inp
    return n < len(text) and (text[n], (text, n+1))

nothing = lambda inp: (None, inp)

filt = lambda predicate: (
         lambda parser:
           lambda inp: (m:=parser(inp)) and predicate(m[0]) and m)

literal = lambda value: filt(lambda v: v==value)
char = lambda value: literal(value)(shift)

fmap = lambda func: (
         lambda parser:
           lambda inp: (m:=parser(inp)) and (func(m[0]), m[1]))

either = lambda p1, p2: (lambda inp: p1(inp) or p2(inp))
maybe  = lambda parser: either(parser, nothing)
choice = lambda parser, *parsers: either(parser, choice(*parsers)) if parsers else parser

def seq(*parsers):
    def parse(inp):
        result = [ ]
        for p in parsers:
            if not (m:=p(inp)):
                return False
            value, inp = m
            result.append(value)
        return (result, inp)
    return parse

left = lambda p1, p2: fmap(lambda p: p[0])(seq(p1, p2))
right = lambda p1, p2: fmap(lambda p: p[1])(seq(p1, p2))

def one_or_more(parser):
    def parse(inp):
        result = [ ]
        while (m:=parser(inp)):
            value, inp = m
            result.append(value)
        return bool(result) and (result, inp)
    return parse

zero_or_more = lambda parser: either(one_or_more(parser), seq())

Input = lambda inp: (inp, 0)

# -- Пример: преобразование "key1=value1; key2=value2; ..." в словарь

# числа и значения
dot = char('.')
digit = filt(str.isdigit)(shift)
digits = fmap(''.join)(one_or_more(digit))
decdigits = fmap(''.join)(choice(
               seq(digits, dot, digits),
               seq(digits, dot),
               seq(dot, digits)))

integer = fmap(int)(digits)
decimal = fmap(float)(decdigits)
number = choice(decimal, integer)

# имена
letter = filt(str.isalpha)(shift)
letters = fmap(''.join)(one_or_more(letter))

# Пробел
ws = zero_or_more(filt(str.isspace)(shift))
token = lambda p: right(ws, p)

# Токены (с удалённым пробелом)
eq = token(char('='))
semi = token(char(';'))
name = token(letters)
value = token(number)

# Одна пара key=value;
keyvalue = seq(left(name, eq), left(value, semi))

# Несколько пар "ключ-значение"
keyvalues = fmap(dict)(zero_or_more(keyvalue))

# Пример
result, remaining = keyvalues(Input("x=2; y=3.4; z=.789;"))
print(result)

▍ Похожие работы

Если вас потряс этот пост, то вам следует изучить комбинаторы парсеров. Программирование при помощи комбинаторов — не самая распространённая вещь в Python, но это может быть интересным способом достижения необычной чрезвычайной гибкости.

В мире Python есть множество связанных с парсингом инструментов, построенных на схожих концепциях. Большинство из них содержит излишества, но их стоит изучить:

▍ Размышления

За последние двадцать лет я много работал с парсингом на Python. В том числе я разработал множество пакетов генераторов парсеров LALR (1) и преподавал курс по компиляторам, на котором обычно даю студентам задание написать парсер с рекурсивным спуском. Хотя я раньше слышал сочетание слов «комбинатор парсеров», впервые попробовал поработать с ними только недавно.

В этом январе я решил, что попробую в качестве хобби-проекта реализовать свой курс по компиляторам на Haskell. Ранее никогда не программировав на Haskell, я был вынужден перестроить часть своего мозга. Я начал работу с книги «Programming in Haskell» Грэма Хаттона. Как оказалось, Грэм обладает существенным опытом в монадных комбинаторах парсеров (см., например, эту статью) и многие примеры в его книге используют эту технику.

Мне никогда не доводилось писать парсер таким образом. Поэтому по большей части в моём посте приведён «ремикс» этих идей на Python. Я свободно использовал идиомы Python и делал всё немного иным способом. Однако код всё равно воплощает общую большую идею. Кроме того, я писал код на Python в «эквациональном стиле», отражающем упор на композицию функций, а не на реализацию функций.

Меня поразил минимализм и выразительность кода. Здесь не используется никакого сложного метапрограммирования, перегрузки операторов и даже классов. Если вы хотите посмотреть, как всё работает, то код у вас прямо перед глазами. Большинство функций очень компактно. Удивительно то, как они сочетаются друг с другом.

Примечание: иногда люди спрашивают меня: «Как мне улучшить свои навыки Python?». К их удивлению, я часто предлагаю создать проект на совершенно другом языке или за рамками их сферы опыта. Я думаю, что основной выигрыш от этого заключается в том, что часто вы видите совершенно иной способ мышления о задачах, который можно привнести в свои проекты.

▍ В заключение: буду ли я действительно использовать это?

Как уже говорилось, я изучил эту технику в версии для Haskell. Однако позже я применил её к реализации на Python в моём проекте курса по компиляторам. Получившийся в результате парсер был примерно вдвое меньше написанного вручную парсера рекурсивного спуска и включал в себя меньшее количество концепций. Кроме того, получившийся код напрямую отражал грамматику языка, определённую при помощи PEG. И, наконец, оказалось, что новая реализация имеет множество хороших свойств, связанных с обработкой ошибок и с сообщениями об ошибках. В конечном итоге, она понравилась мне намного больше.

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

Telegram-канал с розыгрышами призов, новостями IT и постами о ретроиграх

© Habrahabr.ru