Parse Tree vs. Abstract Syntax Tree
You'll learn: How concrete parse trees differ from the simplified abstract syntax trees (ASTs) used by compilers.
The Difference Between Full and Simplified Trees
When a parser processes input, it can produce two types of trees. A parse tree (or concrete syntax tree) is a complete, literal representation of the derivation steps taken by the grammar. It includes every grammar rule applied, including nodes for non-terminals that exist only to enforce syntax rules (like operator precedence or parentheses).
An abstract syntax tree (AST), on the other hand, strips away the syntactic "scaffolding" and keeps only the semantically meaningful structure. It omits nodes for punctuation, precedence-enforcing rules, and other grammatical details that were necessary for parsing but aren't needed for understanding what the program means.
Why the Distinction Matters
Analogy: Think of a parse tree as a transcript of a conversation, complete with "um," "uh," and repeated phrases—everything that was said. An AST is like meeting minutes: it captures the decisions and key points while omitting the verbal filler.
For the expression 3 + 4 * 5, a parse tree might have separate nodes for <expr>, <term>, <factor>, and every grammar production used. An AST would simplify this to just:
+
/ \
3 *
/ \
4 5
The AST directly represents the operation hierarchy without the grammar's internal mechanics.
Key Takeaway:
Parse trees capture every derivation step from the grammar, while abstract syntax trees distill only the essential semantic structure—making ASTs the preferred representation for compiler optimization and code generation.