Language - (Syntax|Structural) Tree
Table of Contents
1 - About
There is actually two well knwon tree:
See also: Syntax Formatting
2 - Articles Related
3 - Example
4 - Parse Tree (CST) vs Abstract Syntax Tree (AST)
There are an infinite number of grammars for any single language and hence every gramar will result in a different tree form because of all the intermediate rules.
An abstract syntax tree is a far superior intermediate form precisely because of this insensitivity and because it highlights the structure of the language not the grammar.
It's best to look at an example. For input 3+4 you really want to use the following intermediate form:
+ | \ 3 4
That is, the operator at the root and 3 and 4 as operands (children). In child-sibling form, you'd have
+ | 3 -- 4
Ok, so now a parse tree. I'll pick an extremely simple one out of the infinite number:
expr | plus | \ \ 3 + 4
5 - Operations
Operation from the compiler
- “static semantic” analyses like checking that all variables are defined.
- code generation (type-checking, code optimization, flow analysis, checking for variables being assigned values before they’re used, and so on)
- program restructuring,
- code instrumentation,
- and computing various metrics of a program.
Most of these operations will need to treat nodes that represent assignment statements differently from nodes that represent variables or arithmetic expressions.
6 - Documentation / Reference
- Gamma, Erich; Helm, Richard; Johnson, Ralph; Vlissides, John (1994-10-31). Design Patterns: Elements of Reusable Object-Oriented Software (Kindle Locations 5190-5195). Pearson Education.