Algorithms of the technique for comparing programs written in Lisp-like languages based on abstract semantic trees
Keywords:
lisp, s-expression, abstract semantic tree, hash table, tree traversing, tree comparing
Abstract
This article proposes two algorithms for detecting moved tree fragments. These algorithms are part of implementation of the technique for comparing programs written in Lisp-like languages based on abstract semantic trees. The first of the algorithms for detecting moved tree fragments uses traversal of the forest of trees, and the second algorithm uses a hash table. Speed of the proposed algorithms was compared. A way for further research on improving these algorithms is offered as well.
References
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]
Abstract views: 116 PDF Downloads: 107
Published
2022-12-18
How to Cite
Yermolenko , D., & Marchenko О. (2022). Algorithms of the technique for comparing programs written in Lisp-like languages based on abstract semantic trees. COMPUTER-INTEGRATED TECHNOLOGIES: EDUCATION, SCIENCE, PRODUCTION, (49), 29-37. https://doi.org/10.36910/6775-2524-0560-2022-49-05
Section
Computer science and computer engineering
