Oberon space
General Category => Общий раздел => Тема начата: ilovb от Август 03, 2012, 12:39:09 pm
-
В 1С есть стандартный сериализатор, который преобразует любой объект в поток символов след. формата:
Весь поток - это список элементов через запятую в фигурных скобках.
например:
{1, 2.2, "Один"}
Элементы могут быть трех типов:
1. Число - как первые два элемента в примере
2. Строка - в кавычках как третий элемент в примере (строка может содержать апострофы и удвоенные кавычки "")
3. UID (например 51e7a0d2-530b-11d4-b98a-008048da3034)
Списки могут быть вложенными.
Например:
{1, 2, {1, 2}, "ООО ""Восход"""}
Примеры сериализации:
Массив = Новый Массив;
Массив.Добавить(1);
Массив.Добавить(2);
Массив.Добавить(3);
Массив.Добавить(4);
сериализуется в:
{"#",51e7a0d2-530b-11d4-b98a-008048da3034,
{4,
{"N",1},
{"N",2},
{"N",3},
{"N",4}
}
}
Структура = Новый Структура("Один, Два, Три, Четыре", 1, 2, 3, 4)
сериализуется в:
{"#",4238019d-7e49-4fc9-91db-b6b951d5cf8e,
{4,
{
{"S","Один"},
{"N",1}
},
{
{"S","Два"},
{"N",2}
},
{
{"S","Три"},
{"N",3}
},
{
{"S","Четыре"},
{"N",4}
}
}
}
Байткод из компилированной обработки с предыдущими примерами:
{1,
{"Cmd",40,0,
{1,1},
{2,0},
{18,0},
{51,0},
{16,0},
{1,3},
{2,0},
{4,2},
{18,1},
{20,1},
{1,3},
{1,4},
{2,0},
{4,3},
{18,1},
{20,1},
{1,4},
{1,5},
{2,0},
{4,4},
{18,1},
{20,1},
{1,5},
{1,6},
{2,0},
{4,5},
{18,1},
{20,1},
{1,6},
{1,8},
{2,1},
{4,6},
{4,2},
{4,3},
{4,4},
{4,5},
{18,5},
{51,7},
{16,0},
{22,0}
},
{"Const",8,
{"S","Массив"},
{"S","Добавить"},
{"N",1},
{"N",2},
{"N",3},
{"N",4},
{"S","Один, Два, Три, Четыре"},
{"S","Структура"}
},
{"Var",2,
{"Массив",0,-1},
{"Структура",0,-1}
}
}
Нужно написать парсер, который поднимет это в дерево. Каждый узел дерева должен знать своего родителя и список детей.
Ради эффективности желательно делать без рекурсии (так интереснее :))
Хотелось бы дейкстру тут увидеть ;)
-
Ради эффективности желательно делать без рекурсии (так интереснее :))
А как связаны эффективность и отсутствие рекурсии? о_О
-
Ради эффективности желательно делать без рекурсии (так интереснее :))
А как связаны эффективность и отсутствие рекурсии? о_О
Не обращай внимания на этих императивщиков, у них понятие рекурсии тесно связано с ростом (использования)стека.
-
Просто не везде есть умные оптимизаторы :)
-
Просто не везде есть умные оптимизаторы :)
Во-первых это не есть умная оптимизация, это тупая оптимизация.
Во-вторых для функциональных языков (например haskell) это не оптимизация, а просто корректная кодогенерация.
-
Пусть тупая. Это не отменяет того факта что в некоторых языках цикл много быстрее аналогичной рекурсивной функции
-
Пусть тупая. Это не отменяет того факта что в некоторых языках цикл много быстрее аналогичной рекурсивной функции
А зачем из за проблем некоторых реализаций некоторых языков в условие задания вводить пункт запрещающий рекурсию? Ведь таким образом ты по факту запрещаешь решать задачу на, например, haskell'e, просто потому, что там нет циклов, а есть только рекурсия.
-
Пусть реализации всякие будут. Просто первая естественная мысль - это применить рекурсию. А хочется еще и циклы увидеть
-
Пусть реализации всякие будут. Просто первая естественная мысль - это применить рекурсию. А хочется еще и циклы увидеть
А может сразу goto (с вычисляемой меткой, для пущего хардкора)? :-D
-
количество уровней фиксировано и каждый уровень отвечает за свою область определений?
-
И желательно привести пример того, что хотим получить в результате.
-
В смысле? Результатом должно быть дерево каждый узел которого знает родителя, список потомков, ну и значение узла естественно
-
Пусть реализации всякие будут. Просто первая естественная мысль - это применить рекурсию. А хочется еще и циклы увидеть
А может сразу goto (с вычисляемой меткой, для пущего хардкора)? :-D
-
Пусть реализации всякие будут. Просто первая естественная мысль - это применить рекурсию. А хочется еще и циклы увидеть
А, что, если "применить" рекурсию, то цикл здесь разве не нужен будет?
И, вообще, что-то не понятно, а в чём проблема.
Парсите поток, выделяя кривые скобки, запятую и всё остальное (элемент) и рулите деревом. И никакой рекурсии.
Про МАМПС с его деревьями я уж и молчать буду. :)
-
http://oberspace.dyndns.org/index.php/topic,300.msg7115.html#msg7115 (http://oberspace.dyndns.org/index.php/topic,300.msg7115.html#msg7115)
:-X
-
http://oberspace.dyndns.org/index.php/topic,300.msg7115.html#msg7115 (http://oberspace.dyndns.org/index.php/topic,300.msg7115.html#msg7115)
:-X
Ну, а что еще на черном море делать кроме написания простеньких парсеров на правильных циклах?
-
Просто конечный автомат, древовидная структура - и указатель на текущее место в ней. Со спуском в созданный элемент и подъёмом вверх при закрывающей скобке.
-
Просто конечный автомат, древовидная структура - и указатель на текущее место в ней. Со спуском в созданный элемент и подъёмом вверх при закрывающей скобке.
В принципе "конечный автомат" можно и убрать (состояний маловато :) ) и останется просто: "Просто древо..."
-
http://oberspace.dyndns.org/index.php/topic,300.msg7115.html#msg7115 (http://oberspace.dyndns.org/index.php/topic,300.msg7115.html#msg7115)
:-X
Ну, а что еще на черном море делать кроме написания простеньких парсеров на правильных циклах?
-
http://oberspace.dyndns.org/index.php/topic,300.msg7115.html#msg7115 (http://oberspace.dyndns.org/index.php/topic,300.msg7115.html#msg7115)
:-X
Ну, а что еще на черном море делать кроме написания простеньких парсеров на правильных циклах?
Я его уж года полтора назад написал. Потратил пару минут на обеденном перерыве. :) Задача элементарная. Потому я и предлагаю всем поделиться своими подходами и инструментами. Судя по предыдущим элементарным задачкам подход и предпочтения у всех сильно разные :)
-
Я его уж года полтора назад написал. Потратил пару минут на обеденном перерыве.
Че то тема интереса не вызвала. Ну да ладно.
Вот откопал мое поделие:
Функция РазобратьТекст(Источник) Экспорт
Дерево = Новый ДеревоЗначений;
Дерево.Колонки.Добавить("Значение");
ТекущаяСтрока = Дерево.Строки.Добавить();
ТекущаяСтрока = ТекущаяСтрока.Строки.Добавить();
ТекущийРодитель = ТекущаяСтрока.Родитель;
ИсходныйТекст = Источник.ПолучитьТекст();
КоличествоСимволов = СтрДлина(ИсходныйТекст);
ТекущийСимвол = "";
Позиция = 0;
Пока ТекущийСимвол <> "{" И Позиция < КоличествоСимволов Цикл
Позиция = Позиция + 1;
ТекущийСимвол = Сред(ИсходныйТекст, Позиция, 1);
КонецЦикла;
Если ТекущийСимвол = "{" Тогда
Буфер = "";
РежимЧтенияСтроки = Ложь;
Пока Позиция < КоличествоСимволов Цикл
Позиция = Позиция + 1;
ТекущийСимвол = Сред(ИсходныйТекст, Позиция, 1);
Если ТекущийСимвол = "{" Тогда
ТекущийРодитель = ТекущаяСтрока;
ТекущаяСтрока = ТекущаяСтрока.Строки.Добавить();
ИначеЕсли ТекущийСимвол = "," Тогда
ТекущаяСтрока.Значение = Буфер;
Буфер = "";
ТекущаяСтрока = ТекущийРодитель.Строки.Добавить();
ИначеЕсли ТекущийСимвол = "}" Тогда
ТекущаяСтрока.Значение = Буфер;
Буфер = "";
ТекущаяСтрока = ТекущийРодитель;
ТекущийРодитель = ТекущаяСтрока.Родитель;
ИначеЕсли ТекущийСимвол = """" Тогда
РежимЧтенияСтроки = НЕ РежимЧтенияСтроки;
Буфер = Буфер + ТекущийСимвол;
ИначеЕсли РежимЧтенияСтроки Тогда
Буфер = Буфер + ТекущийСимвол;
ИначеЕсли НЕ ПустаяСтрока(ТекущийСимвол)
ИЛИ (ТекущийСимвол = " ") Тогда
Буфер = Буфер + ТекущийСимвол;
КонецЕсли;
КонецЦикла;
КонецЕсли;
Возврат Дерево;
КонецФункции
-
Кстати, сейчас только заметил, что у меня в этом коде ошибка есть. Я его писал чтобы быстро разобрать конкретный файлик, и там элементы строкового типа не содержали посторонних символов. Строка по идее не может содержать только одиночный символ кавычки.
Чтобы разрешить в строках символы "{", "}", и "," нужно экранировать их переменной "РежимЧтенияСтроки":
Функция РазобратьТекст(Источник) Экспорт
Дерево = Новый ДеревоЗначений;
Дерево.Колонки.Добавить("Значение");
ТекущаяСтрока = Дерево.Строки.Добавить();
ТекущаяСтрока = ТекущаяСтрока.Строки.Добавить();
ТекущийРодитель = ТекущаяСтрока.Родитель;
ИсходныйТекст = Источник.ПолучитьТекст();
КоличествоСимволов = СтрДлина(ИсходныйТекст);
ТекущийСимвол = "";
Позиция = 0;
Пока ТекущийСимвол <> "{" И Позиция < КоличествоСимволов Цикл
Позиция = Позиция + 1;
ТекущийСимвол = Сред(ИсходныйТекст, Позиция, 1);
КонецЦикла;
Если ТекущийСимвол = "{" Тогда
Буфер = "";
РежимЧтенияСтроки = Ложь;
Пока Позиция < КоличествоСимволов Цикл
Позиция = Позиция + 1;
ТекущийСимвол = Сред(ИсходныйТекст, Позиция, 1);
Если НЕ РежимЧтенияСтроки И ТекущийСимвол = "{" Тогда
ТекущийРодитель = ТекущаяСтрока;
ТекущаяСтрока = ТекущаяСтрока.Строки.Добавить();
ИначеЕсли НЕ РежимЧтенияСтроки И ТекущийСимвол = "," Тогда
ТекущаяСтрока.Значение = Буфер;
Буфер = "";
ТекущаяСтрока = ТекущийРодитель.Строки.Добавить();
ИначеЕсли НЕ РежимЧтенияСтроки И ТекущийСимвол = "}" Тогда
ТекущаяСтрока.Значение = Буфер;
Буфер = "";
ТекущаяСтрока = ТекущийРодитель;
ТекущийРодитель = ТекущаяСтрока.Родитель;
ИначеЕсли ТекущийСимвол = """" Тогда
РежимЧтенияСтроки = НЕ РежимЧтенияСтроки;
Буфер = Буфер + ТекущийСимвол;
ИначеЕсли РежимЧтенияСтроки Тогда
Буфер = Буфер + ТекущийСимвол;
ИначеЕсли НЕ ПустаяСтрока(ТекущийСимвол)
ИЛИ (ТекущийСимвол = " ") Тогда
Буфер = Буфер + ТекущийСимвол;
КонецЕсли;
КонецЦикла;
КонецЕсли;
Возврат Дерево;
КонецФункции