Language - (Syntax|Structural) Tree

> Code - (Programming|Computer) Language > Computer Language - (Compiler|Interpreter) - Language translator

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)

In short, a A CST has all information needed to restore the original document completely, AST does not.

For example for an HTML document, CSTs house info on style such as tabs or spaces, but ASTs do not. This makes ASTs often easier to work with.

ASTs can still recreate an exact syntactic representation.

A parse tree (CST) 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 grammar 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:

   | \ \ 
  3  +  4

5 - Operations

Operations that can be performed with a syntax tree (from a 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 - Specification

7 - Documentation / Reference