Node: Tree nodes, Next: Parameter passing, Previous: Language definition, Up: Internals

### 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-oriented 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_variables()` (declared in `declarations.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. This tells GPC to output the contents of the `IDENTIFIER_NODE` 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_NODE` of the `Foobar` identifier node – note the capitalization of the first character in the internal representation.)