|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Об одном алгоритме разбора слов в контекстно-свободных грамматикахкурсовая работа (Специалист)
- Научный руководитель: Боков Г.В.
- Автор: Валиева Руфина Рафаэлевна
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Кафедра математической теории интеллектуальных систем
- Год защиты: 2022
- Курс: 5
- Аннотация: В курсовой работе разбирается новый оригинальный алгоритм синтаксического разбора контекстно-свободных языков. Предложенный автором алгоритм сводит разбор слова к последовательному однопроходному чтению букв входного слова и обновлению внутренних структур данных. Сложность алгоритма на каждом шаге без учета коррекции внутренних структур данных линейна от числа прочитанных букв. Коррекция внутренних структур данных сведена автором к объединению конечных множеств и составляет на данный момент узкое звено алгоритма, не позволяющее в общем случае оценить сложность алгоритма лучше, чем по порядку куб от длины входного слова. К достоинствам алгоритма стоит отнести возможность последовательного разбора всех префиксов входного слова в процессе его чтения.
- Добавил в систему: Боков Григорий Владимирович