Спосіб порівняння абстрактних семантичних дерев програм, написаних Lisp-подібними мовами
Вантажиться...
Дата
2022
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Актуальність теми. Задача порівняння абстрактних семантичних дерев програм є однією з тих задач, що дозволяє аналізувати зміни на структурному рівні в різних версіях кодової бази програми, виконувати пошук плагіату тощо. Наявні способи використовують різноманітні модифікації алгоритму пошуку TED (tree edit distance), де також додають можливість виявлення переміщених фрагментів програм. Так як пошук переміщених фрагментів у загальному випадку є NP-повною задачею, то наявні способи використовують різноманітні спрощення чи емпіричні підходи, які враховують специфіку саме тих мов програмування, для яких були розроблені. Оскільки популярність використання функціональних мов програмування зростає, то розробка особливого способу порівняння абстрактних семантичних дерев, який враховує особливості Lisp-синтаксису та вміє знаходити переміщені фрагменти, є задачею актуальною.
Об’єктом дослідження є процес порівняння абстрактних семантичних дерев програм написаних Lisp-подібними мовами.
Предметом дослідження є способи порівняння абстрактних семантичних дерев програм написаних Lisp-подібними мовами зі знаходженням переміщених фрагментів.
Мета роботи: Метою дослідження є розробка способу порівняння абстрактних семантичних дерев, з урахуванням особливостей Lisp-синтаксису та його прогамна реалізація.
Наукова новизна:
Вперше запропоновано спосіб порівняння абстрактних семантичних дерев, який полягає в порівнянні абстрактних семантичних дерев (АСТ) програм, написаних на Lisp-подібних мовах, відрізняється від існуючих врахуванням особливостей синтаксису Lisp-подібних мов, виконанням операції хешування АСТ, маркуванням вузлів АСТ всього лише на три види, обмеженням на вибір та форму можливих переміщених фрагментів, встановленням оригінальної пріоритетності фрагментів для пошуку, і дозволяє досягнути порівняння таких дерев з одночасним знаходженням переміщених фрагментів без повного перебору усіх можливих варіацій піддерев.
Практична цінність Запропонований спосіб може бути використаний як основа для створення ефективних за часом роботи засобів, які будуть порівнювати на структурному рівні тексти програм написаних на Lisp-подібних мовах на співпадіння, а також знаходити переміщені фрагменти коду.
Апробація роботи. Основні положення і результати роботи були представлені та обговорювались на XV науковій конференції магістрантів та аспірантів «Прикладна математика та компʼютинг» ПМК-2022 (Київ, 16-18 листопада 2022 р.). Алгоритми способу порівняння програм, написаних Lisp-подібними мовами, на основі абстрактних семантичних дерев опубліковані у науковому фаховому виданні “Комп’ютерно-інтегровані технології: освіта, наука, виробництво” №49, що індексується в міжнародних базах даних Index Copernicus Journal Master List, Open Academic Journals Index, Academic Resource Index ResearchBib, Rootindexing, Information Matrix for the Analysis of Journals.
Структура та обсяг роботи. Магістерська дисертація складається з вступу, чотирьох розділів та висновків.
У вступі подано загальну характеристику роботи, зроблено оцінку сучасного стану проблеми, обґрунтовано актуальність напрямку досліджень, сформульовано мету і задачі досліджень, показано наукову новизну отриманих результатів і практичну цінність роботи.
У першому розділі розглянуто наявні способи порівняння абстрактних семантичних дерев, розглянуто проблему виявлення переміщених фрагментів.
У другому розділі виділена особливість синтаксису Lisp-подібних мов й на основі цього було запропоновано спосіб порівняння програм, написаних Lisp-подібними мовами.
У третьому розділі наведено особливості реалізації засобу, який реалізовує алгоритми, які створені на основі запропонованого способу.
У четвертому розділ представлено підхід до генерації тестових вхідних файлів та описано процес та представлено результати порівняння алгоритмів створених на основі представленого способу.
У висновках представлені результати проведеної роботи.
Робота представлена на 80 аркушах, містить 3 додатки та містить посилання на список використаних літературних джерел.
Опис
Ключові слова
Lisp, абстрактне семантичне дерево, abstract semantic tree, tree structure hashing
Бібліографічний опис
Єрмоленко, Д. В. Спосіб порівняння абстрактних семантичних дерев програм, написаних Lisp-подібними мовами : магістерська дис. : 123 Комп'ютерна інженерія / Єрмоленко Денис Вадимович. – Київ, 2022. – 89 с.