Для студентов СПбГУ по предмету ДругиеРеализация и экспериментальное исследование GLL-парсера, основанного на рекурсивном автоматеРеализация и экспериментальное исследование GLL-парсера, основанного на рекурсивном автомате
2024-08-062024-08-06СтудИзба
Курсовая работа: Реализация и экспериментальное исследование GLL-парсера, основанного на рекурсивном автомате
Описание
Оглавление
3
Введение
Представление данных в виде помеченных графов находит широкое применение во многих научных областях [17], таких как анализ соци-альных сетей [2], биоинформатика[16], статический анализ кода [7] и т.д. Одним из основных преимуществ данной модели над реляционной моделью является более быстрое получение информации об отношени-ях между объектами, ведь взаимосвязи между узлами не вычисляются во время выполнения запроса, а хранятся в самой модели.
При работе с такими данными зачастую возникают запросы нави-гации и поиска путей между вершинами. Одним из способов выраже-ния такого рода запросов является определение формальных грамма-тик над алфавитом меток ребер графа [3]. Путь в графе удолетворя-ет ограничениям, задаваемым данной формальной
| Введение | 4 | ||
| 1. | Постановка задачи | 7 | |
| 2. | Обзор | 8 | |
| 2.1. | Базовые определения из теории формальных языков . . | 8 | |
| 2.2. | Базовые определения из теории графов . . . . . . . . . . | 11 | |
| 2.3. | Задачи поиска путей с контекстно-свободными ограниче- | ||
| ниями.............................. | 12 | ||
| 2.4. | ОбобщенныйLLалгоритм . . . . . . . . . . . . . . . . . . | 12 | |
| 2.5. | Алгоритм выполнения контекстно-свободных запросов, ба- | ||
| зирующийсянаGLL ..................... | 14 | ||
| 3. Реализация алгоритма | 16 | |
| 3.1. | Мотивация........................... | 16 |
| 3.2. | Особенностиреализации . . . . . . . . . . . . . . . . . . . | 17 |
| 3.3. | Архитектура.......................... | 18 |
| 4. Экспериментальное исследование | 21 | |
| 4.1. | Оборудование ......................... | 21 |
| 4.2. | Эспериментальные данные . . . . . . . . . . . . . . . . . . | 21 |
| 4.3. | Постановка экспериментов . . . . . . . . . . . . . . . . . . | 27 |
| 4.4. | Результаты экспериментов . . . . . . . . . . . . . . . . . . | 28 |
| Заключение | 36 | |
| Список литературы | 37 | |
3
Введение
Представление данных в виде помеченных графов находит широкое применение во многих научных областях [17], таких как анализ соци-альных сетей [2], биоинформатика[16], статический анализ кода [7] и т.д. Одним из основных преимуществ данной модели над реляционной моделью является более быстрое получение информации об отношени-ях между объектами, ведь взаимосвязи между узлами не вычисляются во время выполнения запроса, а хранятся в самой модели.
При работе с такими данными зачастую возникают запросы нави-гации и поиска путей между вершинами. Одним из способов выраже-ния такого рода запросов является определение формальных грамма-тик над алфавитом меток ребер графа [3]. Путь в графе удолетворя-ет ограничениям, задаваемым данной формальной
Характеристики курсовой работы
СПбГУСписок файлов
Реализация и экспериментальное исследование GLL-парсера, основанного на рекурсивном автомате.doc
Tortuga
06 августа 2024 в 04:46
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
