Андрей Власовских

Блог Андрея Власовских

Простой рекурсивный парсер JSON

with one comment

Недавно наткнулся на интересный метод парсинга, который в «Книге дракона» если и описан, то только в виде упоминания. Метод называется рекурсивный спуск с использованием перебора с возвратом (recursive descent with backtracking). Встретил я пример использования этого метода в русском переводе «Введения в функциональное программирование» Джона Харрисона (John Harrison). Парсеры такого типа можно свободно писать с нуля на функциональных языках.

Upd: Выпустил в июле 2009 года библиотеку funcparserlib. Вот пост о ней. Она включает в себя как пример довольно хороший парсер JSON. Материал ниже можно считать устаревшим.

Если есть BNF-подобное описание грамматики без левой рекурсии, то по её нетерминалам легко пишутся функции их разбора. Каждая такая функция является парсером и имеет тип (здесь и далее используется язык Python) Sequence(a) -> (b, Sequence(a)), где a — тип токенов (например, банальных str), b — тип результата разбора (в общем случае object), а Sequence — тип любой последовательности (вот один из вариантов того, что можно считать последовательностью). Для таких функций-парсеров можно ввести очень удобные комбинаторы типа альтернативы, следования, множественного применения. Вообще, это очень показательный пример преимуществ функционального программирования.

Используя этот метод, я написал парсер JSON на Python на основе грамматики из RFC 4627. Известны проблемы парсеров JSON на Python, но я строго следовал грамматике RFC, так что в лексике и синтаксисе ошибок быть не должно. Приведу исходный код. Вначале часть, которую можно было бы сделать библиотекой: несколько удобных комбинаторов, взятых из книги Харрисона, а также объектная обёртка комбинаторов для перегрузки операторов Python ради красоты:

class NoParse(Exception):
    def __init__(self, tokens, msg=None):
        self.tokens = tokens
        self.msg = msg
    
    def __str__(self):
        s = 'cannot parse input'
        e = 'unparsed data remains:\n%s' % self.tokens
        msg = ' %s' % self.msg if self.msg is not None else ''
        return '%s:%s\n%s' % (s, msg, e)

class Parser(object):
    def __init__(self, p):
        self.wrapped = p

    def __call__(self, tokens):
        return self.wrapped(tokens)

    def __add__(self, other):
        @Parser
        def f(tokens):
            v1, r1 = self(tokens)
            v2, r2 = other(r1)
            return (v1, v2), r2
        return f

    def __or__(self, other):
        @Parser
        def f(tokens):
            try:
                return self(tokens)
            except NoParse:
                return other(tokens)
        return f

    def __rshift__(self, treatment):
        @Parser
        def f(tokens):
            v, r = self(tokens)
            return treatment(v), r
        return f

@Parser
def finished(tokens):
    if len(tokens) == 0:
        return None, tokens
    else:
        raise NoParse(tokens, 'should have reached eof')

def many(p):
    @Parser
    def f(tokens):
        try:
            v, next = p(tokens)
            vs, rest = many(p)(next)
            return [v] + vs, rest
        except NoParse:
            return [], tokens
    return f

def some(predicate):
    @Parser
    def f(tokens):
        if len(tokens) == 0:
            raise NoParse(tokens, 'no tokens left in the stream')
        else:
            t, ts = tokens[0], tokens[1:]
            if predicate(t):
                return t, ts
            else:
                raise NoParse(tokens, 'token "%s" doesn\'t match against the predicate' % t)
    return f

def a(value):
    return some(lambda t: t == value)

def several(predicate):
    return many(some(predicate))

А теперь код самого парсера JSON. Я не хитрил и реализовал разбор «в лоб», просто следуя RFC. Как я уже писал, код всё равно получается прозрачный и краткий:

