Abstract syntax tree: Difference between revisions

Revision as of 19:38, 1 October 2021

Latest revision as of 17:04, 9 August 2025

(39 intermediate revisions by 28 users not shown)

Line 1:

{{Short description|Tree representation of the abstract syntactic structure of source code}}

{{For|the trees used in linguistics|Parseparse tree}}

{{no footnotes|date=February 2013}}

[[File:Abstract syntax tree for Euclidean algorithm.svg|thumb|400px|An abstract syntax tree for the following code for the [[Euclidean algorithm]]:{{pre|1='''while''' b ≠ 0<br>syntaxhighlight '''if''' a > b<br> a :lang= a − b<br"python"> '''else'''<br> b := b − a<br>'''return''' a}}]]

{{Merge from|Abstract syntax|date=September 2021}}

while b ≠ 0:

[[File:Abstract syntax tree for Euclidean algorithm.svg|thumb|400px|An abstract syntax tree for the following code for the [[Euclidean algorithm]]:{{pre|1='''while''' b ≠ 0<br> '''if''' a > b<br> a := a − b<br> '''else'''<br> b := b − a<br>'''return''' a}}]]

if a > b:

In [[computer science]], an '''abstract syntax tree''' ('''AST'''), or just '''syntax tree''', is a [[Tree (data structure)|tree]] representation of the [[abstract syntax|abstract syntactic]] structure of text (often [[source code]]) written in a [[formal language]]. Each node of the tree denotes a construct occurring in the text.

a := a - b

else:

b := b - a

return a

</syntaxhighlight>]]

In [[computer science]], anAn '''abstract syntax tree''' ('''AST'''), is a data structure used in [[computer science]] to represent the structure of a program or justcode '''syntaxsnippet. tree''',It is a [[Tree (data structure)|tree]] representation of the [[abstract syntax|abstract syntactic]] structure of text (often [[source code]]) written in a [[formal language]]. Each node of the tree denotes a construct occurring in the text. It is sometimes called just a '''syntax tree'''.

