Интерлюдия 2: разбор S-выражений

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

Парсеры

Парсером мы будем называть функцию, получающую на вход текст, а в качестве результата выдающая хвост этого текста (хвостом или суффиксом текста t называется любой текст y такой, что для какого-то x выполнено t = x+y), спаренный с некоторыми данными произвольного вида. Будем говорить, что эти данные получены путём разбора или, как ещё говорят, парсинга вырезанного из текста куска.

Вот типичный пример парсера:

def parse_digit(text):
    if len(text) > 0 and '0' <= text[0] <= '9':
        return text[0], text[1:]

Этот парсер разбирает одну цифру из текста. Обратите внимание на то, что в случае неудачи этот парсер возвращает значение None. Договоримся и дальше придерживаться такого соглашения. В связи с этим уточним понятие парсера.

Любой парсер обрабатывает поданный ему на вход текст t так:

• если удалось найти такой x, что t = x + y и x можно разобрать, парсер возвращает пару (r, y), где r — результат разбора текста x;
• если же такого x нет, парсер возвращает None

Приведём ещё один пример парсера:

def parse_spaces(text):
    for i, x in enumerate(text):
        if x != ' ': return i, text[i:]

Этот парсер разбирает все пробелы из начала текста, преобразуя их в их количество.

Генераторы парсеров

Обычно парсеры создаются «на ходу» при помощи функций, называемых генераторами парсеров (далее мы будем их называть просто генераторами; не путать с одноимённым типом данных языка Python!). Вот — типичный пример генератора:

def gen_parse_char(x):
    def parse(text):
        if len(text) > 0 and text[0] == x: return x, text[1:]

    return parse

Но нам в первую очередь будет интересен генератор тривиальных парсеров:

def gen_trivial(x):
    return (lambda text: (x, text))

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

Связывание

Парсерным связыванием называется следующая операция:

def bind(parse, gen):
    def composite(text):
        result = parse(text)
        
        if result == None: return None
        
        value, text_tail = result
        
        return gen(value)(text_tail)


    return composite

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

При помощи операции связывания можно писать странные (на первый взгляд) вещи. Например, вот парсер, распознающий двухзначное число:

parse_two_digit_number = (
    bind(parse_digit, lambda d1:
    bind(parse_digit, lambda d2:
    gen_trivial( int(d1+d2) )))
)

Этот код довольно сильно напоминает программу вида

def extract_two_digit_number():
    d1 = extract_digit()
    d2 = extract_digit()
    return int(d1 + d2)

за тем исключением, что:

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

Альтернатива

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

def alt(parsers):
    def parse(text):
        for p in parsers:
            result = p(text)
            if result != None: return result

    return parse

и выражающаяся в его терминах операция «провала»:

parse_fail = alt([])

Альтернатива позволяет писать рекуррентные парсеры в терминах связывания:

def parse_digits(text):
    p = alt([
        # цифры числа -- это либо цифра, за которой следуют ещё цифры
            bind(parse_digit, lambda d:
            bind(parse_digits, lambda ds:
            gen_trivial(d+ds))), 
        # либо одна цифра
            parse_digit])

    return p(text)

parse_number = bind(parse_digits, lambda ds: 
               gen_trivial(int(ds)))

Разбор S-выражений

Собственно, мы готовы написать простой разбиратель S-выражений. Сначала сделаем чуть более умный парсер числа:

parse_sign = alt([gen_parse_char('-'), gen_parse_char('+'), gen_trivial('')])

parse_number = bind(parse_sign, lambda s:
               bind(parse_digits, lambda ds:
               gen_trivial(int(s+ds))))

Далее сделаем парсер нечисловых слов:

def gen_parse_alphabet(a):
    def parse(text):
        if len(text) > 0 and text[0] in a: 
            return text[0], text[1:]
    
    return parse

def gen_parse_word(a):
    pc = gen_parse_alphabet(a)

    def parse_word(text):
        p = alt([
            bind(pc, lambda c:
            bind(parse_word, lambda w:
            gen_trivial(c+w))),

            pc])

        return p
    
    return parse_word

