Рекурсивные строки анализа

Question

Есть ли способ рекурсивного анализа строки, чтобы получить строку dict?

:

string = 'a {\
    b: text;\
    c {\
        d: text;\
    }\
}';

out:

{
    'a' : {
        'b': 'text',
        'c': {
            'd' : 'text';
        }
    }
}

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

Answer 1

Вы должны взглянуть на модуль pyparsing .

Модуль pyparsing - это альтернативный подход к созданию и выполнению простых грамматик по сравнению с традиционным подходом lex / yaccили использование регулярных выражений.Модуль pyparsing предоставляет библиотеку классов, которые клиентский код использует для построения грамматики непосредственно в коде Python.

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

Обновление (за комментарий): Если кто-то заинтересовался изучением теоретической основы , стоящей за подобными строками, то вынужно понять, какова ваша цель.Эта проблема, в более общем виде, заключается в синтаксическом анализе языка без контекста .У вас есть набор правил, известный как грамматика , который определяет иерархию структуры данных из входных данных.Хорошее место для начала чтения (с образовательной точки зрения) - форма Бэкуса-Наура .

Answer 2

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

Answer 3

Использование lepl библиотеки синтаксического анализатора:

#!/usr/bin/env python
from lepl import AnyBut, Delayed, Drop, DroppedSpace

def Parser():
    dict_ = Delayed()
    str_ = AnyBut('{}:;')[1::'n',...]

    with DroppedSpace():
        pair = str_ & Drop(':') & str_ & Drop(';') > tuple
        value = str_ & dict_ > tuple
        dict_ += Drop('{') & (pair | value)[:] & Drop('}') > dict
        return value > dict

print(Parser().parse("a {  b: text;  c { d: text; }}")[0])

выход

{'a': {'c': {'d': 'text'}, 'b': 'text'}}

См. Также Инструменты разбора Python .

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