Организация статического анализа на абстрактных синтаксических деревьях с помощью конечных автоматов
https://doi.org/10.15514/ISPRAS-2025-37(1)-2
Аннотация
В статье описывается способ организации статического анализа на абстрактных синтаксических деревьях (АСД), повсеместно используемого для поиска ошибок кодирования и других, не требующих глубокого анализа семантики программы. Для большинства известных типов ошибок предложена формализация, основанная на конечных автоматах над деревьями (КАД), аналогичных НКА и ДКА для регулярных языков над символьным алфавитом. В отличие от теории КАД, разработанной для алфавитов с ограниченной арностью, что на практике фиксирует количество потомков для каждого типа вершины, рассмотрен случай конечного числа потомков без заранее заданного ограничения. Описаны недетерминированные и детерминированные КАД, показана их эквивалентность, замкнутость регулярных языков над деревьями относительно объединения и пересечения, доказана линейная сложность задачи распознавания дерева КАД. Для тех алгоритмов анализа АСД, что не покрываются регулярными языками над деревьями, рассмотрены классы контекстно-свободных языков.
Об авторе
Валерий Николаевич ИГНАТЬЕВ
Институт системного программирования им. Иванникова РАН, Московский государственный университет имени М.В. Ломоносова,
Россия
Россия
Кандидат физико-математических наук, старший научный сотрудник ИСП РАН, доцент кафедры системного программирования факультета ВМК МГУ. Научные интересы включают методы поиска ошибок в исходных текстах программ на основе статического анализа.
Список литературы
1. Marpons, G., Mariño, J., Carro, M., Herranz, Á., Moreno-Navarro, J.J., Fredlund, LÅ. (2007). Automatic Coding Rule Conformance Checking Using Logic Programming. In: Hudak, P., Warren, D.S. (eds) Practical Aspects of Declarative Languages. PADL 2008. Lecture Notes in Computer Science, vol 4902. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77442-6_3.
2. С.В. Сыромятников. Декларативный интерфейс поиска дефектов по синтаксическим деревьям: язык KAST. Труды Института системного программирования РАН, т. 20, 2011, с. 51-68.
3. Tomoko Matsumura, Akito Monden, and Ken-ichi Matsumoto. 2002. A method for detecting faulty code violating implicit coding rules. In Proceedings of the International Workshop on Principles of Software Evolution (IWPSE '02). Association for Computing Machinery, New York, NY, USA, 15–21. https://doi.org/10.1145/512035.512040.
4. Stan Jarzabek. – «Design of flexible static program analyzers with PQL». – В: IEEE Transactions on software engineering 24.3 (1998), pp. 197– 215.
5. А. А. Белеванцев. Многоуровневый статический анализ исходного кода программ для обеспечения качества программ. Программирование, 2017, т. 43, № 6, с. 3-26.
6. V.K. Koshelev, V.N. Ignatiev, A.I. Borzilov и A.A. Belevantsev. – «SharpChecker: Static analysis tool for C# programs». – В: Programming and Computer Software 43 (2017), pp. 268– 276.
7. Comon H. et al. Tree automata techniques and applications. – 2008.
8. Gécseg, Ferenc, and Magnus Steinby. «Tree automata» --- 1984, 2015.
9. Neven F., Schwentick T. Query automata over finite trees //Theoretical Computer Science. – 2002. – Т. 275. – №. 1-2. – pp. 633-674.
10. M. Murata, D. Lee, M. Mani, and K. Kawaguchi. Taxonomy of XML schema languages using formal language theory. ACM Transactions on Internet Technology, 5(4):660–704, 2005.
11. G Shobha et al. – «Code clone detection– a systematic review». – В: Emerging Technologies in Data Mining and Information Security: Proceedings of IEMIS 2020, Volume 2 (2021), pp. 645– 655.
12. D.A. Koryabkin, and V.N. Ignatyev. – «Automatic Mining of Code Fix Patterns from Code Repositories». – В: 2022 Ivannikov Memorial Workshop (IVMEM). – IEEE. 2022, – pp. 27– 34.
13. U.V. Tsiazhkorob и V.N. Ignatyev. – «Classification of Static Analyzer Warnings using Machine Learning Methods». – В: 2024 Ivannikov Memorial Workshop (IVMEM). – IEEE. 2024, – pp. 69– 74.
14. N.V. Shimchik, V.N. Ignatyev, and A.A. Belevantsev. – «Improving accuracy and completeness of source code static taint analysis». – В: 2021 Ivannikov ISPRAS OPEN Conference (ISPRAS). – IEEE. 2021, – pp. 61– 68.
Рецензия
Для цитирования:
ИГНАТЬЕВ В.Н. Организация статического анализа на абстрактных синтаксических деревьях с помощью конечных автоматов. Труды Института системного программирования РАН. 2025;37(1):41-54. https://doi.org/10.15514/ISPRAS-2025-37(1)-2
For citation:
IGNATYEV V.N. Static Analysis on Abstract Syntax Trees Based on Finite Automata. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2025;37(1):41-54. (In Russ.) https://doi.org/10.15514/ISPRAS-2025-37(1)-2
Послать статью по эл. почте 