The Open UniversitySkip to content

fAST: Flattening Abstract Syntax Trees for Efficiency

Yu, Yijun (2019). fAST: Flattening Abstract Syntax Trees for Efficiency. In: 41st ACM/IEEE International Conference on Software Engineering, 25-31 May 2019, Montreal, Canada, ACM and IEEE.

Full text available as:
PDF (Version of Record) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (107kB) | Preview
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


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 in the form of hierarchical trees. We argue, counter-intuitively, 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 that parsing flattened AST becomes 100x faster than in textual form AST on a benchmark of open-source projects of 6 different programming languages.

Item Type: Conference or Workshop Item
Copyright Holders: 2019 ACM
Project Funding Details:
Funded Project NameProject IDFunding Body
Adaptive Security And Privacy (XC-11-004-BN)291652EC (European Commission): FP (inc.Horizon2020 & ERC schemes)
SAUSE: Secure, Adaptive, Usable Software EngineeringEP/R013144/1 (previous: EP/R005095/1)EPSRC (Engineering and Physical Sciences Research Council)
Keywords: parser; performance; programming languages; abstract syntax trees
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Computing and Communications
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Related URLs:
Item ID: 59268
Depositing User: Yijun Yu
Date Deposited: 13 Mar 2019 16:30
Last Modified: 20 Sep 2019 11:52
Share this page:


Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU