Language - (Syntax|Structural) Tree

1 - About

The graphical representations of a grammar are called Syntax or Structural tree.

There is actually two well knwon tree:

See also: Syntax Formatting

3 - Example

4 - Parse Tree (CST) vs Abstract Syntax Tree (AST)

A parse tree is a record of the rules (and tokens) used to match some input text whereas a abstract syntax tree records the structure of the input and is insensitive to the grammar that produced it.

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)
  • pretty-printing,
  • 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

code/compiler/syntax_tree.txt · Last modified: 2017/09/17 17:42 by gerardnico