Алгоритми способу порівняння програм, написаних Lisp-подібними мовами, на основі абстрактних семантичних дерев
Ключові слова:
лісп, s-вираз, абстрактне семантичне дерево, хеш-таблиця, обхід дерева, порівняння дерев
Анотація
У даній статті запропоновано два алгоритми виявлення переміщених фрагментів дерев. Ці алгоритми є частинами реалізації способу порівняння програм, написаних Lisp-подібними мовами, на основі абстрактних семантичних дерев. Перший з алгоритмів для виявлення переміщених фрагментів дерев використовує обхід лісу дерев, а другий алгоритм з цією метою використовує хеш-таблицю. Було проведено порівняння швидкодії запропонованих алгоритмів. Зазначено напрямок подальших досліджень щодо покращення цих алгоритмів.
Посилання
1. “State of Clojure 2022”, Robert Randolph , Clojure, https://clojure.org/news/2022/06/02/state-of-clojure-2022. Accessed 20 Nov. 2022.
2. Yermolenko D., Marchenko O. Algorithms of the technique for comparing programs written in Lisp-like languages based on abstract semantic trees. Applied Mathematics and Computing. AMC, 2022 : fifteen scientific conference of master students and postgraduates, 16–18 листопада 2022 р.: зб.тез доп./[редкол.: Дичка І.А. та ін.]. – К. : Просвіта, 2022. – с. 261-265.
3. “Tree edit distance”, Mateusz Pawlik, http://tree-edit-distance.dbresearch.uni-salzburg.at/. Accessed 21 Nov. 2022
4. “S-expression”, Computer Hope, https://www.computerhope.com/jargon/s/s-expression.htm. Accessed 21 Nov. 2022
5. Hashimoto, Masatomo & Mori, Akira. (2008). Diff/TS: A Tool for Fine-Grained Structural Change Analysis. Proceedings - Working Conference on Reverse Engineering, WCRE. 279 - 288. 10.1109/WCRE.2008.44. https://doi.org/10.1109/WCRE.2008.44. Accessed 21 Nov. 2022
6. F. Magniez and M. de Rougemont. Property testing of regular tree languages. Algorithmica, 49(2):127–146, 2007. https://doi.org/10.1007/s00453-007-9028-3. Accessed 21 Nov. 2022
7. “Hashing tree structure”, Said Sryheni, Baeldung, https://www.baeldung.com/cs/hashing-tree. Accessed 22 Nov. 2022
8. Yermolenko D. V. (2021). Tool for comparing versions of programs in the LISP language using an abstract semantic tree [Diploma project, NTUU KPI]
2. Yermolenko D., Marchenko O. Algorithms of the technique for comparing programs written in Lisp-like languages based on abstract semantic trees. Applied Mathematics and Computing. AMC, 2022 : fifteen scientific conference of master students and postgraduates, 16–18 листопада 2022 р.: зб.тез доп./[редкол.: Дичка І.А. та ін.]. – К. : Просвіта, 2022. – с. 261-265.
3. “Tree edit distance”, Mateusz Pawlik, http://tree-edit-distance.dbresearch.uni-salzburg.at/. Accessed 21 Nov. 2022
4. “S-expression”, Computer Hope, https://www.computerhope.com/jargon/s/s-expression.htm. Accessed 21 Nov. 2022
5. Hashimoto, Masatomo & Mori, Akira. (2008). Diff/TS: A Tool for Fine-Grained Structural Change Analysis. Proceedings - Working Conference on Reverse Engineering, WCRE. 279 - 288. 10.1109/WCRE.2008.44. https://doi.org/10.1109/WCRE.2008.44. Accessed 21 Nov. 2022
6. F. Magniez and M. de Rougemont. Property testing of regular tree languages. Algorithmica, 49(2):127–146, 2007. https://doi.org/10.1007/s00453-007-9028-3. Accessed 21 Nov. 2022
7. “Hashing tree structure”, Said Sryheni, Baeldung, https://www.baeldung.com/cs/hashing-tree. Accessed 22 Nov. 2022
8. Yermolenko D. V. (2021). Tool for comparing versions of programs in the LISP language using an abstract semantic tree [Diploma project, NTUU KPI]
Опубліковано
2022-12-18
Як цитувати
Єрмоленко, Д., & Марченко, О. (2022). Алгоритми способу порівняння програм, написаних Lisp-подібними мовами, на основі абстрактних семантичних дерев. КОМП’ЮТЕРНО-ІНТЕГРОВАНІ ТЕХНОЛОГІЇ: ОСВІТА, НАУКА, ВИРОБНИЦТВО, (49), 29-37. https://doi.org/10.36910/6775-2524-0560-2022-49-05
Розділ
Інформатика та обчислювальна техніка