Определение parse_word почти полностью повторяет определение parse_digits. Эти определения абстрагируются комбинатором many1:

def many1(p):
    def parse(text):
        r = alt([
            bind(p,     lambda x:
            bind(parse, lambda xs:
            gen_trivial([x]+xs))),
            
            bind(p, lambda x:
            gen_trivial([x]))])

        return r(text)

    return parse

В терминах этого комбинатора

def gen_parse_word(a):
    return bind(many1(gen_parse_alphabet(a)), lambda xs:
           gen_trivial(''.join(xs)))

parse_digits = gen_parse_word('1234567890')

Также бывает полезен комбинатор many:

def many(p):
    def parse(text):
        r = alt([
            bind(p,     lambda x:
            bind(parse, lambda xs:
            gen_trivial([x]+xs))),
            
            gen_trivial([])
        ])

        return r(text)

    return parse

В терминах которого выражается many1:

def many1(p):
    return bind(p,       lambda x:
           bind(many(p), lambda xs:
           gen_trivial( [x] + xs )))

Теперь, наконец, мы можем описать всю грамматику S-выражений:

parse_word = gen_parse_word(
'qwertyuiop[]asdfghjkl;\'zxcvbnm,./1234567890-'+
'=!@#$%^&*_+\\|QWERTYUIOP{}ASDFGHJKL:"ZXCVBNM<>?'
)

def parse_sexp(text):
    p = bind(parse_spaces, lambda _:
        alt([
            bind(gen_parse_char('('), lambda _:
            bind(many(parse_sexp), lambda exps:
            bind(parse_spaces,        lambda _:
            bind(gen_parse_char(')'), lambda _:
            gen_trivial( exps )))),

            parse_number,
            parse_word
        ]))

    return p(text)

Итоговый код

Приведём для полноты картины итоговую программу, разбирающую S-выражения.

## Комбинаторы парсеров

def gen_trivial(x):
    return (lambda text: (x, text))

def bind(parse, gen):
    def composite(text):
        result = parse(text)
        
        if result == None: return None
        
        value, text_tail = result
        
        return gen(value)(text_tail)


    return composite

def alt(parsers):
    def parse(text):
        for p in parsers:
            result = p(text)
            if result != None: return result

    return parse

def many(p):
    def parse(text):
        r = alt([
            bind(p,     lambda x:
            bind(parse, lambda xs:
            gen_trivial([x]+xs))),
            
            gen_trivial([])
        ])

        return r(text)

    return parse

def many1(p):
    return bind(p,       lambda x:
           bind(many(p), lambda xs:
           gen_trivial( [x] + xs )))


## И сами парсеры

def gen_parse_alphabet(a):
    def parse(text):
        if len(text) > 0 and text[0] in a: 
            return text[0], text[1:]
    
    return parse


def gen_parse_word(a):
    return bind(many1(gen_parse_alphabet(a)), lambda xs:
           gen_trivial(''.join(xs)))


gen_parse_char = gen_parse_alphabet

parse_sign = alt([gen_parse_char('-'), gen_parse_char('+'), gen_trivial('')])

parse_digits = gen_parse_word('1234567890')

parse_number = bind(parse_sign, lambda s:
               bind(parse_digits, lambda ds:
               gen_trivial(int(s+ds))))

parse_word = gen_parse_word(
'qwertyuiop[]asdfghjkl;\'zxcvbnm,./1234567890-'+
'=!@#$%^&*_+\\|QWERTYUIOP{}ASDFGHJKL:"ZXCVBNM<>?'
)

parse_spaces = many(gen_parse_char(' '))

def parse_sexp(text):
    p = bind(parse_spaces, lambda _:
        alt([
            bind(gen_parse_char('('), lambda _:
            bind(many(parse_sexp), lambda exps:
            bind(parse_spaces,        lambda _:
            bind(gen_parse_char(')'), lambda _:
            gen_trivial( exps ))))),

            parse_number,

            parse_word
        ]))

    return p(text)