Static analysis on abstract syntax trees based on finite automata

V. N. Ignatyev<sup>ab

a</sup> Lomonosov Moscow State University
^b Ivannikov Institute for System Programming of the RAS

Abstract: The paper describes a way of organizing static analysis on abstract syntax trees (AST) widely used for finding coding errors as well as errors that do not require deep understanding of program semantics. For most known types of errors, a formalization is proposed that is based on finite automata over trees (FATs), similar to NFAs and DFAs for regular languages over an alphabet. In contrast to the theory of FATs developed for alphabets with bounded arity, which in practice fixes the number of children for each node type, the case of a finite number of children without a priori bound is considered. Nondeterministic and deterministic FAT are described, their equivalence is shown, the closure of regular languages over trees with respect to union and intersection is shown, and the linear complexity of the FAT tree recognition problem is proven. For the AST analysis algorithms not covered by regular languages over trees, context-free languages are considered.

Keywords: static analysis, abstract syntax tree, finite automata, regular languages

DOI: 10.15514/ISPRAS-2025-37(1)-2