The syntax is "abstract" in the sense that it does not represent every detail appearing in the real syntax, but rather just the structural or content-related details. For instance, grouping [[Bracket#Parentheses|parentheses]] are implicit in the tree structure, so these do not have to be represented as separate nodes. Likewise, a syntactic construct like an if-condition-then statement may be denoted by means of a single node with three branches.

Line 21 ⟶ 28:

* An AST usually contains extra information about the program, due to the consecutive stages of analysis by the compiler. For example, it may store the position of each element in the source code, allowing the compiler to print useful error messages.

ASTs are needed because of the inherent nature of programming languages and their documentation. Languages are often [[syntactic ambiguity|ambiguous]] by nature. In order to avoid this ambiguity, programming languages are often specified as a [[context-free grammar]] (CFG). However, there are often aspects of programming languages that a CFG can't express, but are part of the language and are documented in its specification. These are details that require a context to determine their validity and behaviour. For example, if a language allows new types to be declared, a CFG cannot predict the names of such types nor the way in which they should be used. Even if a language has a predefined set of types, enforcing proper usage usually requires some context. Another example is [[duck typing]], where the type of an element can change depending on context. [[Operator overloading]] is yet another case where correct usage and final function are determined based on the context. Java provides an excellent example, where the '+' operator is both numerical addition and concatenation of strings-dependent.

Although there are other [[data structure]]s involved in the inner workings of a compiler, the AST performs a unique function. During the first stage, the [[syntax analysis]] stage, a compiler produces a parse tree. This parse tree can be used to perform almost all functions of a compiler by means of syntax-directed translation. Although this method can lead to a more efficient compiler, it goes against the software engineering principles of writing and maintaining programs{{Citation needed|date=April 2015}}. Another advantage that the AST has over a parse tree is the size, particularly the smaller height of the AST and the smaller number of elements.

=== Design ===

Line 40 ⟶ 45:

To support compiler verification it should be possible to unparse an AST into source code form. The source code produced should be sufficiently similar to the original in appearance and identical in execution, upon recompilation.

=== Usage ===

The AST is used intensively during [[Semantic analysis (compilers)|semantic analysis]], where the compiler checks for correct usage of the elements of the program and the language. The compiler also generates [[symbol table]]s based on the AST during semantic analysis. A complete traversal of the tree allows verification of the correctness of the program.

After verifying correctness, the AST serves as the base for code generation. The AST is often used to generate an intermediate representation (IR), sometimes called an [[intermediate language]], for the code generation.

== Other usages ==

=== AST differencing ===

AST differencing, or for short tree differencing, consists of computing the list of differences between two ASTs.<ref>{{Cite journal |last1=Fluri |first1=Beat |last2=Wursch |first2=Michael |last3=PInzger |first3=Martin |last4=Gall |first4=Harald |date=2007 |title=Change Distilling:Tree Differencing for Fine-Grained Source Code Change Extraction |url=http://dx.doi.org/10.1109/tse.2007.70731 |journal=IEEE Transactions on Software Engineering |volume=33 |issue=11 |pages=725–743 |doi=10.1109/tse.2007.70731 |s2cid=13659557 |issn=0098-5589|url-access=subscription }}</ref> This list of differences is typically called an edit script. The edit script directly refers to the AST of the code. For instance, an edit action may result in the addition of a new AST node representing a function.

=== Clone detection ===

An AST is a powerful abstraction to perform code [[clone detection]].<ref>{{Cite book |last1=Koschke |first1=Rainer |last2=Falke |first2=Raimar |last3=Frenzel |first3=Pierre |title=2006 13th Working Conference on Reverse Engineering |chapter=Clone Detection Using Abstract Syntax Suffix Trees |date=2006 |chapter-url=http://dx.doi.org/10.1109/wcre.2006.18 |pages=253–262 |publisher=IEEE |doi=10.1109/wcre.2006.18|isbn=0-7695-2719-1 |s2cid=6985484 }}</ref>

== See also ==

Line 53 ⟶ 64:

* [[Document Object Model]] (DOM)

* [[Expression tree]]

* [[Extended Backus–Naur Formform]]

* [[Lisp (programming language)|Lisp]], a family of languages written in trees, with macros to manipulate code trees

* [[Parse tree]], also known as ''concrete syntax tree''

* [[Semantic resolution tree]] (SRT)

* [[Shunting -yard algorithm]]

* [[Symbol table]]

* [[TreeDL]]

* [[Interpreter (computing)#Abstract syntax tree interpreters|Abstract Syntax Tree Interpreters]]

== References ==

{{Reflist}}

{{refbegin}}

* {{FOLDOC}}

{{refend}}

== Further reading ==

* {{cite documentweb |last=Jones |first=Joel |title=Abstract Syntax Tree Implementation Idioms |url=http://www.hillside.net/plop/plop2003/Papers/Jones-ImplementingASTs.pdf |url-status=dead |archive-url=https://web.archive.org/web/20240721094334/http://hillside.net/plop/plop2003/Papers/Jones-ImplementingASTs.pdf |archive-date=21 July 2024 |access-date=9 November 2011 }} (overview of AST implementation in various language families)

* {{cite conference |last1=Neamtiu |first1=Iulian |last2=Foster |first2=Jeffrey S. |last3=Hicks |first3=Michael |date=May 17, 2005 |title=Understanding Source Code Evolution Using Abstract Syntax Tree Matching |conference=MSR'05 |___location=Saint Louis, Missouri |publisher=ACM |citeseerx=10.1.1.88.5815}}

* {{cite conference |last1=Baxter |first1=Ira D. |last2=Yahin |first2=Andrew |last3=Moura |first3=Leonardo |last4=Sant' Anna |first4=Marcelo |last5=Bier |first5=Lorraine |date=November 16–19, 1998 |title=Clone Detection Using Abstract Syntax Trees |work=Proceedings of ICSM'98 |___location=Bethesda, Maryland |publisher=[[IEEE]] |url=http://www.semanticdesigns.com/Company/Publications/ICSM98.pdf }}

* {{cite document |last1=Fluri |first1=Beat |last2=Würsch |first2=Michael |last3=Pinzger |first3=Martin |last4=Gall |first4=Harald C. |title=Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction |url=http://www.merlin.uzh.ch/publication/show/2531 |format=PDF}} ([http://www.merlin.uzh.ch/contributionDocument/download/2162 direct link to PDF])

* {{cite thesis |last=Würsch |first=Michael |degree=Diploma |title=Improving Abstract Syntax Tree based Source Code Change Detection |url=http://www.ifi.uzh.ch/seal/research/tools/archive/changeDetection.html}}

* {{cite web |last=Lucas |first=Jason |title=Thoughts on the Visual C++ Abstract Syntax Tree (AST) |date=16 August 2006 |url=https://devblogs.microsoft.com/cppblog/thoughts-on-the-visual-c-abstract-syntax-tree-ast/}}

* {{cite conference |work=Proceedings of ASE 2014|last1=Falleri |first1=Jean-Rémy |last2=Morandat |first2=Floréal |last3=Blanc |first3=Xavier |last4=Martinez |first4=Matias |last5=Monperrus |first5=Martin |title=Fine-grained and Accurate Source Code Differencing |url=https://hal.archives-ouvertes.fr/hal-01054552/document |format=PDF|doi=10.1145/2642937.2642982}}

* {{cite web |last=Lucas |first=Jason |title=Thoughts on the Visual C++ Abstract Syntax Tree (AST) |url=https://devblogs.microsoft.com/cppblog/thoughts-on-the-visual-c-abstract-syntax-tree-ast/}}

==External links==

Line 81 ⟶ 87:

*{{cite web|url=http://www.eclipse.org/articles/Article-JavaCodeManipulation_AST/index.html|title=Abstract Syntax Tree and Java Code Manipulation in the Eclipse IDE|work=eclipse.org}}

*{{cite web|url=http://www.cs.utah.edu/flux/flick/current/doc/guts/gutsch6.html|title=CAST representation|work=cs.utah.edu}}

*[httphttps://eli-project.sourceforge.net/elionline/idem_3.html eli project]: Abstract Syntax Tree [[Unparsing]]

*{{cite web | url = http://www.omg.org/news/meetings/workshops/ADM_2005_Proceedings_FINAL/T-3_Newcomb.pdf | title = Abstract Syntax Tree Metamodel Standard }}

*{{cite web | url = http://www.omg.org/spec/ASTM/ | title = Architecture‑Driven Modernization — ADM: Abstract Syntax Tree Metamodeling — ASTM }} ([[Object Management Group|OMG]] standard).

*[https://javaparser.org JavaParser]: The JavaParser library provides you with an Abstract Syntax Tree of your Java code. The AST structure then allows you to work with your Java code in an easy programmatic way.

*[https://github.com/INRIA/spoon Spoon]: A library to analyze, transform, rewrite, and transpile Java source code. It parses source files to build a well-designed AST with powerful analysis and transformation API.

*[https://astexplorer.net AST Explorer]: A website to help visualize ASTs in several popular languages such as Go, Python, Java, and JavaScript.

{{Parsers}}