Frequently source code analysis tools need to exchange internal representations of abstract syntax trees (AST) with each other. Conveniently, and intuitively, the externalised representations are just in the form of hierarchical trees. Counter-intuitively, we argue that hierarchical representation is not the most efficient way for source analysis tools to exchange parsed AST. In this work, we propose to speed up AST parsing whilst preserving the equivalence of hierarchies in binary forms: (1) AST could be saved as a flat one-dimensional array where pointers to tree nodes are converted into integer offsets, and (2) such flattened AST are more efficient to access by programming tools through the generated application programming interfaces (API). In programming language-agnostic evaluations, we show some benefits of the new approach. Parsing of flattened AST becomes 100x faster than in textual form AST for a benchmark of 30 open-source projects of 7 different programming languages. With fAST, one can also observe 2.5 times faster program slicing and 35 times faster tree-based differencing.
Yijun Yu is a Professor of Software Engineering at The Open University, UK. His research explores automated techniques for improving the performance of both software engineers and the software artefacts that they produce. He serves as an Associate Editor of the Software Quality Journal, Chair of BCS Specialist Group on Requirements Engineering, a PC member of international conferences on Software Engineering (FSE, ICSE), Requirements Engineering (RE, CAiSE, ER), Software Maintenance and Evolution (ICSME, CSMR, SANER, ICPC), Security (ESSoS), and Internet of Things (WF-IoT). As Principal Investigator, he managed knowledge transfer projects with NATS, Huawei, IBM, CA, RealTelekom. His research on requirements-driven adaptation receives a 10 Year Most Influential Paper award (CASCON’16), 6 Best Paper awards (SEAMS’18, iRENIC’16, TrustCom’14, EICS’13, VMPDP’01), 3 Distinguished Paper awards (RE’11, BCS’08, ASE’07), a Best Tool Demo Paper Award (RE’13) and a Best Student Paper Award (PDCS’02).
