ProgHubPH

Пишем простой парсер JSON на Python

Перевод статьи Phil Eaton

Написание парсера JSON - один из простейших способов ознакомления с техниками парсинга. Форматирование предельно просто, оно построено на рекурсии. Поэтому оно немного сложнее чем, скажем, Braifuck. Также, вероятно, вы уже сталкивались с JSON.

Если вы просто хотите увидеть код - его можно найти на Github.

Что такое парсинг, и чем он не является

Обычно парсинг разбивается на два этапа: лексический анализ и синтаксический анализ. Лексический анализ разбивает исходные данные на простейшие элементы языка - токены (или лексемы). Синтаксический анализ собирает из лексем осмысленные (для этого языка) выражения.

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

Интерфейс библиотеки

В данном случае мы реализуем лишь один метод from_string, который из строки вернёт словарь (dictionary). Пример теста:

assert_equal(from_string('{"foo": 1}'), {"foo": 1})

Лексический анализ

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

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

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

Последняя версия движка V8 JavaScript теперь может воспроизводить точный код вызванной функции. Это огромный прорыв для лексера языка с анонимными функциями и классами.

Реализация лексера JSON

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

Пример вывода:

assert_equal(lex('{"foo": [1, 2, {"bar": 2}]}'),
             ['{', 'foo', ':', '[', 1, ',', 2, ',', '{', 'bar', ':', 2, '}', ']', '}'])

Заготовка кода:

def lex(string):
    tokens = []

    while len(string):
        json_string, string = lex_string(string)
        if json_string is not None:
            tokens.append(json_string)
            continue

        

        if string[0] in JSON_WHITESPACE:
            string = string[1:]
        elif string[0] in JSON_SYNTAX:
            tokens.append(string[0])
            string = string[1:]
        else:
            raise Exception('Unexpected character: {}'.format(string[0]))

    return tokens

Задача здесь - выделить из ввода числа, строки, булевы значения и null. Если ни один из них не подходит, то проверяем символ на пробел (отступ) и синтаксическую часть JSON. Всё, кроме whitespaces, добавляется в список токенов, который возвращается функцией.

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

def lex_string(string):
    return None, string


def lex_number(string):
    return None, string


def lex_bool(string):
    return None, string


def lex_null(string):
    return None, string


def lex(string):
    tokens = []

    while len(string):
        json_string, string = lex_string(string)
        if json_string is not None:
            tokens.append(json_string)
            continue

        json_number, string = lex_number(string)
        if json_number is not None:
            tokens.append(json_number)
            continue

        json_bool, string = lex_bool(string)
        if json_bool is not None:
            tokens.append(json_bool)
            continue

        json_null, string = lex_null(string)
        if json_null is not None:
            tokens.append(None)
            continue

        if string[0] in JSON_WHITESPACE:
            string = string[1:]
        elif string[0] in JSON_SYNTAX:
            tokens.append(string[0])
            string = string[1:]
        else:
            raise Exception('Unexpected character: {}'.format(string[0]))

    return tokens

Определение строк

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

def lex_string(string):
    json_string = ''

    if string[0] == JSON_QUOTE:
        string = string[1:]
    else:
        return None, string

    for c in string:
        if c == JSON_QUOTE:
            return json_string, string[len(json_string)+1:]
        else:
            json_string += c

    raise Exception('Expected end-of-string quote')

Определение чисел

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

def lex_number(string):
    json_number = ''

    number_characters = [str(d) for d in range(0, 10)] + ['-', 'e', '.']

    for c in string:
        if c in number_characters:
            json_number += c
        else:
            break

    rest = string[len(json_number):]

    if not len(json_number):
        return None, string

    if '.' in json_number:
        return float(json_number), rest

    return int(json_number), rest

Определение булевых значений и null

Это самые простые типы данных для обнаружения:

def lex_bool(string):
    string_len = len(string)

    if string_len >= TRUE_LEN and \
       string[:TRUE_LEN] == 'true':
        return True, string[TRUE_LEN:]
    elif string_len >= FALSE_LEN and \
         string[:FALSE_LEN] == 'false':
        return False, string[FALSE_LEN:]

    return None, string


def lex_null(string):
    string_len = len(string)

    if string_len >= NULL_LEN and \
       string[:NULL_LEN] == 'null':
        return True, string[NULL_LEN]

    return None, string

Теперь лексер закончен. Полный исходный код можно найти в файле pj/lexer.py.

Синтаксический анализ

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

Реализация парсера JSON

Заготовка JSON парсера будет итерировать по токенам, которые вернул лексический анализатор, и соотносить их с объектами, списками или парами ключ-значение:

tokens = lex('{"foo": [1, 2, {"bar": 2}]}')
assert_equal(tokens,
             ['{', 'foo', ':', '[', 1, ',', 2, '{', 'bar', ':', 2, '}', ']', '}'])
assert_equal(parse(tokens),
             {'foo': [1, 2, {'bar': 2}]})

Логика будет выглядеть следующим образом:

def parse_array(tokens):
    return [], tokens

def parse_object(tokens):
    return {}, tokens

def parse(tokens):
    t = tokens[0]

    if t == JSON_LEFTBRACKET:
        return parse_array(tokens[1:])
    elif t == JSON_LEFTBRACE:
        return parse_object(tokens[1:])
    else:
        return t, tokens[1:]

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

Так как JSON - формат сериализации данных, а не язык, то парсер должен возвращать объекты языка Python, а не синтаксическое дерево, с которым можно было бы работать далее (или сгенерировать код в случае компилятора).

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

Парсинг массивов

Массив всегда начинается с левой квадратной скобки. Поэтому парсинг массивов сводится к поиску элементов массива, запятых между ними или же закрывающих скобок:

def parse_array(tokens):
    json_array = []

    t = tokens[0]
    if t == JSON_RIGHTBRACKET:
        return json_array, tokens[1:]

    while True:
        json, tokens = parse(tokens)
        json_array.append(json)

        t = tokens[0]
        if t == JSON_RIGHTBRACKET:
            return json_array, tokens[1:]
        elif t != JSON_COMMA:
            raise Exception('Expected comma after object in array')
        else:
            tokens = tokens[1:]

    raise Exception('Expected end-of-array bracket')

Парсинг объектов

Парсинг объектов заключается в поиске пар ключ-значение, где ключ от значения отдёлен двоеточием, а пары разделены запятыми. Поиск продолжается до окончания объекта:

def parse_object(tokens):
    json_object = {}

    t = tokens[0]
    if t == JSON_RIGHTBRACE:
        return json_object, tokens[1:]

    while True:
        json_key = tokens[0]
        if type(json_key) is str:
            tokens = tokens[1:]
        else:
            raise Exception('Expected string key, got: {}'.format(json_key))

        if tokens[0] != JSON_COLON:
            raise Exception('Expected colon after key in object, got: {}'.format(t))

        json_value, tokens = parse(tokens[1:])

        json_object[json_key] = json_value

        t = tokens[0]
        if t == JSON_RIGHTBRACE:
            return json_object, tokens[1:]
        elif t != JSON_COMMA:
            raise Exception('Expected comma after pair in object, got: {}'.format(t))

        tokens = tokens[1:]

    raise Exception('Expected end-of-object brace')

Парсер готов. Полный код можно увидеть в pj/parser.py.

Собираем библиотеку

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

def from_string(string):
    tokens = lex(string)
    return parse(tokens)[0]

Библиотека готова. Дополнительные вещи, вроде тестов, можно найти в репозитории Github.

Дополнение: парсинг в один этап

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

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