В C++17 (нет-нет, Питон скоро будет, вы правильно зашли!) появляется новый синтаксис для оператора if, позволяющий объявлять переменные прямо в заголовке блока. Это довольно удобно, поскольку конструкции вида

Foo foo = make_foo();
if(foo.is_nice()) {
    // do work with foo
}
// never use foo again
// foo gets deleted

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

if(Foo foo = make_foo(); foo.is_nice()) {
    // do work with foo
}  // foo gets deleted
// never use foo again (well, you can't anyway)

Стало чуть-чуть лучше, хотя всё ещё не выглядит идеально. В Python нет и такого, но если вы ненавидите if в Python-коде так же сильно, как я, и хотите научиться быстро писать простые парсеры, то добро пожаловать под кат. В этой статье мы попытаемся написать короткий и изящный парсер для JSON на Python 2 (без каких-либо дополнительных модулей, конечно же).

Что такое парсинг и с чем его едят


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

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

  2. Разбить ввод на токены. Пишется лексический анализатор (в народе токенайзер), который разбивает входную строку или файл на последовательность токенов, то есть валидных слов нашего языка (или ноет, что это нельзя сделать).

  3. Проверить синтаксис и построить синтаксическое дерево. Проверяем, соответствует ли последовательность токенов описанию нашего языка. Здесь в ход идут алгоритмы вроде метода рекурсивного спуска. Каждое валидное предложение языка включает какое-то конечное количество валидных слов или других валидных предложений; если токены смогли сложиться в стройную картину, то на выходе мы автоматически получаем дерево, которое и называется абстрактным синтаксическим деревом.

  4. Сделать, наконец, работу. У вас есть синтаксическое дерево и вы можете наконец сделать то, что хотели: посчитать значение арифметического выражения, организовать запрос в БД, скомпилировать программу, отобразить веб-страницу и так далее.

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

Модельная задача


Написание парсера проиллюстрируем на простом, но не до конца тривиальном примере — парсинге JSON. Грамматика выглядит примерно так:

root ::= value
value ::= string | number | object | array | 'true' | 'false' | 'null'

array ::= '[' ']' | '[' comma-separated-values ']'
comma-separated-values ::= value | value ',' comma-separated-values

object ::= '{' '}' | '{' comma-separated-keyvalues '}'
comma-separated-keyvalues ::= keyvalue | keyvalue ',' comma-separated-keyvalues
keyvalue ::= string ':' value

Здесь нет правил для string и number — они, вместе со всеми строками в кавычках, будут нашими токенами.

Парсим JSON


Полноценный токенайзер мы писать не станем (это скучно и не совсем тема статьи) — будем работать с целой строкой и бить её на токены по мере необходимости. Напишем две первые функции:

import re

# без re.DOTALL мы сломаемся на первом же переносе строки
number_regex = re.compile(r"(-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?)\s*(.*)", re.DOTALL)
def parse_number(src):
    match = number_regex.match(src)
    if match is not None:
        number, src = match.groups()
        return eval(number), src  # использовать eval - не лучшее решение, но самое простое

string_regex = re.compile(r"('(?:[^\\']|\\['\\/bfnrt]|\\u[0-9a-fA-F]{4})*?')\s*(.*)", re.DOTALL)
def parse_string(src):
    match = string_regex.match(src)
    if match is not None:
        string, src = match.groups()
        return eval(string), src  # здесь мы вообще подменили JSON'овский
                                  # формат строк на питоновский, ну да ладно