def json_loads(s):
    'str -> object'
    head = lambda (x, xs): x
    from operator import add
    word = lambda w: reduce(add, [a(c) for c in w])
    
    # RFC 4627 productions, nearly 1-to-1
    ws = several(lambda c: c in ' \t\n\r')
    begin_array = ws + a('[') + ws
    end_array = ws + a(']') + ws
    begin_object = ws + a('{') + ws
    end_object = ws + a('}') + ws
    name_separator = ws + a(':') + ws
    value_separator = ws + a(',') + ws
    false = (word('false')
        >> (lambda _: False))
    true = (word('true')
        >> (lambda _: True))
    null = (word('null')
        >> (lambda _: None))
    unescaped = some(lambda c: any(min <= ord(c) <= max
        for min, max in [(0x20, 0x21), (0x23, 0x5b), (0x5d, 0x10ffff)]))
    escape = a('\\')
    quotation_mark = a('"')
    hexdig = some(lambda c: c in '0123456789ABCDEF')
    char = (
          unescaped
        | ((escape + (
              a('"')
            | a('\\')
            | a('/')
            | a(unichr(0x0008)) # backspace
            | a(unichr(0x000c)) # form feed
            | a('\n')
            | a('\r')
            | a('\t')
            | (a('u') + hexdig + hexdig + hexdig + hexdig # uXXXX
                >> (lambda ((((_, d1), d2), d3), d4):
                   (unichr(int('%s%s%s%s' % (d1, d2, d3, d4), 16)))))
        )) >> (lambda (_, v): v))
    )
    string = (quotation_mark + many(char) + quotation_mark
        >> (lambda ((_1, cs), _2): ''.join(cs)))
    minus = a('-')
    plus = a('+')
    e = a('e') | a('E')
    decimal_point = a('.')
    digit1_9 = some(lambda c: c in '123456789')
    zero = a('0')
    digit = digit1_9 | zero
    integer = (
          zero
        | (digit1_9 + many(digit)
            >> (lambda (x, xs): ''.join([x] + xs))))
    frac = (decimal_point + digit + many(digit)
        >> (lambda ((_, x), xs): ''.join([x] + xs)))
    exp = (
          (e + minus + digit + many(digit)
            >> (lambda (((_1, _2), x), xs): '-%s' % ''.join([x] + xs)))
        | (e + plus + digit + many(digit)
            >> (lambda (((_1, _2), x), xs): ''.join([x] + xs)))
    )
    number = (
          (minus + integer + frac + exp
            >> (lambda (((_, x), f), e): float('-%s.%se%s' % (x, f, e))))
        | (minus + integer + frac
            >> (lambda ((_, x), f): float('-%s.%s' % (x, f))))
        | (minus + integer + exp
            >> (lambda ((_, x), e): float('-%se%s' % (x, e))))
        | (minus + integer
            >> (lambda (_, x): int('-%s' % x)))
        | (integer + frac + exp
            >> (lambda ((x, f), e): float('%s.%se%s' % (x, f, e))))
        | (integer + frac
            >> (lambda (x, f): float('%s.%s' % (x, f))))
        | integer
            >> (lambda x: int(x))
    )
    @Parser
    def value(tokens):
        return (
            false | null | true | object | array | number | string
        )(tokens)
    array = (
          (begin_array + value + many(value_separator + value) + end_array
            >> (lambda (((_1, x), vs), _2):
               ([x] + [v for _, v in vs])))
        | (begin_array + end_array
            >> (lambda _: []))
    )
    member = (string + name_separator + value
        >> (lambda ((k, _), v): (k, v)))
    object = (
          (begin_object + member + many(value_separator + member) + end_object
            >> (lambda (((_1, x), ms), _2):
               (dict([x] + [m for _, m in ms]))))
        | (begin_object + end_object
            >> (lambda _: {}))
    )
    json_text = (object | array) + finished >> head
    return head(json_text(s))

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

Несколько замечаний об использовании:

  • В грамматике RFC 4627 лексемы отдельно не описываются, так что я лексический анализ как стадию не выделил. Но вообще парсить поток токенов с их типом, значением и позицией в потоке удобнее
  • Если в грамматике есть левая рекурсия, то её нужно устранить, т. к. это LL-парсер
  • За счёт возврата при переборе парсер может заглядывать на сколько угодно токенов вперёд, то есть это LL(*)
  • При использовании в качестве входа функций разбора обычных строк без состояния нельзя установить место, в котором произошла ошибка. К тому же весь разбираемый текст надо держать в памяти. Введение состояния портит красоту и немного усложняет код. Мне кажется, таких проблем можно избежать в монадических парсерах
Реклама

Written by vlan

2008-07-24 в 05:28

Опубликовано в Uncategorized

Tagged with , , , , , ,

Один ответ

Subscribe to comments with RSS.

  1. […] funcparserlib возникла поначалу из игрушечного примера парсера JSON, который я написал в 2008 году. Пример был создан, чтобы […]


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

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

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: