An abstract syntax tree for the following code for the Euclidean algorithm:

while b ≠ 0

if a > b

a := a − b

else

b := b − a

return a

In computer science, an abstract syntax tree (AST), or just syntax tree, is a tree representation of the abstract syntactic structure of source code written in a programming language. Each node of the tree denotes a construct occurring in the source code. The syntax is 'abstract' in the sense that it does not represent every detail that appears in the real syntax. For instance, grouping parentheses are implicit in the tree structure, and a syntactic construct such as an if-condition-then expression may be denoted by a single node with two branches.

This makes abstract syntax trees different from concrete syntax trees, traditionally called parse trees, which are often built by a parser as part of the source code translation and compiling process. Once built, additional information is added to the AST by subsequent processing, e.g., contextual analysis.

Abstract syntax trees are also used in program analysis and program transformation systems.

See also

• Abstract semantic graph (ASG)
• Composite pattern
• Document Object Model (DOM)
• Extended Backus–Naur Form
• Lisp, a family of languages written in trees, with macros to manipulate code trees at compile time
• Semantic resolution tree (RST)
• Shunting yard algorithm
• Symbol table
• TreeDL

References

• This article is based on material taken from the Free On-line Dictionary of Computing prior to 1 November 2008 and incorporated under the "relicensing" terms of the GFDL, version 1.3 or later.

External links

• AST View: an Eclipse plugin to visualize a Java abstract syntax tree
• Good information about the Eclipse AST and Java Code Manipulation
• PMD on SourceForge.net: uses AST representation to control code source quality
• CAST representation
• eli project: Abstract Syntax Tree Unparsing

Papers

• Jones, Joel. Abstract Syntax Tree Implementation Idioms. http://www.hillside.net/plop/plop2003/Papers/Jones-ImplementingASTs.pdf.  (overview of AST implementation in various language families)
• Howarth, Nicola. Abstract Syntax Tree Design. http://www.ansa.co.uk/ANSATech/95/Primary/155101.pdf.  (note that this merely presents the design of one particular project's AST, and is not generally informative)
• Neamtiu, Iulian; Foster, Jeffrey S.; Hicks, Michael. Understanding source code evolution using abstract syntax tree matching. CiteSeerX: 10.1.1.88.5815. 
• Baxter, Ira D.; et al.. Clone Detection Using Abstract Syntax Trees. http://www.semanticdesigns.com/Company/Publications/ICSM98.pdf. 
• Fluri, Beat; Würsch, Michael; Pinzger, Martin; Gall, Harald C.. Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction. http://seal.ifi.uzh.ch/fileadmin/User_Filemount/Publications/fluri-changedistilling.pdf. 
• Würsch, Michael. Improving Abstract Syntax Tree based Source Code Change Detection (Diploma thesis). http://seal.ifi.unizh.ch/137/. 
• Lucas, Jason. "Thoughts on the Visual C++ Abstract Syntax Tree (AST)". http://blogs.msdn.com/vcblog/archive/2006/08/16/702823.aspx. 

Tutorial

• "Abstract Syntax Tree Metamodel Standard". http://www.omg.org/news/meetings/workshops/ADM_2005_Proceedings_FINAL/T-3_Newcomb.pdf.