(Я обещал без if'ов, но это последние, чесслово!)

Для всего остального напишем одну функцию, генерящую простенькие функции-парсеры:


def parse_word(word, value=None):
    l = len(word)
    def result(src):
        # добавьте в следующую строчку вызовы .lower() для case-insensitive языка!
        if src.startswith(word):  # опять if! вот живучая тварь!
            return value, src[l:].lstrip()  # lstrip нужен для игнорирования пробелов, см. ниже
    result.__name__ = "parse_%s" % word  # для отладки
    return result

parse_true = parse_word("true", True)
parse_false = parse_word("false", False)
parse_null = parse_word("null", None)

Итого, по какому принципу мы строим наши функции:

  1. Они принимают строку, которую нужно парсить.
  2. Они возвращают пару (результат, оставшаяся_строка) при успехе (то есть когда требуемая конструкция нашлась в начале строки) и None при провале.
  3. Они отправляют в небытие все пробельные символы между токенами. (Не делайте так, если пишете парсер Питона!)

Собственно, на этих трёх функциях проблемы с токенами решены, и мы можем перейти к интересной части.

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


Как должна выглядеть функция parse_value, соответствующая грамматике выше? Обычно как-то так:


def parse_value(src):
    # попытайся распарсить строковый литерал
    match = parse_string(src)
    if match is not None:
        # получилось!
        return match
    # не получилось; ну тогда попытайся распарсить число
    match = parse_number(src)
    if match is not None:
        return match
    # да что ж такое. ну тогда попытайся расп...
    # ...

Ну уж нет, эти if достали меня!

Давайте поменяем три функции выше самым неожиданным образом: заменим return на yield! Теперь они возвращают генераторы — пустые, если парсинг не удался, и ровно с одним элементом, если удался. Да-да, мы разворачиваем на 90 градусов наш принцип номер 2: все наши функции мы будем теперь писать в таком стиле:


number_regex = re.compile(r"(-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?)\s*(.*)", re.DOTALL)

def parse_number(src):
    match = number_regex.match(src)
    if match is not None:
        number, src = match.groups()
        yield eval(number), src
    # если управление дошло до сюда без yield, числа обнаружить не удалось.
    # ну что же, пустой генератор тоже генератор.

string_regex = re.compile(r"('(?:[^\\']|\\['\\/bfnrt]|\\u[0-9a-fA-F]{4})*?')\s*(.*)", re.DOTALL)

def parse_string(src):
    match = string_regex.match(src)
    if match is not None:
        string, src = match.groups()
        yield eval(string), src

def parse_word(word, value=None):
    l = len(word)
    def result(src):
        if src.startswith(word):
            yield value, src[l:].rstrip()
    result.__name__ = "parse_%s" % word
    return result  # здесь возвращаем функцию-парсер, не yield'им

parse_true = parse_word("true", True)
parse_false = parse_word("false", False)
parse_null = parse_word("null", None)

Во что же превратится наша parse_value? На первый взгляд во что-то такое:


def parse_value(src):
    for match in parse_string(src):
        yield match
        return
    for match in parse_number(src):
        yield match
        return
    # ...

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


# весьма полезная itertools.chain объединяет переданные ей итераторы
# в цепочку, не трогая ни один раньше времени
from itertools import chain

def parse_value(src):
    for match in chain(
        parse_string(src),
        parse_number(src),
        parse_array(src),
        parse_object(src),
        parse_true(src),
        parse_false(src),
        parse_null(src),
    ):  # закрывающей скобке грустно, но веселье только начинается
        yield match
        return

При этом эффективность остаётся на прежнем уровне — каждая функция начнёт выполняться (а стало быть, делать работу, проверяя регулярные выражения) только тогда, когда предыдущая не даст результата. return гарантирует, что лишняя работа не будет выполнена, если где-то в середине списка парсинг удался.

Парсим последовательности конструкций


Перейдём к следующему номеру нашей программы — функции parse_array. Выглядеть она должна как-то так:


parse_left_square_bracket = parse_word("[")
parse_right_square_bracket = parse_word("]")

def parse_array(src):
    # здесь потребуется временная переменная tsrc, иначе даже при неудачном
    # парсинге пустого массива открывающая скобка может быть "съедена"
    for _, tsrc in parse_left_square_bracket(src):
        for _, tsrc in parse_right_square_bracket(tsrc):
            # если мы здесь, то нам удалось последовательно распарсить '[' и ']'
            yield [], tsrc
            return
    # здесь переменную src уже не жалко -- за этим циклом только боль и пустота
    for _, src in parse_left_square_bracket(src):
        for items, src in parse_comma_separated_values(src):
            for _, src in parse_right_square_bracket(src):
                yield items, src
    # если управление дошло сюда без yield, то парсинг массива не удался

Ни одного if, как и обещано, но что-то всё равно не так… Давайте напишем небольшую вспомогательную функцию, которая поможет нам соединять функции-парсеры в последовательности подобно тому, как chain помогла соединять их в режиме «или». Эта функция должна будет аккуратно брать все результаты и вернуть все первые элементы результатов (результаты анализа) и последний второй элемент (оставшуюся непроанализированной часть строки). Мой вариант выглядит так:


def sequence(*funcs):
    if len(funcs) == 0:  # ну простите, не могу в рекурсию без if'а
        def result(src):
            yield (), src
        return result
    def result(src):
        for arg1, src in funcs[0](src):
            for others, src in sequence(*funcs[1:])(src):
                yield (arg1,) + others, src  # конкатенируем содержательные результаты
    return result

С этим мощным (пусть и страшноватым) инструментом наша функция перепишется в виде:


parse_left_square_bracket = parse_word("[")
parse_right_square_bracket = parse_word("]")
parse_empty_array = sequence(parse_left_square_bracket, parse_right_square_bracket)

def parse_array(src):
    for _, src in parse_empty_array(src):  # увы, эта функция недостаточно умна, чтобы вернуть []
        yield [], src
        return  # этот return нужен, чтобы не пойти радостно парсить
                # дальше в конструкции вида {} {"a": 1}

    for (_, items, _), src in sequence(
        parse_left_square_bracket,
        parse_comma_separated_values,
        parse_right_square_bracket,
    )(src):
        yield items, src
    # если управление дошло сюда без yield, то парсинг массива не удался

Ну а дописать функцию parse_comma_separated_values — раз плюнуть:


parse_comma = parse_word(",")

def parse_comma_separated_values(src):
    for (value, _, values), src in sequence(
        parse_value,
        parse_comma,
        parse_comma_separated_values  # я говорил, что не могу в рекурсию без if? я соврал
    )(src):
        yield [value] + values, src
        return

    for value, src in parse_value(src):
        yield [value], src

Приведёт ли такое решение к бесконечной рекурсии? Нет! Однажды функция parse_comma не найдёт очередной запятой, и до последующей parse_comma_separated_values выполнение уже не дойдёт.

Идём дальше! Объект:

parse_left_curly_bracket = parse_word("{")
parse_right_curly_bracket = parse_word("}")
parse_empty_object = sequence(parse_left_curly_bracket, parse_right_curly_bracket)

def parse_object(src):
    for _, src in parse_empty_object(src):
        yield {}, src
        return
    for (_, items, _), src in sequence(
        parse_left_curly_bracket,
        parse_comma_separated_keyvalues,
        parse_right_curly_bracket,
    )(src):
        yield items, src

parse_colon = parse_word(":")

def parse_keyvalue(src):
    for (key, _, value), src in sequence(
        parse_string,
        parse_colon,
        parse_value
    )(src):
        yield {key: value}, src

def parse_comma_separated_keyvalues(src):
    for (keyvalue, _, keyvalues), src in sequence(
        parse_keyvalue,
        parse_comma,
        parse_comma_separated_keyvalues, # тут снова рекурсия, не проглядите
    )(src):
        keyvalue.update(keyvalues)
        yield keyvalue, src
        return
        
    for keyvalue, src in parse_keyvalue(src):
        # к сожалению, питон не умеет в генераторе возвращать другой генератор
        yield keyvalue, src

Ну, что там дальше?


Собственно, всё! Остаётся добавить простую интерфейсную функцию:

def parse(s):
    s = s.strip()  # наш токенайзер убивает пробелы после токенов, но не терпит до
    match = list(parse_value(s))
    if len(match) != 1:
        # где-то что-то пошло не так. про отладку расскажу в другой раз :)
        raise ValueError("not a valid JSON string")
    result, src = match[0]
    if src.strip():
        # мы распарсили, но в строке ещё что-то осталось. это ошибка.
        raise ValueError("not a valid JSON string")
    return result

Вуаля!

Весь код вместе
from itertools import chain
import re

def sequence(*funcs):
    if len(funcs) == 0:
        def result(src):
            yield (), src
        return result
    def result(src):
        for arg1, src in funcs[0](src):
            for others, src in sequence(*funcs[1:])(src):
                yield (arg1,) + others, src
    return result

number_regex = re.compile(r"(-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?)\s*(.*)", re.DOTALL)

def parse_number(src):
    match = number_regex.match(src)
    if match is not None:
        number, src = match.groups()
        yield eval(number), src

string_regex = re.compile(r"('(?:[^\\']|\\['\\/bfnrt]|\\u[0-9a-fA-F]{4})*?')\s*(.*)", re.DOTALL)

def parse_string(src):
    match = string_regex.match(src)
    if match is not None:
        string, src = match.groups()
        yield eval(string), src

def parse_word(word, value=None):
    l = len(word)
    def result(src):
        if src.startswith(word):
            yield value, src[l:].lstrip()
    result.__name__ = "parse_%s" % word
    return result

parse_true = parse_word("true", True)
parse_false = parse_word("false", False)
parse_null = parse_word("null", None)

def parse_value(src):
    for match in chain(
        parse_string(src),
        parse_number(src),
        parse_array(src),
        parse_object(src),
        parse_true(src),
        parse_false(src),
        parse_null(src),
    ):
        yield match
        return

parse_left_square_bracket = parse_word("[")
parse_right_square_bracket = parse_word("]")
parse_empty_array = sequence(parse_left_square_bracket, parse_right_square_bracket)

def parse_array(src):
    for _, src in parse_empty_array(src):
        yield [], src
        return

    for (_, items, _), src in sequence(
        parse_left_square_bracket,
        parse_comma_separated_values,
        parse_right_square_bracket,
    )(src):
        yield items, src

parse_comma = parse_word(",")

def parse_comma_separated_values(src):
    for (value, _, values), src in sequence(
        parse_value,
        parse_comma,
        parse_comma_separated_values
    )(src):
        yield [value] + values, src
        return

    for value, src in parse_value(src):
        yield [value], src

parse_left_curly_bracket = parse_word("{")
parse_right_curly_bracket = parse_word("}")
parse_empty_object = sequence(parse_left_curly_bracket, parse_right_curly_bracket)

def parse_object(src):
    for _, src in parse_empty_object(src):
        yield {}, src
        return
    for (_, items, _), src in sequence(
        parse_left_curly_bracket,
        parse_comma_separated_keyvalues,
        parse_right_curly_bracket,
    )(src):
        yield items, src

parse_colon = parse_word(":")

def parse_keyvalue(src):
    for (key, _, value), src in sequence(
        parse_string,
        parse_colon,
        parse_value
    )(src):
        yield {key: value}, src

def parse_comma_separated_keyvalues(src):
    for (keyvalue, _, keyvalues), src in sequence(
        parse_keyvalue,
        parse_comma,
        parse_comma_separated_keyvalues,
    )(src):
        keyvalue.update(keyvalues)
        yield keyvalue, src
        return

    for keyvalue, src in parse_keyvalue(src):
        yield keyvalue, src

def parse(s):
    s = s.strip()
    match = list(parse_value(s))
    if len(match) != 1:
        raise ValueError("not a valid JSON string")
    result, src = match[0]
    if src.strip():
        raise ValueError("not a valid JSON string")
    return result


130 строк. Попробуем запустить:


>>> import my_json
>>> my_json.parse("null")
>>> my_json.parse("true")
True
>>> my_json.parse("false")
False
>>> my_json.parse("0.31415926E1")
3.1415926
>>> my_json.parse("[1, true, '1']")
[1, True, '1']
>>> my_json.parse("{}")
{}
>>> my_json.parse("{'a': 1, 'b': null}")
{'a': 1, 'b': None}

Успех!

Заключение


Конечно, я рассмотрел далеко не все ситуации, которые могут возникнуть при написании парсеров. Иногда программисту может потребоваться ручное управление выполнением, а не запуск последовательности chainов и sequenceов. К счастью, это не так неудобно в рассмотренном подходе, как может показаться. Так, если нужно попытаться распарсить необязательную конструкцию и сделать действие в зависимости от её наличия, можно написать:

for stuff, src in parse_optional_stuff(src):
    # опциональная конструкция на месте -- работаем
    break # предотвращает выполнение else
else:
    # опциональная конструкция отсутствует -- грустим
    pass

Здесь мы пользуемся малопопулярной фишкой Питона — блоком else у циклов, который выполняется, если цикл дошёл до конца без break. Это выглядит не так привлекательно, как наш код в статье, но точно не хуже, чем те if, от которых мы столь изящно избавились.

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

Как обычно, не откладывая пишите в личку обо всех обнаруженных неточностях, орфографических, грамматических и фактических ошибках — иначе я сгорю от стыда!
Поделиться с друзьями
-->

Комментарии (39)


  1. bak
    06.09.2016 00:17
    +4

    Судя по первому абзацу думал что будет парсинг питона с поддержкой

    if foo = make_foo():
      # do work with foo
    


    1. SystemXFiles
      06.09.2016 06:30
      +1

      Аналогично, логика повествования явно где-то хромает


  1. AxisPod
    06.09.2016 06:08

    А чем лучше на C++ во втором варианте? В будущих проблемах с утечками памяти? Такой вариант разве что с умными указателями имеет смысл, но никак не с обычными.


    1. mmMike
      06.09.2016 06:49
      +6

      На мой взгляд, даже хуже. Хуже для глаз в первую очередь.
      Все же уже есть какие то сложившиеся шаблоны в восприятии исходников.
      Шаблоны, в которых сознательная часть мозга не используется. А новый синтаксис просто срывает это шаблон.
      А в чем преимущество этого варианта написания — лично я не вижу. Экономим перевод строки?


      Так и не понял, почему автору "if" не нравится. Вообще… как концепция.


      1. AxisPod
        06.09.2016 07:17

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


        1. mmMike
          06.09.2016 07:33

          Ну единственное применение для такой конструкции "if", что я вижу — ограничение области видимости переменной (жизни ее на стеке… например).
          Но для демонстрации этого, пример автором выбран не удачный с указателем.


          Хотя, лично мне, как то не лень пару "{}" поставить. Более общее и наглядное и, главное, совместимое по исходникам решение.


          А насчет "for"… До сих пор под некоторое железо (старые модели Verifone PINPAD) приходится пользовать кросс компиляторы где, "i" в выражении "for(int i=..." не является ограниченным в видимости "for".


          Увы… все эти новые фичи языка интересны, но приходится писать так, что бы код был переносим всегда.


  1. hdfan2
    06.09.2016 07:17
    -2

    Удачи в поддержке всего этого. Особенно когда автор уже уволился, а комментариев или нет, или кот наплакал. Всё это выглядит очень красиво и изящно, пока пишешь сам. Но если это не проектик just for fun, приготовься к тому, что какой-то бедолага будет матюкать тебя самым площадным-беспощадным образом, пытаясь выяснить, что за траву ты курил статьи на Хабре ты читал, когда писал это.


    1. saluev
      06.09.2016 08:43
      +9

      Если я напишу генератор этого по БНФ, бедолага станет лучше себя чувствовать?

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


    1. igrishaev
      06.09.2016 09:58
      +5

      Готов поспорить, этот аргумент слышали разработчики Питона, Джанго, Реакта… список можно продолжать.


  1. VioletGiraffe
    06.09.2016 08:14

    Справедливости ради, именно приведенный пример можно написать и на С++03:

    if ((Foo* foo = make_foo()))
    {
    }


    1. barker
      06.09.2016 08:46

      И с одной скобкой можно же? Ну и не только на С++03, оператор присваивания всегда возвращал lvalue.


      1. VioletGiraffe
        06.09.2016 08:51
        +1

        C одной будет предупреждение «присваивание в условии if».


        1. barker
          06.09.2016 09:34

          А, точно.


        1. qw1
          07.09.2016 16:52

          Это странный анализатор, если он не отличает однозначное объявление переменной в

          if (Foo* foo = make_foo())

          и возможность перепутать сравнение с присваиванием в
          if (foo = make_foo())


          1. ZyXI
            08.09.2016 08:11

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


            Хотя я бы ещё предположил, что к тому времени, как такое присваивание дойдёт до анализатора, информации о том, что там есть и объявление переменной у него уже не будет.


  1. vitorg
    06.09.2016 08:22

    cycle? chain?


  1. coldwind
    06.09.2016 08:29

    Не пробовали для разбора текста на лексемы использовать *flex*?


    1. saluev
      06.09.2016 11:24
      +2

      Я попробовал обойтись без зависимостей.


  1. buriy
    06.09.2016 08:56
    +1

    А, по-моему, с готовым качественным DSL выглядит намного изящнее, чем ваш велосипед (да и пишется быстрее).
    Скажем, github.com/vlasovskikh/funcparserlib:

    def parse(seq):
        'Sequence(Token) -> object'
        ...
        n = lambda s: a(Token('Name', s)) >> tokval
        def make_array(n):
            if n is None:
                return []
            else:
                return [n[0]] + n[1]
        ...
        null = n('null') >> const(None)
        true = n('true') >> const(True)
        false = n('false') >> const(False)
        number = toktype('Number') >> make_number
        string = toktype('String') >> make_string
        value = forward_decl()
        member = string + op_(':') + value >> tuple
        object = (
            op_('{') +
            maybe(member + many(op_(',') + member)) +
            op_('}')
            >> make_object)
        array = (
            op_('[') +
            maybe(value + many(op_(',') + value)) +
            op_(']')
            >> make_array)
        value.define(
              null
            | true
            | false
            | object
            | array
            | number
            | string)
        json_text = object | array
        json_file = json_text + skip(finished)
    
        return json_file.parse(seq)
    


    1. saluev
      06.09.2016 09:08
      +3

      Таки у вас либа. С либами я и не соревнуюсь.


    1. zloddey
      06.09.2016 10:06
      +3

      Не сказал бы, что полный код примера funcparserlib радикально выигрывает в изящности или "понятности с первого взгляда". И по числу строчек примерно соответствует (144 против 130). Так что не стоит спешить обвинять автора в велосипедостроении. То, что он нам представил, — это в первую очередь упражнение, которое небесполезно было бы повторить самому. Это заслуживает и плюса, и благодарности за проделанную работу.


      1. Akon32
        06.09.2016 10:27
        +1

        Имхо, выигрывает. В funcparserlib нет лишних управляющих структур (for/yield), которые есть в коде из статьи. Это значит, что без этих структур можно обойтись, и следовательно они не нужны.
        И что-то мне подсказывает, что по 2 yield'а в каждой функции — не Python-way (это не выглядит просто).


  1. slonopotamus
    06.09.2016 10:14
    +1

    1. В C++ давным давно можно делать так:

    if (Foo* foo = make_foo())
    {
    // do something with foo, it is != nullptr
    }
    // no foo here


    2. Рекурсия в parse_comma_separated_values — это провал. «Извините, ваш список слишком длинный, у меня стэк кончился».

    3. Ну и сколько гбайт/с пережевывает этот парсер? Ну хотя бы сотен мегабайт/с?

    4. Где изящество-то?


    1. saluev
      06.09.2016 11:19
      +1

      1. Пример поправил.
      2. Да, действительно, на очень больших списках будет так себе. Но можно переписать без рекурсии:

      def parse_comma_separated_values(src):
          result = []
          for value, src in parse_value(src): # достаем первый элемент (mommy says I'm special)
              result.append(value)
              break
          else:
              return #  ни одного элемента не получается достать, ну упс
          while src:
              for (_, value), src in sequence(parse_comma, parse_value):
                  result.append(value)
                  break
              else:
                  break # все сломалось, возвращаем сколько нашли
          yield result, src
      

      А это уже можно завернуть в ещё одну отдельную функцию, чтобы было вообще parse_list(item=parse_value, delimiter=parse_comma). Но в статье я решил сделать упор в сторону лаконичности.
      3. Воу-воу, если бы мне нужно было пережёвывать гигабайты в секунду, я бы спокойно и академично написал на С с lex-yacc.
      4. В заголовке.


      1. slonopotamus
        06.09.2016 11:43
        +1

        3. Ну и тогда возникает вопрос (без троллинга): зачем вообще учиться писать recursive descent parser'ы? Это примерно как bubble sort — сортирует, конечно, но для решения практических задач так не надо делать НИКОГДА. Ещё и на питоне.


        1. saluev
          06.09.2016 12:21
          +5

          Тут вы не правы. Практическая задача™ не всегда требует парсинга гигабайт в секунду. Иногда, например, бывает нужно в Python-проекте распарсить консольный вывод какой-нибудь медленной программы. Парсер нужен, желательно на Питоне (чтобы не усложнять сборку), скорость не критична, расширяемость желательна. Вот и пример.


  1. Akon32
    06.09.2016 10:16
    +2

    Комбинаторные парсеры (пример выше) выглядят гораздо "изящнее", чем for'ы вместо последовательностей термов. (Если эти for'ы убрать, то и получатся комбинаторные парсеры. А так — "код в стиле барокко").
    Рекурсивный спуск выглядит проще (но объёмнее).
    И ещё есть всякие генераторы парсеров, которые должны работать быстрее.


    Статья хорошо показывает, что парсер с нуля написать несложно, но я бы не рекомендовал использовать конкретно этот подход. Он избыточен и неочевиден.


    И почему Python 2 ?


    1. saluev
      06.09.2016 12:31

      И почему про парсинг?
      И почему на Хабре?
      И почему на русском языке?

      (Я не знаю ответа на ваш вопрос, но чувствую, что он как-то связан с ответами на приведённые вопросы...)


    1. potan
      06.09.2016 13:57

      «for», на сколько я понял, здесь используется как «do» в Haskell. То есть вполне в стиле монадических парсеров.


      1. Akon32
        06.09.2016 17:33

        Да, но do-синтаксис менее многословен и семантически больше подходит.


  1. Shamov
    06.09.2016 11:00

    Я когда-то тоже довольно долго мучился с if'ами при необходимости сматчить строку с одной из нескольких регулярок. Но потом мне всё-таки удалось сконцентрировать волю и сделать тривиальную обёртку вокруг re.

    Обёртка
    class Re(object):
        def __init__(self):
            self.last_match = None
    
        def match(self, pattern, text):
            self.last_match = re.match(pattern, text)
            return self.last_match
    
        def search(self, pattern, text):
            self.last_match = re.search(pattern, text)
            return self.last_match
    
        def group(self, index):
            return self.last_match.group(index)
    


  1. nikitadanilov
    06.09.2016 11:32

    В BNF нужно заменить "," на "','".


    1. saluev
      06.09.2016 11:52

      Действительно, спасибо!


  1. varnav
    06.09.2016 13:39
    -3

    на Python 2


    Меня как из ушата окатили. Так гадко стало. И обидно.


  1. potan
    06.09.2016 14:11
    +1

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


  1. nickolaym
    06.09.2016 14:22
    +1

    Вот явно же здесь монада Maybe проглядывает!
    А генераторы — это способ по-быстрому оформить ленивость.

    Ну и начинать надо было с обёртки над match

    def maybe(x):
      ''' lift optional value (maybe None) to the single-item-list monad '''
      return [v for v in [x] if v is not None]
    
    def maybe_match(expr, g1, g2, src):
      ''' expr - regular expression, g1 - identifier of token group, g2 - identifier of the rest, src - source '''
      return [m.group(g1,g2) for m in maybe(re.match(expr, src)]
    
    . . .
    for token,rest in maybe_match(r'([+\-]?[0-9]+)(.*)', 1,2, src):
       . . .
    


  1. iUser
    07.09.2016 05:19
    +1

    Вопрос, без подковырок: а зачем избавляться от if, если с ними даже написаный на коленке на скорую руку парсер получается короче минимум раза в 2? Не модно? В чём практический смысл?

    например
    def tkn(iv):
    	fv = {'null':None, 'true':True, 'false':False}
    	s = iv.strip()
    	if s in fv.keys():
    		rv = fv[s]
    	else:
    		try:
    			rv = float(s) if ('.' in s) | ('e' in s) | ('E' in s) else int(s)
    		except ValueError:
    			rv = s[1:-1] if (s[0] == s[-1]) and s[0] in "\"'" else s
    	return rv
    
    def arr(iv):
    	rv = []
    	tkn = ""
    	ignore = False
    	if iv[0] == '[' and iv[-1] == ']':
    		for c in iv[1:-1]:
    			if c in "'\"[]{}":
    				ignore = not ignore
    			tkn += '' if c == ',' and not ignore else c
    			if (c == ',') and not ignore:
    				rv.append(parse(tkn))
    				tkn = ""
    		rv.append(parse(tkn))
    	return rv
    
    def split(iv):
    	s = iv.strip()
    	i = s[1:].find(s[0])
    	j = s[i+1:].find(':')
    	return [s[1:i+1], s[i+j+2:]] if i > -1 and j > -1 else []
    
    def dict(iv):
    	rv = {}
    	tkn = ""
    	p = []
    	ignore = False
    	if iv[0] == '{' and iv[-1] == '}':
    		for c in iv[1:-1]:
    			if c in "'\"{}[]":
    				ignore = not ignore
    			tkn += '' if c == ',' and not ignore else c
    			if (c == ',') and not ignore:
    				p = split(tkn)
    				if len(p) > 0:
    					rv[p[0]] = parse(p[1])
    				tkn = ""
    		p = split(tkn)
    		if len(p) > 0:
    			rv[p[0]] = parse(p[1])
    	return rv
    
    def parse(iv):
    	s = iv.strip()
    	return None if len(s) < 1 else arr(s) if s[0] == '[' else ( dict(s) if s[0] == '{' else tkn(s) )
    


    1. saluev
      07.09.2016 08:55

      Вам самому-то ваш код как, нравится? Представьте, что по нему нужно понять, что он парсит. А теперь представьте, что где-то что-то потребовалось поменять.


      1. iUser
        07.09.2016 09:24

        Вы не ответили на вопрос. В чём практический смысл избавления от if?

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