Abstract syntax tree: Difference between revisions

Revision as of 06:49, 3 April 2024

Latest revision as of 17:04, 9 August 2025

(10 intermediate revisions by 9 users not shown)

Line 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 context-dependent.

=== Design ===

Line 48:

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>

type "Program"

start 0

end 831

body

0

type "ExpressionStatement"

start 0

end 140

expression

type "CallExpression"

start 0

end 139

callee

type "ArrowFunctionExpression"

start 2

end 135

id null

expression false

generator false

async false

params []

body

type "BlockStatement"

start 8

end 135

body

0

type "VariableDeclaration"

start 14

end 64

declarations […]

kind "let"

1

type "ExpressionStatement"

start 69

end 114

expression {…}

2

type "ExpressionStatement"

start 119

end 133

expression {…}

arguments []

optional false

1

type "FunctionDeclaration"

start 143

end 203

id

type "Identifier"

start 152

end 156

name "l33t"

expression false

generator false

async false

params []

body

type "BlockStatement"

start 159

end 203

body

0

type "ExpressionStatement"

start 165

end 201

expression

type "CallExpression"

start 165

end 201

callee

type "MemberExpression"

start 165

end 176

object {…}

property {…}

computed false

optional false

arguments

0 {…}

optional false

2

type "FunctionDeclaration"

start 208

end 783

id

type "Identifier"

start 217

end 227

name "gen_sensor"

expression false

generator false

async false

params []

body

type "BlockStatement"

start 230

end 783

body

0

type "VariableDeclaration"

start 236

end 271

declarations

0

type "VariableDeclarator"

start 240

end 271

id {…}

init {…}

kind "let"

1

type "IfStatement"

start 276

end 325

test

type "BinaryExpression"

start 280

end 298

left

type "AssignmentExpression"

start 281

end 291

operator ">>="

left {…}

right {…}

operator "=="

right

type "Literal"

start 296

end 298

value 20

raw "20"

consequent

type "BlockStatement"

start 300

end 325

body

0 {…}

alternate null

2

type "VariableDeclaration"

start 331

end 761

declarations

0

type "VariableDeclarator"

start 335

end 761

id {…}

init {…}

kind "let"

3

type "ReturnStatement"

start 767

end 780

argument

type "Identifier"

start 774

end 780

name "sensor"

3

type "VariableDeclaration"

start 784

end 809

declarations

0

type "VariableDeclarator"

start 788

end 809

id

type "Identifier"

start 788

end 794

name "sensor"

init

type "CallExpression"

start 797

end 809

callee

type "Identifier"

start 797

end 807

name "gen_sensor"

arguments []

optional false

kind "let"

4

type "ExpressionStatement"

start 811

end 830

expression

type "CallExpression"

start 811

end 830

callee

type "MemberExpression"

start 811

end 822

object

type "Identifier"

start 811

end 818

name "console"

property

type "Identifier"

start 819

end 822

name "log"

computed false

optional false

arguments

0

type "Identifier"

start 823

end 829

name "sensor"

optional false

5

type "jaajajajajajajajajajajajaj"

sourceType "module"

== See also ==

Line 290 ⟶ 71:

* [[Symbol table]]

* [[TreeDL]]

* [[Interpreter (computing)#Abstract Syntaxsyntax Treetree interpreters|Abstract Syntax Tree Interpreters]]

== References ==

Line 296 ⟶ 77:

== Further reading ==

* {{cite web |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 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}}

Line 306 ⟶ 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.