<p>Compiling and interpreting programming languages typically involves parsing text into a tree that represents the different groupings of syntactic elements. The hierarchy represents which syntactic elements a program has but in data structure form instead of string form. A very basic example would be <code>2*(3+4)</code> being parsed into a tree of:</p>
<pre><code>  *
 / \
2   +
   / \
  3   4
</code></pre>
<p>A tree for a real programming language would include keywords and blocks and declarations in addition to parenthesized expressions with mathematical operators.
Both seem to involve a tree data-structural representation of a program.</p>
<p>How exactly are they different in terms of behavior and implementation?</p>

<parsing><abstract-syntax-tree><parse-tree>
What is the difference between an Abstract Syntax Tree and a Parse Tree?
CC BY-SA 4.0
2023-05-17T17:14:09.903Z
In your example of `2*(3+4)`, the parse tree would include the fact that the original string had parentheses in it, while the AST wouldn't.
user
<p>The difference is abstraction. Parse trees are typically much harder to work with and manipulate than abstract syntax trees (ASTs); for this reason, most programming languages first build a parse tree, then convert it to an AST. Parse trees are a direct tree representation of the source code, including all the keywords, structures, variables, literals, etc.</p>
<p>ASTs are a more abstract entity. They are typically formed after the desugaring step (where syntax sugar is converted into the full form), and often strip out the unnecessary parts of the syntax. ASTs can represent much more abstract operations than a parse tree, and can be a considered a type of intermediate representation, depending on how abstract it is.</p>

CC BY-SA 4.0
2023-05-17T17:19:47.200Z
2023-05-17T17:54:26.123Z
2023-05-17T17:54:26.123Z
Seggan
<h2>Parse Tree (Concrete Syntax Tree)</h2>
<p>A Parse Tree is a hierarchical representation of the syntactic structure of a program according to the rules of a formal grammar. It captures the complete structure of the input code, including all the syntactic details, such as parentheses, semicolons, and other language-specific constructs. Each node in the tree corresponds to a specific grammar rule or terminal symbol in the input code. Parse trees are often generated by a parser during the initial phase of compilation.</p>
<p><strong>Advantages of Parse Trees:</strong></p>
<ul>
<li>Preserve all syntactic details: Parse trees retain all the syntactic elements of the input code, making them useful for certain analysis tasks, such as source code transformations or code generation.</li>
<li>Direct mapping to grammar rules: Each node in the parse tree corresponds to a specific production rule in the grammar, facilitating a one-to-one mapping between the code and its syntactic representation.</li>
</ul>
<p><strong>Disadvantages of Parse Trees:</strong></p>
<ul>
<li>Redundant information: Parse trees can contain a lot of redundant information due to their detailed representation of the syntax, making them larger and potentially more complex than necessary.</li>
<li>Not optimized for analysis: The parse tree may not be the most efficient representation for performing certain analysis tasks, as it retains information that is not always relevant for these tasks.</li>
</ul>
<h2>Abstract Syntax Tree (AST)</h2>
<p>An Abstract Syntax Tree is an abstracted representation of the syntactic structure of a program, focusing on the essential elements and their relationships. It captures the underlying structure and semantics of the code, excluding unnecessary syntactic details. ASTs are usually generated from parse trees as a subsequent step in the compilation process, often during the semantic analysis phase.</p>
<p><strong>Advantages of Abstract Syntax Trees:</strong></p>
<ul>
<li>Compact and focused representation: ASTs eliminate redundant details and focus on the essential structure of the program, providing a more concise representation of the code.</li>
<li>Semantically meaningful: ASTs capture the semantic structure of the code, making them well-suited for various analysis tasks, such as type checking, optimization, and interpretation.</li>
<li>Language-independent: ASTs can be designed to represent the essential elements of the code in a language-independent manner, allowing for easier analysis and transformation across different programming languages.</li>
</ul>
<p><strong>Disadvantages of Abstract Syntax Trees:</strong></p>
<ul>
<li>Loss of syntactic details: ASTs abstract away certain syntactic elements, which may be required for certain analysis or transformation tasks that rely on detailed syntax information.</li>
<li>Additional processing required: Generating an AST requires an additional step after parsing, adding some overhead to the compilation process.</li>
</ul>
<h2>Further reading</h2>
<p>For more information, you might want to see <a href="https://stackoverflow.com/a/9864571/18746959">this answer on Stack Overflow</a>.</p>

CC BY-SA 4.0
2023-05-17T17:20:01.057Z
2023-05-17T17:24:44.907Z
2023-05-17T17:24:44.907Z
The Thonnu
CC BY-SA 4.0
2023-05-17T20:55:07.767Z
@user the AST stores the original code information *within* the AST in my programming language, for error reporting purposes
Seggan
CC BY-SA 4.0
2023-05-17T17:20:43.570Z
Note that the [tag:pros-cons] tag was removed apparently while you were writing this.
Seggan
CC BY-SA 4.0
2023-05-17T17:21:13.970Z
@Seggan It still doesn't hurt to include it.
CPlus
CC BY-SA 4.0
2023-05-17T17:21:39.373Z
@Seggan oh, thanks for telling me. I'll keep the advantages/disadvantages in there though, since it's still sort-of relevant.
The Thonnu
CC BY-SA 4.0
2023-05-17T17:22:00.977Z
I think compilers using ASTs do record information about the original code (the exact text as well as line numbers and column numbers), but this information may be stored outside the AST itself and still doesn't really turn it into a parse tree. Still, I feel like the lines can get a little blurred.
user
CC BY-SA 4.0
2023-05-17T17:23:00.993Z
Could you add an example of a parse tree and an AST for the same piece of code, by the way? Just to help out someone who doesn't know what they are at all?
user
CC BY-SA 4.0
2023-05-17T17:23:02.713Z
I suggest not keeping the pros-cons, as it may be slightly confusing; people may think you can use one without the other (you can, but it’s very hard)
Seggan
CC BY-SA 4.0
2023-05-17T17:25:05.523Z
@user I linked in a SO answer with some images. Is that ok?
The Thonnu
# What is the difference between an Abstract Syntax Tree and a Parse Tree?
Posted by: username_0 on 2023-05-17
Compiling and interpreting programming languages typically involves parsing text into a tree that represents the different groupings of syntactic elements. The hierarchy represents which syntactic elements a program has but in data structure form instead of string form. A very basic example would be 2*(3+4) being parsed into a tree of:
  *
 / \
