Abstract syntax tree

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

: while b != 0: if a > b: a := a - b else: b := b - a return a An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the 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 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. This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated parse trees. Parse trees are typically built by a parser during the source code translation and compiling process. Once built, additional information is added to the AST by means of subsequent processing, e.g., contextual analysis. Abstract syntax trees are also used in program analysis and program transformation systems.

: while b != 0: if a > b: a := a - b else: b := b - a return a An abstract syntax tree (AST) is a data structure used in computer science to represent the structure of a program or code snippet. It is a tree representation of the 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 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. This distinguishes abstract syntax trees from concrete syntax trees, traditionally designated parse trees. Parse trees are typically built by a parser during the source code translation and compiling process. Once built, additional information is added to the AST by means of subsequent processing, e.g., contextual analysis. Abstract syntax trees are also used in program analysis and program transformation systems. Let S be a set of sorts, an arity is a tuple (s_1,\dots,s_n,s) , for s_1,\dots,s_n,s\in S , also written as (s_1,\dots,s_n)s . More precisely, \mathrm{Arity}(S) := \coprod_{n \in \mathbb{N}} S^{n + 1} . Let \mathcal{O} = \{ \mathcal{O_\alpha} \}_{\alpha \in \mathrm{Arity}(S)} be an \mathrm{Arity}(S) -indexed family of disjoint sets of operators. If o is an operator arity (s_1,\dots,s_n)s we say that o has sort s and has n arguments of sorts s_1,\dots,s_n . Fix S be a finite set of sorts, and \mathcal{O} an \mathrm{Arity}(S) -indexed family of disjoint sets of operators. Let \mathcal{X} = \{ \mathcal{X}_s \}_{s \in S} be an S -indexed family of disjoint sets of variables. The family \mathcal{A}[\mathcal{X}] = \{ \mathcal{A}[\mathcal{X}]_s \}_{s\in S} of abstract syntax trees, or ASTs, is the smallest S -indexed family of disjoint sets closed under the following conditions: Variables are ASTs: if x \in \mathcal{X}_s , then x \in \mathcal{A}[\mathcal{X}]_s . Operators combine ASTs: If o is an operator of arity (s_1,\dots,s_n)s , and a_i\in \mathcal{A}[\mathcal{X}]_{s_i} for all 1 \leq i \leq n , then o(a_1;\dots;a_n) \in \mathcal{A}[\mathcal{X}]_s .

External links

AST View: an Eclipse plugin to visualize a Java abstract syntax tree eli project: Abstract Syntax Tree Unparsing (OMG standard). 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. 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. AST Explorer: A website to help visualize ASTs in several popular languages such as Go, Python, Java, and JavaScript.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374803086 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.