Виртуальная машина для работы с деревьями 3м Автор: Ханов А.Р. Научный руководитель: Зеленчук И.В

Написать виртуальную машину для работы с корневыми атрибутными деревьями 1) Работа с деревьями потенциально огромных размеров. 2)Наличие системы настроек, позволяющей управлять работой машины 3)Наличие интерпретатора байт-кода ассемблера машины, реализующего простейшие операции над деревьями. Постановка задачи атрибут Корень Текст программы Байт-код машины Интерпретатор байт-кода

Устройство памяти Адресное пространство машины Файл памяти Окно доступа к памяти Загруженный участок памяти машины FileMapping

Устройство памяти Заголовок памяти Название поляразмер Версия1 байт Длина указателя(lol)1 байт Количество параграфов памяти по 256 б Lol байт Адрес первого сегментаLol байт Ссылка на первый свободный 1 категории Lol байт … Ссылка на первый свободный freec категории Lol байт Сегмент ЗаголовокФлаг занят /свободен 1 байт Размер сегментаLol байт Размер предыдущего сегмента Lol байт ДанныеСсылка на следующий свободный или ноль Lol байт Ссылка на следующий свободный или ноль Lol байт

Деревья Контейнер с узлами Занятые ячейки Заголовок Ячейки, входящие в свободные фрагменты Ссылки Узел Флаг занятости Номер родителя Дополнитель ные поля Атрибут

Атрибуты 1) Внутренний (в структуре самого узла) 2) Внешний (в другом сегменте) Первый сегмент дерева Сегмент атрибутов Сегмент дерева Сегмент атрибутов Заголовок Занятые ячейки атрибутов Свободные ячейки атрибутов Ссылки Ссылки в сегменте атрибутов

Байт-код Команды: 1)Управление регистрами машины 2)Управление деревьями 3)Управление атрибутами 4)Управление потоком исполнения 5)Команды для отладки и тестов

Применение 1)Иерархическая БД 2)Хранение и обработка данных (XML) 3)Программы, использующие огромные деревья – контекстные модели, BSP-дерево, дерево разбора …