[ < ] | [ > ] |  | [ << ] | [ 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