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.
Dr. Yijun Yu is a Senior Lecturer in Computing and Communications at The Open University, UK. He is interested in developing automated, efficient and scalable software techniques and tools to better support human activities in software engineering. He has the vision to improve aviation security through cloud computing and blockchains by live streaming black boxes after the missing MH370 flight, which featured in interviews with BBC Radio 4 and BBC World Services aired in April 2014, and subsequently received a Microsoft Azure Award (2017), an Amazon Cloud Award (2018), and an EU SESAR JU EngageKTN Grant (2019). 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). 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 Principle Investigator, he managed knowledge transfer projects with NATS, Huawei, IBM, CA, RealTelekom, and is a co-investigator on research projects including Adaptive Security and Privacy (ERC Adv. Grant, 2012-2018), and Adaptive Information Systems (QNRF, 2012-2016), Lifelong Security Engineering for Evolving Systems (EU FP7, 2009-2012), and Usable Privacy for Mobile Apps (Microsoft SEIF, 2012).