[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

13.5 Tree Nodes

If you want really to understand how the GNU Pascal language front-end works internally and perhaps want to improve the compiler, it is important that you understand GPC's internal data structures.

The data structure used by the language front-end to hold all information about your Pascal program are the so-called "tree nodes". (Well, it needn't be Pascal source -- tree nodes are language independent.) The tree nodes are kind of objects, connected to each other via pointers. Since the GNU compiler is written in C and was created at a time where nobody really thought about object-orientated programming languages yet, a lot of effort has been taken to create these "objects" in C.

Here is an extract from the "object hierarchy". Omissions are marked with "..."; nodes in parentheses are "abstract": They are never instantiated and aren't really defined. They only appear here to clarify the structure of the tree node hierarchy. The complete list is in `../tree.def'; additional information can be found in `../tree.h'.

 
(tree_node)
|
|--- error_mark  { enables GPC to continue after an error }
|
|--- (identifier)
|    |
|    |--- identifier_node
|    |
|    \--- op_identifier
|
|--- tree_list  { a list of nodes, also used as a
|                  general-purpose "container object" }
|
|--- tree_vec
|
|--- block
|
|--- (type)  { information about types }
|    |
|    |--- void_type
|    |
|    |--- integer_type
|   ...
|    |
|    |--- record_type
|    |
|    |--- function_type
|    |
|    \--- lang_type  { for language-specific extensions }
|
|--- integer_cst  { an integer constant }
|
|--- real_cst
|
|--- string_cst
|
|--- complex_cst
|
|--- (declaration)
|    |
|    |--- function_decl
|   ...
|    |
|    |--- type_decl
|    |
|    \--- var_decl
|
|--- (reference)
|    |
|    |--- component_ref
|   ...
|    |
|    \--- array_ref
|
|--- constructor
|
\--- (expression)
     |
     |--- modify_expr  { assignment }
     |
     |--- plus_expr  { addition }
    ...
     |
     |--- call_expr  { procedure/function call }
     |
     |--- goto_expr
     |
     \--- loop_expr  { for all loops }

Most of these tree nodes -- struct variables in fact -- contain pointers to other tree nodes. A `tree_list' for instance has a `tree_value' and a `tree_purpose' slot which can contain arbitrary data; a third pointer `tree_chain' points to the next `tree_list' node and thus allows us to create linked lists of tree nodes.

One example: When GPC reads the list of identifiers in a variable declaration

 
var
  foo, bar, baz: Integer;

the parser creates a chain of `tree_list's whose `tree_value's hold `identifier_node's for the identifiers `foo', `bar', and `baz'. The function `declare_vars()' (declared in `util.c') gets this tree list as a parameter, does some magic, and finally passes a chain of `var_decl' nodes to the back-end.

The `var_decl' nodes in turn have a pointer `tree_type' which holds a `_type' node -- an `integer_type' node in the example above. Having this, GPC can do type-checking when a variable is referenced.

For another example, let's look at the following statement:

 
baz := foo + bar;

Here the parser creates a `modify_expr' tree node. This node has two pointers, `tree_operand[0]' which holds a representation of `baz', a `var_decl' node, and `tree_operand[1]' which holds a representation of the sum `foo + bar'. The sum in turn is represented as a `plus_expr' tree node whose `tree_operand[0]' is the `var_decl' node `foo', and whose `tree_operand[1]' is the `var_decl' node `bar'. Passing this (the `modify_expr' node) to the back-end results in assembler code for the assignment.

If you want to have a closer look at these tree nodes, write a line `{$debug-tree="Foobar"}' into your program with `FooBar' being some identifier in your program. (Note the capitalization of the first character in the internal representation.) This tells GPC to output the `identifier_local_value' tree node -- the meaning of this identifier -- to the standard error file handle in human-readable form.

While hacking and debugging GPC, you will also wish to have a look at these tree nodes in other cases. Use the `debug_tree()' function to do so. (In fact `{$debug-tree="Foobar"}' does nothing else than to `debug_tree()' the `identifier_local_value' of the `Foobar' identifier node.)


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

This document was generated by Frank Heckenbach on May, 10 2002 using texi2html