2   +
   / \
  3   4

A tree for a real programming language would include keywords and blocks and declarations in addition to parenthesized expressions with mathematical operators.
Both seem to involve a tree data-structural representation of a program.
How exactly are they different in terms of behavior and implementation?
**Tags:** parsing abstract-syntax-tree parse-tree
> **Comments:**
> **username_1**: In your example of `2*(3+4)`, the parse tree would include the fact that the original string had parentheses in it, while the AST wouldn't.  
---
## 2 answers
### Answer by username_3 on 2023-05-17. Score: 10 | Accepted answer
## Parse Tree (Concrete Syntax Tree)

A Parse Tree is a hierarchical representation of the syntactic structure of a program according to the rules of a formal grammar. It captures the complete structure of the input code, including all the syntactic details, such as parentheses, semicolons, and other language-specific constructs. Each node in the tree corresponds to a specific grammar rule or terminal symbol in the input code. Parse trees are often generated by a parser during the initial phase of compilation.

**Advantages of Parse Trees:**

* Preserve all syntactic details: Parse trees retain all the syntactic elements of the input code, making them useful for certain analysis tasks, such as source code transformations or code generation.
* Direct mapping to grammar rules: Each node in the parse tree corresponds to a specific production rule in the grammar, facilitating a one-to-one mapping between the code and its syntactic representation.

**Disadvantages of Parse Trees:**

* Redundant information: Parse trees can contain a lot of redundant information due to their detailed representation of the syntax, making them larger and potentially more complex than necessary.
* Not optimized for analysis: The parse tree may not be the most efficient representation for performing certain analysis tasks, as it retains information that is not always relevant for these tasks.

## Abstract Syntax Tree (AST)

An Abstract Syntax Tree is an abstracted representation of the syntactic structure of a program, focusing on the essential elements and their relationships. It captures the underlying structure and semantics of the code, excluding unnecessary syntactic details. ASTs are usually generated from parse trees as a subsequent step in the compilation process, often during the semantic analysis phase.

**Advantages of Abstract Syntax Trees:**

* Compact and focused representation: ASTs eliminate redundant details and focus on the essential structure of the program, providing a more concise representation of the code.
* Semantically meaningful: ASTs capture the semantic structure of the code, making them well-suited for various analysis tasks, such as type checking, optimization, and interpretation.
* Language-independent: ASTs can be designed to represent the essential elements of the code in a language-independent manner, allowing for easier analysis and transformation across different programming languages.

**Disadvantages of Abstract Syntax Trees:**

* Loss of syntactic details: ASTs abstract away certain syntactic elements, which may be required for certain analysis or transformation tasks that rely on detailed syntax information.
* Additional processing required: Generating an AST requires an additional step after parsing, adding some overhead to the compilation process.

## Further reading

For more information, you might want to see [this answer on Stack Overflow](https://stackoverflow.com/a/9864571/18746959).
> **Comments:**
> **username_2** (2023-05-17): Note that the [tag:pros-cons] tag was removed apparently while you were writing this.  
> **username_0** (2023-05-17): @Seggan It still doesn't hurt to include it.  
> **username_3** (2023-05-17): @Seggan oh, thanks for telling me. I'll keep the advantages/disadvantages in there though, since it's still sort-of relevant.  
> **username_1** (2023-05-17): I think compilers using ASTs do record information about the original code (the exact text as well as line numbers and column numbers), but this information may be stored outside the AST itself and still doesn't really turn it into a parse tree. Still, I feel like the lines can get a little blurred.  
> **username_1** (2023-05-17): Could you add an example of a parse tree and an AST for the same piece of code, by the way? Just to help out someone who doesn't know what they are at all?  
> **username_2** (2023-05-17): I suggest not keeping the pros-cons, as it may be slightly confusing; people may think you can use one without the other (you can, but it’s very hard)  
> **username_3** (2023-05-17): @user I linked in a SO answer with some images. Is that ok?  
> **username_2** (2023-05-17): @user the AST stores the original code information *within* the AST in my programming language, for error reporting purposes  
---
### Answer by username_2 on 2023-05-17. Score: 2
The difference is abstraction. Parse trees are typically much harder to work with and manipulate than abstract syntax trees (ASTs); for this reason, most programming languages first build a parse tree, then convert it to an AST. Parse trees are a direct tree representation of the source code, including all the keywords, structures, variables, literals, etc.

ASTs are a more abstract entity. They are typically formed after the desugaring step (where syntax sugar is converted into the full form), and often strip out the unnecessary parts of the syntax. ASTs can represent much more abstract operations than a parse tree, and can be a considered a type of intermediate representation, depending on how abstract it is.
---
