APT Generation

APT-Generation

The APT (Abstract Pattern Tree) is generated from the AST (Abstract Syntax Tree). To transform the AST into the APT a sequence of steps is necessary. These steps will be dicussed in the following page. Steps:

1. Generate a function/variable table
2. Generate the functions top down
3. Generate the bottom up structure (parent awareness)
4. Generate the data traces for expression
5. Generate the data traces for parent nodes

Step 1: Generate a function/variable table

The function and variable table are similar to the symbol table in the AST. The tables contain a reference to the APT implementation of the corresponding function/variable. This step breaks the circular dependency in between the function table and the APT, the call node needs a reference to the actual function node but the function node must be defined beforehand. By creating the function table with empty function nodes (generated in step 2) the call nodes can be generated, without the function node needing to be generated.

Both tables can easily be generated, by either traversing the AST or the symbol table. The current implementation traverses the AST for simplicity.

Step2: Generate the functions top down

In this step a forest (a graph consisting of multiple trees) is generated. Each individual tree represents a function. To get the APT we follow the references in the call nodes to function nodes. The references can be found in the function table generated in the previous step. This approach was chosen to reduce the amount of memory necessary for representing the APT.

In this step the general structure of the APT will be generated including expressions, control statements etc.

Step3: Generate the bottom up structure (parent awareness)

In this step the representation from step 2 is traversed to generate the parent attribute for each pattern node. Function nodes do NOT have a parent node, since pattern nodes are restricted to a single parent node. Moreover, as stated in step 2 function nodes represent the root for our partial APTs.

Step 4: Generate the Data Traces for Expressions

Due to the definition of the APT data structure, accesses to data elements can only directly happen in the context of an expression. To ensure that the order of the data accesses within the data trace corresponds to the order of a sequential execution we traverse the APT again. The structure of our expression, especially the operation expressions allows us to easily collect the the accesses and and data elements. Which then are stored in the expression nodes.

Step 5: Generate the data traces for parent nodes

To allow a more coarse grained view on certain pattern nodes, the data accesses are passed to their ancestors. To the accesses passed are limited to data elements within the scope of the parent.